Skip to main content

Day 19: Aplenty

by @mbovel

Puzzle description

Data structures

We define the following data structures for today's puzzle:

enum Channel:
case X, M, A, S

enum Operator:
case LessThan, GreaterThan

enum Result:
case Reject, Accept

enum Instruction:
case IfThenElse(
channel: Channel,
operator: Operator,
value: Int,
thenBranch: GoTo | Return,
elseBranch: Instruction
case Return(result: Result)
case GoTo(target: String)

import Instruction.*

type Workflow = Map[String, Instruction]

case class Part(x: Int, m: Int, a: Int, s: Int)


Then, we write the associated parsing methods, using String's split method and regular expression patterns

object Channel:
def parse(input: String): Channel =
input match
case "x" => Channel.X
case "m" => Channel.M
case "a" => Channel.A
case "s" => Channel.S
case _ => throw Exception(s"Invalid channel: $input")

object Operator:
def parse(input: String): Operator =
input match
case "<" => Operator.LessThan
case ">" => Operator.GreaterThan
case _ => throw Exception(s"Invalid operator: $input")

object Result:
def parse(input: String): Result =
input match
case "R" => Result.Reject
case "A" => Result.Accept
case _ => throw Exception(s"Invalid result: $input")

object Instruction:
private val IfThenElseRegex = """([xmas])([<>])(\d+):(\w+),(.*)""".r
private val ReturnRegex = """([RA])""".r
private val GoToRegex = """(\w+)""".r
def parse(input: String): Instruction =
input match
case IfThenElseRegex(channel, operator, value, thenBranch, elseBranch) =>
Instruction.parse(thenBranch) match
case thenBranch: (GoTo | Return) =>
case _ => throw Exception(s"Invalid then branch: $thenBranch")
case ReturnRegex(result) => Return(Result.parse(result))
case GoToRegex(target) => GoTo(target)
case _ => throw Exception(s"Invalid instruction: $input")

object Workflow:
def parse(input: String): Workflow =

private val BlockRegex = """(\w+)\{(.*?)\}""".r
private def parseBlock(input: String): (String, Instruction) =
input match
case BlockRegex(label, body) =>
(label, Instruction.parse(body))

object Part:
val PartRegex = """\{x=(\d+),m=(\d+),a=(\d+),s=(\d+)\}""".r
def parse(input: String): Part =
input match
case PartRegex(x, m, a, s) => Part(x.toInt, m.toInt, a.toInt, s.toInt)
case _ => throw Exception(s"Invalid part: $input")

Part 1 – Evaluation

These helpers allow us to implement the core logic succinctly:

def part1(input: String): Int =
val Array(workflowLines, partLines) = input.split("\n\n")
val workflow = Workflow.parse(workflowLines.trim())
val parts = partLines.trim().split("\n").map(Part.parse)

def eval(part: Part, instruction: Instruction): Result =
instruction match
case IfThenElse(channel, operator, value, thenBranch, elseBranch) =>
val channelValue = channel match
case Channel.X => part.x
case Channel.M => part.m
case Channel.A => part.a
case Channel.S => part.s
val result = operator match
case Operator.LessThan => channelValue < value
case Operator.GreaterThan => channelValue > value
if result then eval(part, thenBranch) else eval(part, elseBranch)
case Return(result) => result
case GoTo(target) => eval(part, workflow(target))

.collect: part =>
eval(part, workflow("in")) match
case Result.Reject => 0
case Result.Accept => part.x + part.m + part.a + part.s

Part 2 – Symbolic execution

To solve the second part efficiently, we use symbolic execution to count the number of executions of the workflow that lead to an Accept result.

We represent symbolic values with the AbstractPart structure, where the value associated to each channel is not a number, but a range of possible values:

case class Range(from: Long, until: Long):
assert(from < until)
def count() = until - from

object Range:
def safe(from: Long, until: Long): Option[Range] =
if from < until then Some(Range(from, until)) else None

case class AbstractPart(x: Range, m: Range, a: Range, s: Range):
def count() = x.count() * m.count() * a.count() * s.count()

def withChannel(channel: Channel, newRange: Range) =
channel match
case Channel.X => copy(x = newRange)
case Channel.M => copy(m = newRange)
case Channel.A => copy(a = newRange)
case Channel.S => copy(s = newRange)

def getChannel(channel: Channel) =
channel match
case Channel.X => x
case Channel.M => m
case Channel.A => a
case Channel.S => s

We will start the evaluation with abstract parts that contain all possible values for each channel: four ranges from 1 until 4001.

When we evaluate an IfThenElse instruction, we split the argument AbstractPart into two parts, one that contains only the values that satisfy the condition, and one that contains only the values that do not satisfy the condition.

This is achieved with the split method of AbstractPart:

  def split(
channel: Channel,
value: Int
): (Option[AbstractPart], Option[AbstractPart]) =
val currentRange = getChannel(channel)
(, value).map(withChannel(channel, _)),, currentRange.until).map(withChannel(channel, _))

Using these helpers, we can implement the abstract evaluator as follows:

def part2(input: String): Long = combinations(input, 4001)

extension [T](part: (T, T)) private inline def swap: (T, T) = (part._2, part._1)

def combinations(input: String, until: Long): Long =
val Array(workflowLines, _) = input.split("\n\n")
val workflow = Workflow.parse(workflowLines.trim())

def count(part: AbstractPart, instruction: Instruction): Long =
instruction match
case IfThenElse(channel, operator, value, thenBranch, elseBranch) =>
val (trueValues, falseValues) =
operator match
case Operator.LessThan => part.split(channel, value)
case Operator.GreaterThan => part.split(channel, value + 1).swap, thenBranch)).getOrElse(0L)
+, elseBranch)).getOrElse(0L)
case Return(Result.Accept) => part.count()
case Return(Result.Reject) => 0L
case GoTo(target) => count(part, workflow(target))

Range(1, until),
Range(1, until),
Range(1, until),
Range(1, until)

Solutions from the community

Share your solution to the Scala community by editing this page. You can even write the whole article! See here for the expected format