Python

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

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)

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

Haskell

Echoes of Day 5… Not particularly difficult, but lots of typing. I’d like to golf this one a bit more.

import Control.Monad
import Data.Either
import Data.Maybe
import Text.Parsec

type Rule = (Maybe (Char, Ordering, Int), String)

type Flow = (String, [Rule])

type Part = [(Char, Int)]

readInput :: String -> ([Flow], [Part])
readInput s =
  let (flows, _ : parts) = break (== "") $ lines s
   in (map readFlow flows, map readPart parts)
  where
    readFlow = fromRight (error "bad flow") . parse flow ""
    readPart = fromRight (error "bad part") . parse part ""
    flow = do
      name <- many1 letter
      rules <- between (char '{') (char '}') (rule `sepBy` char ',')
      return (name, rules)
    rule = do
      c <- optionMaybe $ try condition
      n <- many1 letter
      return (c, n)
    condition = do
      p <- anyChar
      o <- choice [LT <$ char '<', GT <$ char '>']
      n <- read <$> many1 digit
      char ':' >> return (p, o, n)
    part = between (char '{') (char '}') (param `sepBy` char ',')
    param = do
      p <- anyChar
      n <- char '=' >> (read <$> many1 digit)
      return (p, n)

runPart :: [Flow] -> Part -> Bool
runPart flows part = runFlow "in"
  where
    runFlow "A" = True
    runFlow "R" = False
    runFlow f = runRules $ fromJust $ lookup f flows
    runRules ((Nothing, next) : _) = runFlow next
    runRules ((Just (p, o, n), next) : rest)
      | compare (fromJust $ lookup p part) n == o = runFlow next
      | otherwise = runRules rest

mapRanges :: [Flow] -> [(Char, (Int, Int))] -> [[(Char, (Int, Int))]]
mapRanges flows = runFlow "in"
  where
    runFlow "A" = return
    runFlow "R" = const mzero
    runFlow f = runRules (fromJust $ lookup f flows)
    runRules ((Nothing, next) : _) = runFlow next
    runRules ((Just test, next) : rest) =
      (\(a, b) -> join [a >>= runFlow next, b >>= runRules rest]) . splitRange test
    splitRange (p, op, n) range =
      let (v1, v2) = fromJust $ lookup p range
          others = filter ((/= p) . fst) range
       in case op of
            LT
              | v1 >= n -> ([], [range])
              | v2 < n -> ([range], [])
              | otherwise -> ([(p, (v1, n - 1)) : others], [(p, (n, v2)) : others])
            GT
              | v2 <= n -> ([], [range])
              | v1 > n -> ([range], [])
              | otherwise -> ([(p, (n + 1, v2)) : others], [(p, (v1, n)) : others])

main = do
  (flows, parts) <- readInput <$> readFile "input19"
  print . sum . concatMap (map snd) $ filter (runPart flows) parts
  print $
    sum . map (product . map (\(_, (v1, v2)) -> v2 - v1 + 1)) $
      mapRanges flows [(p, (1, 4000)) | p <- "xmas"]

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

C

Bit of typing and testing again but part 2 was fun and not hard, although I did make a few logic mistakes.

Didn’t optimize anything in particular but as in day 8 (iirc) I avoid dealing with strings for references to things, so I keep a string table and only use indices.

Abridged excerpt of data structures and eval():

struct expr { int type, var, imm, next; };
struct partrange { int min[4], max[4]; };

static struct expr flows[600][5];
static int accept_id, reject_id, in_id;

static int64_t eval(int id, struct partrange p)
{
	struct partrange q;
	struct expr *e;
	int64_t acc=0;
	int i;

	if (id == reject_id ||
	    p.min[0] > p.max[0] || p.min[1] > p.max[1] ||
	    p.min[2] > p.max[2] || p.min[3] > p.max[3])
	    	return 0;

	if (id == accept_id)
		return (int64_t)
		    (p.max[0] -p.min[0] +1) * (p.max[1] -p.min[1] +1) *
		    (p.max[2] -p.min[2] +1) * (p.max[3] -p.min[3] +1);

	for (i=0; i < (int)LEN(*flows); i++)
		switch ((e = &flows[id][i])->type) {
		case EXPR_LT:
			q = p;
			q.max[e->var] = MIN(q.max[e->var], e->imm-1);
			p.min[e->var] = MAX(p.min[e->var], e->imm);
			acc += eval(e->next, q);
			break;
		case EXPR_GT:
			q = p;
			q.min[e->var] = MAX(q.min[e->var], e->imm+1);
			p.max[e->var] = MIN(p.max[e->var], e->imm);
			acc += eval(e->next, q);
			break;
		case EXPR_CALL:
			acc += eval(e->next, p);
			return acc;
		}
	
	assert(!"bad flow");
}

https://github.com/sjmulder/aoc/blob/master/2023/c/day19.c

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