eternal latch
Code Structure
Using numbers: 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 25, 50, 75, 100
Using operators: +, -, *, /
Note: I encode the numbers/operators to work for char arrays (1 = a, 10 = j, * = q)
All examples of data are a reduced form of what I actually will be working with.
This is the usual form of the data: [[100, 4, -, 3, 4, 1, /, *, *, 9, /], [100, 4, -, 3, 4, 1, /, *, /, 9, +]...]
- I generate all 24c6 combinations (removing duplicates). This generates 13,243 combinations.
- I then generate all permutations for each combination (also removing duplicates): This generates 5,281,560 permutations
- I store the results in a Map (key = combination i.e. [1, 2, 3], value = permutations i.e. [[1, 2, 3], [3, 2, 1], [2, 1, 3]...])
3.1 Map<List<String>, List<List<String>>>
Up until here the code runs in milliseconds
- For each permutation I generate all possible equations (in postfix form). Store the results in a map, similar to the combination-permutation map. (key = [3, 1, 2] value = [[3, 1, 2, +, +], [3, 1, +, 2, +]...]): Each permutation has around 40,000 equations
4.1 Map<List<String>, char[][]>
Without evaluating, generating all possible equations takes around 6-7 hours
- After each permutation has postfix generated I evaluate the equations, then clear the permutation-postfix map to save on memory
5.1 There will be ~200 billion equations total (I have never gotten here as it would takes days currently)
Evaluating will take an estimated 6-7 days
My questions are as follows
Question
I have code that evaluates postfix equations, however I am finding it is running slower than I would like. It does use nested for loops which I know are slow, but I am unsure of any other way to approach it atm. Is there a faster method?
example postfix array = [[3, 1, 2, +, +], [3, 1, +, 2, +]...]
public void evaluate(String[][] postfixArray) {
int[] resultList = new int[200000];
int index = 0;
for (String[] postfix : postfixArray) {
if (postfix[0] == null) break;
boolean valid = true;
int[] stack = new int[11];
int stackIndex = 0;
for (String token : postfix) {
// Checks if the equation remains valid
if (!valid) break;
// Evaluates the token
if (token.matches("[0-9]+")) {
stack[stackIndex++] = Integer.parseInt(token);
} else {
int b = stack[--stackIndex], a = stack[--stackIndex];
switch (token) {
case "+" -> stack[stackIndex++] = a + b;
case "*" -> stack[stackIndex++] = a * b;
case "-" -> {
// If result is negative, equation is not valid
if (a > b) stack[stackIndex++] = a - b;
else valid = false;
}
case "/" -> {
// If result is not an integer, equation is not valid
if (a % b == 0) stack[stackIndex++] = a / b;
else valid = false;
}
default -> throw new IllegalStateException("Unexpected value: " + token);
}
}
if (stackIndex == 1 && valid) {
int result = stack[0];
if (result >= 101 && result <= 999) {
resultList[index++] = result;
validSolutions++;
} else {
invalidSolutions++;
}
}
}
/*
If equation is valid, add result to list
Valid equations are the following
*/
if (valid) validEquations++;
else invalidEquations++;
}
for (int result : resultList) {
if (result != 0) {
Runner.solutions.put(result, Runner.solutions.getOrDefault(result, 0) + 1);
}
}
real dragon
slate island
