Operator Search for Puzzle

Question

I was wondering if I could solve the problem here (mostly unrelated) using only simple binary operators since it is just mapping 100 different inputs to a boolean. For this I wrote this, but I have no real way to test, and I was also hoping it could be faster.

#include <iostream>
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MAX_VAL 100

bool CODES[] = {1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1};

int op(int a, int b, int index) {
    switch (index) {
        case 0: return a + b; break;
        case 1: return a - b; break;
        case 2: return a * b; break;
        case 3: return a / b; break;
        case 4: return a & b; break;
        case 5: return a | b; break;
        case 6: return a ^ b; break;
        case 7: return a % b; break;
    }
}

int main(int argc, char const *argv[]) {
    for (int A=1; A < 2; A++) {
        std::cout << A << std::endl;
        for (int B=1; B < 2; B++) {
            std::cout << A << " " << B << std::endl;
            for (int C=1; C < 2; C++) {
                for (int D=1; D < MAX_VAL; D++) {
                    std::cout << A << " " << B << " " << C << " " << D << std::endl;
                    for (int E=1; E < MAX_VAL; E++) {
                        for (int opA = 0; opA < 8; opA++) {
                            for (int opB = 0; opB < 8; opB++) {
                                for (int opC = 0; opC < 8; opC++) {
                                    for (int opD = 0; opD < 8; opD++) {
                                        for (int opE = 0; opE < 8; opE++) {
                                            bool good = true;
                                            int index = 1;
                                            for (bool item : CODES) {
                                                int val = op(index, A, opA);
                                                val = op(val, B, opB);
                                                val = op(val, C, opC);
                                                val = op(val, D, opD);
                                                val = op(val, E, opE);
                                                val &= 1;
                                                if (val != item) {
                                                    good = false;
                                                    break;
                                                }
                                                index++;
                                            }
                                            if (good) {
                                                std::cout<<"GOOD "<<A<<" "<<opA<<" "<<B<<" "<<opB<<" "<<C<<" "<<opC<<" "<<D<<" "<<opD<<" "<<E<<" "<<opE<<std::endl;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return 0;
}

I am specifically looking for help for optimization, but of course style, correctness, or anything else is much appreciated.

Answer 1

Before we even get started into optimizations, I would like to point out a couple of things. First- many permutations of operands + operators are going to behave identically. There isn't a whole lot we can do to skip these, but in practice it seems that "similar" permutations are composed of "similar" components. That is, a handful of permutations of operands + operators that differ by 1 operand or operator will often have very similar input->output mappings. Some times you can take advantage of this to speedup your search. Sometimes the best solution is to do a completely random search of permutations to avoid the problem completely (at the cost of trying duplicate permutations). I won't explore either option below, but I wanted to mention them for completeness.

Secondly, you are trying to create a (int->bool) input->output mapping for 100 unique values. Even if we never tried two permutations of operands + operators that produce the same mapping, there's still 2^100 unique mappings to explore. That is not something that we can reasonably brute force. For 5 operands chosen (with replacement) from your 8 and 5 constants each in the range [0-99] inclusive, we have 8^5 * 100^5 == 3.27*10^14 == 2^48 permutations. Unless we are astronomically lucky, you're going to need to at least double your operand + argument count anyways. We need something smarter.

We need to try to prune the search space, but in order to do that we need to be able to determine early on whether a permutations is worth pursing. In the process of restructuring your code to support such a heuristic, we're also going to gain a small performance boost. The following line of code is executed over and over for all 100 indices, and isn't going to change when you change opB, opC, and so on.

int val = op(index, A, opA);

This logic also applies to val = op(val, B, opB);, and the others. This isn't too bad- you're only losing a factor of 5 in performance, but it needs to be changed anyways to give our algorithm some foresight. We can reorder your loops to put the argument and operand together, and then compute the intermediate values immediately-

for (int A=1; A < 2; A++) {
    std::cout << A << std::endl;
    for (int opA = 0; opA < 8; opA++) {
        int valA[100];
        // compute val for all indices
        // Loop over B, C, D

This will allow us to compute the intermediate value of val exactly once- every time it is changed, rather than every time we change any operand / operator.

Now how does this help us prune the search space? Notice that for any mapping our operand constant is... constant. Together with the operator, they make a new (unary) operator. We can take this further as well- since all our new operators are "chained" together, they can be seen as one big (unary) operator.

input <operator> <operand_constant>  => output
input <new_operator> output
...
input <new_operator_A> <new_operator_B> => output
input <combined_operator> => output

The index itself is the only input and each index is unique, but each intermediate value/output might not be unique. Regardless of the index value, if two intermediate operations produce the same intermediate value, then both will produce the same output value. We can use this to prune the search space.

If two values in the array are identical, then their corresponding bits in the original array must both be the same. If they are not, immediately attempt the next operator / operand value. If you reduce your computations to unsigned chars spanning [0, 255] inclusive, the probability of having two equal intermediate values is roughly 0.999999999827. There will likely be many intermediate values with the same value, allowing you to quickly prune bad branches in the search tree.

To quickly determine if two values in the array cause a conflict, use an external array of size 256. When you compute an intermediate value v, check that array[v] is either uninitialized, or matches the desired output (map 0->1 and 1->2 maybe, and leave 0 to indicate uninitialized) and set the array element accordingly. If it doesn't match, then there's a conflict.

You could probably optimize this further by using a linked list to store the unique values of the array (every time array[v] is uninitialized), and then only check that those values are correct- avoiding redundant computations.

Even with this pruning, I suspect this will probably still be intractable. 2^100 is a huge number. You'll likely need to find a second way to check for "dead-end" branches, and/or an algorithmic breakthrough.