PROBLEM STATEMENT
You are programming a cheat code detector for an old, poorly-designed video
game system. The system polls the controller port every second and receives an
8-bit status reading describing any player input that occurred since the last
polling. Below is a mapping between user buttons and the status bits, where 0
is the low-order bit (rightmost).
UP 0
DOWN 1
LEFT 2
RIGHT 3
B 4
A 5
SELECT 6
START 7
For example, if the status reading is "00110001", then you know the player
pushed both the "A" and "B" buttons as well as "UP" within the last second.
Your game has a set of cheat codes that trigger whenever a sequence of the
player's button presses match the code. As soon as any matching code triggers,
then you begin looking for the beginning of a new cheat code (in other words,
you can never have two cheat codes which overlap in time). If multiple cheat
codes complete during the same second, cheat codes with lower indices in the
input, names, take precedence. See examples 3, 4 and 5.
Possible cheat movements are: "UP", "RIGHT", "DOWN", "LEFT", "UP-RIGHT",
"DOWN-RIGHT", "DOWN-LEFT", "UP-LEFT", "A", "B", "SELECT", "START", where
"UP-RIGHT" occurs when both the "UP" and the "RIGHT" status bit are 1 and,
similarly, the other combinations occur when both of the appropriate status
bits are 1.
Cheat codes consist of a sequence of moves separated by single spaces (no
leading or trailing):
<Move> <Move> <Move> <Move> ...
for example,
"UP UP DOWN DOWN LEFT RIGHT LEFT RIGHT B A B A"
The only correct matching sequence of presses would be:
00000001 // UP
00000001 // UP
00000010 // DOWN
00000010 // DOWN
00000100 // LEFT
00001000 // RIGHT
00000100 // LEFT
00001000 // RIGHT
00010000 // B
00100000 // A
00010000 // B
00100000 // A
In order for a sequence to match a cheat code, button pushes in the cheat code
must appear in the sequence without any intervening pollings or extra button
presses (extra 1's in the status code). Thus, the above sequence is the only
possible sequence which matches the above cheat code. Adding extra button
pushes within the sequence would cause it not to match.
You are given a String[] of button presses, a String[] of secret code names,
and a String[] of secret code sequences (names[i] matches sequences[i]). Write
a method that returns a String[], in chronological order, of all cheat codes
triggered. If no codes were triggered, then return an empty array.
DEFINITION
Class: CheatCodes
Method: detect
Parameters: String[], String[], String[]
Returns: String[]
The method signature is (make sure it is declared public): String[] detect
(String[] presses, String[] names, String[] sequences);
NOTES
-The cheat codes may not overlap. No cheat code may use a button press used in
a previous sequence.
-As soon as a valid cheat code is found, that cheat code is triggered, and the
button pushes that it used may not be used by subsequent cheat codes.
-If multiple cheat codes complete simultaneously, the one with the lowest index
in names takes precedence.
-Two cheat codes may have the same name.
TopCoder will ensure:
-Each element of presses will have a length of 8 consisting only of 1's and 0's.
-Each element of sequences will be a valid move sequence as described above.
-Each element of sequences and names will be between 1 and 50 characters,
inclusive.
-The length of names is equal to the length of sequences.
-Each element of names will consist of the characters 'a' to 'z', 'A' to 'Z',
spaces, and '-'.
-presses, names, and sequences will contain between 0 and 50 elements inclusive.
-All cheat sequences will contain at least 1 button push.
-There will be no extra, leading, or trailing spaces in elements of sequences.
EXAMPLES
Example 1:
presses = {"00000001", "00000001", "00000010", "00000010", "00000100",
"00001000", "00000100", "00001000", "00010000", "00100000", "00010000",
"00100000"}
names = {"THIRTY-LIVES-TRICK"}
sequences = {"UP UP DOWN DOWN LEFT RIGHT LEFT RIGHT B A B A"}
returns {"THIRTY-LIVES-TRICK"}
Example 2:
presses = {}
names = {}
sequences = {}
returns {}
Example 3:
presses = {"11111111", "00001111", "00001111", "00000001", "00000001"}
names = {"FOO-BAR", "FOO"}
sequences = {"UP UP", "UP"}
Although the sequence "UP UP" can be found, the secret FOO-BAR will never
trigger. Instead, the first "UP" will trigger FOO, and since cheat codes can
not overlap, "FOO-BAR" will never trigger.
returns {"FOO", "FOO"}
Example 4:
presses = {"00000001", "00000010", "00010000", "00000010"}
names = {"Kirby Smash", "Samus Bomb"}
sequences = {"UP DOWN B", "DOWN B"}
The "UP DOWN B" sequence found will match both secret moves, but only the
earlier indexed move will trigger.
returns {"Kirby Smash"}
Example 5:
presses = {"00000001", "00000010", "00010000", "00000010"}
names = {"Samus Bomb", "Kirby Smash"}
sequences = {"DOWN B", "UP DOWN B"}
This time "Samus Bomb" triggers because it appears earlier in the array than
"Kirby Smash"
returns {"Samus Bomb"}
Example 6:
presses = {"00000001", "00000010", "00010000", "00000010", "00010000"}
names = {"Kirby Smash", "Samus Bomb"}
sequences = {"UP DOWN B", "DOWN B"}
returns {"Kirby Smash", "Samus Bomb"}
Example 7:
presses = {"00000110","00000110","00000110","10000000"}
names = {"A"}
sequences = {"DOWN-LEFT DOWN-LEFT START"}
returns {"A"}