2022 AOC Day 15

part1.exs

defmodule Beacons do
  @regex ~r/Sensor at x=(?<x>-?\d+), y=(?<y>-?\d+): closest beacon is at x=(?<bx>-?\d+), y=(?<by>-?\d+)$/

  def read(filename) do
    File.stream!(filename)
    |> Stream.map(&String.trim/1)
    |> Stream.map(&Regex.named_captures(@regex, &1))
    |> Stream.map(fn h -> 
      {
        {String.to_integer(h["x"]), String.to_integer(h["y"])},
        {String.to_integer(h["bx"]), String.to_integer(h["by"])}
      }
    end)
  end

  def all_ruled_out(beacons, target_y) do
    beacons
    |> Stream.map(&ruled_out(&1, target_y))
    |> Enum.reduce(MapSet.new(), &MapSet.union/2)
  end

  def ruled_out({{x, y} = pos, beacon}, target_y) do
    max_dx = distance(pos, beacon) - abs(y - target_y)

    if max_dx < 0 do
      MapSet.new()
    else
      x-max_dx..x+max_dx
      |> MapSet.new(&{&1, target_y})
      |> MapSet.delete(beacon)
    end
  end

  defp distance({x1, y1}, {x2, y2}) do
    abs(x1 - x2) + abs(y1 - y2)
  end
end

# target_y = 10
target_y = 2_000_000

Beacons.read("input.txt")
|> Beacons.all_ruled_out(target_y)
|> MapSet.size()
|> IO.inspect()

part2.exs

defmodule Beacons do
  @regex ~r/Sensor at x=(?<x>-?\d+), y=(?<y>-?\d+): closest beacon is at x=(?<bx>-?\d+), y=(?<by>-?\d+)$/

  def read(filename) do
    File.stream!(filename)
    |> Stream.map(&String.trim/1)
    |> Stream.map(&Regex.named_captures(@regex, &1))
    |> Stream.map(fn h -> 
      {
        {String.to_integer(h["x"]), String.to_integer(h["y"])},
        {String.to_integer(h["bx"]), String.to_integer(h["by"])}
      }
    end)
  end

  def all_ruled_out(beacons, max_x, target_y) do
    beacons
    |> Stream.flat_map(&ruled_out(&1, target_y))
    |> Enum.reduce([0..max_x], &subtract/2)
    |> Enum.map(fn r when r.first == r.last -> {r.first, target_y} end)
  end

  def ruled_out({{x, y} = pos, beacon}, target_y) do
    max_dx = distance(pos, beacon) - abs(y - target_y)

    if max_dx < 0 do
      []
    else
      [x-max_dx..x+max_dx]
    end
  end

  defp distance({x1, y1}, {x2, y2}) do
    abs(x1 - x2) + abs(y1 - y2)
  end

  defp subtract(range1, ranges) do
    Enum.flat_map(ranges, &subtract_one(range1, &1))
  end

  def subtract_one(to_subtract, range) do
    cond do
      Range.disjoint?(to_subtract, range) ->
        # no overlap
        [range]

      to_subtract.first <= range.first and to_subtract.last >= range.last ->
        # to_subtract is bigger
        []

      to_subtract.first <= range.first and to_subtract.last < range.last ->
        # trim the beginning
        [Range.new(to_subtract.last+1, range.last)]

      to_subtract.first > range.first and to_subtract.last >= range.last ->
        # trim the end
        [Range.new(range.first, to_subtract.first-1)]

      to_subtract.first > range.first and to_subtract.last < range.last ->
        # split the range
        [Range.new(range.first, to_subtract.first - 1), Range.new(to_subtract.last + 1, range.last)]
    end
  end
end

# max_x = 20
max_x = 4_000_000

beacons = Beacons.read("input.txt") |> Enum.to_list()

(0..max_x)
|> Task.async_stream(&Beacons.all_ruled_out(beacons, max_x, &1), ordered: false)
|> Stream.flat_map(fn {:ok, x} -> x end)
|> Enum.to_list()
|> IO.inspect()