this repo has no description
hauleth.dev
1# Day 10
2
3```elixir
4Mix.install([:kino_aoc, {:dantzig, github: "hauleth/dantzig", ref: "use-proper-binary"}],
5config: [
6 dantzig: [
7 highs_binary_path: System.find_executable("highs")
8 ]
9])
10```
11
12## Section
13
14<!-- livebook:{"attrs":"eyJhc3NpZ25fdG8iOiJwdXp6bGVfaW5wdXQiLCJkYXkiOiIxMCIsInNlc3Npb25fc2VjcmV0IjoiQURWRU5UX09GX0NPREVfU0VTU0lPTiIsInllYXIiOiIyMDI1In0","chunks":null,"kind":"Elixir.KinoAOC.HelperCell","livebook_object":"smart_cell"} -->
15
16```elixir
17{:ok, puzzle_input} =
18 KinoAOC.download_puzzle("2025", "10", System.fetch_env!("LB_ADVENT_OF_CODE_SESSION"))
19```
20
21```elixir
22defmodule Decoder do
23 def decode("[" <> pattern), do: do_lights(String.reverse(String.trim_trailing(pattern, "]")), 0)
24
25 def decode("(" <> rest) do
26 <<seq::binary-size(byte_size(rest) - 1), ")">> = rest
27
28 seq
29 |> String.split(",")
30 |> Enum.map(&String.to_integer/1)
31 end
32
33 def decode("{" <> rest) do
34 <<seq::binary-size(byte_size(rest) - 1), "}">> = rest
35
36 seq
37 |> String.split(",")
38 |> Enum.map(&String.to_integer/1)
39 end
40
41 defp do_lights("", num), do: num
42 defp do_lights("." <> rest, num), do: do_lights(rest, 2 * num)
43 defp do_lights("#" <> rest, num), do: do_lights(rest, 2 * num + 1)
44end
45```
46
47```elixir
48indicators =
49 puzzle_input
50 |> String.split("\n", trim: true)
51 |> Enum.map(fn raw ->
52 [lights | rest] =
53 raw
54 |> String.split()
55 |> Enum.map(&Decoder.decode/1)
56
57 {buttons, [whatever]} = Enum.split(rest, -1)
58
59 {lights, buttons, whatever}
60 end)
61```
62
63<!-- livebook:{"branch_parent_index":0} -->
64
65## Part 1
66
67We are looking for such sequence of buttons that will provide pattern we are looking for. It can be solved by brute force with simple observation that buttons $a_n$ as well as light pattern $p$ can be represented by binary pattern. This allows us to use $\oplus$ (exclusive or, aka `XOR`) as an operation for pressing button.
68
69Thanks to that observation we can see, that order in which we press buttons doesn't matter, as $\oplus$ is reflexive, i.e.:
70
71$$
72\begin{equation}
73a \oplus b = b \oplus a
74\end{equation}
75$$
76
77Additionally, wrt. $\oplus$ we have identity element $0$ and inverse element is the same as an original element, i.e.
78
79$$
80\begin{align}
81a \oplus 0 = a \\
82a \oplus a = 0
83\end{align}
84$$
85
86Additionally we can observe that:
87
88$$
89\begin{equation}
90(a \oplus b) \oplus c = a \oplus (b \oplus c)
91\end{equation}
92$$
93
94With that observation we can deduce that each button will be pressed at most once and the order in which we press buttons doesn't matter.
95
96---
97
98So now we look for set $A = \{a_n\}$ of buttons that
99
100$$
101A \in \mathcal{P}(\text{Buttons}) \\
102\forall_{i, j} \; i \ne j \implies a_i \ne a_j \\
103\bigoplus A = p
104$$
105
106```elixir
107defmodule Comb do
108 def all_possible([]), do: [[]]
109 def all_possible([a | rest]) do
110 sub = all_possible(rest)
111
112 sub ++ Enum.map(sub, &[a | &1])
113 end
114end
115```
116
117```elixir
118indicators
119|> Enum.sum_by(fn {p, a, _} ->
120 a
121 |> Enum.map(&Enum.sum_by(&1, fn p -> 2 ** p end))
122 |> Comb.all_possible()
123 |> Enum.sort_by(&length/1)
124 |> Enum.find(fn seq ->
125 r = Enum.reduce(seq, 0, &Bitwise.bxor/2)
126
127 p == r
128 end)
129 |> length()
130end)
131```
132
133<!-- livebook:{"branch_parent_index":0} -->
134
135## Part 2
136
137```elixir
138defmodule Joltage do
139 alias Dantzig.Polynomial
140 alias Dantzig.Constraint
141 alias Dantzig.Problem
142
143 def solve({_pat, buttons, goal}) do
144 p = Problem.new(direction: :minimize)
145
146 {vars, {p, map}} =
147 buttons
148 |> Enum.with_index()
149 |> Enum.map_reduce({p, %{}}, fn {list, idx}, {p, acc} ->
150 {p, var} = Problem.new_variable(p, "v#{idx}", min: 0, type: :integer)
151
152 acc =
153 Enum.reduce(list, acc, fn key, map ->
154 Map.update(map, key, [var], &[var | &1])
155 end)
156
157 {var, {p, acc}}
158 end)
159
160 p =
161 map
162 |> Enum.sort()
163 |> Enum.map(&elem(&1, 1))
164 |> Enum.zip(goal)
165 |> Enum.reduce(p, fn {vars, target}, p ->
166 poly = Polynomial.sum(vars)
167 const = Constraint.new(poly, :==, target)
168
169 Problem.add_constraint(p, const)
170 end)
171
172 p = Problem.increment_objective(p, Polynomial.sum(vars))
173
174 {:ok, s} = Dantzig.HiGHS.solve(p)
175
176 Enum.sum_by(vars, &Dantzig.Solution.evaluate(s, &1))
177 end
178end
179```
180
181```elixir
182indicators
183|> Task.async_stream(&Joltage.solve/1, ordered: false)
184|> Enum.sum_by(&elem(&1, 1))
185|> trunc()
186```
187
188<!-- livebook:{"offset":4336,"stamp":{"token":"XCP.sfoBGIHkFvWbEHVrY-dL-QiEcwRz_ZCIjn3lQ0RFHActIOwEapmOPBt0ygbQAmrnEjYPlFm5KrcWx4LfIPbSznxxcea0fYORG9GbBBpRCm-tYbGXYTCGgqgTvOsifyWDNg","version":2}} -->