Choosers
TCI '02 Finals · 2002-11-23 · by lbackstrom
TCI '02 Finals · 2002-11-23 · by lbackstrom · Simulation
Problem Statement
Problem Statement
This problem involves an elaborate marble maze game. The maze is composed of choosers that look like this:
game = {"L 1 2","R 2 0","L X X"}
This means that chooser 0 begins oriented to the left. Its left path leads to chooser 1, and its right path leads to chooser 2. Chooser 1 begins oriented to the right. Its left path leads to chooser 2, and its right path leads to chooser 0. Chooser 2 begins oriented to the left. Its left and right path both leave the game. If I place a marble in chooser 0 it will pass through 4 choosers before leaving the game (namely 0 then 1 then 0 then 2). Given a network of choosers, and a chooser that we drop the marble into, determine how many choosers the marble will pass through before leaving the game. If it will never leave return -1.
Create a class Choosers that contains the method length, which takes a String[] game, and an int chooser, and returns an int representing how many choosers the marble will pass through before leaving the game. Return -1 if it will never leave.
Right Oriented Left Oriented
| | | |
| | | |
| | | |
/ \ \ / / \
/ \ \ / / \
/ \ \ / / \
/ O \ / O \
/ / \ \ / / \ \
/ / \ \ / / \ \
A marble is put in the top of the chooser. The bar in the middle of the chooser determines whether the marble will leave to the left or the right. After a marble passes through the chooser the bar moves. For example, if a marble enters the right oriented chooser pictured above, it would leave toward the right but, the next marble to pass through would leave toward the left. The exact opposite would hold true for the left oriented chooser pictured above. We can make a game by networking a bunch of choosers together using tubes. For example:game = {"L 1 2","R 2 0","L X X"}
This means that chooser 0 begins oriented to the left. Its left path leads to chooser 1, and its right path leads to chooser 2. Chooser 1 begins oriented to the right. Its left path leads to chooser 2, and its right path leads to chooser 0. Chooser 2 begins oriented to the left. Its left and right path both leave the game. If I place a marble in chooser 0 it will pass through 4 choosers before leaving the game (namely 0 then 1 then 0 then 2). Given a network of choosers, and a chooser that we drop the marble into, determine how many choosers the marble will pass through before leaving the game. If it will never leave return -1.
Create a class Choosers that contains the method length, which takes a String[] game, and an int chooser, and returns an int representing how many choosers the marble will pass through before leaving the game. Return -1 if it will never leave.
Constraints
- game will contain between 1 and 15 elements, inclusive.
- Each element of game will be formatted as "
" with no extra, leading or trailing spaces, or extra leading 0's. is either 'L' or 'R' and are each either the character 'X' or integers between 0 and the length of game - 1, inclusive.
Examples
0)
{"R 1 0",
"R 2 0",
"R 3 0",
"R 4 0",
"R 5 0",
"R 6 0",
"R 7 0",
"R 8 0",
"R 9 0",
"R 10 0",
"R 11 0",
"R 12 0",
"R 13 0",
"R 14 0",
"R X 0"}
0
Returns: 65534
1)
{"L 1 2","R 2 0","L X X"}
0
Returns: 4
The marble goes from 0 to 1 to 0 to 2 and then leaves.
2)
{"L 1 2","R 2 0","L X X"}
2
Returns: 1
The marble leaves immediately.
3)
{"L 0 0"}
0
Returns: -1
Clearly, the marble never leaves.
4)
{"L 0 1","R X 0"}
1
Returns: 4
Submissions are judged against all 56 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Choosers with a public method int length(vector<string> game, int start) · 56 test cases · 2 s / 256 MB per case