# Day 15 ```elixir Mix.install([ {:kino_aoc, git: "https://github.com/ljgago/kino_aoc"} ]) ``` ``` :ok ``` ## Section ```elixir {:ok, puzzle_input} = KinoAOC.download_puzzle("2022", "15", System.fetch_env!("LB_ADVENT_OF_CODE_SESSION")) ``` ``` {:ok, "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"} ``` ```elixir points = puzzle_input |> String.split("\n", trim: true) |> Enum.map(fn line -> %{"sx" => sx, "sy" => sy, "bx" => bx, "by" => by} = Regex.named_captures( ~r/x=(?-?\d+), y=(?-?\d+):.*x=(?-?\d+), y=(?-?\d+)/, line ) %{ sensor: {String.to_integer(sx), String.to_integer(sy)}, beacon: {String.to_integer(bx), String.to_integer(by)} } end) circles = points |> Enum.map(fn %{beacon: {bx, by}, sensor: {sx, sy}} -> radius = abs(bx - sx) + abs(by - sy) {{sx, sy}, radius} end) ``` ``` [ {{2288642, 2282562}, 717544}, {{2215505, 2975419}, 748134}, {{275497, 3166843}, 925344}, {{1189444, 2115305}, 548911}, {{172215, 2327851}, 601896}, {{3953907, 1957660}, 1094699}, {{685737, 2465261}, 1089766}, {{1458348, 2739442}, 591336}, {{3742876, 2811554}, 960112}, {{437819, 638526}, 1901123}, {{2537979, 1762726}, 516163}, {{1368739, 2222863}, 262058}, {{2743572, 3976937}, 781451}, {{2180640, 105414}, 1037680}, {{3845753, 474814}, 1411237}, {{2493694, 3828087}, 382723}, {{2786014, 3388077}, 573273}, {{3593418, 3761871}, 1058809}, {{856288, 3880566}, 1544168}, {{1757086, 2518373}, 421799}, {{2853518, 2939097}, 503865}, {{1682023, 1449902}, 921879}, {{3360575, 1739100}, 673451}, {{2904259, 1465606}, 490629}, {{3078500, 3564862}, 457572}, {{2835288, 1011055}, 970525}, {{2998762, 2414323}, 596217} ] ``` ```elixir defmodule RangeSet do defstruct ranges: [] def new(), do: %__MODULE__{} def new(%__MODULE__{} = set), do: set def new(a..b//1) when a <= b, do: %__MODULE__{ranges: [a..b//1]} def new(b..a//-1) when b > a, do: %__MODULE__{ranges: [a..b//1]} def new(list), do: %__MODULE__{ranges: list |> Enum.sort_by(& &1.first) |> squash()} def min(%__MODULE__{ranges: [a.._ | _]}), do: a def max(%__MODULE__{ranges: ranges}) do _..a = List.last(ranges) a end def continuous?(%__MODULE__{ranges: []}), do: true def continuous?(%__MODULE__{ranges: [_]}), do: true def continuous?(%__MODULE__{ranges: _}), do: false def gaps(%__MODULE__{ranges: []} = set), do: set def gaps(%__MODULE__{ranges: [_]}), do: %__MODULE__{ranges: []} def gaps(%__MODULE__{ranges: ranges}) do gaps = ranges |> Enum.chunk_every(2, 1, :discard) |> Enum.flat_map(fn [_..a, b.._] -> [(a + 1)..(b - 1)] end) |> squash() %__MODULE__{ranges: gaps} end def empty?(%__MODULE__{ranges: ranges}), do: ranges == [] def has?(%__MODULE__{ranges: ranges}, value), do: Enum.any?(ranges, &(value in &1)) def length(%__MODULE__{ranges: ranges}), do: Enum.reduce(ranges, 0, fn r, acc -> acc + Range.size(r) end) def to_list(%__MODULE__{ranges: ranges}), do: Enum.flat_map(ranges, & &1) def remove(%__MODULE__{ranges: ranges}, int) when is_integer(int) do new_ranges = Enum.flat_map(ranges, fn a..b -> cond do a == int -> [(int + 1)..b] b == int -> [a..(int - 1)] int in a..b -> [a..(int - 1), (int + 1)..b] true -> [a..b] end end) %__MODULE__{ranges: new_ranges} end def remove(%__MODULE__{ranges: ranges}, c..d//1) when c <= d do new_ranges = Enum.flat_map(ranges, fn a..b -> cond do a in c..d and b in c..d -> [] a < c and b in c..d -> [a..(c - 1)] a in c..d and b > d -> [(d + 1)..b] c in a..b and d in a..b -> [a..(c - 1), (d + 1)..b] true -> [a..b] end end) %__MODULE__{ranges: new_ranges} end def remove(%__MODULE__{} = set, %__MODULE__{ranges: ranges}), do: Enum.reduce(ranges, set, &remove(&2, &1)) def remove(%__MODULE__{} = set, list), do: Enum.reduce(list, set, &remove(&2, &1)) def add(set, int) when is_integer(int), do: add(set, int..int//1) def add(set, a..b//-1), do: add(set, b..a//1) def add(%__MODULE__{} = set, a..b//1) when a > b, do: set def add(%__MODULE__{ranges: ranges}, a..b//1 = range) when a <= b do ranges = ranges |> insert_sorted(range) |> squash() %__MODULE__{ranges: ranges} end defp insert_sorted([], val), do: [val] defp insert_sorted([a.._ = x | rest], b.._ = y) when a < b, do: [x | insert_sorted(rest, y)] defp insert_sorted(rest, y), do: [y | rest] defp squash([]), do: [] defp squash([_] = list), do: list defp squash([a..b, c..d | rest]) when b >= c - 1, do: squash([a..max(b, d) | rest]) defp squash([x | rest]), do: [x | squash(rest)] end ``` ``` {:module, RangeSet, <<70, 79, 82, 49, 0, 0, 39, ...>>, {:squash, 1}} ``` ```elixir RangeSet.new([6..10, -8..26]) ``` ``` %RangeSet{ranges: [-8..26]} ``` Our 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 $$ r \ge d(C, a) $$ where $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: $$ d(a, b) = |a_x - b_x| + |a_y - b_y| $$ So after substitution at the above inequality we get: $$ r \ge |C_x - a_x| + |C_y - a_y| $$ In 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. That gives us: $$ |a_x - C_x| \le r - d_y $$ $$ \begin{align*} \therefore&\ -r + d_y &\le&\ a_x - C_x &\le&\ r - d_y \\ \therefore&\ -r + d_y + C_x &\le&\ a_x &\le&\ r - d_y + C_x \end{align*} $$ ```elixir defmodule Beacons do def covered_at_line(circles, a_y) do Enum.reduce(circles, RangeSet.new(), fn {{c_x, c_y}, r}, set -> d_y = abs(c_y - a_y) RangeSet.add(set, (-r + d_y + c_x)..(r - d_y + c_x)//1) end) end end ``` ``` {:module, Beacons, <<70, 79, 82, 49, 0, 0, 9, ...>>, {:covered_at_line, 2}} ``` ## Task 1 ```elixir a_y = 2_000_000 beacons_at_line = Enum.flat_map(points, fn %{beacon: {x, y}} -> if y == a_y, do: [x], else: [] end) circles |> Beacons.covered_at_line(a_y) |> IO.inspect() |> RangeSet.remove(beacons_at_line) |> RangeSet.length() ``` ``` %RangeSet{ranges: [-101830..5006266]} ``` ``` 5108096 ``` ## Task 2 ```elixir range = 4_000_000..0//-1 # range = 0..4_000_000 {y, [x]} = range |> Enum.find_value(fn y -> covered = Beacons.covered_at_line(circles, y) if not RangeSet.continuous?(covered) do gaps = RangeSet.gaps(covered) {y, RangeSet.to_list(gaps)} end end) |> Kino.render() x * 4_000_000 + y ``` ``` {2650264, [2638485]} ``` ``` 10553942650264 ```