this repo has no description
hauleth.dev
1<!-- vim:ft=markdown -->
2
3<!-- livebook:{"persist_outputs":true} -->
4
5# Day 19
6
7## Section
8
9```elixir
10# File.read!("day19.txt")
11input =
12 File.read!("day19.txt")
13 |> String.split("\n\n")
14 |> Enum.map(fn scanner ->
15 scanner
16 |> String.split("\n", trim: true)
17 |> Enum.drop(1)
18 |> Enum.map(fn coords ->
19 coords
20 |> String.split(",")
21 |> Enum.map(&String.to_integer/1)
22 |> Enum.zip(~w[x y z]a)
23 |> Map.new(fn {v, k} -> {k, v} end)
24 end)
25 |> MapSet.new()
26 end)
27
28length(input)
29```
30
31```output
3234
33```
34
35$$
36\left\{
37\begin{alignat*}{3}
38b_{x_1} r_x + b_{x_0} = a_{x_1} \\
39b_{x_2} r_x + b_{x_0} = a_{x_2}
40\end{alignat*}
41\right.
42\left\{
43\begin{alignat*}{3}
44b_{y_1} r_y + b_{y_0} = a_{y_1} \\
45b_{y_2} r_y + b_{y_0} = a_{y_2} \\
46\end{alignat*}
47\right.
48\left\{
49\begin{alignat*}{3}
50b_{z_1} r_z + b_{z_0} = a_{z_1} \\
51b_{z_2} r_z + b_{z_0} = a_{z_2} \\
52\end{alignat*}
53\right.
54$$
55
56Where $$r_x, r_y, r_z \in \{-1, 1\}$$ and $$a_{xyz}, b_{xyz} = \text{const}$$.
57This mean that we need to solve:
58
59$$
60B_x x + b_0 = a_x \\
61B_y y + b_0 = a_y \\
62B_z z + b_0 = a_z
63$$
64
65Where:
66
67$$
68B_d = \begin{bmatrix}
69{b_1}_d & 1 \\
70{b_2}_d & 1 \\
71\end{bmatrix}
72d = \begin{bmatrix}
73r_d \\
74b_{d_0}
75\end{bmatrix}
76a_d = \begin{bmatrix}
77{a_1}_d \\
78{a_2}_d
79\end{bmatrix}
80$$
81
82By applying [Cramer's Rule](https://en.wikipedia.org/wiki/Cramer%27s_rule) we can solve these
83linear equations with:
84
85$$
86e_d = \frac{
87\begin{vmatrix}
88{b_1}_d & 1 \\
89{b_2}_d & 1
90\end{vmatrix}
91}{
92\begin{vmatrix}
93{a_1}_d & 1 \\
94{a_2}_d & 1
95\end{vmatrix}
96} = \frac{{b_1}_d - {b_2}_d}{{a_1}_d - {a_2}_d} \\
97b_{d_0} = \frac{
98 \begin{vmatrix}
99{a_1}_d & {b_1}_d \\
100{a_2}_d & {b_2}_d
101\end{vmatrix}
102}{
103 \begin{vmatrix}
104{a_1}_d & 1 \\
105{a_2}_d & 1
106\end{vmatrix}
107} = \frac{{a_1}_d {b_2}_d - {b_1}_d {a_2}_d}{{a_1}_d - {a_2}_d}
108
109```elixir
110defmodule Day19 do
111 def rebase(base, pairs1) do
112 pairs0 = pairs(base)
113 # Take common points
114 pa = Map.take(pairs0, Map.keys(pairs1))
115 pb = Map.take(pairs1, Map.keys(pairs0))
116
117 # Merge them
118 [{{a, b, axes1}, {_, _, axes2}} = p0 | others] =
119 Map.merge(pa, pb, fn _, a, b -> {a, b} end)
120 |> Map.values()
121
122 p1 = Enum.find(others, fn {{x, y, _}, _} -> a in [x, y] end)
123 p2 = Enum.find(others, fn {{x, y, _}, _} -> b in [x, y] end)
124
125 axes = axes_transformations(axes1, axes2)
126
127 a_1 = a
128 a_2 = b
129 b_1 = reaxe(select_common(p0, p1), axes)
130 b_2 = reaxe(select_common(p0, p2), axes)
131
132 transform =
133 for i <- ~w[x y z]a, into: %{} do
134 a_1 = a_1[i]
135 a_2 = a_2[i]
136 b_1 = b_1[i]
137 b_2 = b_2[i]
138 det_b = b_1 - b_2
139 r = div(a_1 - a_2, det_b)
140
141 b_0 = div(b_1 * a_2 - a_1 * b_2, det_b)
142
143 {i, {r, b_0}}
144 end
145
146 new_points =
147 pairs1
148 |> Map.values()
149 |> Enum.flat_map(&[elem(&1, 0), elem(&1, 1)])
150 |> Enum.uniq()
151 |> Enum.map(&reaxe(&1, axes))
152 |> do_rebase(transform)
153 |> MapSet.new()
154
155 %{x: {_, sx}, y: {_, sy}, z: {_, sz}} = transform
156 scanner = %{x: sx, y: sy, z: sz}
157
158 {new_points, scanner}
159 end
160
161 defp do_rebase(points, transform) do
162 points
163 |> Enum.map(fn p ->
164 Map.merge(p, transform, fn _k, d, {r, b} -> d * r + b end)
165 end)
166 |> MapSet.new()
167 end
168
169 defp select_common(a, b) do
170 case {a, b} do
171 {{_, {_, x, _}}, {_, {_, x, _}}} -> x
172 {{_, {x, _, _}}, {_, {x, _, _}}} -> x
173 {{_, {_, x, _}}, {_, {x, _, _}}} -> x
174 {{_, {x, _, _}}, {_, {_, x, _}}} -> x
175 end
176 end
177
178 defp axes_transformations(a, b) do
179 Map.merge(a, b, fn
180 _, a, b -> {a, b}
181 end)
182 |> Map.values()
183 |> Map.new()
184 end
185
186 defp reaxe(point, axes) do
187 %{
188 x: point[axes[:x]],
189 y: point[axes[:y]],
190 z: point[axes[:z]]
191 }
192 end
193
194 def pairs(points) do
195 for a <- points,
196 b <- points,
197 a < b,
198 dx = abs(a.x - b.x),
199 dy = abs(a.y - b.y),
200 dz = abs(a.z - b.z),
201 into: %{},
202 do: {{dx ** 2 + dy ** 2 + dz ** 2, dx + dy + dz}, {a, b, %{dx => :x, dy => :y, dz => :z}}}
203 end
204end
205```
206
207```output
208{:module, Day19, <<70, 79, 82, 49, 0, 0, 26, ...>>, {:pairs, 1}}
209```
210
211```elixir
212[first | rest] = Enum.map(input, &Day19.pairs/1)
213
214{joinable, later} =
215 Enum.split_with(rest, fn pairs ->
216 s1 = MapSet.new(first, fn {k, _} -> k end)
217 s2 = MapSet.new(pairs, fn {k, _} -> k end)
218
219 case MapSet.size(MapSet.intersection(s1, s2)) do
220 66 -> true
221 x when x < 66 -> false
222 end
223 end)
224
225{length(joinable), length(later)}
226```
227
228```output
229{3, 30}
230```
231
232```elixir
233# Distances between each pair of points in `first`
234
235points_set = MapSet.new(hd(input))
236
237{points_set, scanners} =
238 Enum.reduce_while(
239 1..34,
240 {points_set, joinable, later, []},
241 fn i, {set, joinable, later, scanners} ->
242 {time, {set, scanners}} =
243 :timer.tc(fn ->
244 Enum.reduce(joinable, {set, scanners}, fn new, {base, scanners} ->
245 {new, scanner} = Day19.rebase(base, new)
246
247 {MapSet.union(new, base), [scanner | scanners]}
248 end)
249 end)
250
251 IO.inspect(time / 1_000_000)
252
253 current = Day19.pairs(set)
254
255 Enum.split_with(later, fn pairs ->
256 s1 = MapSet.new(current, fn {k, _} -> k end)
257 s2 = MapSet.new(pairs, fn {k, _} -> k end)
258
259 MapSet.size(MapSet.intersection(s1, s2)) >= 66
260 end)
261 |> case do
262 {[], []} ->
263 {:halt, {set, scanners}}
264
265 {joinable, later} ->
266 IO.inspect({length(joinable), length(later)}, label: i)
267 {:cont, {set, joinable, later, scanners}}
268 end
269 end
270 )
271
272MapSet.size(points_set)
273```
274
275```output
2760.002822
2771: {5, 25}
2780.017052
2792: {5, 20}
2800.0355
2813: {7, 13}
2820.134655
2834: {6, 7}
2840.229952
2855: {5, 2}
2860.288351
2876: {1, 1}
2880.076665
2897: {1, 0}
2900.071942
291```
292
293```output
294396
295```
296
297```elixir
298for(
299 a <- scanners,
300 b <- scanners,
301 do: abs(a.x - b.x) + abs(a.y - b.y) + abs(a.z - b.z)
302)
303|> Enum.max()
304```
305
306```output
30711828
308```