Statistics

Problem Statement for "Choosers"

Problem Statement

This problem involves an elaborate marble maze game. The maze is composed of choosers that look like this:
        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.

Definition

Class:
Choosers
Method:
length
Parameters:
String[], int
Returns:
int
Method signature:
int length(String[] game, int start)
(be sure your method is public)

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

  1. {"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

  2. {"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.

  3. {"L 1 2","R 2 0","L X X"}

    2

    Returns: 1

    The marble leaves immediately.

  4. {"L 0 0"}

    0

    Returns: -1

    Clearly, the marble never leaves.

  5. {"L 0 1","R X 0"}

    1

    Returns: 4

  6. {"R 0 3","L 3 0","R 0 1","L 0 0"}

    1

    Returns: -1

  7. {"R 4 3","R 5 6","L 2 5","R 0 0","L 3 6","L 5 3","L 7 4","R 3 7","L 4 3"}

    3

    Returns: -1

  8. {"L 1 0","R 3 4","L 0 2","R 8 5","L 6 3","L 4 4","R 7 1","L 0 6","R 4 3"}

    1

    Returns: -1

  9. {"L 0 0"}

    0

    Returns: -1

  10. {"L 0 4","L 2 2","R 2 3","L 4 3","R 4 4"}

    3

    Returns: -1

  11. {"R 1 1","R 2 2","R 1 2","R 0 3"}

    3

    Returns: -1

  12. {"L 0 5","L 4 2","R 0 0","R 3 0","R 0 5","L 2 1"}

    4

    Returns: -1

  13. {"R 1 3","L 2 2","L 5 1","L 2 3","R 5 2","L 4 1"}

    5

    Returns: -1

  14. {"L 2 1","L 5 2","L 3 0","R 5 6","R 0 0","R 5 0","R 3 4"}

    5

    Returns: -1

  15. {"L 1 1","L 0 1"}

    1

    Returns: -1

  16. {"R 3 3","R 0 0","L 0 1","L 2 1"}

    3

    Returns: -1

  17. {"R 1 3","L 0 0","R 5 2","R 3 0","R 5 5","L 1 3"}

    0

    Returns: -1

  18. {"R 6 3","L 6 3","R 10 3","R 11 0","L 7 9","R 4 10","R 2 2","R 2 8","R 6 9","L 5 3","R 2 5","L 6 9"}

    10

    Returns: -1

  19. {"L 1 1","R 0 0"}

    0

    Returns: -1

  20. {"L 0 2","L 2 0","L 0 0"}

    1

    Returns: -1

  21. {"R 8 11","L 12 3","L 3 7","R 5 3","R 9 10","L 6 1","L 8 5","L 1 3","R 1 9","L 7 11","R 12 3","L 9 7","L 5 11"}

    0

    Returns: -1

  22. {"R 3 5","L 3 0","R 3 5","R 0 2","R 2 2","L 2 2"}

    5

    Returns: -1

  23. {"R 6 3","L 6 3","L 8 1","R 6 3","R 12 9","R 11 7","L 4 4","L 10 5","L 12 9","R 8 3","R 6 0","L 4 4","L 12 7"}

    6

    Returns: -1

  24. {"L 8 2","R 1 4","R 7 4","R 6 10","L 10 4","L 5 0","L 3 1","R 8 3","R 7 0","L 6 4","R 8 3"}

    9

    Returns: -1

  25. {"R 11 5","L 8 6","R 8 3","L 5 8","R 10 3","L 0 0","R 5 4","R 0 0","L 8 7","L 8 4","R 11 11","L 7 8"}

    8

    Returns: -1

  26. {"R 6 6","R 6 7","R 2 2","R 0 2","R 5 1","L 6 7","L 0 5","R 4 7"}

    7

    Returns: -1

  27. {"L 2 0","L 1 0","R 2 1"}

    0

    Returns: -1

  28. {"L 2 2","R 0 2","R 1 1","L 1 3"}

    3

    Returns: -1

  29. {"L 4 5","L 1 6","R 3 3","R 3 1","L 7 5","L 5 2","L 5 6","L 0 4"}

    5

    Returns: -1

  30. {"L 2 9","R 8 7","R 1 4","R 9 7","R 10 9","L 7 9","L 6 1","R 6 1","L 2 0","R 8 2","R 6 5"}

    1

    Returns: -1

  31. {"R 3 0","R 9 3","R 10 11","L 11 9","R 7 10","L 9 7","L 7 1","L 9 5","R 7 1","L 8 4","L 8 1","R 1 9"}

    8

    Returns: -1

  32. {"R 0 0"}

    0

    Returns: -1

  33. {"L 0 2","L 0 2","L 5 3","L 4 3","R 3 2","L 4 4"}

    4

    Returns: -1

  34. {"L 1 2","R 0 0","R 0 1"}

    2

    Returns: -1

  35. {"R 11 2","R 2 9","R 4 3","L 7 3","L 10 11","L 7 3","L 10 10","R 1 4","L 5 7","L 7 2","L 6 5","R 11 0"}

    11

    Returns: -1

  36. {"R 0 0","L 0 2","L 2 1"}

    0

    Returns: -1

  37. {"L 2 2","L 0 0","R 0 0"}

    1

    Returns: -1

  38. {"R 0 4","L 4 11","R 11 13","R 12 4","R 7 0","L 0 9","R 8 3","L 3 5","R 11 6","R 0 9","R 4 0","R 0 12","R 2 10","L 10 0"}

    9

    Returns: -1

  39. {"R 5 7","L 5 5","L 7 5","R 6 4","L 7 2","R 4 6","L 6 3","R 4 1"}

    5

    Returns: -1

  40. {"L 3 1","R 6 5","R 2 6","L 5 6","R 0 4","R 0 0","R 0 4"}

    3

    Returns: -1

  41. {"R 10 7","R 3 6","R 8 1","R 10 1","R 0 3","R 7 3","R 8 1","R 4 5","L 2 5","R 0 9","R 6 3"}

    1

    Returns: -1

  42. {"L 6 12","R 12 5","R 1 4","L 0 7","R 9 8","R 4 9","L 8 8","L 9 12","R 2 13","L 8 12","L 8 9","L 0 4","R 7 7","L 11 13","R 1 4"}

    12

    Returns: -1

  43. {"R 0 5","R 5 3","R 6 5","R 4 2","L 2 5","R 6 0","L 3 5"}

    6

    Returns: -1

  44. {"L 5 7","R 2 8","R 1 4","L 8 0","R 8 1","R 5 5","R 7 9","R 0 9","L 0 3","R 5 0","L 3 10"}

    5

    Returns: -1

  45. {"R 2 3","L 3 2","R 4 5","R 0 3","R 2 0","L 2 5","R 1 3"}

    6

    Returns: -1

  46. {"R 1 1","L 0 0"}

    1

    Returns: -1

  47. {"R 0 0"}

    0

    Returns: -1

  48. {"L 6 9","R 7 7","R 12 7","R 2 9","L 12 4","L 10 7","R 6 5","L 0 7","L 1 8","R 0 5","R 3 10","L 6 9","L 11 7"}

    4

    Returns: -1

  49. {"L 4 6","L 0 3","R 7 8","R 11 11","R 4 2","R 13 2","R 2 3","R 12 13","R 2 5","R 4 2","L 12 5","R 5 9","R 5 1","R 8 1"}

    7

    Returns: -1

  50. {"R 3 11","R 0 7","L 12 2","L 12 0","R 8 0","L 9 3","R 1 4","L 7 5","L 8 2","L 9 4","L 2 9","R 3 9","L 0 1"}

    5

    Returns: -1

  51. {"L 1 1","R 0 1"}

    0

    Returns: -1

  52. {"L 11 0","L 7 8","L 13 4","L 12 7","R 6 0","L 11 7","L 7 11","L 7 10","L 13 6","L 10 2","L 4 8","L 12 10","R 0 1","L 4 13"}

    13

    Returns: -1

  53. {"R 2 3","R 0 1","L 0 1","R 3 3"}

    3

    Returns: -1

  54. {"R 1 3","L 4 2","R 0 5","L 0 7","L 7 2","L 4 2","R 0 6","R 6 0","L 2 3"}

    7

    Returns: -1

  55. {"R 3 5","R 0 1","R 5 0","R 0 6","R 5 5","R 5 6","L 6 1"}

    3

    Returns: -1

  56. { "L 1 0", "L 2 3", "L 0 X", "L 0 0" }

    0

    Returns: 11

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: