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}"`
def start_link(spec) do
{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)
{:noreply, rules}
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
def start_link() do
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
{:reply, state, state}
end
end
And the blackhole
defmodule Rejector do
use GenServer
def start_link() do
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
{:noreply, state}
end
end
Start all the servers:
Acceptor.start_link()
Rejector.start_link()
for spec <- specs do
Pipe.start_link(spec)
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_leading("{")
|> 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:
