# Advent of Code 2023 - Day 19

A rather verbose solution but simple enough I guess.

1 Like

My approach today:

Part 1 is basically just a loop navigating over the map.

Part 2 is building a â€śbinary treeâ€ť: if a certain condition is true, the next execution is a branch â€śto the leftâ€ť with the target workflow; if itâ€™s false, continue with the next step of the current workflow. I maintain a map of ranges (`%{x: {1, 4000}, ...}`) throughout and adjust the range based on each condition. If the execution is to the â€śleftâ€ť of the tree, then I just apply the condition, otherwise I apply the inverse of the condition. When A is reached, I multiply the ranges.

For part2 I used MapSet.intersection/2, which didnâ€™t perform very well, but the whole coding experience was very smooth, no debugging, and I got the right results in one go. The idea is also very easy to understand.

1 Like

Here is my solution:

I just canâ€™t understand what Part 2 is talking about

Hereâ€™s my solution, it went pretty well !

``````import Input

defmodule Day19 do
def part1(input) do
{map, parts} = parse_input(input)

parts
|> Enum.map(&walk(map, "in", &1))
|> Enum.zip(parts)
|> Enum.map(&score/1)
|> Enum.sum()
end

defp walk(map, wf_name, part) do
conds = Map.fetch!(map, wf_name)

conds
|> Enum.find(fn
{field, ">", thresh, _} ->
part
|> Map.fetch!(field)
|> Kernel.>(thresh)

{field, "<", thresh, _} ->
part
|> Map.fetch!(field)
|> Kernel.<(thresh)

_ ->
true
end)
|> then(fn
{_, _, _, res} -> res
default -> default
end)
|> case do
"A" -> "A"
"R" -> "R"
new_wf_name -> walk(map, new_wf_name, part)
end
end

defp score({"R", _}), do: 0
defp score({"A", %{"x" => x, "m" => m, "a" => a, "s" => s}}), do: x + m + a + s

def part2(input) do
{map, _} = parse_input(input)

combs(map, Map.fetch!(map, "in"), %{
"x" => {1, 4001},
"m" => {1, 4001},
"a" => {1, 4001},
"s" => {1, 4001}
})
end

defp combs(map, [{field, op, thresh, res} | tail], threshs) do
{new_thresh, rev_thresh} = split_treshs(threshs, field, op, thresh)
combs(map, res, new_thresh) + combs(map, tail, rev_thresh)
end

defp combs(map, [key], threshs), do: combs(map, key, threshs)

defp combs(map, "A", threshs) do
threshs
|> Enum.map(fn {_, {min, max}} -> max - min end)
|> Enum.map(&max(&1, 0))
|> Enum.reduce(1, &(&1 * &2))
end

defp combs(map, "R", threshs), do: 0
defp combs(map, key, threshs), do: combs(map, Map.fetch!(map, key), threshs)

defp split_treshs(threshs, field, "<", thresh) do
new_threshs =
Map.update!(threshs, field, fn {min, max} ->
{min, min(max, thresh)}
end)

rev_threshs =
Map.update!(threshs, field, fn {min, max} ->
{max(min, thresh), max}
end)

{new_threshs, rev_threshs}
end

defp split_treshs(threshs, field, ">", thresh) do
new_threshs =
Map.update!(threshs, field, fn {min, max} ->
{max(min, thresh + 1), max}
end)

rev_threshs =
Map.update!(threshs, field, fn {min, max} ->
{min, min(max, thresh + 1)}
end)

{new_threshs, rev_threshs}
end

defp parse_input([workflows, parts]) do
{
workflows |> Enum.map(&parse_workflow/1) |> Map.new(),
Enum.map(parts, &parse_part/1)
}
end

defp parse_workflow(input) do
input
|> Utils.splitrim(~r/[{},]/)
|> Enum.map(&Utils.splitrim(&1, ":"))
|> Enum.map(fn
[solo] ->
solo

[<<field::bytes-size(1), op::bytes-size(1), thresh::binary>>, res] ->
{field, op, String.to_integer(thresh), res}
end)
|> then(fn [name | conds] -> {name, conds} end)
end

