:date: 2023-12-12 12:00
I started on part one with a very tidy brute force enumeration of all possibilities using easy peasy Python. It finished in 10 seconds so that was not a problem.
But then part two was very different. The general premise here is that you had to find binary numbers that satisfied complex criteria. Just running through all of them was fine in part one when there were only 20 binary digits — basically a "mega", 1048576 values. However when this was multiplied by 5 plus 4 more, that could be 84 bits or 2e25 states — all the grains of sand on 1000 earth-like planets (says Wolfram). So clearly this would have to be rewritten.
And I rewrote it. I used a recursive function to branch into a state tree and along the way I tried to cut off obvious intransigent candidates. Of course this is subtle and it's hard to really predict what will be impossible without pretty much checking it. But I got pretty ok results. Part A (no expansion) produced the same result in about the same time. However running on the expanded data made it clear I was not going to finish.
I realized that there were only 1000 inputs and they were completely
independent. This meant that I could use the split command to break
them up into 20 files and have my computer's 20 cores work on the
problem 20x faster. Unfortunately, that's not the 1e20x faster I was
probably needing.
So in summary, I did create a working program. Twice. Just not one that would finish in time. I tried some things like functools argument caching but really my approach should never really have had much duplication in the function (the whole idea of my second attempt).