PROBLEM STATEMENT
A common type of puzzle gives the puzzle solver a set of constraints relating
to the digits of the number and asks for the number that satisfies the
constraints. Your task is, given a set of constraints relating to the digits
of an N digit number, determine the smallest number such that all of the
constraints are satisfied. The constraints will restrict the range of various
digits by giving equations that either specify absolutely what the digit must
be, or else that it is related to some other digit in some way. For example,
one contraint might specify that the tens digit were 3 times the ones digit,
this would be represented as "D1 = 3 * D0"
Constraints will be either of the form "D<i> = <num> <op> D<j>" or "D<i> =
<num>". Where <num> is an integer, and <op> is either '+' or '*'.
Each constraint indicates that the ith digit is related to the jth digit by the
given equation, where the 0th digit is the ones digit.
Thus, "D1 = 2 * D0" would indicate that the tens digit is twice the ones digit.
Your method should return the smallest number of length N digits that satisfies
all of the constraints and does not have leading 0's.
If no number is possible with the given constraints, then return "IMPOSSIBLE".
DEFINITION
Class: Puzzle
Method: satisfy
Parameters: String[], int
Returns: String
Method signature (be sure your method is public): String satisfy(String[]
constraints, int N);
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- constraints will contain between 0 and 50 elements, inclusive
- each element will be formatted exactly as "D<i> = <num> <op> D<j>" or "D<i> =
<num>", with no extra spaces(angle brackets and quotes are only for clarity)
- N will be between 1 and 50, inclusive
- All referenced digits (<i> and <j>) will be within the range 0 to N-1,
inclusive.
- <num> will be in the range -700,000,000 to 700,000,000, inclusive
- There will be no extra leading 0's, leading or trailing spaces, or extra
spaces in the constraints
NOTES
- The single digit 0 is considered a leading 0. (see example 8)
EXAMPLES
1. constraints = {"D0 = 1 * D0"}, N = 2
all numbers with two digits will satisfy this. Thus we return the smallest one
without leading 0's, which is 10
returns 10
2. constraints = {"D1 = 2 * D0","D2 = 2 * D1"}, N = 3
The tens digit (D1) must be twice the ones digit (D0), and the hundreds digit
(D2) must be twice the tens digit (D1). Only 421 and 842 satisfy these
constraints, and since 421 is smaller the method returns "421"
3. constraints = {"D1 = 2 * D0","D2 = 2 * D1"}, N = 4
Since there are no constraints on D3, any value is valid (except 0, due to the
implicit contraint that there be no leading 0's). For the other three digits,
000, 421, and 842 satisfy the constraints (note that 000 was not valid above
because it resulted in leading 0's, but it is here because there are 4 digits).
Thus the smallest possible number without leading 0's is 1000.
returns "1000"
4. constraints = {"D2 = 3 * D0","D2 = 2 * D1","D3 = 3 + D2","D4 = -1 + D2"}
N = 5: returns "59632"
N = 6: returns "159632"
N = 7: returns "1059632"
5. contraints = {}, N = 3
returns "100"
6. contraints = {"D0 = 1 + D0"} N = 10
returns "IMPOSSIBLE"
7. contraints = {"D0 = 10"} N = 10
returns "IMPOSSIBLE"
8. contraints = {} N = 1
returns "1"
9. contraints = {"D0 = 10"} N = 1
returns "IMPOSSIBLE"
10. contraints = {"D2 = 6"} N = 4
returns "1600"