defp parse_part(input) do
input
|> Utils.splitrim(~r/[{},]/)
|> Enum.map(&Utils.splitrim(&1, "="))
|> Enum.map(fn [field, value] -> {field, String.to_integer(value)} end)
|> Map.new()
end

def run() do
part2(~i[19]c)
end

def bench() do
Benchmark.mesure_milliseconds(&run/0)
end
end
``````

`Input` is just a collection of sigils (such as `~i`) to manipulate inputs (like returning parts separated by an empty line).

2 Likes

Part 2 wants you to count all possible combinations of `x, m, a, s` (between 1 and 4000) that would be accepted by the workflows.

So basically this:

``````    for x <- 1..4000, m <- 1..4000, s <- 1..4000, a <- 1..4000, reduce: 0 do
count ->
if accepted_part?(%{x: x, m: m, s: s, a: a}, worfklows) do
count + 1
else
count
end
end
``````
2 Likes

Thank you for your extremely clear explanation

Finally, I did it!

I just feel today is the GenServer day, so I started a bunch of `GenServer` processes to handle the situation.

All the variable named `xmas` in the following code binds to a map that looks like

``````%{
"x" => 123..321,
"m" => 132..213,
"a" => 321..132,
"s" => 312..213
}
``````

First, hereâ€™s the GenServer module that models one pipe in the workflow.

``````defmodule Pipe do
use GenServer

# `spec` is a string like `"foo{x>123:bar,R}"`
{name, rules} = parse_spec(spec)
GenServer.start_link(__MODULE__, rules, name: name)
end

@impl true
def init(rules) do
{:ok, rules}
end

@impl true
def handle_cast({:handle, xmas}, rules) do
rules
|> Enum.reduce(xmas, fn rule, xmas ->
rule.(xmas)
end)

end

defp parse_spec(spec) do
[name, rules] =
~r/^(\w+)\{(.*)\}\$/
|> Regex.run(spec, capture: :all_but_first)

name = String.to_atom(name)

rules =
rules
|> String.split(",")
|> Enum.map(&parse_rule/1)

{name, rules}
end

defp parse_rule(rule) do
case Regex.split(~r/\W/, rule, trim: true, include_captures: true) do
[next] ->
next = String.to_atom(next)
fn xmas ->
GenServer.cast(next, {:handle, xmas})
nil
end

[key, comp, thres, ":", next] ->
thres = String.to_integer(thres)
next = String.to_atom(next)
fn xmas ->
range = xmas[key]
{met, unmet} = split(comp, thres, range)
GenServer.cast(next, {:handle, %{xmas | key => met}})
%{xmas | key => unmet}
end
end
end

defp split("<", thres, a..b), do: {a..(thres - 1), thres..b}
defp split(">", thres, a..b), do: {(thres + 1)..b, a..thres}
end
``````

Then thereâ€™s a GenServer for accumulating the results:

``````defmodule Acceptor do
use GenServer

GenServer.start_link(__MODULE__, [], name: :A)
end

@impl true
def init(state) do
{:ok, state}
end

@impl true
def handle_cast({:handle, xmas}, sum) do
xmas
|> Map.values()
|> Stream.map(fn a..b ->
b - a + 1
end)
|> Stream.map(&max(&1, 0))
|> Enum.product()
|> then(&{:noreply, &1 + sum})
end

@impl true
def handle_call(:get, _from, state) do
end
end
``````

And the blackhole

``````defmodule Rejector do
use GenServer

GenServer.start_link(__MODULE__, nil, name: :R)
end

@impl true
def init(state) do
{:ok, state}
end

@impl true
def handle_cast({:handle, _xmas}, state) do
end
end
``````

Start all the servers:

``````Acceptor.start_link()

for spec <- specs do
end
``````

And finally, do the job

``````GenServer.cast(:in, {:handle, %{
"x" => 1..4000,
"m" => 1..4000,
"a" => 1..4000,
"s" => 1..4000
}})

# Wait a sec

GenServer.call(:A, :get)
``````
1 Like

Got to use `Agent` today, pretty fun day honestly:

