Advent of Dusa, 2024 Edition

Now that I’ve rewritten Dusa using the lessons I learned writing a paper about it over the last year, I get to do some fun exploring. Here’s a screenshot of a forest fire model that I implemented with p5js and Dusa:

(Incidentally, I’m incredibly grateful for Julia Evans’ timely discussion of the state of JavaScript libraries. Her post was intended for people that use JS libraries, but it was also very helpful in helping me sort out the way(s) in which the Dusa package should be distributed via NPM, and that helps the p5js sketch look like actual idiomatic p5js instead of needing weird exports and module stuff.)

But it’s also December, and that means another attempt to do Advent of Code in Dusa. I’m going to give myself a rating system to judge my examples this year:

• 1 stars: ⭐ — I solved the problem, but just used JavaScript/did not use Dusa at all.
• 2 stars: ⭐⭐ — I solved the problem, and used Dusa, but in a mostly trivial way (for instance, if I’m using Dusa mostly as a fancy Map).
• 3 stars: ⭐⭐⭐ — I solved the problem using a combination of Dusa code and JavaScript code. That forest fire model would be a 3-star solution because I call Dusa in a loop.
• 4 stars: ⭐⭐⭐⭐ — The solution is a JavaScript program that parses the input into JSON, processes the input with Dusa, and then does some final computation in JavaScript with something like a call to solution.lookup('answers').reduce(...). I expect this will be relatively common, because Dusa’s not great at aggregation.
• 5 stars: ⭐⭐⭐⭐⭐ — There’s a minimal JS step parsing the input into JSON, and the solution runs using the dusa command line utility.

Black stars ★ for solutions that works on the examples, that I think are conceptually sound, but that don’t work for the full example due to efficiency issues or some bug I don’t understand.

I updated this post over the month, with some commentary on solutions over on Mastodon. I ended this Advent of Code with, by my count, 188 out of a possible 245 stars. A solid passing grade for Dusa, with room for improvement!

• Day 1: 10⭐ (JS parsing code)

  • Part 1 ⭐⭐⭐⭐⭐ github dusa.rocks
  • Part 2 ⭐⭐⭐⭐⭐ github dusa.rocks

  Notable: implemented a Prolog-style quicksort with Dusa’s experimental lazy predicates.

• Day 2: 10⭐ (JS parsing code)

  • Part 1 ⭐⭐⭐⭐⭐ github dusa.rocks
  • Part 2 ★★★★★ (can’t handle full input) github dusa.rocks
  • Part 2 ⭐⭐⭐⭐ github
  • Part 2 ⭐⭐⭐⭐⭐ (added Dec 4) github

  First time this year with a solution that works on the test but not the full input. At fault is the double-default-reasoning pattern (safe defaults to tt and hasSafe defaults to 0) which leads to exponential backtracking in Dusa.

  I (believe that I) know how to optimize Dusa search to totally avoid this, making the 4-star solution a 5-star solution, but I didn’t include that in the November rewrite to avoid second-system syndrome (full rewrites are already dangerous enough) and because I wanted the rewrite to remain an honest implementation of the system described in the POPL paper. These kinds of examples are good for motivating doing that work later, though!

  (Update Dec 4: The double-default pattern was arising because I needed to count the solutions. But according to my own rules a 5-star solution just needs to use the dusa cli as the final step, and I added a “count all the tuples in this relation” feature months ago. This can be used to get a full-credit solution according to my own arbitrary rules.)

• Day 3: 10⭐ (JS parsing code)

  • Part 1 ⭐⭐⭐⭐⭐ github dusa.rocks
  • Part 2 ⭐⭐⭐⭐⭐ github dusa.rocks

  Just barely had enough standard library to hobble through this one. Part 2 is a mess, and is also very slow for reasons I don’t fully understand; I hope it’s just “using concat in this way was a feature you barely implemented,” but this is something I should return to and profile. A first part 2 attempt was very concerned about adapting to situations where multiple do()s and don’t()s appearing between two successive muls(), but the solution I ended up with just aborts if this happens.\

