If you've ever played 24, this is kind of like that. I'm working on creating a program that given an array of numbers, it attempts to use arithmetic to evaluate it to a specific other number. It is quite complex and recursive as well...and it works, although subtraction is unstable and division is untested. If you disable subtraction and division, it has solved any multiplication and addition problem I have given it (some take longer than others, I had one take almost 10 minutes). What's cool is that it doesn't use brute force, and the array that you give it can be any size. Here's my current code:
Code:
This version is actually slightly outdated since I switch between using different computers which means that it's missing a couple lines of code but nothing that makes it not work.
Code:
import java.util.ArrayList;
import java.util.Scanner;
public class NumberSolver {
static Scanner input = new Scanner(System.in);
static int recursionDepth = 0;
static boolean overrideDepth = false;
static int[] array = {7,8,4,3};
static boolean[] used;
static int maxNum;
static int number;
static boolean solve2r = false;
public static int maxForArray() {
int number1 = 1;
for(int i = 0; i < array.length; i++)
if(array[i] > number1 && !used[i])
number1 = array[i];
use(number1);
int number2 = 1;
for(int i = 0; i < array.length; i++)
if(array[i] > number2 && !used[i])
number2 = array[i];
resetUsed();
return number1 * number2;
}
public static int[] factor(int num){
ArrayList<Integer> ini = new ArrayList<Integer>();
ini.add(1);
for(int i = 2; i <= Math.sqrt(num); i++)
if(num % i == 0)
ini.add(i);
int[] arr = new int[ini.size()*2];
for(int i = 0; i < ini.size(); i++)
arr[i] = ini.get(i);
for(int i = 0; i < ini.size(); i++)
arr[arr.length - i -1] = num/arr[i];
return arr;
}
public static String solve(int complexity, int num){
recursionDepth++;
int a = indexOf(unused(),num);
if(a != -1) {
if(!use(num))
return null;
return " " + Integer.toString(num) + " ";
}
String factored = findFromMultiplication(complexity,num);
if(factored != null)
return factored;
if(num == number) {
resetUsed();
}
String added = findFromAddition(complexity,num);
if(added != null || solve2r)
return added;
if(num == number) {
resetUsed();
}
String divided = findFromDivision(complexity,num);
if(divided != null)
return divided;
if(num == number) {
resetUsed();
}
return findFromSubtraction(complexity,num);
}
public static String solve2(int complexity, int num){
recursionDepth++;
int a = indexOf(unused(),num);
if(a != -1) {
if(!use(num))
return null;
return " " + Integer.toString(num) + " ";
}
String factored = findFromMultiplication(complexity,num);
if(factored != null)
return factored;
if(num == number) {
resetUsed();
}
return findFromAddition(complexity,num);
}
public static String findFromMultiplication(int complexity, int num) {
if(num == 1 || unused().length == 0)
return null;
int[] factors = factor(num);
if(factors.length == 2) {
int factor2i = indexOf(unused(),num);
if(factor2i != -1) {
if(!use(num))
return null;
return " " + Integer.toString(num) + " ";
}
return null;
}
int[] globalUnused = unused();
String solved1;
String solved2;
for(int i = 1; i <= (factors.length -2)/2; i++) {
if(num == 592 && factors[i] == 4)
ifDebug();
solved1 = solve(complexity,factors[i]);
if(solved1 != null) {
solved2 = solve(complexity,factors[factors.length - 1 - i]);
if(solved2 != null)
return "(" + solved1 + ") * (" + solved2 + ")";
}
setUnused(globalUnused);
}
return null;
}
public static void ifDebug() {}
public static String findFromAddition(int complexity, int num) {
if(num == 1 || unused().length == 0)
return null;
String solved1;
String solved2;
int[] globalUnused = unused();
for(int i = 1; i <= num/2; i++) {
if(i == 12)
ifDebug();
setUnused(globalUnused);
solved1 = solve(complexity, i);
if(solved1 != null) {
solved2 = solve(complexity,num-i);
if(solved2 != null) {
return "(" + solved1 + ") + (" + solved2 + ")";}
}
}
return null;
}
public static String findFromSubtraction(int complexity,int num) {
solve2r = true;
// if(true) return null;
String solved1;
String solved2;
int[] globalUnused = unused();
if(num == 52)
ifDebug();
for(int i = 1; i + num <=maxNum; i++) {
if(i == 4)
ifDebug();
solved1 = solve(complexity,i+num);
if(solved1 != null) {
solved2 = solve(complexity,i);
if(solved2 != null) {
solve2r = false;
return "(" + solved1 + ") - (" + solved2 + ")";
}
}
setUnused(globalUnused);
}
solve2r = false;
return null;
}
public static String findFromDivision(int complexity,int num) {
if(true) return null;
String solved1;
String solved2;
int[] globalUnused = unused();
for(int i = 1; i * num <=maxNum; i++) {
solved1 = solve(complexity,i);
if(solved1 != null) {
solved2 = solve(complexity, num * i);
if(solved2 != null)
return "(" + solved2 + ") / (" + solved1 + ")";
}
setUnused(globalUnused);
}
return null;
}
public static void dumpUnused() {
for(int element : unused())
System.out.print(element + ",");
System.out.println();
}
public static void dumpArray(int [] arr) {
for(int element : arr)
System.out.print(element + ",");
System.out.println();
}
public static String findNextNum(String str, int index) {
String fin = "";
boolean hasBeenFound = false;
for(int i = index; i < str.length(); i++) {
if("1234567890".indexOf(str.substring(i,i+1)) == -1 && hasBeenFound)
return fin;
if("1234567890".indexOf(str.substring(i,i+1)) != -1) {
fin += str.substring(i,i+1);
hasBeenFound = true;
}
}
return fin;
}
public static void setUsedFromString(String str) {
if(str == null)
return;
String next;
for(int i = 0; i < str.length(); i++) {
next = findNextNum(str,i);
i += next.length();
if(next.length() != 0) {
use(Integer.parseInt(next));
}
}
}
public static void setUnused(int[] arr) {
for(int i = 0; i < array.length; i++)
used[i] = true;
for(int element : arr)
for(int i = 0; i < array.length; i++)
if(array[i] == element && used[i]) {
used[i] = false;
break;
}
}
public static void resetUsed() {
for(int i = 0; i < used.length; i++)
used[i] = false;
}
public static boolean use(int num) {
if(num == 2) {
ifDebug();
}
for(int i = 0; i < array.length; i++) {
if(array[i] == num && !used[i]) {
used[i] = true;
return true;
}
}
return false;
}
public static int nextEmptyIndex(int[] arr) {
for(int i = 0; i < arr.length; i++)
if(arr[i] == 0)
return i;
return -1;
}
public static int indexOf(int[] arr,int a) {
for(int i = 0; i < arr.length; i++)
if(arr[i] == a)
return i;
return -1;
}
public static int indexOf(int[] arr,int a,int b) {
for(int i = b; i < arr.length; i++)
if(arr[i] == a)
return i;
return -1;
}
public static int[] unused() {
int[] arr = new int[trues(used)];
for(int i = 0; i < array.length; i++)
if(!used[i])
arr[nextEmptyIndex(arr)] = array[i];
return arr;
}
public static int trues(boolean [] arr) {
int counter = 0;
for(boolean element : arr)
counter += parseBool(!element);
return counter;
}
public static int parseBool(boolean a) {
return a ? 1 : 0;
}
public static void main(String[] args) {
System.out.println("Setting up...");
// System.out.println("Enter number of numbers: ");
// array = new int[input.nextInt()];
used = new boolean[array.length];
// for(int i = 0; i < array.length; i++){
// System.out.println("Enter number " + i + ": ");
// array[i] = input.nextInt();
// }
// System.out.println("Enter number to solve for: ");
// int num = input.nextInt();
// System.out.println("Minimum complexity? ");
// int min = input.nextInt();
// int[] factors = factor(num);
int min = 1;
number = 156;
maxNum = maxForArray();
String solved = solve(min, number);
if(solved != null){
System.out.println("Solved!");
System.out.println(solved);
System.out.println("Reached recursion depth of: " + recursionDepth);
return;
}
System.out.println("Failed.");
}
}This version is actually slightly outdated since I switch between using different computers which means that it's missing a couple lines of code but nothing that makes it not work.