Advent of Dusa, Day 19

I wrote a logic programming language at Recurse Center and now I’m doing Advent of Code with it. Today was a good use case for Dusa, and Part 2 was a kind of problem I understood pretty well — I’ve even written a paper about using logic programing to “do this sort of thing” (but only if you define “this sort of thing” very broadly, I don’t actually recommend that paper.)

Interpreters and abstract interpreters

Here’s how I approached the shape of Day 19. Instead of the imaginary analysis language, imagine we’re dealing with programs like this:

0  
1  if a > 3:
2     
3     if a > 7:
5        accept
6     else: 
7        reject
8  else:
9     
10    if b > 2:
11       accept
12    else:
13       reject

In Part 1, the goal is to trace through the program from some initial positions to the final positions, which sort all the inputs into “accept” and “reject” states.

The “nodes” of our trace are specific program states, where a program state is the value of all the properties and also a property that keeps track of where we are in the program.

As a graph, this isn’t very interesting: each parent has at most one child.

Frame 15.png

In Part 2, we trace through the program for all initial states, treating nodes as sets of states rather than as individual states. The top box in represents 100 different specific states, (all 10 possible values for a) * (all 10 possible values for b).

This is now a more interesting graph/tree, because a node might have two children if it includes states that both pass the relevant check and fail the relevant check.

Frame 16.png

Put differently, in part 1 we write an (abstract) machine for sorting inputs, and in part 2 we abstract that abstract machine. I do recommend the Abstracting Abstract Machines paper, and the subsequent work by Van Horn and Might, if you’re interested in this sort of thing.

Code

Today had the most complicated parsing-into-json logic I’ve dealt with so far, I think:

import { Dusa } from './lib/client.cjs';

const [programStr, inputsStr] = `

px{a<2006:qkq,m>2090:A,rfg}
pv{a>1716:R,A}
lnx{m>1548:A,A}
rfg{s<537:gd,x>2440:R,A}
qs{s>3448:A,lnx}
qkq{x<1416:A,crn}
crn{x>2662:A,R}
in{s<1351:px,qqz}
qqz{s>2770:qs,m<1801:hdj,R}
gd{a>3333:R,R}
hdj{m>838:A,pv}

{x=787,m=2655,a=1222,s=2876}
{x=1679,m=44,a=2067,s=496}
{x=2036,m=264,a=79,s=2244}
{x=2461,m=1339,a=466,s=291}
{x=2127,m=1623,a=2188,s=1013}
`
  .trim()
  .split('\\n\\n');

const INPUT = {
  program: programStr.split('\\n').map((line) => {
    const [name, checks] = line.slice(0, line.length - 1).split('{');
    const checkList = checks.split(',');
    const fallthrough = checkList.pop();
    return {
      name,
      checks: checkList.map((str) => ({
        property: str[0],
        check: str[1],
        quantity: parseInt(str.slice(2).split(':')[0]),
        goto: str.slice(2).split(':')[1],
      })),
      length: checkList.length,
      fallthrough,
    };
  }),
  inputs: inputsStr.split('\\n').map((line) =>
    line
      .slice(1, line.length - 1)
      .split(',')
      .map((entry) => entry.split('='))
      .map(([property, amount]) => ({ property, amount: parseInt(amount) })),
  ),
};

All the rest of the logic fell nicely inside of Dusa.

Here’s the program for part 1 at dusa.rocks. The answer is the N such that goal is N.