• Day 4: 10⭐ (JS parsing code)

  • Part 1 ⭐⭐⭐⭐⭐ github dusa.rocks
  • Part 2 ⭐⭐⭐⭐⭐ github dusa.rocks

  Beautiful Dusa example if I do say so myself. Over breakfast, Chris described and then explained a different way of handling the “count up solutions” problem that works reasonably well even if there’s no way to order the solutions. I can use this to solve part one like this, but I also realized I was overthinking things for this and for day 2 slightly, because my arbitrary rules allowed me a route to solving day 2 by counting the number of safe lines (there) and the number of XMAS occurances (here) as a command line option.

• Day 5: 10⭐ (JS parsing code)

  • Part 1 ⭐⭐⭐⭐⭐ github dusa.rocks
  • Part 2 ⭐⭐⭐ github
  • Part 2 ⭐⭐⭐⭐⭐ github dusa.rocks

  The “right” solution to Part 2 is, IMO, the three-star one. There’s no point in doing the sorting part in Dusa, but it’s quite nice to “export” our custom comparison function from Dusa, as in the 3-star solution. However, lazy predicates are fun, have an selection sort, why not.

• Day 6: 8⭐ (JS parsing code)

  • Part 1 ⭐⭐⭐⭐⭐ github dusa.rocks
  • Part 2 ★★★★★ (can’t handle full input) github dusa.rocks
  • Part 2 ⭐⭐⭐ github

  Part 1 goes swimmingly. The cycle detection in Part 2 is expensive (it is quadratic in the length of the path) but the real kicker is out of memory errors. This is a good performance (speed AND memory) benchmark for the future, and also I think this would work fine with a non-randomized, just-DFS state space exploration; it’s the randomization that’s causing the memory leak here to a significant degree.

  Also badly wanted to be able to compute an optimized “after” relation and efficiently use that across instances, which I have some ideas to do with the current API.

  Standard solution from last year: pull the outer loops (in this case, where the blockage is placed) out of Dusa and into JS. Result is not going to win any speed records — like, slow, way too slow, like an hour or so? — but I was happy to do some other work while it bumbles along and wasn’t super pumped to come up with a faster solution.

• Day 7: 8⭐ (JS parsing code)

  • Part 1 ⭐⭐⭐⭐⭐, prunes a little github TODO add dusa.rocks
  • Part 1 ⭐⭐⭐⭐⭐, prunes a lot github TODO add dusa.rocks
  • Part 2 ★★★★★ (can’t handle full input) github TODO add dusa.rocks
  • Both parts ⭐⭐⭐ github

  Here, my desire for five stars led me astray — Dusa can do backtracking search, but it’s not currently smart enough to notice that the backtracking search needed for line 1 is totally independent of the backtracking search needed for line 2, so the right way to reasonably solve this problem in Dusa is to do a line-by-line invocation the way the 3-star solution does.

  I think of folks found the “do part 1 search and only do the part 2 search if it fails, because part 2 search is slower” method useful, and it gives you a part 1 solver for free in your part 2 solver.

  Overall, I like the last solution I came up with, and it would be worth seeing what could get it running faster.

• Day 8: 10⭐ (JS parsing code)

  • Part 1 ⭐⭐⭐⭐⭐ github dusa.rocks
  • Part 2 ⭐⭐⭐⭐⭐ github dusa.rocks

  This is a nice one! Both parts are straightforward to express in Dusa, and I don’t expect to ever do much better than “three parsing rules and 2-3 logic rules.”

• Day 9: 7⭐ (JS parsing code)

  • Part 1 ⭐⭐⭐⭐⭐ github dusa.rocks
  • Part 2 ⭐⭐ github

  This was messy for lots of folks, and it was messy for me. Reasonably happy with the Part 2 solution as a straightforward JavaScript solution, but I spent too long trying to do imperative programming in Dusa before I got there. Also, thanks to mutation and the edge case dealt with inelegantly here this was the first time this year that I got a “that’s not right” message for one of my submissions. I had either 2 or 3 incorrect submissions on part 2.

• Day 10: 10⭐ (JS parsing code)

  • Part 1 ⭐⭐⭐⭐⭐ github dusa.rocks
  • Part 2 ⭐⭐⭐⭐⭐ github dusa.rocks

  Pretty easy for everyone based on the vibes I’m picking up, but I think the Dusa solution is particularly nice and clean. Two design choices in Dusa make part 2 both elegant and efficient: the support for structured terms makes part 2 elegant, and allows list-like representation of the interesting paths, and the choice to use ubiquitous hashconsing makes this fast.

• Day 11: 10⭐ (JS parsing code)

  • Part 1 only ⭐⭐⭐⭐⭐ github dusa.rocks
  • Parts 1&2 ⭐⭐⭐⭐⭐ github dusa.rocks

  By far the hardest part was splitting an 2N digit number into two N digit numbers without integer-to-string conversions and without division. I think it would have been faster to just add a division primitive to the language!

  The efficient solution is just dynamic programming: the computation of descendents looks like a recursive functional program for the most part! This solution is an advertisement for tabled logic programming as much as it’s an advertisement for Dusa specifically.

• Day 12: 8⭐

  • Parts 1&2 ⭐⭐⭐⭐ github

  General vibes seem to be that this was not so much “challenging” as “messy” for most folks. So I’m going to declare myself a bit smug, given that this solution is two successive versions of the textbook algorithm showing what Dusa does well: counting the connected components in the graph. In the first instance, the nodes in the graph are positions on the grid, and in the second instance, the nodes in the graph are individual segments of fence. Then, counting the number of canonical representatives gives you the number of segments of fence.

  I said at the outset that I expected four-star solutions to be super common; that hasn’t turned out to be the case so far, but it felt like the easiest way to do the calculation in Part 1 here. That was valuable for Part 2, because Dusa does get confused and do expensive backtracking if you try to do two instances of this canonical representative algorithm at once. Given that these choices probably lead to the overall cleanest solution on a generally messy day, I’m glad I didn’t bother shooting for all ten stars.

• Day 13: 4⭐

  • Part 1 ⭐⭐⭐ github
  • Part 2 ⭐ github

  Not much to say; this problem is mostly linear algebra and I haven’t implemented, like, division in Dusa.

• Day 14: 4⭐

  • Part 1 ⭐⭐ github
  • Part 2 ⭐⭐ github

  I could probably give myself a third star for the part 2 solution, it’s borderline. I may be the only person who implemented “count the connected components” to measure graph interestingness, but counting connected components is easy in Dusa!

  There are a lot of times I’m calling dusa.solution.lookup() when all I want is a count of facts. That could be worth implementing more efficient support for.

• Day 15: 6⭐

  • Part 1 ⭐⭐⭐ github
  • Part 2 ⭐⭐⭐ github

  I was very slow to get the “which boxes get pushed” logic suitably into Dusa, and implementing “oh, there’s a wall there” as a constraint violation in Part 2 was nice. Overall this solution feels pretty meh.

• Day 16: 6⭐

  • Part 1 ★★★★★ (doesn’t scale to solution) github dusa.rocks
  • Parts 1&2 ⭐⭐⭐ github

  A first Dusa program was used to cut the state space down dramatically by observing that, once you’re in a hallway, you gotta run down the hallway. I checked whether the results of the first program would cut down search space enough for unguided with DFS to work, but no such luck.

  A second Dusa program performed A* on that smaller search problem, though instead of the priority queue I just re-calculate the whole frontier and find the frontier node with the lowest cost. An interesting thing here that I haven’t done elsewhere was maintain a single Dusa instance and repeatedly add new facts to it as I removed things from the A* queue and added them to the “committed” set.

• Day 17: 2⭐

  • Part 1 ⭐ github
  • Part 2 ⭐ github

  This is not what Dusa’s for and I didn’t even try. Part 2 mighta been interesting if Dusa had bitwise operations, which it does not. (Would not be hard to add though!)

• Day 18: 6⭐

  • Part 1 ⭐⭐⭐ github
  • Part 2 ⭐⭐⭐ github

  Part 1 was a refinement of the “bad priority queue for best-first search” that I developed on Day 16. It is a really good example of something that an API should be able to handle quite fast, but the implementation doesn’t easily support, and the API doesn’t easily enable, doing this problem well.

  Part 2 I mostly shamed myself by getting binary search off by one the first time despite documenting invariants, but so it goes. It would be silly but maybe possible to move the binary search logic into Dusa, though the lack of division hurts.