Part 1 was relatively straightforward, part 2 was a little more challenging in the data storing front, but the actual calculation was quite straightforward

2 Likes

For Part 2 I first recursively walked the tree from `"in"` and built up a list of branches that lead to `"A"`. Then I flattened the conditions in each branch into a ranges by category. Lastly I found the number of permutations of each branch using `Enum.product` and summed all of the permutations for each branch. I probably could have combined the first two steps, but I was thinking about the problem as â€śfind all the acceptance branches, then find the number of permutations in each branchâ€ť.

Part 1
``````defmodule Part1 do
def parse(input) do
[workflows, ratings] = String.split(input, "\n\n")

workflows =
for line <- String.split(workflows, "\n", trim: true), into: %{} do
[name, rules] = String.split(line, ["{", "}"], trim: true)

rules =
for rule <- String.split(rules, ",") do
case Regex.run(~r/(?:(\w)([<>])(\d+):)?(\w+)/, rule, capture: :all_but_first) do
["", "", "", output] ->
output

[category, op, threshold, output] ->
threshold = String.to_integer(threshold)
{category, op, threshold, output}
end
end

{name, rules}
end

ratings =
for line <- String.split(ratings, "\n", trim: true) do
for field <- String.split(line, ["{", "}", ","], trim: true), into: %{} do
[key, value] = String.split(field, "=")
{key, String.to_integer(value)}
end
end

{workflows, ratings}
end

def eval(rating, workflows), do: eval(rating, workflows, "in")
def eval(_, _, "R"), do: false
def eval(_, _, "A"), do: true
def eval(rating, workflows, <<name::binary>>), do: eval(rating, workflows, workflows[name])
def eval(rating, workflows, [<<name::binary>>]), do: eval(rating, workflows, name)

def eval(rating, workflows, [{category, op, threshold, output} | rules]) do
fun = if op == "<", do: &Kernel.</2, else: &Kernel.>/2
next = if fun.(rating[category], threshold), do: output, else: rules
eval(rating, workflows, next)
end
end

{workflows, ratings} = Part1.parse(input)

ratings
|> Enum.filter(&Part1.eval(&1, workflows))
|> Enum.flat_map(&Map.values/1)
|> Enum.sum()
``````
Part 2
``````defmodule Part2 do
def acceptance(workflows), do: acceptance("in", workflows) |> Enum.map(&flatten/1)

def acceptance("R", _), do: false
def acceptance("A", _), do: true
def acceptance(<<name::binary>>, workflows), do: acceptance(workflows[name], workflows)
def acceptance([<<name::binary>>], workflows), do: acceptance(name, workflows)

def acceptance([{category, op, threshold, output} | rest], workflows) do
left =
output
|> acceptance(workflows)
|> prepend({category, op, threshold})

right_op = if op === "<", do: ">=", else: "<="

right =
rest
|> acceptance(workflows)
|> prepend({category, right_op, threshold})

left ++ right
end

def prepend(false, _), do: []
def prepend(true, rule), do: [[rule]]
def prepend(branches, rule), do: Enum.map(branches, &[rule | &1])

@input "xmas"
|> String.graphemes()
|> Enum.map(&{&1, 1..4000})
|> Map.new()

def flatten(branch), do: flatten(branch, @input)
def flatten([], acc), do: acc

def flatten([{category, op, threshold} | branch], acc) do
lo..hi = acc[category]

range =
case op do
">" -> max(threshold + 1, lo)..hi
">=" -> max(threshold, lo)..hi
"<" -> lo..min(threshold - 1, hi)
"<=" -> lo..min(threshold, hi)
end

acc = %{acc | category => range}
flatten(branch, acc)
end
end

Part2.acceptance(workflows)
|> Enum.map(fn rating ->
rating
|> Map.values()
|> Enum.map(&Enum.count/1)
|> Enum.product()
end)
|> Enum.sum()
``````
2 Likes

A crude parser and two simple interpreters.
For part 2 used xmas map holding ranges,
and some simple recursion.

``````import AOC

