Nim

Part 1 was pretty straightforward. For part 2 I made an ItemRange type that’s just one integer range for each attribute. I also made a split function that returns two ItemRange objects, one for the values that match the specified rule, and the others for the unmatched values. When iterating through the workflows, I start a new recursion branch to process any matching values, and continue stepping through with the unmatched values until none remain or they’re accepted/rejected.

• Day 19, part 1
• Day 19, part 2

Python

6.528 line-seconds (ranks 8th hardest after days 17, 8, 12, 16, 14, 11 and 10).

Also on Github

import functools
import operator
import re

import portion as P  # noqa: N812

from .solver import Solver


def isize(i: P.Interval):
  return sum(i_part.upper - i_part.lower - int(i_part.left == P.OPEN) + int(i_part.right == P.CLOSED)
             for i_part in i)

class Day19(Solver):
  workflows: dict[str, list[str|tuple[str, str, int, str]]]
  parts: list[dict[str, int]]

  def __init__(self):
    super().__init__(19)

  def presolve(self, input: str):
    lines = input.splitlines()
    self.workflows = {}
    while lines:
      line = lines.pop(0)
      if not line:
        break
      name, program = line.split('{')
      instructions = program[:-1].split(',')
      self.workflows[name] = []
      for item in instructions:
        match_condition = re.fullmatch(r'(\w+)([<>])(\d+):(\w+)', item)
        if match_condition:
          category, op, threshold, goto = match_condition.groups()
          self.workflows[name].append((category, op, int(threshold), goto))
        else:
          self.workflows[name].append(item)
    self.parts = []
    while lines:
      items = lines.pop(0)[1:-1].split(',')
      part = {}
      for category, value in (i.split('=') for i in items):
        part[category] = int(value)
      self.parts.append(part)

  def solve_first_star(self):
    return sum(sum(part.values()) for part in self.parts if
               self._count_options('in', 0, {c: P.singleton(v) for c, v in part.items()}) > 0)

  def solve_second_star(self):
    return self._count_options('in', 0, {c: P.closed(1, 4000) for c in self.parts[0].keys()})

  def _count_options(self, workflow_name: str, workflow_index: int, ranges: dict[str, P.Interval]) -> int:
    if workflow_name == 'A':
      return functools.reduce(operator.mul, (isize(r) for r in ranges.values()), 1)
    if workflow_name == 'R':
      return 0
    if any(isize(r) == 0 for r in ranges.values()):
      return 0
    match self.workflows[workflow_name][workflow_index]:
      case (category, '>', threshold, goto):
        new_ranges_true = {c: r & P.open(threshold, P.inf) if c == category else r for c, r in ranges.items()}
        new_ranges_false = {c: r & P.openclosed(-P.inf, threshold) if c == category else r for c, r in ranges.items()}
        return (self._count_options(goto, 0, new_ranges_true) +
                self._count_options(workflow_name, workflow_index + 1, new_ranges_false))
      case (category, '<', threshold, goto):
        new_ranges_true = {c: r & P.open(-P.inf, threshold) if c == category else r for c, r in ranges.items()}
        new_ranges_false = {c: r & P.closedopen(threshold, P.inf) if c == category else r for c, r in ranges.items()}
        return (self._count_options(goto, 0, new_ranges_true) +
                self._count_options(workflow_name, workflow_index + 1, new_ranges_false))
      case next_workflow:
        return self._count_options(next_workflow, 0, ranges)

Scala3

case class Part(x: Range, m: Range, a: Range, s: Range):
    def rating: Int = x.start + m.start + a.start + s.start
    def combinations: Long = x.size.toLong * m.size.toLong * a.size.toLong * s.size.toLong

type ActionFunc = Part => (Option[(Part, String)], Option[Part])

case class Workflow(ops: List[ActionFunc]):
    def process(p: Part): List[(Part, String)] =
        @tailrec def go(p: Part, ops: List[ActionFunc], acc: List[(Part, String)]): List[(Part, String)] =
            ops match
                case o :: t => o(p) match
                    case (Some(branch), Some(fwd)) => go(fwd, t, branch::acc)
                    case (None, Some(fwd)) => go(fwd, t, acc)
                    case (Some(branch), None) => branch::acc
                    case (None, None) => acc
                case _ => acc
        go(p, ops, List())

def run(parts: List[Part], workflows: Map[String, Workflow]) =
    @tailrec def go(parts: List[(Part, String)], accepted: List[Part]): List[Part] =
        parts match
            case (p, wf) :: t => 
                val res = workflows(wf).process(p)
                val (acc, rest) = res.partition((_, w) => w == "A")
                val (rej, todo) = rest.partition((_, w) => w == "R")
                go(todo ++ t, acc.map(_._1) ++ accepted)
            case _ => accepted
    go(parts.map(_ -> "in"), List())

def parseWorkflows(a: List[String]): Map[String, Workflow] =
    def generateActionGt(n: Int, s: String, accessor: Part => Range, setter: (Part, Range) => Part): ActionFunc = p => 
        val r = accessor(p)
        (Option.when(r.end > n + 1)((setter(p, math.max(r.start, n + 1) until r.end), s)), Option.unless(r.start > n)(setter(p, r.start until math.min(r.end, n + 1))))
    def generateAction(n: Int, s: String, accessor: Part => Range, setter: (Part, Range) => Part): ActionFunc = p => 
        val r = accessor(p)
        (Option.when(r.start < n)((setter(p, r.start until math.min(r.end, n)), s)), Option.unless(r.end <= n)(setter(p, math.max(r.start, n) until r.end)))
    
    val accessors = Map("x"->((p:Part) => p.x), "m"->((p:Part) => p.m), "a"->((p:Part) => p.a), "s"->((p:Part) => p.s))
    val setters = Map("x"->((p:Part, v:Range) => p.copy(x=v)), "m"->((p:Part, v:Range) => p.copy(m=v)), "a"->((p:Part, v:Range) => p.copy(a=v)), "s"->((p:Part, v:Range) => p.copy(s=v)))

    def parseAction(a: String): ActionFunc =
        a match
            case s"$v<$n:$s" => generateAction(n.toInt, s, accessors(v), setters(v))
            case s"$v>$n:$s" => generateActionGt(n.toInt, s, accessors(v), setters(v))
            case s => p => (Some((p, s)), None)

    a.map(_ match{ case s"$name{$items}" => name -> Workflow(items.split(",").map(parseAction).toList) }).toMap

def parsePart(a: String): Option[Part] =
    a match
        case s"{x=$x,m=$m,a=$a,s=$s}" => Some(Part(x.toInt until 1+x.toInt, m.toInt until 1+m.toInt, a.toInt until 1+a.toInt, s.toInt until 1+s.toInt))
        case _ => None

def task1(a: List[String]): Long = 
    val in = a.chunk(_ == "")
    val wfs = parseWorkflows(in(0))
    val parts = in(1).flatMap(parsePart)
    run(parts, wfs).map(_.rating).sum

def task2(a: List[String]): Long =
    val wfs = parseWorkflows(a.chunk(_ == "").head)
    val parts = List(Part(1 until 4001, 1 until 4001, 1 until 4001, 1 until 4001))
    run(parts, wfs).map(_.combinations).sum

Nim

I optimized Part1 by directly referencing workflows between each rule (instead of doing a table lookup between them), in expectation of part 2 needing increased performance. But that turned out to not be needed 😋

I had to dig through my dusty statistics knowledge for part 2, and decided to try out Mermaid.js to create a little graph of the sample input to help visualize the solution.

After that it was pretty straightforward.

Day 19, part 1+2