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.
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
{"X X", "X _"}{"X X", "X 0"}Returns: 0
0 works quite easily.{"X X", "X _"}{"X X", "X 2"}Returns: -1
The lower right node in finish can send its tokens, so we immediately return -1.{"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{"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
{"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.
Back to all problems