Last active
September 7, 2018 14:04
-
-
Save dkovacevic/dc6fd254822c40503181ce37c4230ae1 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| @Test | |
| public void number113() { | |
| int[] a = {2, 4, 1, 3, 10, 75}; | |
| int x = 113; // ((75 / 3) * 4) + 2 + 1 + 10 | |
| System.out.printf("%d, %d, %d, %d, %d, %d... X is: %d\n\n", a[0], a[1], a[2], a[3], a[4], a[5], x); | |
| forceItIn(a, x); | |
| } | |
| @Test | |
| public void number425() { | |
| int[] a = {2, 4, 1, 3, 10, 75}; | |
| int x = 425; // (75 / 3) * (4 + 2 + 1 + 10) | |
| System.out.printf("%d, %d, %d, %d, %d, %d... X is: %d\n\n", a[0], a[1], a[2], a[3], a[4], a[5], x); | |
| forceItIn(a, x); | |
| } | |
| @Test | |
| public void number4124() { | |
| int[] a = {9, 8, 7, 6, 96, 75}; | |
| int x = 4124; // 9 + 8 + (7 * 6 * 96) + 75 | |
| System.out.printf("%d, %d, %d, %d, %d, %d... X is: %d\n\n", a[0], a[1], a[2], a[3], a[4], a[5], x); | |
| forceItIn(a, x); | |
| } | |
| @Test | |
| public void number81() { | |
| int[] a = {9, 8, 7, 6, 96, 75}; | |
| int x = 81; // 6 + 75 | |
| System.out.printf("%d, %d, %d, %d, %d, %d... X is: %d\n\n", a[0], a[1], a[2], a[3], a[4], a[5], x); | |
| forceItIn(a, x); | |
| } | |
| private void forceItIn(int[] a, int x) { | |
| char[] ops = {'+', '-', '*', ':'}; | |
| for (char s1 : ops) { | |
| for (char s2 : ops) { | |
| for (char s3 : ops) { | |
| for (char s4 : ops) { | |
| for (char s5 : ops) { | |
| char[] op = {s1, s2, s3, s4, s5}; | |
| if (permute(a, op, x, 0)) | |
| return; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| System.out.println("No solution"); | |
| } | |
| // Checks if equation (a,ops) is equal `x`. If not, recursively check for n-1 element of `a` | |
| // Returns `true` if any of subsets of `a` results in `x` | |
| private boolean check(int[] a, char[] ops, int x) { | |
| if (a.length < 2) | |
| return false; | |
| try { | |
| if (evaluate(a, ops) == x) { | |
| String eq = print(a, ops); | |
| System.out.printf("%s = %d\n", eq, x); | |
| return true; | |
| } | |
| } catch (IllegalArgumentException ignore) { | |
| } | |
| // Copy n-1 elements of `a` and check() | |
| int[] a1 = Arrays.copyOfRange(a, 0, a.length - 1); | |
| char[] ops1 = Arrays.copyOfRange(ops, 0, ops.length - 1); | |
| return check(a1, ops1, x); | |
| } | |
| // Evaluate the array `a` of operations `ops` and return the result | |
| // result = a[0] ops[0] a[1] ops[1] a[2] ... | |
| // array `a` must have more than 1 element, `ops` array must have one element less than `a` | |
| private int evaluate(int[] a, char[] ops) throws IllegalArgumentException { | |
| assert (a.length > 1); | |
| assert (ops.length == a.length - 1); | |
| int r = a[0]; | |
| for (int i = 1; i < a.length; i++) { | |
| r = f(r, a[i], ops[i - 1]); | |
| } | |
| return r; | |
| } | |
| // Print the equation (`a`,`ops`) | |
| private String print(int[] a, char[] ops) { | |
| assert (a.length > 1); | |
| assert (ops.length == a.length - 1); | |
| StringBuilder sb = new StringBuilder(); | |
| sb.append(a[0]); | |
| for (int i = 1; i < a.length; i++) { | |
| if (i != a.length - 1) | |
| sb.insert(0, "("); | |
| sb.append(" ").append(ops[i - 1]).append(" ").append(a[i]); | |
| if (i != a.length - 1) | |
| sb.append(")"); | |
| } | |
| return sb.toString(); | |
| } | |
| // Evaluate the operation (sign) against two numbers (`a` and `b`) | |
| private int f(int a, int b, char sign) throws IllegalArgumentException { | |
| if (sign == '+') return a + b; | |
| if (sign == '-') return a - b; | |
| if (sign == '*') return a * b; | |
| if (a % b != 0) | |
| throw new IllegalArgumentException("illegal operation: " + a + " : " + b); | |
| return a / b; | |
| } | |
| private boolean permute(int[] a, char[] ops, int x, int index) { | |
| if (index >= a.length - 1) { | |
| return check(a, ops, x); | |
| } | |
| for (int i = index; i < a.length; i++) { | |
| swap(a, index, i); | |
| if (permute(a, ops, x, index + 1)) | |
| return true; | |
| swap(a, index, i); | |
| } | |
| return false; | |
| } | |
| private void swap(int[] a, int j, int i) { | |
| int t = a[j]; | |
| a[j] = a[i]; | |
| a[i] = t; | |
| } | |
| private boolean evaluate(int[] a, char[] ops, int x) { | |
| try { | |
| StringBuilder sb = new StringBuilder(); | |
| sb.append(a[0]); | |
| int r = a[0]; | |
| for (int i = 1; i < a.length; i++) { | |
| sb.insert(0, "(").append(" ").append(ops[i - 1]).append(" ").append(a[i]).append(")"); | |
| r = f(r, a[i], ops[i - 1]); | |
| if (r == x) { | |
| sb.append(" = ").append(r); | |
| System.out.println(sb.toString()); | |
| return true; | |
| } | |
| } | |
| return false; | |
| } catch (IllegalArgumentException ex) { | |
| return false; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment