PROBLEM STATEMENT
This problem is based on an early-days computer game of Snake. A snake of
length N initially stretches from (0,0) to (N-1, 0) on the coordinate plane,
with its tail at (0,0), and its head at (N-1, 0). A stream of commands directs
the snake around the coordinate plane. Write a method that determines the
coordinates of the location where the snake's head crosses over its body for
the first time.
DEFINITION
Class name: Snakes
Method name: crawl
Parameters: int, String
Return type: String
Method signature (be sure your method is public): String crawl(int N, String
commands);
N is the length of the snake. Initially, the snake stretches horizontally,
facing east (increasing horizontal coordinates). Snake's head is located at
(N-1,0).
String commands consists of numbers and characters 'R' and 'L'. Numbers direct
the snake to move forward. Characters 'R' and 'L' make the snake turn right and
left 90 degrees, and then move forward one position. Once a snake turns, it
continues facing that direction until the next turn. For example if the
commands="50LL20R10R", the snake moves forward 50 positions, turns left and
moves forward one position, turns left and moves forward one position again,
moves forward 20 positions, turns right and moves forward one position, moves
forward another 10 positions, and then turns right and moves forward one
position again.
Your method should return a String formatted as "X,Y" (quotation marks are for
clarity only), where X and Y are integers representing the horizontal and the
vertical coordinates of the snake's head when it crosses over its body for the
first time. If after processing the entire command string your method
determines that the snake never crosses itself over, your method should return
the special string "***" (quotation marks are for clarity only).
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- N is between 1 and 50, inclusive.
- commands contains 0 to 50 characters, inclusive.
- commands consists of digits and upper-case characters 'R' and 'L'.
- Numbers imbedded in the command string are in the range from 1 to 100,
inclusive.
NOTES
Commands 'L' and 'R' instruct the snake to change its direction and move
forward one position at the same time. In the illustrations below, 'X' shows
snake's head, and 'O's show snake's body; snake's head is included in snake's
length.
2 .......... ..........
1 .......... ..........
0 OOOOOX.... ..OOOO....
-1 .......... .....OX...
-2 .......... ..........
0123456789 0123456789
Initial "RL"
Illustration above shows a snake of length 6 in its initial position (left),
and the snake after the "RL" command (right).
2 .......... ..........
1 .......... ..........
0 OOOOOX.... .....O....
-1 .......... .....O.X..
-2 .......... .....OOO..
0123456789 0123456789
Initial "R1L1L"
Illustration above shows a snake of length 6 in its initial position (left),
and the snake after the "R1L1L" command (right).
EXAMPLES
- if N=5 and commands="LLLLL", your method should return "3,0"
- if N=1 and commands="LLLLL", your method should return "***"
- if N=9 and commands="L3LLRLL3", your method should return "8,2"
- if N=8 and commands="L3LLRLL3", your method should return "***"
- if N=50 and commands="74L45LLL", your method should return "123,45"
- if N=1 and commands="", your method should return "***"