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