AoC 2024 in ECLiPSe-CLP
This year a friend challenged me to do the Advent of Code challenge (AoC) in Prolog. This is a sort of test of software engineering skills: the organizers of the project post a series of puzzles, two per day from December 1 to December 25. It's not the kind of thing I usually do and not the kind of thing I usually post here; but I thought it would be fun to try once, and having put in the work, I'd like to get as much value from it as possible - so I'm posting my solutions and some notes about them here. If you're coming to this page from a software engineering source, I hope you'll stick around and take a look at my products before leaving the site.
There is a little bit of connection to synthesizers in that the same tool I used for this project, the ECLiPSe-CLP logic programming system, is also one I frequently use in electronic design. If you read the "circuit explanation" chapters in the manuals of products like the MSK 008 Dual VC Octave Switch, you'll find comments on how I use constraint logic programming to solve problems like finding the best resistor values in a module design.
The AoC site posts a new pair of puzzles every day. The puzzles are intended for computer-aided solution. There's a generic description of each puzzle which is available to everybody, posted at midnight Eastern Time on each of the days of the challenge. Users can sign up with their login information from other sites, and then the site gives each user their own specific input data - their own instance of the shared problem, in computer science terms. If you solve the first problem (called "Part I") for the day, you can enter your answer on the site and then it will unlock access to the description of Part II, which is usually a more advanced version of the same puzzle on the same input data. Then you can similarly enter your answer for the Part II problem. Participants get one "star" for each puzzle part solved, so in principle there are 50 stars available, but really, the 50th star is awarded automatically if you get all of the first 49, so there are 49 puzzles requiring actual solutions.
There's a basic principle that people should use the challenge in whatever way is useful for them. Some people try to beat each other for speed, to complete the entire puzzle within a minute or two of its midnight posting; many people try to do it in unfamiliar (to them) languages that they hope to learn; some try to make their solutions run as fast as possible on the computer. In principle it would seem that some people might treat it as a computer science challenge rather than a software engineering challenge, and pursue goals like asymptotic complexity rather than fast implementation, but in fact I've seen very little evidence of anyone doing serious computer science on AoC. My plan was to attempt it as follows:
- In Prolog (read broadly, to include ECLiPSe-CLP)
- All by myself (that is, without hints from how other people solve the puzzles)
- On the day of (that is, solving Parts I and II before the next Part I is available)
- Prioritizing correctness over elegance (so, not necessarily in the algorithmically optimal way, but in a way that works)
- On the given data (not necessarily attempting to solve harder instances than they gave me)
I think I basically succeeded. Day 21 was an exception - I didn't finish Day 21, Part II (and therefore score the last two stars) until New Years' Eve, and by that point I had some though not a lot of insight gleaned by reading about others' solutions. I also went a bit beyond the stated problems on some of the easier days, looking into puzzle instances harder than the ones they gave me, and the computer science implications of the puzzles.
Doing it in Prolog was an interesting wrinkle. I think many people (including the fellow who suggested that to me) would think Prolog makes the challenge more difficult. In fact, on many problems I think Prolog actually made the challenge easier. Some of these puzzles would be difficult to do with more conventional, imperative languages. So it may have been a wash overall: an advantage on some puzzles and a disadvantage on others.
My comments here will contain spoilers, but are not intended to be tutorial on how to solve the puzzles. I'm mostly commenting for the benefit of others who have attempted the 2024 puzzles, and I'll assume readers are familiar with the puzzle statements themselves. This also isn't a tutorial on Prolog, though I'll probably make some comments comparing and contrasting the Prolog way of doing things with the way such things are done in other programming languages, for readers more accustomed to other programming languages. It's the Prolog angle that I figure justifies posting a commentary at all: lots of people are making similar postings about their experiences in languages like Python and Ruby, but those are too mainstream to be really interesting. Section headings link to the puzzle statements on the AoC site, and my ECLiPSe code for each one is linked below the headings.
Day 1 ("Historian Hysteria")
Part I is a simple warm-up; just sort the lists and do the calculation. The time bound is that of sorting. I implemented Part II in more or less the stupidest way possible, by comparing every number on the first list with every number on the second; that is O(n2) time, but in asymptotic terms you could actually do it in linear time, faster than Part I, by counting the numbers in a hash table.
Input parsing will be a recurring theme through all of these; in this first puzzle, I just used Prolog's input tokenizer and put alternating tokens into the two lists.
Day 2 ("Red-Nosed Reports")
Good opportunity here to show what Prolog is good at, namely the evaluation of logical constraints: I just needed to give a description that answers the question "What is a safe report?" (Answer: it is a report that is (all increasing OR all decreasing) AND obeys the rate constraint.) And then the code just reads the reports and counts how many are safe reports.
For Part II, the question is "How many reports either are safe reports, or would be safe reports if we deleted one temperature reading?" and so the code just says, okay, delete one temperature reading, and check whether that makes the report safe. That's where it may look like flim-flam because I didn't ever say anything about how to find which temperature reading to delete. It just sort of happens by magic: Prolog just implements nondeterministic choice, "succeed if there is any value of the variables that would make this work," as a feature of the language.
I ended up inventing and solving a bonus puzzle for Day 2, namely the Super Perturbulator, which inserts a single reading instead of deleting one, but can only insert prime numbers.
Day 3 ("Mull It Over")
I wasn't thrilled with this puzzle because the example data they give does not cover a lot of cases that I think ought to be covered - so you can end up writing code that will solve the data they give you, but still really isn't correct according to the description. It's like software engineering with Aardvark and Bandicoot - sadly realistic, but the kind of thing I did a science degree to avoid. In particular, they don't seem to ever hand out any data containing integers with leading zeros, nor anything else that closely resembles valid mul/do/don't instructions without actually being valid instructions. So your parser can appear to succeed while actually not handling those cases.
I implemented the parser using a Definite Clause Grammar because that was easy to do in Prolog. I think most people using other languages would've used regular expressions. That's fine as far as it goes, but the do/don't state in Part II really seems to force an iterative approach: find the first relevant instruction, then look for the next relevant instruction after that, and so on, one at a time, keeping some state from each match to the next. Carrying state between matches is easy to do with the DCG I built. It is theoretically possible with regexes because it's just a finite state machine and those are equivalent to regexes; and it would be easy to do with something like Perl's //g repeated-match regex flag. But I watched some friends try to do it using "split" type regex operations, attempting to process the entire string at once instead of iterating through matches one at a time, and they found that quite difficult.
Day 4 ("Ceres Search")
Another of these "follows naturally from the description" solutions: the declarative Prolog code just consists of defining what an XMAS or an X-MAS looks like and then asking the question, what are all the coordinates where that pattern occurs? First use of the "Prolog asserted database" data structure, which is not very efficient, but so convenient that it's usually worth it.
Day 5 ("Print Queue")
This basic operation of "find an ordering that meets these limitations" is called a topological sort in computer science. In principle there may be many different valid topological sort results for a given input; we just have to take the puzzle-generators' word for it that they will create instances where the "middle element" is uniquely defined, so that the puzzle will have a single correct answer.
Doing the topological sort takes advantage of Prolog backtracking magic: the logical statements amount to "This list is a topological sort of that list" and then it's up to the interepreter to choose one and return it. In Part II, the potential for multiple returns becomes relevant (along with what other languages might call "multiple dispatch") because the call to topological_sort/2 actually passes in what would otherwise be a return value; instead of asking "What is the topological sort of this input?" it's asking "Is this a topological sort of this input?" with what looks like nearly identical syntax.
Day 6 ("Guard Gallivant")
First puzzle to take significant processing time for me, largely because I was depending on some data structures that my Prolog interepreter doesn't implement efficiently, so at several points it was doing linear-time searches where constant-time hash lookups would've been reasonably possible.
It's an interesting question how fast this can really be done, in comp-sci asymptotic terms. Part I is pretty clearly a linear time upper and lower bound: you have to spend that much time just to read the input, and then having done so, you can easily solve it just by following the guard's path. I saw a lot of people on Reddit talking about how they thought it would be possible, or even more or less mandatory, to speed it up by "skipping" from one corner to another without examining every cell in between. But in asymptotic terms you don't really gain anything from that. If the density of obstacles is a constant fraction, then the guard only traverses a constant number of cells from one corner to the next, and "skipping" can at best improve the constants, not the asmyptotic time complexity.
For Part II, although I fear my own solution may have been as bad as O(n4), I think with a careful implementation it can be done as fast as O(n) times the complexity of persistent set operations. The idea is that you make one pass of Part I, annotating the cells the guard passes through, and then you make another pass over all the cells in something like Dijkstra's Algorithm to answer the question, for each cell and orientation, "If the guard ever passes through this cell in this orientation, then will she escape and which cells of the original path will she pass through?" That makes it possible, for each place you might add an extra obstacle, to figure out quickly whether the guard who steps off the path at that point will or won't end up escaping. But you need to do a "persistent set" operation for each (cell,orientation) pair, to maintain the "which cells will she pass through" information which is needed to evaluate whether the new obstacle creates a loop. And I don't have a completely solid proof of this entire approach. Just doing a good implementation of the slow way is plenty good enough for the problem size actually in play here.
Persistent set seems to be no worse than O(log log n) by way of van Emde Boas trees, so O(n log log n) seems to be a theoretical upper bound for the overall problem. I don't see a clear argument for persistent hash tables to really work in constant time, although it seems reasonable to hope that they might. There is a paper I've seen cited in several places for the proposition that persistent set is O(alpha(n)) where alpha(n) is the inverse Ackermann function, by way (of course) of persistent union-find; but if you read the widely-cited persistent union-find paper, it doesn't actually work to prove an upper bound of alpha(n), because their idea of "persistence" puts strict limits on the order in which you're allowed to call the operations in order for them to be fast, violating the basic assumption of what a time bound means. As far as I can tell, the real time bound here is still unknown. It's likely to be good, but unlikely to be easily provable.
Day 7 ("Bridge Repair")
Simple backtracking again. Easy in Prolog, would be harder in a language that didn't have that built-in. The trickiest bit for my own solution was the "concatenate digits" operation, which I implemented by going to strings and back. But this day's puzzle, by invoking large numbers, also highlights something that is frequently significant in AoC puzzles: you really need "bignum" (arbitrary-precision integer) arithmetic to do AoC. That may be an unfair advantage for languages that have it, and I don't think it's really a reasonable expectation that all languages will or should. Anybody using C or assembly or anything else with a routine limit on how large integers can be, will end up spending a lot of extra work just implementing bignums rather than addressing the actual puzzle.
Day 8 ("Resonant Collinearity")
The antenna-pattern thing is cute; although it's not an accurate simulation of radio propagation in detail, it does convey pretty well the feeling of doing these kinds of calculations. I ended up using floating-point math (with appropriate guards against division by zero) to do the slope comparisons in Part II; if the problem got a little bigger it would probably make sense to do it "really right" with exact rationals. I know ECLiPSe-CLP does support those, but would have to refresh my memory on how to use them.
Day 9 ("Disk Fragmenter")
Important lesson here is that you have to follow the problem description to the letter. It's not "compact the disk, at all" or "compact the disk, in the best way"; it's "compact the disk, according to this specific algorithm." That makes the puzzle a little less interesting because it's more or less a pure implementation question. I didn't want to bother with trying to use arrays (an ECLiPSe-CLP extension not in standard Prolog) so I ended up with a list-based implementation that is suboptimal for speed, but still runs faster than the human time it would take me to create a more efficient version.
Day 10 ("Hoof it")
Simple illustration of the difference between setof/3 and bagof/3 in Prolog: are we counting the summits you can reach, or the paths to those summits? It's easy to get both counts provided the path-finding code is disciplined about its successes: it needs to succeed exactly once for each path to each summit, and then setof/3 and bagof/3 can do the work of performing the right kind of count. This would break if the input could be set up to create very large numbers of distinct paths, but because there are only a few different altitude levels possible, that can't actually happen.
Day 11 ("Plutonian Pebbles")
My implementation for Part I just computes the list of pebbles in order. That's small enough to reasonably fit in memory, and I wrote the code for it not yet having seen the Part II question. If Part II had required some information about the order of the pebbles, then this implementation might've been necessary.
In fact, Part II is just "do Part I again, but with a list that's too big to fit in memory," so the big spoiler insight is that the order of the pebbles doesn't matter and you can abbreviate the list down to the counts of how many pebbles have each number. This is reasonably straightforward.
Some commentators have analysed it further and discovered that the set of distinct pebble numbers converges on a fairly small, fixed set. Any numbers that are bigger than a certain limit will always decrease, so they quickly end up within the set. Then it turns into a matrix eigenvector thing: you have a vector saying how many pebbles there are with each number, each time you blink you are multiplying that vector by a fixed matrix, and so it's relatively easy to say what the numbers will be after any arbitrary number of blinks.
As with Day 7, there's an operation here that requires going to strings of decimal digits and back, defying simple mathematical analysis although it can be done closely enough to make the convergence proof valid.
A lot of commentators were saying "Oh, this is lanternfish, it's just lanternfish again"; apparently that is a reference to some well-known AoC problem from a previous year.
As I mentioned, this could be made more interesting by preventing easy abbreviation of the long list in Part II. For instance, if there were an additional rule about pairs of adjacent pebbles doing something different when they add up to a prime number, then just counting how many pebbles have each value would no longer work, and it'd require more serious thought to handle sequences too long to fit in memory.
Day 12 ("Garden Groups")
Some annoying details here because of the way the input is represented - each contiguous region is counted separately even if more than one has the same letter in the input. So there is some caution necessary when doing the "flood fill"-type operation to assign cells to regions, and as usual my implementation went for simplicity and correctness at the cost of using some inefficient, default Prolog data structures. Then there's also some careful pattern matching to do to get a correct count of "sides" in Part II. Nothing really difficult, though; it's just a matter of carefully implementing all the stated rules.
Day 13 ("Claw Contraption")
This one was a chance to use ECLiPSe's constraint libraries - certainly not the most efficient way to solve the problem, but a convenient and fun way. The try_for_prize/3 predicate just directly implements the rules of the game as constraints on variables: number of presses on each button is nonnegative (I dropped the "at most 100 presses" constraint as incorrect for Part II and unnecessary even for Part I); cost in tokens is what it is; coordinates must line up with the prize; and so on. Then I just call the branch-and-bound library to find the best possible solution.
That worked well for Part I. It didn't work so well for Part II because of technical aspects of how the ic solver works. In Part II you need more precision than a typical floating-point number has. Even though this solver works with arbitrary-precision integers, it works by also using floating point numbers internally to bound the integers, and the bounding technique doesn't work well on this specific problem. I ended up having to do some careful "black magic" tweaking of the search parameters to get it to run in reasonable time. I also had to add a separate check on the GCDs of the button-press coordinates to pre-filter out prizes that were not gettable at all, because apparently when the problem is not actually feasible at all, with numbers the size of those used in Part II, the ic solver isn't smart enough to recognize the infeasibility and fail. Instead it just spends effectively forever searching.
As with many of these puzzles, the instances actually generated by the Web site fail to cover some hard cases. I created a harder input file of my own for testing purposes and if you've implemented a solution for Day 13, you might like to try it on that input to see if you've really got a correct solution. I reckon the correct answers for that file are 1000013 for Part I, 22500001000013 for Part II; and my own code manages to solve Part II on the torture-test file only by aborting with a branch-and-bound timeout.
Day 14 ("Restroom Redoubt")
Part II of this puzzle gave a lot of people fits because it is so vague, and it has no example or test. The robots arrange themselves into "a picture of a Christmas tree" but what does that actually look like?
The problem seems designed to force participants to simulate time steps and look at the results visually - possibly an extra challenge for a blind participant of my acquantance, but probably intended as an AI killer. I don't think it worked for keeping out the AIs, given the leaderboard results, but I guess they wanted to try. The actual number of time steps before the pattern appears is big enough (in the high four figures for me) that manually looking at them all one by one is not really practical, but some people clearly did it that way anyway.
After simulating a couple hundred time steps, I could see that the robots were periodically clustering in the X and Y coordinates, and it would be reasonable to assume that the picture turns up when they do that in both coordinates at once. It would be possible (see the Chinese Remainder Theorem) to calculate the time when the clusters in X and Y would coincide based on the information from the per-axis clustering, but instead, I just implemented it the straightforward, stupid way: simulate every time step until the cluster appears on both dimensions.
I used the standard deviation of the coordinates in each dimension to recognize clustering, triggering when that went below a threshold, with some trial and error to choose the thresholds. A lot of people had the "insight" that you can use the safety score from Part I as a test statistic, triggering when that goes low, but unfortunately, I don't think that really works in general even if it may work in many individual cases. If the cluster occurs in a single quadrant then the safety score will go low, but if the cluster is right in the middle of the grid, straddling the division betwen quadrants, then the safety score won't be much different from usual.
Day 15 ("Warehouse Woes")
This one isn't algorithmically very difficult, but there are a lot of finicky details to get wrong. My code was lengthy and took a while to write because of needing to sort out all those details.
Some sliding-block puzzles are potentially very difficult from an algorithmic perspective too (PSPACE-complete), but the puzzle actually given here is basically just implementation, with the double-cell crates as the only real wrinkle. If they had turned it into a real sokoban-style puzzle (choose the sequence of pushes to move the crates into a specified configuration) then it could easily have become too difficult for even the fairly high standard of AoC participants.
Day 16 ("Reindeer Maze")
Two ways to do this: implement Dijkstra's Algorithm for shortest path, or do a branch-and-bound over paths. The former is probably the best way to do it algorithmically, but I ended up doing the latter because it seemed conceptually simpler. The algorithmic problem is that there could possibly be an exponential number of tied "best" paths; so if the instance is big enough, and you do anything that involves executing code on every "best" path individually, then you can lose. The instance they gave me was just small enough for that not to be a problem.
Day 17 ("Chronospatial Computer")
Part I is straightforward, basically just a warm-up for the more complicated Part II.
"Easy instances" again: it seems clear that they give the same "program" to everybody, with only very minor cosmetic tweaks. So you don't really need to solve the problem at full generality (that is, for every possible program); you just need to analyze the one specific program they gave you and come up with an answer to make that program write itself out.
It's also clear from the nature of the instruction set what the program is going to look like if it can write itself out at all, and it can't be very complicated. All you can do with register A is basically to shift it right and copy the low bits elsewhere. You can do a little bit of XORing and other munging on the other registers, but not much. The only jump instruction you have is "jump if A is nonzero." So it's no secret that what you're going to do is write out the low bits of A, shift them away, and loop until there is nothing left. A solution to Part II follows from solving it for suffixes of the program and then extending them to cover the entire program.
This is not the classical "quine" problem, of getting a program to write out its own source code, because traditional quines are expected to do that without any input. In the AoC problem, the computer is allowed an arbitrary-sized input, and the output only needs to be the program itself without including that input; so it's much easier.
I think there's some interest in trying to solve it at full generality, that is, with an arbitrary sequence of three-bit integers that wasn't human-designed to make the puzzle easier. Obviously, for many such programs the computer would fail to write anything, fail on invalid operand, or go into an infinite loop; so the successful general solution would need to detect and exclude those cases. Either state the integer value of register A to make it write the program out, or prove no such integer exists.
This isn't the Halting Problem (and therefore unsolvable) because I don't think the computer in the puzzle is anywhere near Turing-complete. It seems to be an infinite state machine but only just barely. The entropy of the registers can only decrease, like tapes that can't be rewound, and there are only eight possible destinations of jump instructions. There are only a few simple looping structures that could possibly loop infinitely. I think it's likely, but I haven't proved, that it's possible for every program to compute with certainty whether it halts and whether it can print itself.
Day 18 ("RAM Run")
My Part I solution isn't the most efficient it could be, but is reusable for Part II, which just does a binary search over different values of "how many obstacles?" for Part I to find the smallest number of obstacles that makes escape impossible. Interestingly enough, running all of Part II takes less time for me than running the single iteration of Part I to answer Part I as such, even though Part II involves multiple calls to Part I. That comes about because the single first iteration in Part I is at a low number of obstacles, making the search slow, whereas all the iterations used in Part II are at higher numbers of obstacles, where the search succeeds or fails quickly.
Day 19 ("Linen Layout")
Straightforward application of memoization here: each call to design_feasible/1 or count_designs/2 is potentially expensive, but each time you call it, you can write down the answer, and then if you ever call it again with the same arguments you use the stored value instead of really doing the work. I ended up writing separate and incompatible implementations for Parts I and II because, of course, I had to finish Part I before seeing the problem statement for Part II; if trying for the most elegant solution possible, I might cut out the Part I solution (counting is really no harder than evaluating feasibility here) and just have Part I report success whenever the count for Part II is more than zero.
Day 20 ("Race Condition")
When I started work on this I had some concern that the input might be poorly-behaved, with things like branching paths and open spaces wider than a single cell. It doesn't appear that those kinds of things really occur; the input seems to always be just a straightforward path from start to finish. In that case it hardly seems difficult, but I guess one opportunity for confusion would be if you used an inefficient search algorithm for determining where possible "cheats" can occur.
Does it really count as cheating if it's specifically permitted, and controlled in detail, by the rules?
Day 21 ("Keypad Conundrum")
This was the one I found really difficult. I think it was the 23rd before I got even Part I, and after spending a few more days working on Part II (during which time I had other things to do, as you can imagine) I ended up shelving it until New Years' Eve, when I finally completed it. All the other problems I was able to do same-day. Over the course of the time I spent on it, I think I ended up writing at least five complete implementations, all incorrect until the last one.
For Part I: there are 5×5×11 states for the fingers on the three keypads other than the human-controlled keypad. That comes to only 275 states. So you can do all-pairs shortest-path and come up with a minimal set of keystrokes to get from any state to any other state. I implemented that, but did it in an inefficient way, and my first correct implementation took more than 48 hours to run. By the time it finished, I'd actually done a couple more generations of better implementations - in particular, making use of the fact that every interesting path either starts or ends on a state where all the intermediate fingers are on "A," that is, one of 11 states, so the number of paths really worth calculating is much less than the roughly 75,000 paths that a naive calculation might suggest. I had already finished Part I with a later-generation implementation of shortest-path and then just let the first implementation run to completion to see how long it would take.
That approach doesn't work in Part II because with 25 intermediate fingers there are 525×11 states, which is approximately 3.3 quintillion. It's possible to shrink the count down a lot by observing that the only states you really care about are the ones where you focus on one finger, all fingers before it are on "A," and you don't care about and won't move any fingers after it. Then you basically have 136 "interesting" states, but a lot more complexity in mapping out the paths between them.
I feel I was steered wrong by the way the problem statement was written. They go through a whole big thing of describing how to start with a sequence of moves on the door keypad, then expanding it to the moves to make on the last intermediate keypad, then the second-to-last, and so on. And to get a correct solution to Part II, you must not actually do that. It's not a string substitution problem. The best sequence of moves at one level depends on how deeply it's buried under earlier levels; in particular, "v<A" and "<vA" are not created equal, because the way they will expand out does or doesn't allow for shortcuts, differently, at higher levels of expansion.
The sequence of moves for Part II is too long to fit in memory, but that's not the real problem - even with clever ways of abbreviating it (and I wrote and threw away several), the real problem is that this isn't the string-substitution problem it looks like. And the fact that treating it as string substitution doesn't work, only shows up after you have more levels than occur in Part I, so it's easy to write a piece of code that gives the right answers for Part I but can't correctly solve Part II when extended to more levels.
Instead, you have to start at the other end: figure out how to move around efficiently on the first (nearest the human) robot directional keypad, then use that to figure out how to move around efficiently on the second directional keypad, and so on. With careful, clear thought about what level you're at at each step, and then memoization of the answers, the resulting code ends up being pretty strightforward and gives an answer quickly, and the code is not even very long - much of the source code file is just my rant about disliking the problem, making the same points made here.
It also didn't help that this was another one where they gave no example or test data for Part II. All in all, a frustrating problem.
Day 22 ("Monkey Market")
I just implemented this in the straightforward way; about the only "clever" thing being that I limited the possible buying orders to quadruples of differences that could actually match real price sequences. For instance, (9,9,9,9) is not a sensible buying order because if one price difference is 9, then that means the two prices in question had to have been 0 and 9, and then the next price difference cannot be positive (let alone 9 again) because that would mean a third price of greater than 9. Applying that kind of logic wherever possible significantly reduces how many different orders are worth considering.
It might be interesting to think about cryptanalysis techniques applied to the price-generating hash function to try to speed up the matching/testing process and find especially good instructions, but that's likely to consume a lot more human time than the computer time that would be saved over the simple approach. Probably only worthwhile if you are a monkey market mutual fund manager.
Day 23 ("LAN Party")
Finding triangles is straightforward enough. I parsed the input in such a way that the node names would end up as A-B pairs (the minus sign is just a convenient functor for pattern matching, not actually representing subtraction here), so that I could do an easy pattern match to find node names starting with "t." Part II is exactly what's called the "maximum clique" problem in computer science, and it's an NP-hard problem, although easy enough on the input actually given by the puzzle generator. ECLiPSe-CLP has a graph library that might be of use, but instead I implemented it using the ic solver: I just created binary variables to say whether each node is or isn't in the clique (the "LAN party," as the problem calls it), and constraints to say that two nodes can't both be in the clique if they don't have an edge connecting them. Then the question is, find values for the variables so that their sum (equal to the size of the clique) is maximized. And once the problem is set up, "find values for the variables respecting the constraints so that this value is maximized" is just a single call to a library function.
Day 24 ("Crossed Wires")
Another good case for the ic solver. The stated problem basically is constraint satisfaction on its face. I just had to create variables for all the, well, variables in the problem, and then add constraints saying this one should be 1, that one should be 0, this other one should be the XOR of these two, and so on.
ECLiPSe-CLP's language interpreter does a thing called "coroutining" which basicially means bits of code can be attached to variables so that the code runs as the variables are updated. That is how the constraints used by the solver are implemented: I can start with a variable that has no restrictions, then add constraints like "this variable must be either 0 or 1" or "this variable plus that other variable must add to less than 2" and as these constraints get tighter and tighter, inferences like "therefore this variable must actually be equal to 1" will be made and applied behind the scenes whenever they become valid. (Inferences that lead to contradiction, cause backtracking - bearing in mind that backtracking is a fundamental operation of the interpreter anyway.)
These inferences from constraints are not the same as "types," although they can certainly be used to do some of the same things for which people use types.
So after applying all the constraints, it ends up that I can just read the result values for Part I out of the corresponding variables without needing to do anything explicit to calculate them. The calculations happened automatically along the way.
It's not at all clear what might be the optimal way to do Part II. I came up with a sort of hill-climbing, which seems to work but it's hard to guarantee it will be correct. I evaluate the circuit on a bunch of randomly-chosen test vectors and get a score based on how many output bits it gets wrong. Then I try every possible swap of two wires, and see which one gives the best score (hoped to be an improvement on no swap at all). I keep the best swap (breaking ties arbitrarily) and keep trying. With luck, four swaps chosen that way will bring the circuit to correctness.
That approach worked pretty well in practice. I did some manual experimentation on number of test vectors to use and the details of how to use them, and ran multiple instances on separate CPUs. It is possible that in some cases with not enough test vectors, it will choose an incorrect swap and then fail. And I haven't formally disproven that some especially fiendish swaps might exist that would be difficult or impossible to detect this way. But overall, with the parameters given in my posted code, it seems to work pretty well. If I needed a more bulletproof solution (trustworthy to work the first time and without human supervision) I might wrap the whole thing in another layer of backtracking and confirmation of the results.
Some people attacked this problem similarly to Day 17, with human analysis of the given circuit. That was an opportunity to do some fun visualizations, but it also would make for a more fragile solution because it'd depend on the fact that the input circuit was (apparently) a fairly straightforward and standard adder circuit. A skilled human looking at the circuit would probably be able to understand how it should be rewired without really needing a computer search to find the swapped wires. I tried to write something that would not depend on assuming anything about the structure of the input; the input circuit for my code could be anything that happens to produce an addition result (or that will, after unswapping the wires), whether it is an adder of standard design or not.
Day 25 ("Code Chronicle")
They backed the difficulty off for the final puzzle. My solution does most of the work in the parser, by assigning unique variable names to the grid cells and then feeding them in the right order to depth/6, which pattern-matches the graphical columns to get numbers that can be easily compared. The parser is a bit fragile (in particular, because it doesn't keep track of lines and just depends on the count of non-whitespace characters) but works for the given inpuit.
Despite that I did a software engineering challenge this year, it's not really my thing; I'd rather sell synthesizers. However, the synthesizer business isn't going well, and I do need money. So if you'd like to talk about how constraint logic programming or my other areas of expertise can help with whatever problems you face, drop me a line.
◀ PREV Remote-debugging the Gracious Host