Here’s the program for part 2 at dusa.rocks.%20Check%20(s%20N)%20%3A-%0A%20%20%20%20path%20P%20Check%20N%2C%0A%20%20%20%20check%20Check%20N%20is%20Ref%2C%0A%20%20%20%20field%20Ref%20%22goto%22%20is%20Next.%0A%0ArangeAt%201%20Prop%20is%20(range%201%204000)%20%3A-%0A%20%20%20%20field%20_%20%22property%22%20is%20Prop.%0A%0A%23%20If%20both%20paths%20get%20explored%2C%20unchecked%20props%20go%20both%20ways%0ArangeAt%20Path2%20Prop%20is%20Range%20%3A-%0A%20%20%20%20rangeAt%20Path%20Prop%20is%20Range%2C%0A%20%20%20%20path%20Path%20Check%20N%2C%0A%20%20%20%20check%20Check%20N%20is%20Ref%2C%0A%20%20%20%20field%20Ref%20%22property%22%20is%20Prop2%2C%0A%20%20%20%20Prop%20!%3D%20Prop2%2C%20d%20D%2C%0A%20%20%20%20Path2%20%3D%3D%20plus%20D%20(times%202%20Path)%2C%0A%20%20%20%20rangeAt%20Path2%20_%20is%20_.%20%0A%0A%23%20Subroutine%20for%20checking%20an%20individual%20prop%20at%20a%20step%0Astep%20Path%20Prop%20Range%20Op%20Threshold%20Next%20%3A-%0A%20%20%20%20rangeAt%20Path%20Prop%20is%20Range%2C%0A%20%20%20%20path%20Path%20Check%20N%2C%0A%20%20%20%20check%20Check%20N%20is%20Ref%2C%0A%20%20%20%20field%20Ref%20%22property%22%20is%20Prop%2C%0A%20%20%20%20field%20Ref%20%22check%22%20is%20Op%2C%0A%20%20%20%20field%20Ref%20%22quantity%22%20is%20Threshold%2C%0A%20%20%20%20field%20Ref%20%22goto%22%20is%20Next.%0A%0ArangeAt%20(times%20Path%202)%20Prop%20is%20(range%20Lo%20Hi)%20%3A-%0A%20%20%20%20step%20Path%20Prop%20(range%20Lo%20Hi)%20%22%3C%22%20Threshold%20Next%2C%0A%20%20%20%20Hi%20%3C%20Threshold.%0A%0ArangeAt%20(plus%201%20(times%20Path%202))%20Prop%20is%20(range%20Lo%20Hi)%20%3A-%0A%20%20%20%20step%20Path%20Prop%20(range%20Lo%20Hi)%20%22%3C%22%20Threshold%20Next%2C%0A%20%20%20%20Lo%20%3E%3D%20Threshold.%0A%0Astep%20Path%20Prop%20(range%20Lo%20(minus%20Threshold%201))%20%22%3C%22%20Threshold%20Next%20%3A-%0A%20%20%20%20step%20Path%20Prop%20(range%20Lo%20Hi)%20%22%3C%22%20Threshold%20Next%2C%0A%20%20%20%20Lo%20%3C%20Threshold%2C%20Hi%20%3E%3D%20Threshold.%0Astep%20Path%20Prop%20(range%20Threshold%20Hi)%20%22%3C%22%20Threshold%20Next%20%3A-%20%0A%20%20%20%20step%20Path%20Prop%20(range%20Lo%20Hi)%20%22%3C%22%20Threshold%20Next%2C%0A%20%20%20%20Lo%20%3C%20Threshold%2C%20Hi%20%3E%3D%20Threshold.%0A%0ArangeAt%20(times%20Path%202)%20Prop%20is%20(range%20Lo%20Hi)%20%3A-%0A%20%20%20%20step%20Path%20Prop%20(range%20Lo%20Hi)%20%22%3E%22%20Threshold%20Next%2C%0A%20%20%20%20Lo%20%3E%20Threshold.%0A%0ArangeAt%20(plus%201%20(times%20Path%202))%20Prop%20is%20(range%20Lo%20Hi)%20%3A-%0A%20%20%20%20step%20Path%20Prop%20(range%20Lo%20Hi)%20%22%3E%22%20Threshold%20Next%2C%0A%20%20%20%20Hi%20%3C%3D%20Threshold.%0A%0Astep%20Path%20Prop%20(range%20Lo%20Threshold)%20%22%3E%22%20Threshold%20Next%20%3A-%20%0A%20%20%20%20step%20Path%20Prop%20(range%20Lo%20Hi)%20%22%3E%22%20Threshold%20Next%2C%0A%20%20%20%20Lo%20%3C%3D%20Threshold%2C%20Hi%20%3E%20Threshold.%0Astep%20Path%20Prop%20(range%20(plus%201%20Threshold)%20Hi)%20%22%3E%22%20Threshold%20Next%20%3A-%20%0A%20%20%20%20step%20Path%20Prop%20(range%20Lo%20Hi)%20%22%3E%22%20Threshold%20Next%2C%0A%20%20%20%20Lo%20%3C%3D%20Threshold%2C%20Hi%20%3E%20Threshold.%0A%0Agoal%20Path%20is%20(times%20X%20M%20A%20S)%20%3A-%0A%20%20%20%20path%20Path%20%22A%22%20_%2C%0A%20%20%20%20rangeAt%20Path%20%22x%22%20is%20(range%20XL%20XH)%2C%20X%20%3D%3D%20minus%20(s%20XH)%20XL%2C%0A%20%20%20%20rangeAt%20Path%20%22m%22%20is%20(range%20ML%20MH)%2C%20M%20%3D%3D%20minus%20(s%20MH)%20ML%2C%0A%20%20%20%20rangeAt%20Path%20%22a%22%20is%20(range%20AL%20AH)%2C%20A%20%3D%3D%20minus%20(s%20AH)%20AL%2C%0A%20%20%20%20rangeAt%20Path%20%22s%22%20is%20(range%20SL%20SH)%2C%20S%20%3D%3D%20minus%20(s%20SH)%20SL.%0A%0A%0Afield%20ref64%20%22property%22%20is%20%22s%22.%0Afield%20ref64%20%22amount%22%20is%201013.%0Afield%20ref63%20%22property%22%20is%20%22a%22.%0Afield%20ref63%20%22amount%22%20is%202188.%0Afield%20ref62%20%22property%22%20is%20%22m%22.%0Afield%20ref62%20%22amount%22%20is%201623.%0Afield%20ref61%20%22property%22%20is%20%22x%22.%0Afield%20ref61%20%22amount%22%20is%202127.%0Afield%20ref60%200%20is%20ref61.%0Afield%20ref60%201%20is%20ref62.%0Afield%20ref60%202%20is%20ref63.%0Afield%20ref60%203%20is%20ref64.%0Afield%20ref59%20%22property%22%20is%20%22s%22.%0Afield%20ref59%20%22amount%22%20is%20291.%0Afield%20ref58%20%22property%22%20is%20%22a%22.%0Afield%20ref58%20%22amount%22%20is%20466.%0Afield%20ref57%20%22property%22%20is%20%22m%22.%0Afield%20ref57%20%22amount%22%20is%201339.%0Afield%20ref56%20%22property%22%20is%20%22x%22.%0Afield%20ref56%20%22amount%22%20is%202461.%0Afield%20ref55%200%20is%20ref56.%0Afield%20ref55%201%20is%20ref57.%0Afield%20ref55%202%20is%20ref58.%0Afield%20ref55%203%20is%20ref59.%0Afield%20ref54%20%22property%22%20is%20%22s%22.%0Afield%20ref54%20%22amount%22%20is%202244.%0Afield%20ref53%20%22property%22%20is%20%22a%22.%0Afield%20ref53%20%22amount%22%20is%2079.%0Afield%20ref52%20%22property%22%20is%20%22m%22.%0Afield%20ref52%20%22amount%22%20is%20264.%0Afield%20ref51%20%22property%22%20is%20%22x%22.%0Afield%20ref51%20%22amount%22%20is%202036.%0Afield%20ref50%200%20is%20ref51.%0Afield%20ref50%201%20is%20ref52.%0Afield%20ref50%202%20is%20ref53.%0Afield%20ref50%203%20is%20ref54.%0Afield%20ref49%20%22property%22%20is%20%22s%22.%0Afield%20ref49%20%22amount%22%20is%20496.%0Afield%20ref48%20%22property%22%20is%20%22a%22.%0Afield%20ref48%20%22amount%22%20is%202067.%0Afield%20ref47%20%22property%22%20is%20%22m%22.%0Afield%20ref47%20%22amount%22%20is%2044.%0Afield%20ref46%20%22property%22%20is%20%22x%22.%0Afield%20ref46%20%22amount%22%20is%201679.%0Afield%20ref45%200%20is%20ref46.%0Afield%20ref45%201%20is%20ref47.%0Afield%20ref45%202%20is%20ref48.%0Afield%20ref45%203%20is%20ref49.%0Afield%20ref44%20%22property%22%20is%20%22s%22.%0Afield%20ref44%20%22amount%22%20is%202876.%0Afield%20ref43%20%22property%22%20is%20%22a%22.%0Afield%20ref43%20%22amount%22%20is%201222.%0Afield%20ref42%20%22property%22%20is%20%22m%22.%0Afield%20ref42%20%22amount%22%20is%202655.%0Afield%20ref41%20%22property%22%20is%20%22x%22.%0Afield%20ref41%20%22amount%22%20is%20787.%0Afield%20ref40%200%20is%20ref41.%0Afield%20ref40%201%20is%20ref42.%0Afield%20ref40%202%20is%20ref43.%0Afield%20ref40%203%20is%20ref44.%0Afield%20ref39%200%20is%20ref40.%0Afield%20ref39%201%20is%20ref45.%0Afield%20ref39%202%20is%20ref50.%0Afield%20ref39%203%20is%20ref55.%0Afield%20ref39%204%20is%20ref60.%0Afield%20ref38%20%22property%22%20is%20%22m%22.%0Afield%20ref38%20%22check%22%20is%20%22%3E%22.%0Afield%20ref38%20%22quantity%22%20is%20838.%0Afield%20ref38%20%22goto%22%20is%20%22A%22.%0Afield%20ref37%200%20is%20ref38.%0Afield%20ref36%20%22name%22%20is%20%22hdj%22.%0Afield%20ref36%20%22checks%22%20is%20ref37.%0Afield%20ref36%20%22length%22%20is%201.%0Afield%20ref36%20%22fallthrough%22%20is%20%22pv%22.%0Afield%20ref35%20%22property%22%20is%20%22a%22.%0Afield%20ref35%20%22check%22%20is%20%22%3E%22.%0Afield%20ref35%20%22quantity%22%20is%203333.%0Afield%20ref35%20%22goto%22%20is%20%22R%22.%0Afield%20ref34%200%20is%20ref35.%0Afield%20ref33%20%22name%22%20is%20%22gd%22.%0Afield%20ref33%20%22checks%22%20is%20ref34.%0Afield%20ref33%20%22length%22%20is%201.%0Afield%20ref33%20%22fallthrough%22%20is%20%22R%22.%0Afield%20ref32%20%22property%22%20is%20%22m%22.%0Afield%20ref32%20%22check%22%20is%20%22%3C%22.%0Afield%20ref32%20%22quantity%22%20is%201801.%0Afield%20ref32%20%22goto%22%20is%20%22hdj%22.%0Afield%20ref31%20%22property%22%20is%20%22s%22.%0Afield%20ref31%20%22check%22%20is%20%22%3E%22.%0Afield%20ref31%20%22quantity%22%20is%202770.%0Afield%20ref31%20%22goto%22%20is%20%22qs%22.%0Afield%20ref30%200%20is%20ref31.%0Afield%20ref30%201%20is%20ref32.%0Afield%20ref29%20%22name%22%20is%20%22qqz%22.%0Afield%20ref29%20%22checks%22%20is%20ref30.%0Afield%20ref29%20%22length%22%20is%202.%0Afield%20ref29%20%22fallthrough%22%20is%20%22R%22.%0Afield%20ref28%20%22property%22%20is%20%22s%22.%0Afield%20ref28%20%22check%22%20is%20%22%3C%22.%0Afield%20ref28%20%22quantity%22%20is%201351.%0Afield%20ref28%20%22goto%22%20is%20%22px%22.%0Afield%20ref27%200%20is%20ref28.%0Afield%20ref26%20%22name%22%20is%20%22in%22.%0Afield%20ref26%20%22checks%22%20is%20ref27.%0Afield%20ref26%20%22length%22%20is%201.%0Afield%20ref26%20%22fallthrough%22%20is%20%22qqz%22.%0Afield%20ref25%20%22property%22%20is%20%22x%22.%0Afield%20ref25%20%22check%22%20is%20%22%3E%22.%0Afield%20ref25%20%22quantity%22%20is%202662.%0Afield%20ref25%20%22goto%22%20is%20%22A%22.%0Afield%20ref24%200%20is%20ref25.%0Afield%20ref23%20%22name%22%20is%20%22crn%22.%0Afield%20ref23%20%22checks%22%20is%20ref24.%0Afield%20ref23%20%22length%22%20is%201.%0Afield%20ref23%20%22fallthrough%22%20is%20%22R%22.%0Afield%20ref22%20%22property%22%20is%20%22x%22.%0Afield%20ref22%20%22check%22%20is%20%22%3C%22.%0Afield%20ref22%20%22quantity%22%20is%201416.%0Afield%20ref22%20%22goto%22%20is%20%22A%22.%0Afield%20ref21%200%20is%20ref22.%0Afield%20ref20%20%22name%22%20is%20%22qkq%22.%0Afield%20ref20%20%22checks%22%20is%20ref21.%0Afield%20ref20%20%22length%22%20is%201.%0Afield%20ref20%20%22fallthrough%22%20is%20%22crn%22.%0Afield%20ref19%20%22property%22%20is%20%22s%22.%0Afield%20ref19%20%22check%22%20is%20%22%3E%22.%0Afield%20ref19%20%22quantity%22%20is%203448.%0Afield%20ref19%20%22goto%22%20is%20%22A%22.%0Afield%20ref18%200%20is%20ref19.%0Afield%20ref17%20%22name%22%20is%20%22qs%22.%0Afield%20ref17%20%22checks%22%20is%20ref18.%0Afield%20ref17%20%22length%22%20is%201.%0Afield%20ref17%20%22fallthrough%22%20is%20%22lnx%22.%0Afield%20ref16%20%22property%22%20is%20%22x%22.%0Afield%20ref16%20%22check%22%20is%20%22%3E%22.%0Afield%20ref16%20%22quantity%22%20is%202440.%0Afield%20ref16%20%22goto%22%20is%20%22R%22.%0Afield%20ref15%20%22property%22%20is%20%22s%22.%0Afield%20ref15%20%22check%22%20is%20%22%3C%22.%0Afield%20ref15%20%22quantity%22%20is%20537.%0Afield%20ref15%20%22goto%22%20is%20%22gd%22.%0Afield%20ref14%200%20is%20ref15.%0Afield%20ref14%201%20is%20ref16.%0Afield%20ref13%20%22name%22%20is%20%22rfg%22.%0Afield%20ref13%20%22checks%22%20is%20ref14.%0Afield%20ref13%20%22length%22%20is%202.%0Afield%20ref13%20%22fallthrough%22%20is%20%22A%22.%0Afield%20ref12%20%22property%22%20is%20%22m%22.%0Afield%20ref12%20%22check%22%20is%20%22%3E%22.%0Afield%20ref12%20%22quantity%22%20is%201548.%0Afield%20ref12%20%22goto%22%20is%20%22A%22.%0Afield%20ref11%200%20is%20ref12.%0Afield%20ref10%20%22name%22%20is%20%22lnx%22.%0Afield%20ref10%20%22checks%22%20is%20ref11.%0Afield%20ref10%20%22length%22%20is%201.%0Afield%20ref10%20%22fallthrough%22%20is%20%22A%22.%0Afield%20ref9%20%22property%22%20is%20%22a%22.%0Afield%20ref9%20%22check%22%20is%20%22%3E%22.%0Afield%20ref9%20%22quantity%22%20is%201716.%0Afield%20ref9%20%22goto%22%20is%20%22R%22.%0Afield%20ref8%200%20is%20ref9.%0Afield%20ref7%20%22name%22%20is%20%22pv%22.%0Afield%20ref7%20%22checks%22%20is%20ref8.%0Afield%20ref7%20%22length%22%20is%201.%0Afield%20ref7%20%22fallthrough%22%20is%20%22A%22.%0Afield%20ref6%20%22property%22%20is%20%22m%22.%0Afield%20ref6%20%22check%22%20is%20%22%3E%22.%0Afield%20ref6%20%22quantity%22%20is%202090.%0Afield%20ref6%20%22goto%22%20is%20%22A%22.%0Afield%20ref5%20%22property%22%20is%20%22a%22.%0Afield%20ref5%20%22check%22%20is%20%22%3C%22.%0Afield%20ref5%20%22quantity%22%20is%202006.%0Afield%20ref5%20%22goto%22%20is%20%22qkq%22.%0Afield%20ref4%200%20is%20ref5.%0Afield%20ref4%201%20is%20ref6.%0Afield%20ref3%20%22name%22%20is%20%22px%22.%0Afield%20ref3%20%22checks%22%20is%20ref4.%0Afield%20ref3%20%22length%22%20is%202.%0Afield%20ref3%20%22fallthrough%22%20is%20%22rfg%22.%0Afield%20ref2%200%20is%20ref3.%0Afield%20ref2%201%20is%20ref7.%0Afield%20ref2%202%20is%20ref10.%0Afield%20ref2%203%20is%20ref13.%0Afield%20ref2%204%20is%20ref17.%0Afield%20ref2%205%20is%20ref20.%0Afield%20ref2%206%20is%20ref23.%0Afield%20ref2%207%20is%20ref26.%0Afield%20ref2%208%20is%20ref29.%0Afield%20ref2%209%20is%20ref33.%0Afield%20ref2%2010%20is%20ref36.%0Afield%20ref1%20%22program%22%20is%20ref2.%0Afield%20ref1%20%22inputs%22%20is%20ref39.%0A) The answer is the sum of all N such that goal _ is N.