I peeked at the Day 10 puzzle before I went to bed last night. Part 1, at least, had a lot of the keywords I love to look for:
Defined starting point… need to find the fewest steps toward a defined goal… that sounds like Dijkstra, or his less specific cousin Breadth-First Search (BFS) to me.
The sample data was a little bit cryptic. For part 1, the problem asks us to ignore that last brace-surrounded term. (Play the ominous Part 2 music). Basically, the first term with the spots and meshes represents a binary number, so “[.##.]” would equal 0110 in binary, or the number 6 in decimal. The bits are number from 0..4 starting from the left. The lists of numbers in parentheses represent buttons, and the numbers inside are the bits that are flipped from 0 to 1 and 1 to 0 each time that button is pushed.
The Part 1 value for each line is the least number of button presses necessary to match the bits template, the the sum of those is the answer to Part 1.
There’s some things we know up front. The operation these buttons do is the exclusive-or operation, and this has the property that pressing it twice undoes pressing it once. Upshot is, we will never press any button more than once.
The standard algorithm for finding the shortest path between two fixed points is called Dijkstra’s algorithm, after inventor Edsger Dijkstra. It is a special case of the Breadth-First algorithm that uses a priority queue to quickly present next step candidates in their best order. Picotron’s Lua doesn’t have a priority queue. I wrote one, but it was super slow so I nuked it and just used BFS and it worked fine and fast. And that was part 1.
Part 2 asks you to forget about bit flipping. The final, brace-delimited term are values we want to reach by pressing buttons. Instead of flipping bits, we’re incrementing term values. For instance, in the log above, we’re trying to match the sequence 10, 11, 11, 5, 10, 5. These numbers are indexed from 0 .. 5, so element 0 is 10, elements 1 and 2 are both 11, etc. The buttons increment the values, so the first button would add 1 to the value of each element except the last. We want to sum up the minimum number of button presses for each line for the part 2 value.
While it’s possible to make a linear equation solver for Lua, probably, that wasn’t going to be something I had any interest in doing, so I turned to Python and the standard Microsoft Z3 library, which easily solves these. Eric even hinted that we might want to use external libraries:
Those, of course, become constraints to a linear equation solver package.
It’s easy enough to build a Python solution that does this; there’s plenty of packages that just do it. Many people used SciPy; I used Z3; and there are others. They all work more or less the same way. Define the variables, define the values, define the equations and constraints, solve for the variables and minimize the result.
Yesterday I just plain solved Part 2 with a Python solution. I wanted to route the answer through Picotron, so I dove into the docs and found out about “sockets”.
Sockets are buckets a process can dump data into. Another process can be watching the bucket and take out what is put in, do some work on it, and dump the answer back in the bucket. It’s just a place to transfer data without necessarily assigning any sort of structure to that data.
It was perfect for my needs.
I built and ran the Python program that would listen for work. The Lua program would dump a line into the socket and then go on its merry way until it saw an answer, which it would then sum to the Part 2 value.
I couldn’t do it in Lua, but I did learn about Z3 and sockets, so this, for me, is an unqualified… partial success.
Leave a Reply