<!-- livebook:{"persist_outputs":true} -->
# Day 20 - Advent of Code 2023
```elixir
Mix.install([
{:kino, "~> 0.12.0"},
{:benchee, "~> 1.2"},
{:math, "~> 0.7.0"}
])
```
## Links
* [Advent of Code (AoC)](https://adventofcode.com/2023/day/20)
* [AoC Puzzle Input](https://adventofcode.com/2023/day/20/input)
* [tylerj GitHub - Livebook](https://github.com/tylerj/aoc/blob/main/lib/advent_of_code/2023/day-20.livemd)
## Input
```elixir
input = Kino.Input.textarea("Please paste your input file:")
```
<!-- livebook:{"reevaluate_automatically":true} -->
```elixir
input = input |> Kino.Input.read()
```
<!-- livebook:{"output":true} -->
```
"%gv -> lq, pm\n%rv -> jd, nh\n%nh -> rs, jd\n&vt -> tj\n%zv -> pm, gv\n%gh -> jd, vd\n%hh -> bf, qm\n%kx -> nf\n%st -> pm, zc\n%bh -> qm, pv\n&sk -> tj\n%hl -> nf, pn\n%mt -> st, pm\n&jd -> ts, gh, vd, dc, xc\n%zm -> hm\n%pv -> vv\n%zf -> nf, cz\n&xc -> tj\n%bf -> qm\n%ts -> sg\n%ht -> ch, nf\n%pb -> rv, jd\n%nx -> fc\n%mb -> mt\n%mh -> jd, pb\n%lc -> bh\n%xg -> mb, pm\n%vd -> dc\nbroadcaster -> gh, dl, xg, fb\n%sg -> mh, jd\n%qq -> ts, jd\n%dl -> nf, sv\n%vv -> sm, qm\n%zc -> tb\n%sr -> zv, pm\n%dc -> gb\n%cz -> nf, zm\n%rs -> jd\n%hm -> nf, hl\n%gd -> sr\n&qm -> lc, pv, nx, fb, kk\n&tj -> rx\n%gb -> qq, jd\n%xf -> zf\n%tb -> lg\n%sm -> qm, hh\n%fb -> dr, qm\n%lq -> pm\n&nf -> zm, dl, ch, xf, vt\n&pm -> sk, zc, tb, gd, mb, xg\n%pn -> nf, kx\n%fc -> xb, qm\n%ch -> xf\n&kk -> tj\n%lg -> pm, gd\n%sv -> nf, ht\n%xb -> qm, lc\n%dr -> nx, qm"
```
## Solution
```elixir
defmodule Day20 do
defdelegate parse(input), to: __MODULE__.Input
def part1(input) do
input
|> parse()
|> press_button(1000)
|> then(fn %{high: high, low: low} -> high * low end)
end
def part2(input) do
state = parse(input)
high_cycles = for k <- get_sources(state, "rx"), into: %{}, do: {k, nil}
state
|> Map.merge(%{high_cycles: high_cycles, button_count: 0})
|> find_high_cycle_counts()
|> Map.values()
|> Enum.reduce(1, &Math.lcm/2)
end
defp get_sources(state, dest_key) do
Enum.find_value(state, fn
{_, {:conj, dests, sources_memory}} ->
if dest_key in dests, do: Map.keys(sources_memory)
_ ->
nil
end)
end
defp find_high_cycle_counts(state) do
if Enum.all?(state.high_cycles, fn {_, v} -> v end) do
state.high_cycles
else
state
|> press_button(1)
|> Map.update!(:button_count, &(&1 + 1))
|> find_high_cycle_counts()
end
end
defp press_button(state, count \\ 0, max_count)
defp press_button(state, count, max_count) when count < max_count do
[{:low, "button", "broadcaster"}]
|> send_pulses(state)
|> press_button(count + 1, max_count)
end
defp press_button(state, _, _), do: state
defp send_pulses([], state), do: state
defp send_pulses([h | tail], state) do
{new_pulses, new_state} = send_pulse(h, state)
send_pulses(tail ++ new_pulses, new_state)
end
defp send_pulse({pulse, source_module, module}, state) do
new_state = Map.update(state, pulse, 1, &(&1 + 1))
do_send_pulse(pulse, source_module, module, state[module], new_state)
end
# 'output' for example testing
defp do_send_pulse(_pulse, _source, _module, nil, state) do
{[], state}
end
defp do_send_pulse(pulse, _source, module, {:broadcast, dests}, state) do
{
Enum.map(dests, &{pulse, module, &1}),
state
}
end
defp do_send_pulse(:high, _source, _module, {:flip, _, _}, state) do
{[], state}
end
defp do_send_pulse(:low, _source, module, {:flip, dests, :off}, state) do
new_state = Map.put(state, module, {:flip, dests, :on})
{
Enum.map(dests, &{:high, module, &1}),
new_state
}
end
defp do_send_pulse(:low, _source, module, {:flip, dests, :on}, state) do
new_state = Map.put(state, module, {:flip, dests, :off})
{
Enum.map(dests, &{:low, module, &1}),
new_state
}
end
defp do_send_pulse(pulse, source, module, {:conj, dests, memory}, state) do
state =
case state do
%{high_cycles: %{^source => nil}} when pulse == :high ->
Map.update!(state, :high_cycles, fn cycles ->
Map.put(cycles, source, state.button_count + 1)
end)
state ->
state
end
new_memory = Map.put(memory, source, pulse)
new_state = Map.put(state, module, {:conj, dests, new_memory})
next_pulse = if Enum.all?(new_memory, &(elem(&1, 1) == :high)), do: :low, else: :high
{
Enum.map(dests, &{next_pulse, module, &1}),
new_state
}
end
defmodule Input do
def parse(input) do
input
|> String.splitter("\n", trim: true)
|> Enum.map(&parse_line/1)
|> Enum.into(%{})
|> setup_conjunctions()
end
defp setup_conjunctions(modules) do
for {k, {_, dests, _}} <- modules, reduce: %{} do
acc ->
Enum.reduce(dests, acc, fn d, acc ->
case modules[d] do
{:conj, _, _} -> Map.update(acc, d, [k], &[k | &1])
_ -> acc
end
end)
end
|> Enum.reduce(modules, fn {k, sources}, acc ->
Map.update!(acc, k, fn
{:conj, d, %{}} ->
{:conj, d, sources |> Enum.map(&{&1, :low}) |> Enum.into(%{})}
v ->
v
end)
end)
end
def parse_line(line) do
dest = &String.split(&1, ", ")
case String.split(line, " -> ") do
["%" <> module, d] ->
{module, {:flip, dest.(d), :off}}
["&" <> module, d] ->
{module, {:conj, dest.(d), %{}}}
[module, d] ->
{module, {:broadcast, dest.(d)}}
end
end
end
end
```
<!-- livebook:{"output":true} -->
```
{:module, Day20, <<70, 79, 82, 49, 0, 0, 28, ...>>,
{:module, Day20.Input, <<70, 79, 82, ...>>, {:parse_line, 1}}}
```
### Part 1:
Consult your module configuration; determine the number of low pulses and high pulses that would be sent after pushing the button 1000 times, waiting for all pulses to be fully handled after each push of the button. **What do you get if you multiply the total number of low pulses sent by the total number of high pulses sent?**
Your puzzle answer was `818649769`.
<!-- livebook:{"reevaluate_automatically":true} -->
```elixir
Day20.part1(input)
```
<!-- livebook:{"output":true} -->
```
818649769
```
### Part 2:
The final machine responsible for moving the sand down to Island Island has a module attached named rx. The machine turns on when a single low pulse is sent to rx.
Reset all modules to their default states. Waiting for all pulses to be fully handled after each button press, **what is the fewest number of button presses required to deliver a single low pulse to the module named rx?**
Your puzzle answer was `246313604784977`.
<!-- livebook:{"reevaluate_automatically":true} -->
```elixir
Day20.part2(input)
```
<!-- livebook:{"output":true} -->
```
246313604784977
```
Both parts of this puzzle are complete! They provide two gold stars: **
At this point, you should [return to your Advent calendar](https://adventofcode.com/2023) and try another puzzle.
If you still want to see it, you can [get your puzzle input](https://adventofcode.com/2023/day/20/input).
## Tests
<!-- livebook:{"reevaluate_automatically":true} -->
```elixir
ExUnit.start(auto_run: false)
defmodule Day20Test do
use ExUnit.Case, async: false
setup_all do
[
input1: "broadcaster -> a, b, c\n%a -> b\n%b -> c\n%c -> inv\n&inv -> a",
input2: "broadcaster -> a\n%a -> inv, con\n&inv -> b\n%b -> con\n&con -> output"
]
end
describe "part1/1" do
test "returns expected value", %{input1: input1, input2: input2} do
assert Day20.part1(input1) == 32_000_000
assert Day20.part1(input2) == 11_687_500
end
end
end
ExUnit.run()
```
<!-- livebook:{"output":true} -->
```
.
Finished in 0.00 seconds (0.00s async, 0.00s sync)
1 test, 0 failures
Randomized with seed 432984
```
<!-- livebook:{"output":true} -->
```
%{total: 1, failures: 0, excluded: 0, skipped: 0}
```
## Benchmarking
```elixir
defmodule Benchmarking do
# https://github.com/bencheeorg/benchee
def run(input) do
Benchee.run(
%{
"Part 1" => fn -> Day20.part1(input) end,
"Part 2" => fn -> Day20.part2(input) end
},
memory_time: 2,
reduction_time: 2
)
nil
end
end
```
<!-- livebook:{"output":true} -->
```
{:module, Benchmarking, <<70, 79, 82, 49, 0, 0, 7, ...>>, {:run, 1}}
```
```elixir
Benchmarking.run(input)
```
<!-- livebook:{"output":true} -->
```
Operating System: macOS
CPU Information: Apple M1 Pro
Number of Available Cores: 10
Available memory: 32 GB
Elixir 1.15.7
Erlang 26.1
Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 2 s
reduction time: 2 s
parallel: 1
inputs: none specified
Estimated total run time: 22 s
Benchmarking Part 1 ...
Benchmarking Part 2 ...
Name ips average deviation median 99th %
Part 1 74.99 13.34 ms ±1.39% 13.35 ms 13.98 ms
Part 2 17.15 58.32 ms ±2.99% 57.91 ms 67.32 ms
Comparison:
Part 1 74.99
Part 2 17.15 - 4.37x slower +44.98 ms
Memory usage statistics:
Name average deviation median 99th %
Part 1 41.53 MB ±0.01% 41.53 MB 41.53 MB
Part 2 170.40 MB ±0.01% 170.40 MB 170.42 MB
Comparison:
Part 1 41.53 MB
Part 2 170.40 MB - 4.10x memory usage +128.87 MB
Reduction count statistics:
Name Reduction count
Part 1 1.51 M
Part 2 6.32 M - 4.18x reduction count +4.81 M
**All measurements for reduction count were the same**
```
<!-- livebook:{"output":true} -->
```
nil
```