aoc 2023, 19 do
def p1(input) do
[code, data] = input |> String.split("\n\n")
code = parse_code(code)
data
|> String.split("\n", trim: true)
|> Enum.map(&parse_data/1)
|> Enum.map(&process(code, :in, &1))
|> Enum.sum()
end

def process(_, :A, xmas), do: xmas |> Map.values |> Enum.sum
def process(_, :R, _), do: 0
def process(code, label, xmas), do: evaluate(code, code[label], xmas)

def evaluate(code, [label], xmas), do: process(code, label, xmas)
def evaluate(code, [{pred, label} | rest], xmas), do: if(evaluate_pred(pred, xmas), do: process(code, label, xmas), else: evaluate(code, rest, xmas))

def evaluate_pred({var, "<", n}, xmas), do: xmas[var] < n
def evaluate_pred({var, ">", n}, xmas), do: xmas[var] > n

def parse_data(data) do
data
|> String.trim_trailing("}")
|> String.split(",", trim: true)
|> Enum.map(fn pair -> pair |> String.split("=", trim: true) |> then(fn [var, num] -> {String.to_atom(var), String.to_integer(num)} end) end)
|> Map.new
end

def do_snd({fst, snd}, f), do: {fst, f.(snd)}

def parse_code(code) do
code
|> String.split("\n", trim: true)
|> Enum.map(
fn line ->
[name, rules, _] = String.split(line, ["{", "}"])
{String.to_atom(name),
String.split(rules, ",")
|> Enum.map(
fn rule ->
case String.split(rule, ":") do
[pred, label] -> {compile_op(pred, if(String.contains?(pred, "<"), do: "<", else: ">")), String.to_atom(label)}
[label] -> String.to_atom(label)
end
end
)}
end
)
|> Map.new
end

def ranges_size(ranges) do
ranges
|> Map.values()
|> Enum.map(&Enum.count/1)
|> Enum.product()
end

def compile_op(pred, op) do
[var, num] = String.split(pred, op)
{String.to_atom(var), op, String.to_integer(num)}
end

def split_ranges(ranges, true), do: ranges
def split_ranges(ranges, {var, "<", num}) do
cond do
num in ranges[var] ->
{lo, hi} = split_range(ranges[var], num)
[Map.put(ranges, var, lo), Map.put(ranges, var, hi)]
ranges[var].last < num -> [ranges, empty_ranges()]
true -> [empty_ranges(), ranges]
end
end
def split_ranges(ranges, {var, ">", num}) do
cond do
num in ranges[var] ->
{lo, hi} = split_range(ranges[var], num+1)
[Map.put(ranges, var, hi), Map.put(ranges, var, lo)]
ranges[var].first > num -> [ranges, empty_ranges()]
true -> [empty_ranges(), ranges]
end
end

def empty_ranges(), do: %{x: [], m: [], a: [], s: []}

def split_range(lo..hi, n), do: {lo..(n-1), n..hi}

def process2(_, :A, ranges), do: ranges_size(ranges)
def process2(_, :R, _), do: 0
def process2(code, label, ranges), do: evaluate2(code, code[label], ranges)

def evaluate2(code, [label], ranges), do: process2(code, label, ranges)
def evaluate2(code, [{pred, label} | rest], ranges) do
[true_ranges, false_ranges] = split_ranges(ranges, pred)
process2(code, label, true_ranges) + evaluate2(code, rest, false_ranges)
end

def p2(input) do
input
|> String.split("\n\n")
|> hd()
|> parse_code()
|> process2(:in, %{x: 1..4000, m: 1..4000, a: 1..4000, s: 1..4000})
end
end
``````
1 Like

Part 2 felt a lot like Day 5 Part 2, a la using ranges to optimize. I donâ€™t know if I would have been able to solve this one as easily had I not done that one. My code is nothing different than what has been covered here, other than I did it all in Livebook and with only anonymous functions because I was lazy. Canâ€™t wait to read these solutions using Agents and GenServers. I havenâ€™t touched any of that since I started learning Elixir in Nov. (other than following some Phoenix tut).

Kept optimizing part 2 until it turned out pretty short: