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.