this repo has no description
hauleth.dev
1<!-- livebook:{"persist_outputs":true} -->
2
3# Day 15
4
5```elixir
6Mix.install([
7 {:kino_aoc, git: "https://github.com/ljgago/kino_aoc"}
8])
9```
10
11<!-- livebook:{"output":true} -->
12
13```
14:ok
15```
16
17## Section
18
19<!-- livebook:{"attrs":{"day":"15","session_secret":"ADVENT_OF_CODE_SESSION","variable":"puzzle_input","year":"2022"},"chunks":null,"kind":"Elixir.KinoAOC.HelperCell","livebook_object":"smart_cell"} -->
20
21```elixir
22{:ok, puzzle_input} =
23 KinoAOC.download_puzzle("2022", "15", System.fetch_env!("LB_ADVENT_OF_CODE_SESSION"))
24```
25
26<!-- livebook:{"output":true} -->
27
28```
29{:ok,
30 "Sensor at x=2288642, y=2282562: closest beacon is at x=1581951, y=2271709\nSensor at x=2215505, y=2975419: closest beacon is at x=2229474, y=3709584\nSensor at x=275497, y=3166843: closest beacon is at x=-626874, y=3143870\nSensor at x=1189444, y=2115305: closest beacon is at x=1581951, y=2271709\nSensor at x=172215, y=2327851: closest beacon is at x=-101830, y=2000000\nSensor at x=3953907, y=1957660: closest beacon is at x=2882446, y=1934422\nSensor at x=685737, y=2465261: closest beacon is at x=1581951, y=2271709\nSensor at x=1458348, y=2739442: closest beacon is at x=1581951, y=2271709\nSensor at x=3742876, y=2811554: closest beacon is at x=3133845, y=3162635\nSensor at x=437819, y=638526: closest beacon is at x=-101830, y=2000000\nSensor at x=2537979, y=1762726: closest beacon is at x=2882446, y=1934422\nSensor at x=1368739, y=2222863: closest beacon is at x=1581951, y=2271709\nSensor at x=2743572, y=3976937: closest beacon is at x=2229474, y=3709584\nSensor at x=2180640, y=105414: closest beacon is at x=3011118, y=-101788\nSensor at x=3845753, y=474814: closest beacon is at x=3011118, y=-101788\nSensor at x=2493694, y=3828087: closest beacon is at x=2229474, y=3709584\nSensor at x=2786014, y=3388077: closest beacon is at x=3133845, y=3162635\nSensor at x=3593418, y=3761871: closest beacon is at x=3133845, y=3162635\nSensor at x=856288, y=3880566: closest beacon is at x=2229474, y=3709584\nSensor at x=1757086, y=2518373: closest beacon is at x=1581951, y=2271709\nSensor at x=2853518, y=2939097: closest beacon is at x=3133845, y=3162635\nSensor at x=1682023, y=1449902: closest beacon is at x=1581951, y=2271709\nSensor at x=3360575, y=1739100: closest beacon is at x=2882446, y=1934422\nSensor at x=2904259, y=1465606: closest beacon is at x=2882446, y=1934422\nSensor at x=3078500, y=3564862: closest beacon is at x=3133845, y=3162635\nSensor at x=2835288, y=1011055: closest beacon is at x=2882446, y=1934422\nSensor at x=2998762, y=2414323: closest beacon is at x=2882446, y=1934422\n"}
31```
32
33```elixir
34points =
35 puzzle_input
36 |> String.split("\n", trim: true)
37 |> Enum.map(fn line ->
38 %{"sx" => sx, "sy" => sy, "bx" => bx, "by" => by} =
39 Regex.named_captures(
40 ~r/x=(?<sx>-?\d+), y=(?<sy>-?\d+):.*x=(?<bx>-?\d+), y=(?<by>-?\d+)/,
41 line
42 )
43
44 %{
45 sensor: {String.to_integer(sx), String.to_integer(sy)},
46 beacon: {String.to_integer(bx), String.to_integer(by)}
47 }
48 end)
49
50circles =
51 points
52 |> Enum.map(fn %{beacon: {bx, by}, sensor: {sx, sy}} ->
53 radius = abs(bx - sx) + abs(by - sy)
54
55 {{sx, sy}, radius}
56 end)
57```
58
59<!-- livebook:{"output":true} -->
60
61```
62[
63 {{2288642, 2282562}, 717544},
64 {{2215505, 2975419}, 748134},
65 {{275497, 3166843}, 925344},
66 {{1189444, 2115305}, 548911},
67 {{172215, 2327851}, 601896},
68 {{3953907, 1957660}, 1094699},
69 {{685737, 2465261}, 1089766},
70 {{1458348, 2739442}, 591336},
71 {{3742876, 2811554}, 960112},
72 {{437819, 638526}, 1901123},
73 {{2537979, 1762726}, 516163},
74 {{1368739, 2222863}, 262058},
75 {{2743572, 3976937}, 781451},
76 {{2180640, 105414}, 1037680},
77 {{3845753, 474814}, 1411237},
78 {{2493694, 3828087}, 382723},
79 {{2786014, 3388077}, 573273},
80 {{3593418, 3761871}, 1058809},
81 {{856288, 3880566}, 1544168},
82 {{1757086, 2518373}, 421799},
83 {{2853518, 2939097}, 503865},
84 {{1682023, 1449902}, 921879},
85 {{3360575, 1739100}, 673451},
86 {{2904259, 1465606}, 490629},
87 {{3078500, 3564862}, 457572},
88 {{2835288, 1011055}, 970525},
89 {{2998762, 2414323}, 596217}
90]
91```
92
93```elixir
94defmodule RangeSet do
95 defstruct ranges: []
96
97 def new(), do: %__MODULE__{}
98 def new(%__MODULE__{} = set), do: set
99 def new(a..b//1) when a <= b, do: %__MODULE__{ranges: [a..b//1]}
100 def new(b..a//-1) when b > a, do: %__MODULE__{ranges: [a..b//1]}
101 def new(list), do: %__MODULE__{ranges: list |> Enum.sort_by(& &1.first) |> squash()}
102
103 def min(%__MODULE__{ranges: [a.._ | _]}), do: a
104
105 def max(%__MODULE__{ranges: ranges}) do
106 _..a = List.last(ranges)
107
108 a
109 end
110
111 def continuous?(%__MODULE__{ranges: []}), do: true
112 def continuous?(%__MODULE__{ranges: [_]}), do: true
113 def continuous?(%__MODULE__{ranges: _}), do: false
114
115 def gaps(%__MODULE__{ranges: []} = set), do: set
116 def gaps(%__MODULE__{ranges: [_]}), do: %__MODULE__{ranges: []}
117
118 def gaps(%__MODULE__{ranges: ranges}) do
119 gaps =
120 ranges
121 |> Enum.chunk_every(2, 1, :discard)
122 |> Enum.flat_map(fn [_..a, b.._] -> [(a + 1)..(b - 1)] end)
123 |> squash()
124
125 %__MODULE__{ranges: gaps}
126 end
127
128 def empty?(%__MODULE__{ranges: ranges}), do: ranges == []
129
130 def has?(%__MODULE__{ranges: ranges}, value), do: Enum.any?(ranges, &(value in &1))
131
132 def length(%__MODULE__{ranges: ranges}),
133 do: Enum.reduce(ranges, 0, fn r, acc -> acc + Range.size(r) end)
134
135 def to_list(%__MODULE__{ranges: ranges}),
136 do: Enum.flat_map(ranges, & &1)
137
138 def remove(%__MODULE__{ranges: ranges}, int) when is_integer(int) do
139 new_ranges =
140 Enum.flat_map(ranges, fn a..b ->
141 cond do
142 a == int -> [(int + 1)..b]
143 b == int -> [a..(int - 1)]
144 int in a..b -> [a..(int - 1), (int + 1)..b]
145 true -> [a..b]
146 end
147 end)
148
149 %__MODULE__{ranges: new_ranges}
150 end
151
152 def remove(%__MODULE__{ranges: ranges}, c..d//1) when c <= d do
153 new_ranges =
154 Enum.flat_map(ranges, fn a..b ->
155 cond do
156 a in c..d and b in c..d -> []
157 a < c and b in c..d -> [a..(c - 1)]
158 a in c..d and b > d -> [(d + 1)..b]
159 c in a..b and d in a..b -> [a..(c - 1), (d + 1)..b]
160 true -> [a..b]
161 end
162 end)
163
164 %__MODULE__{ranges: new_ranges}
165 end
166
167 def remove(%__MODULE__{} = set, %__MODULE__{ranges: ranges}),
168 do: Enum.reduce(ranges, set, &remove(&2, &1))
169
170 def remove(%__MODULE__{} = set, list),
171 do: Enum.reduce(list, set, &remove(&2, &1))
172
173 def add(set, int) when is_integer(int), do: add(set, int..int//1)
174
175 def add(set, a..b//-1), do: add(set, b..a//1)
176
177 def add(%__MODULE__{} = set, a..b//1) when a > b, do: set
178
179 def add(%__MODULE__{ranges: ranges}, a..b//1 = range) when a <= b do
180 ranges =
181 ranges
182 |> insert_sorted(range)
183 |> squash()
184
185 %__MODULE__{ranges: ranges}
186 end
187
188 defp insert_sorted([], val), do: [val]
189
190 defp insert_sorted([a.._ = x | rest], b.._ = y) when a < b,
191 do: [x | insert_sorted(rest, y)]
192
193 defp insert_sorted(rest, y),
194 do: [y | rest]
195
196 defp squash([]), do: []
197 defp squash([_] = list), do: list
198
199 defp squash([a..b, c..d | rest]) when b >= c - 1,
200 do: squash([a..max(b, d) | rest])
201
202 defp squash([x | rest]), do: [x | squash(rest)]
203end
204```
205
206<!-- livebook:{"output":true} -->
207
208```
209{:module, RangeSet, <<70, 79, 82, 49, 0, 0, 39, ...>>, {:squash, 1}}
210```
211
212```elixir
213RangeSet.new([6..10, -8..26])
214```
215
216<!-- livebook:{"output":true} -->
217
218```
219%RangeSet{ranges: [-8..26]}
220```
221
222Our list can be change into list of radii of the circles (in Taxicab metric these will be visually squares), so then using inequality for circle
223
224$$
225r \ge d(C, a)
226$$
227
228where $d(a, b)$ is distance function for given metric, we can compute possible ranges of values at given line in constant time. In Taxicab metric $d$ is defined as:
229
230$$
231d(a, b) = |a_x - b_x| + |a_y - b_y|
232$$
233
234So after substitution at the above inequality we get:
235
236$$
237r \ge |C_x - a_x| + |C_y - a_y|
238$$
239
240In the task $a_y = const$ and $C = const$, so we need to solve only for $a_x$. So we can define $d_y = |C_y - a_y| = const$ as well.
241
242That gives us:
243
244$$
245|a_x - C_x| \le r - d_y
246$$
247
248$$
249\begin{align*}
250\therefore&\ -r + d_y &\le&\ a_x - C_x &\le&\ r - d_y \\
251\therefore&\ -r + d_y + C_x &\le&\ a_x &\le&\ r - d_y + C_x
252\end{align*}
253$$
254
255```elixir
256defmodule Beacons do
257 def covered_at_line(circles, a_y) do
258 Enum.reduce(circles, RangeSet.new(), fn {{c_x, c_y}, r}, set ->
259 d_y = abs(c_y - a_y)
260 RangeSet.add(set, (-r + d_y + c_x)..(r - d_y + c_x)//1)
261 end)
262 end
263end
264```
265
266<!-- livebook:{"output":true} -->
267
268```
269{:module, Beacons, <<70, 79, 82, 49, 0, 0, 9, ...>>, {:covered_at_line, 2}}
270```
271
272## Task 1
273
274```elixir
275a_y = 2_000_000
276
277beacons_at_line =
278 Enum.flat_map(points, fn %{beacon: {x, y}} -> if y == a_y, do: [x], else: [] end)
279
280circles
281|> Beacons.covered_at_line(a_y)
282|> IO.inspect()
283|> RangeSet.remove(beacons_at_line)
284|> RangeSet.length()
285```
286
287<!-- livebook:{"output":true} -->
288
289```
290%RangeSet{ranges: [-101830..5006266]}
291```
292
293<!-- livebook:{"output":true} -->
294
295```
2965108096
297```
298
299## Task 2
300
301```elixir
302range = 4_000_000..0//-1
303# range = 0..4_000_000
304
305{y, [x]} =
306 range
307 |> Enum.find_value(fn y ->
308 covered = Beacons.covered_at_line(circles, y)
309
310 if not RangeSet.continuous?(covered) do
311 gaps = RangeSet.gaps(covered)
312 {y, RangeSet.to_list(gaps)}
313 end
314 end)
315 |> Kino.render()
316
317x * 4_000_000 + y
318```
319
320<!-- livebook:{"output":true} -->
321
322```
323{2650264, [2638485]}
324```
325
326<!-- livebook:{"output":true} -->
327
328```
32910553942650264
330```