Statistics

Problem Statement for "TokenGrid"

Problem Statement

There is an n by n grid of network nodes. Each node is either standard, or a token consumer. Element i of setup, which corresponds to row i of the grid, will contain a single space delimited list of n values. A consumer will be denoted by an 'X' character. A standard node is denoted by a nonnegative integer with no extra leading zeros, which represents how many tokens it possesses. An unknown will be denoted by a '_' character (there will be exactly 1 unknown).

Suppose a particular standard node is adjacent to d nodes (upward, downward, leftward, or rightward with no wrap-around), and has at least d tokens. Then that node can send 1 token to each adjacent node leaving it with d fewer tokens. For example, a node in the corner with at least 2 tokens could send. Token consumers accept tokens but never send them. finish, which is formatted like setup but with the '_' character replaced by a number, should describe the state of the network after all possible tokens have been sent, and no more can be sent. Return the smallest possible nonnegative value of the unknown, or -1 if no value will work. If finish does not describe a network where tokens cannot be sent (a standard node has too many tokens), also return -1.

Definition

Class:
TokenGrid
Method:
getUnknown
Parameters:
String[], String[]
Returns:
int
Method signature:
int getUnknown(String[] setup, String[] finish)
(be sure your method is public)

Notes

  • The order in which nodes send their tokens is irrelevant.

Constraints

  • setup and finish will be formatted as described in the problem statement.
  • setup will contain between 2 and 4 elements inclusive.
  • setup and finish will agree on the placement of consumer nodes.
  • setup and finish will contain the same number of elements.
  • Each integer in setup and finish will be between 0 and 50 inclusive.
  • setup will contain at least 1 consumer node.

