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