This assignment is based on the Combinatorial Iterators lecture (notes
are here), and uses
Permutations, Combinations, Power Sets, and/or BaseNCounting from that
lecture.
For this problem, we will solve
Krypto problems.
There are variants on this game, so we will set out the rules here.
You are given a set of non-zero int values and an int target. Your goal is to form an
arithmetic expression using those numbers (in any order) and the operators
+, -, *, /, or %. You must use each value exactly once, though you can
use operators any number of times.
Important note: operators are evaluated left-to-right, without regard
for ordinary precedence or associativity. So, 2+3*4 equals 5*4 or 20,
and not 2+12 or 14.
Also: all numbers are non-zero integers and all operators are integer-based.
So this uses integer division (with truncation) and integer modulus, with no
worries about division by zero.
Do not worry about overflow.
For example: say you are given the values {1, 2, 3, 4} and the target
5. This problem has numerous solutions, including:
1 + 2 / 3 + 4 = 5
and
1 + 2 * 3 - 4 = 5
and
4 * 2 - 3 * 1 = 5
Not every problem has multiple solutions. For example: say you
are given the values { 2, 4, 7, 9 } and the target -32. This problem
has exactly one solution:
7 % 2 - 9 * 4 = -32
And, as you would expect, some problems have no solutions at all. For
example: the values { 2, 4, 7, 9} have solutions for positive targets
from 1 to 42, inclusive, but there is no solution for these values with the
target of 43.
Your task: write a method with this signature:
public static
boolean solveKrypto(int target, int[] values) {
}
This method takes a target and an array of non-zero values, and returns true if there
is a Krypto solution, as described above, for the given target and values,
and false otherwise (including if the array is null or empty). Also,
as a side effect, if a solution is found, the method will print out the
solution in the form given above. Consider the following:
boolean ok =
solveKrypto(-32, new int[]{2, 4, 7, 9});
The solveKrypto method will return true (which is then assigned to the
variable "ok"), but it will also print out this equation:
7 % 2 - 9 * 4 = -32
If there is more than one solution, your code should print out the first
solution it finds (whatever it is) and return true. On the other hand,
the same call with values { 2, 4, 7, 9} and a target of 43 would print
nothing out and simply return false.
Here is the start of a test method for solveKrypto: public static void testSolveKrypto() {
// 1 + 2 * 3 + 4 = 13, among others
verify(solveKrypto(13,new int[]{1,2,3,4}));
// 1 + 3 * 4 - 2 = 14, among others
verify(solveKrypto(14,new int[]{1,2,3,4}));
// No solution for 29:
verify(!solveKrypto(29,new int[]{1,2,3,4}));
// harder problems with solutions
verify(solveKrypto(80,new int[]{2, 6, 7, 8}));
verify(solveKrypto(-59, new int[]{4, 6, 8, 9, 10}));
verify(solveKrypto(-1240,new int[]{5, 6, 7, 15, 16, 19}));
verify(solveKrypto(145927, new int[]{5, 21, 22, 77, 81, 89, 94}));
// harder problems without solutions
// interesting aside: in each case, the given target is the first positive
// target which is not solvable for the given set of numbers!
verify(!solveKrypto(33,new int[]{2, 6, 7, 8}));
verify(!solveKrypto(131, new int[]{4, 6, 8, 9, 10}));
verify(!solveKrypto(949,new int[]{5, 6, 7, 15, 16, 19}));
verify(!solveKrypto(10486, new int[]{5, 21, 22, 77, 81, 89, 94}));
}
Aside: before writing your code, you might see if you can solve the Kryptos in the test method by hand:
| Kryptos in the test method |
| values |
target |
| 2, 6, 7, 8 |
80 |
| 4, 6, 8, 9, 10 |
-59 |
| 5, 6, 7, 15, 16, 19 |
-1240 |
| 5, 21, 22, 77, 81, 89, 94 |
145927 |
If you find this to be rather difficult (and I do!), of course your own
code will find and print out the answers for you!
HINTS
- Because the values can occur in any order in the solution, you
should use a Permutation
object, where "n" is the size of your values array.
- Each call to the Permutation's "next" method will return a new
permutation, or ordering, of the values from 0 to (n-1). You
should think of these as indexes into your values array.
So, if your values array is {2, 6, 9} and your permutation array is {2,
0, 1}, then you are considering the values ordered as such: 9, 2, 6.
- Ok, so now we can consider every possible ordering of the values
thanks to that Permutation object. But what about the operators?
- If we have 3 values, we'll need 2 operators. Each operator can
be +, -, *, /, or %. Let's numbers these 0 (+), 1 (-), 2 (*), 3
(/), and 4 (%). So we can think of an operator assignment as a
2-digit base-5 number (as numbers in base-5 contain just the digits 0,
1, 2, 3, and 4). For example, the 2-digit base-5 number 32
corresponds to a "/" followed by a "*". Inserting these operators into
the values with the permutation from above -- that is, 9, 2, 6 -- gives
us the expression 9 / 2 * 6.
- More generally, if we have n values, we need (n-1) operators.
So we will use a BaseNCounter
object, supplying 5 as the base and (n-1) as the number of digits.
Again, each base-5 digit is an operator (+,-,*,/,%) and we insert these
operators between the digits of the given permutation of our values to
obtain an arithmetic expression.
- Finally, we evaluate this expression, left-to-right without
precedence or associativity, and if we get the target value, we are
done! (Well, we print out the equation and return true, then we're
done.)
- If we try every possible choice of operators for every possible
permutation of values, and none of these expressions equals the target,
then we return false.
- Use well-chosen helper methods of your own choosing. Do not
place all your code in one method!
- Don't get discouraged by this long description and the fact that the
problem itself is hard for humans to solve. As far as a Java
solution goes, the "heavy lifting" is already done for you in the
Permutation and BaseNCounter classes. The solution we wrote
required only 30 lines of straightforward code. You can do this!