Examples

  1. {"X X", "X _"}

    {"X X", "X 0"}

    Returns: 0

    0 works quite easily.

  2. {"X X", "X _"}

    {"X X", "X 1"}

    Returns: 1

  3. {"X X", "X _"}

    {"X X", "X 2"}

    Returns: -1

    The lower right node in finish can send its tokens, so we immediately return -1.

  4. {"X 1", "X _"}

    {"X 1", "X 1"}

    Returns: 1

  5. {"X 2", "X _"}

    {"X 1", "X 0"}

    Returns: 1

    If the unknown node begins with 1 token, the following sequence of scenarios occurs: X 2 ---> X 0 ---> X 1 X 1 X 2 X 0

  6. {"9 9 9 9", "9 9 9 9", "9 9 9 9", "_ 9 9 X"}

    {"1 1 1 1", "1 1 1 1", "1 2 2 1", "1 1 1 X"}

    Returns: -1

  7. {"0 0 0 0", "0 0 0 0", "0 0 0 0", "_ 0 0 X"}

    {"1 1 1 1", "1 1 1 1", "1 2 2 1", "1 1 1 X"}

    Returns: -1

  8. {"0 0 0 0", "0 0 0 0", "0 0 0 0", "_ 0 0 X"}

    {"1 1 0 1", "2 2 2 1", "2 3 3 2", "0 1 1 X"}

    Returns: 26

  9. {"X 0 0 0", "0 0 0 0", "0 0 0 0", "_ 0 0 X"}

    {"X 1 0 1", "2 2 2 1", "2 3 3 2", "0 1 1 X"}

    Returns: -1

  10. { "X 0 0 0", "X _ X 0", "0 X X 0", "0 0 0 0" }

    { "X 1 1 1", "X 1 X 1", "0 X X 1", "1 1 1 1" }

    Returns: 4929

  11. { "X 0 0 0", "X _ X 0", "1 X X 0", "0 0 0 0" }

    { "X 1 1 1", "X 1 X 1", "0 X X 1", "1 1 1 1" }

    Returns: 11294

  12. { "0 0 0 0", "0 0 0 0", "1 0 X 0", "0 0 _ X" }

    { "0 2 1 1", "2 3 3 1", "2 1 X 2", "1 2 0 X" }

    Returns: 21873

  13. {"X 0 1 X","1 0 0 1","1 0 1 X","0 _ 0 0"}

    {"X 1 2 X","1 3 2 0","2 2 3 X","1 2 1 0"}

    Returns: 152338

  14. {"_ X", "20 17"}

    {"0 X", "0 1"}

    Returns: -1

  15. {"_ 32 X X", "X 44 9 39", "11 16 12 40", "X X 42 X"}

    {"0 1 X X", "X 3 3 0", "2 3 3 1", "X X 0 X"}

    Returns: 36401

  16. {"X _ 40 13", "X 29 2 47", "X 4 17 27", "X 8 21 X"}

    {"X 2 1 0", "X 1 2 2", "X 3 3 2", "X 1 0 X"}

    Returns: 24230

  17. {"X 14 48 2", "_ 35 21 X", "X X 29 26", "10 31 4 X" }

    {"X 1 1 0", "1 3 3 X", "X X 1 0", "0 2 2 X"}

    Returns: 36466

  18. {"X _ 7 X", "6 X 3 5", "6 0 7 X", "X X 10 X"}

    {"X 0 2 X", "0 X 0 1", "2 0 3 X", "X X 0 X"}

    Returns: 14292

  19. {"_ X X 10", "6 X 7 9", "7 4 1 1", "X 7 8 X"}

    {"0 X X 1", "1 X 3 2", "2 0 2 0", "X 1 2 X"}

    Returns: 33780

  20. {"X 6 1 X", "_ 3 10 5", "X 5 8 7", "X 3 X X"}

    {"X 2 1 X", "1 0 2 1", "X 3 0 2", "X 1 X X"}

    Returns: 48533

  21. {"X _ 8 X", "4 X 1 2", "8 X X 5", "6 6 0 7"}

    {"X 1 1 X", "1 X 3 1", "0 X X 2", "1 1 2 0"}

    Returns: 16040

  22. {"_ 6 10", "8 4 X", "X 9 2"}

    {"0 2 0", "2 3 X", "X 1 1"}

    Returns: 226

  23. {"0 _ X", "X 8 3", "6 3 X"}

    {"1 2 X", "X 0 1", "0 2 X"}

    Returns: 199

  24. {"_ 9 3 1", "X 4 5 X", "2 X 9 3", "8 7 7 X"}

    {"0 1 2 0", "X 2 3 X", "1 X 3 2", "1 2 0 X"}

    Returns: 48784

  25. {"5 _ 8 X", "5 X 9 7", "5 6 4 3", "0 8 0 X"}

    {"2 0 1 X", "1 X 2 3", "2 1 1 2", "2 2 1 X"}

    Returns: -1

  26. {"8 2 1 4", "_ 10 2 X", "9 1 4 2", "X 5 4 X"}

    {"1 0 3 0", "1 2 1 X", "3 4 3 2", "X 0 0 X"}

    Returns: -1

  27. {"_ 10 10 X", "X 7 6 5", "8 X 5 5", "5 1 9 7"}

    {"1 3 3 X", "X 2 3 2", "2 X 2 1", "0 2 1 2"}

    Returns: -1

  28. {"X 0 10 1", "8 _ 2 X", "4 5 9 5", "X 8 X 10"}

    {"X 0 3 2", "2 2 1 X", "3 2 1 3", "X 2 X 2"}

    Returns: -1

  29. {"0 1 5 8", "X _ 5 3", "10 4 5 6", "X 9 5 X"}

    {"1 2 0 2", "X 3 1 2", "2 1 4 2", "X 1 0 X"}

    Returns: -1

  30. {"X _ X 9", "0 0 0 3", "8 6 7 10", "X 6 10 8"}

    {"X 0 X 2", "0 1 1 3", "0 2 0 1", "X 0 2 2"}

    Returns: -1

  31. {"X _ 5 X", "9 0 10 X", "0 X 6 1", "X 8 0 X"}

    {"X 1 2 X", "2 1 0 X", "2 X 3 1", "X 2 1 X"}

    Returns: 29567

  32. {"_ X 4 5", "1 10 6 5", "8 X 0 2", "X 10 10 X"}

    {"0 X 3 0", "3 1 4 3", "1 X 4 2", "X 3 2 X"}

    Returns: -1

  33. {"7 _ 9 X", "4 1 8 4", "X 1 4 X", "1 10 10 X"}

    {"1 1 1 X", "2 2 0 0", "X 3 0 X", "1 1 2 X"}

    Returns: -1

  34. {"X 2 X 9", "0 _ 8 5", "5 9 5 6", "X 8 1 3"}

    {"X 1 X 1", "1 1 0 0", "0 2 1 0", "X 2 1 1"}

    Returns: -1

  35. {"_ 4 X X", "X 9 0 10", "7 9 2 X", "8 X 1 1"}

    {"1 2 X X", "X 3 2 1", "1 0 3 X", "1 X 1 0"}

    Returns: 41291

  36. {"8 3 0 X", "6 _ X 1", "6 3 6 9", "10 X 3 6"}

    {"0 2 0 X", "2 2 X 1", "0 2 3 2", "1 X 2 0"}

    Returns: 79255

  37. {"X _ 1 X", "7 5 X 10", "9 10 10 1", "X 7 9 X"}

    {"X 2 0 X", "0 1 X 1", "1 3 3 0", "X 2 0 X"}

    Returns: 101042

  38. {"X 0 X 0", "_ 3 2 2", "2 1 0 X", "X 2 2 0"}

    {"X 2 X 1", "1 2 1 0", "2 2 1 X", "X 2 2 1"}

    Returns: 121849

  39. {"X _ 2 X", "2 2 2 1", "2 0 X 2", "0 1 1 1"}

    {"X 1 2 X", "2 3 1 2", "2 1 X 1", "1 0 1 1"}

    Returns: 117148

  40. {"_ X 0 0", "X 0 0 0", "0 0 0 0", "0 0 0 0"}

    {"0 X 0 0", "X 1 0 0", "0 0 0 0", "0 0 0 0"}

    Returns: -1

  41. {"_ 0 0", "0 X 2", "1 X 1"}

    {"1 2 1", "0 X 1", "1 X 1"}

    Returns: 114

  42. {"_ 0 0", "0 X 2", "1 X 1"}

    {"2 2 1", "0 X 1", "1 X 1"}

    Returns: -1

  43. {"_ 0 0", "X X 2", "1 X 1"}

    {"1 2 1", "X X 1", "1 X 1"}

    Returns: 32

  44. {"_ X 0 0", "0 2 1 X", "0 X X 0", "0 0 0 1"}

    {"0 X 1 0", "2 3 2 X", "2 X X 2", "1 2 2 1"}

    Returns: 28961

  45. {"0 _", "0 X"}

    {"1 1", "1 X"}

    Returns: 6

  46. {"X _ 0", "1 X 0", "0 0 0"}

    {"X 0 1", "0 X 2", "1 2 1"}

    Returns: 205

  47. {"_ X 1", "2 X 0", "0 0 1"}

    {"1 X 0", "0 X 2", "1 2 1"}

    Returns: 119

  48. {"50 50 50 X", "X 50 50 50", "50 50 50 50", "X 50 50 _" }

    {"1 1 2 X", "X 1 3 2", "2 2 2 2", "X 2 2 1" }

    Returns: 563

    Big inputs.

  49. {"50 50 50 X", "X 50 50 50", "50 50 50 50", "X 50 50 _" }

    {"1 50 2 X", "X 1 3 2", "32 2 2 2", "X 2 42 1" }

    Returns: -1

  50. {"X 0 0 0", "0 _ 2 X", "X X 2 2", "0 0 2 X"}

    {"X 1 1 1", "1 3 3 X", "X X 3 0", "1 2 2 X"}

    Returns: 46378

  51. {"0 1 0 1", "1 _ 3 X", "1 2 2 2", "X 1 2 X"}

    {"1 2 2 0", "0 3 2 X", "1 2 2 2", "X 1 2 X"}

    Returns: 152328

  52. {"X 2 1 1", "_ 1 2 1", "1 2 X 2", "X 1 0 0"}

    {"X 2 1 0", "2 3 1 2", "0 3 X 2", "X 2 2 1"}

    Returns: 131581

  53. {"0 0 0 0", "0 X X 0", "X _ X 0", "X 0 0 0" }

    {"1 2 2 1", "2 X X 2", "X 3 X 2", "X 2 2 1" }

    Returns: 15906

  54. {"0 0 0 0", "0 X X 0", "X X X 0", "_ 0 0 0" }

    {"1 2 2 1", "2 X X 2", "X X X 2", "1 2 2 1" }

    Returns: 7100

  55. {"50 50 50 X", "X 50 50 50", "50 50 X 50", "X 50 50 _" }

    {"1 1 2 X", "X 1 3 2", "2 2 X 2", "X 2 2 1" }

    Returns: 5063

  56. {"2 X", "X _" }

    {"1 X", "X 0" }

    Returns: -1

  57. {"50 50 50 X", "X 50 50 50", "50 50 50 48", "X 50 50 _" }

    {"1 1 2 X", "X 1 3 2", "2 2 2 2", "X 2 2 1" }

    Returns: 26259

  58. {"2 X 0", "X X 0", "X X _" }

    {"1 X 0", "X X 0", "X X 0" }

    Returns: -1

  59. {"50 50 50 X", "X X 50 49", "50 50 50 50", "X 50 50 _" }

    {"1 2 2 X", "X X 3 1", "0 1 3 2", "X 1 2 0" }

    Returns: 5000

  60. {"X X X X", "X X X X", "X X X X", "_ 9 0 0" }

    {"X X X X", "X X X X", "X X X X", "0 2 0 1" }

    Returns: 20

  61. {"X 50 50 50", "50 50 50 50", "50 50 50 50", "50 50 50 _" }

    {"X 0 0 0", "0 0 0 0", "0 0 0 0", "0 0 0 0" }

    Returns: -1

  62. {"X _ X", "6 6 X", "X X X" }

    {"X 0 X", "2 2 X", "X X X" }

    Returns: 4

  63. {"50 50 50 X", "X 50 50 50", "50 50 50 50", "X 50 50 _" }

    {"1 1 2 X", "X 1 1 2", "2 2 2 2", "X 2 2 1" }

    Returns: 22461

  64. {"50 50 X X", "X 50 50 50", "50 50 X 50", "X 50 50 _" }

    {"1 1 X X", "X 1 3 2", "2 2 X 2", "X 2 2 1" }

    Returns: 9382

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: