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 6-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’ll be updating this post over the month, but will mostly be doing commentary on solutions over on Mastodon.

• 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.