• Day 19: 6⭐

  • Part 1 ⭐⭐⭐⭐⭐ github dusa.rocks
  • Part 2 ⭐ github

  I did this on very little sleep, and initially had to fall back on a three-star solution to part 1 because the solution was greedily consuming too much memory. This was the first time I had to go back and revise my JS parsing code — the solution here uses the STRING_CONCAT builtin rather than trying to explode the strings into individual characters. It’s still much slower than I’d expect or like, something I’d like to look into.

  Dusa doesn’t have aggregation: there’s no idiomatic way to say “count the number of Y such that match X Y holds”, which is necessary to do Part 2 in a reasonable way. An industrial-strength implementation of finite-choice logic programming obviously needs such a capability, though this is the first time I’ve really been unable to express an algorithm in Dusa at all because of this lack of aggregation.

• Day 20: 8⭐

  • Part 1 ⭐⭐⭐⭐⭐ github dusa.rocks
  • Part 2 ★★★★★ (doesn’t scale to solution) github dusa.rocks
  • Part 2 ⭐⭐⭐ github

  Since DFS has a unique solution, I used that in both parts. This presentation of DFS is nice and I wish it was the right answer more often.

  Part 2 choked due to memory use, but the javascript is really just an implementation of the logic from the solution. This is an excellent example to consider if/when I think about optimizing space usage.

• Day 21: 7⭐

  • Part 1 ⭐⭐⭐⭐⭐ github dusa.rocks
  • Parts 1&2 ⭐⭐ github

  This seems to have been the hardest overall challenge of the season, so I feel pretty happy that I was able to do a pure-Dusa solution for this one. At its core, the part 1 analysis uses bounded reachability to figure out all the ways to get from an X<A<A robot configuration to a Y<A<A robot configuration.

  I honestly really dislike this pattern of doing bounded reachability: it’s incredibly wasteful, but it’s common in answer-set-programming like settings. See the at/3 relation defined here. It’s a research question how to do optimized minimizing search in this context, I believe it should absolutely be possible.

  Part 2 is a dynamic programming solution in JavaScript, answering the question “how do you get a robot to move from pointing at X to pointing at Y on top of N roboceptions, assuming all the roboceptions start and end with pointing at A”. It uses Dusa to enumerate all the non-backtracking keysmash sequences that get you from pointing at X to pointing at Y, which is then used in the dynamic programming solution. That’s not a super compelling use of Dusa.

• Day 22: 3⭐

  • Part 1 ⭐ github
  • Part 2, very slow ⭐⭐ github
  • Part 2, actually reasonable ⭐⭐ github

  Gotta have some bitwise operation builtins if I wanna mess with this kind of nonsense. Recording two part 2 solutions because the reasonable solution was done after I’d looked at some other folks’s solutions (everything else I’ve essentially done independently) and also because the marginal use of Dusa in the slow Part 2 is I think a very clear way of enumerating all the possible sequences, but in the fast Part 2 that’s a very silly and unnecessary use of Dusa.

• Day 23: 10⭐

  • Part 1 ⭐⭐⭐⭐⭐ github dusa.rocks
  • Part 2 ⭐⭐⭐⭐⭐ github dusa.rocks

  The Part 1 solution is a nice use of running string concatenation “backward” to check for a t prefix. The Part 2 solution wasn’t particularly efficient, but it’s nice, short, inductive: if you have two cliques with edges alphabetically ordered like ab,cd,blah... and ca,cd,blah..., as long as the cd,blah... parts are the same (which is a constant-time check in Dusa thanks to ubiquitous hash-consing), then an edge ab-ca implies that ab,ca,cd,blah... is also a clique.

• Day 24: 10⭐

  • Part 1 ⭐⭐⭐⭐⭐ github dusa.rocks
  • Part 2 ⭐⭐⭐⭐⭐ TODO upload presentably

  I solved Part 2 entirely with dusa.rocks rather than copying stuff to my computer and running npx dusa or node, so it’s hard to share without sharing my input, which we’re asked not to do. But at a high level, I did some calculation to evaluate “which wire, if any, contains the nth bit of two correctly added inputs, if any,” which generally made it obvious what was wrong.

• Day 25: 5⭐

  • Part 1 ⭐⭐⭐⭐⭐ github dusa.rocks
  • Part 2, as is traditional, is a freebie

  Using Dusa made this problem almost trivial in complexity: of the 9 rules, only one is the actual problem, and the other 8 are just reconfiguring data.