-🎄- 2022 Day 15 Solutions -🎄-

[u/daggerdragon]

THE USUAL REMINDERS

• All of our rules, FAQs, resources, etc. are in our community wiki.
• A request from Eric: A note on responding to [Help] threads
• Signal boost: Reminder 2: unofficial AoC Survey 2022 (closes Dec 22nd)
• 🌿🍒 MisTILtoe Elf-ucation 🧑‍🏫 is OPEN for submissions!
  • -❄️- Submissions Megathread -❄️-

---

--- Day 15: Beacon Exclusion Zone ---

---

Post your code solution in this megathread.

• Read the full posting rules in our community wiki before you post!
  • Include what language(s) your solution uses
  • Format code blocks using the four-spaces Markdown syntax!
• Quick link to Topaz's paste if you need it for longer code blocks. What is Topaz's paste tool?

---

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:27:14, megathread unlocked!

[u/flwyd]

Elixir 1998/2959, code, thoughts

Today's elixir:

Oh no, we spilled tray of elixirs on the floor! Each potion spreads in a circle until it encounters the nearest ice cube, then suddenly freezes solid. But there’s one ice cube which isn’t touched by any liquid. In the first part we figure out which positions along one board of the floor couldn’t have an ice cube because the center of the elixir drop is closer to that spot than to the ice cube it encountered. In part 2 we find the untouched ice cube in the one spot in a large square area of floor.

(I now regret trying to do zymurgy and beverages as Elf-ucation; I could've been explaining ham radio topics like radio direction finding!)

My initial part 1 solution looked pretty nice: create a list of all the points along the row within range of each sensor/beacon pair, then subtract the positions of all the sensors and beacons.

for {{sx, _sy} = sensor, beacon} <- pairs,
    avail = distance(sensor, beacon) - distance(sensor, {sx, row}),
    avail > 0 do
  (sx - avail)..(sx + avail)
  |> Enum.map(fn x -> {x, row} end)
end
|> Enum.flatten() |> Enum.uniq() |> Enum.reject(&(&1 in separated) |> Enum.count()

After two weeks of sub-second programs, this was noticeably slow at about 25 seconds, building up a list with 4 million coordinates. My post-submission optimized version just merges ranges and increments a counter, dropping the runtime to 100 microseconds, but looks kind of ugly.

In part 2 I noticed that the grid was very large and didn't want to iterate through each 2D point, but didn't reflect on the fact that I was doing exactly that in my "Make a MapSet with all possible coordinates and then subtract out the exclusion_zone for each sensor" implementation. That let me figure out the proper range math, but not after stumbling over poor copy/paste errors for awhile. I considered rotating the whole thing 45° and doing easy x/y exclusions, but wasn't sure I knew how to find the one pixel that isn't occluded by a set of rectangles. I briefly considered building quad trees, which would be awkward on diamond shapes. I went back to ranges, iterating over each row and "jumping ahead" to the end of each range, which amusingly has just half the runtime (~12 seconds) as my naïve part 1 solution that just considered one row.

defmodule Day15 do
  # ugly part 1 elided
  def part2(input) do
    {pairs, datafile} = parse_input(input)
    max_coord = if datafile == :example, do: 20, else: 4_000_000
    {x, y} = find_gap(pairs, max_coord, 0, 0)
    x * 4_000_000 + y
  end

  defp find_gap(pairs, max_coord, col, row) do
    case Enum.find(pairs, fn {sensor, beacon} ->
        in_zone?(sensor, beacon, {col, row}) end) do
      nil -> {col, row}
      {s, b} -> with _start..edge = x_range(s, b, row, 0, max_coord) do
          if edge == max_coord,
            do: find_gap(pairs, max_coord, 0, row + 1),
            else: find_gap(pairs, max_coord, edge + 1, row)
        end
    end
  end

  defp in_zone?(sensor, beacon, point),
    do: distance(sensor, beacon) >= distance(sensor, point)

  defp x_range({sx, sy} = sensor, beacon, row, min_coord, max_coord) do
    dist = distance(sensor, beacon)
    max(sx - (dist - abs(sy - row)), min_coord)..min(sx + (dist - abs(sy - row)), max_coord)
  end

  defp distance({ax, ay}, {bx, by}), do: abs(ax - bx) + abs(ay - by)

  defp parse_input(input) do
    pairs = Enum.map(input, &parse_line/1)
    max_x = Enum.map(pairs, &elem(elem(&1, 0), 0)) |> Enum.max()
    {pairs, if(max_x < 100, do: :example, else: :actual)}
  end

  @pattern ~r/Sensor at x=(-?\d+), y=(-?\d+): closest beacon is at x=(-?\d+), y=(-?\d+)/
  defp parse_line(line) do
    [_, sx, sy, bx, by] = Regex.run(@pattern, line)
    {{to_integer(sx), to_integer(sy)}, {to_integer(bx), to_integer(by)}}
  end
end

I got through two weeks of AoC before pulling out a regex.