Skip Navigation

⚙️ - 2023 DAY 19 SOLUTIONS -⚙️

Day 19: Aplenty

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

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

  • 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