Advent of Code 2022

Mix.install([
  {:req, "~> 0.3.2"},
  {:kino, "~> 0.8.1"}
])

Day 15

input =
  "https://adventofcode.com/2022/day/15/input"
  |> Req.get!(headers: [cookie: "session=#{System.get_env("AOC_COOKIE")}"])
  |> Map.get(:body)

sample = """
Sensor at x=2, y=18: closest beacon is at x=-2, y=15
Sensor at x=9, y=16: closest beacon is at x=10, y=16
Sensor at x=13, y=2: closest beacon is at x=15, y=3
Sensor at x=12, y=14: closest beacon is at x=10, y=16
Sensor at x=10, y=20: closest beacon is at x=10, y=16
Sensor at x=14, y=17: closest beacon is at x=10, y=16
Sensor at x=8, y=7: closest beacon is at x=2, y=10
Sensor at x=2, y=0: closest beacon is at x=2, y=10
Sensor at x=0, y=11: closest beacon is at x=2, y=10
Sensor at x=20, y=14: closest beacon is at x=25, y=17
Sensor at x=17, y=20: closest beacon is at x=21, y=22
Sensor at x=16, y=7: closest beacon is at x=15, y=3
Sensor at x=14, y=3: closest beacon is at x=15, y=3
Sensor at x=20, y=1: closest beacon is at x=15, y=3
"""

defmodule A do
  def parse(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.map(fn s ->
      [sx, sy, bx, by] =
        Regex.run(
          ~r/Sensor at x=(-?\d+), y=(-?\d+): closest beacon is at x=(-?\d+), y=(-?\d+)/,
          s,
          capture: :all_but_first
        )
        |> Enum.map(&String.to_integer/1)

      {{sx, sy}, {bx, by}}
    end)
  end

  def part1({input, target_y}) do
    parse(input)
    |> Enum.reduce(
      %{
        beacons_at_target: MapSet.new(),
        sensor_coverage_x: MapSet.new()
      },
      fn {{sx, sy}, {bx, by}}, acc ->
        acc =
          if by == target_y do
            update_in(acc.beacons_at_target, &MapSet.put(&1, bx))
          else
            acc
          end

        sensor_range = abs(bx - sx) + abs(by - sy)

        if target_y in (sy - sensor_range)..(sy + sensor_range) do
          dy =
            cond do
              sy < target_y ->
                target_y - sy

              sy > target_y ->
                sy - target_y

              sy == target_y ->
                0

              true ->
                raise("should not get here")
            end

          x_w = sensor_range - dy

          x_range = (sx - x_w)..(sx + x_w)

          update_in(acc.sensor_coverage_x, &amp;MapSet.union(&amp;1, x_range |> Enum.into(MapSet.new())))
        else
          acc
        end
      end
    )
  end

  def part2({input, max_x}) do
    parse(input)
    |> then(fn pairs -> {pairs, max_x} end)
    |> find_beacon()
    |> calculate_tuning_frequency()
  end

  defp find_beacon({pairs, max_x}) do
    sensors =
      pairs
      |> Enum.map(fn {{sx, sy}, {bx, by}} ->
        r = abs(bx - sx) + abs(by - sy)

        {sx, sy, r}
      end)

    0..max_x
    |> Enum.reduce_while(nil, fn y, _acc ->
      ranges =
        sensors
        |> Enum.reduce([], fn {sx, sy, r}, ranges ->
          dy = abs(y - sy)

          if dy > r do
            ranges
          else
            d = r - dy
            # clamp between 0 and max_x
            x0 = max(0, sx - d)
            x1 = min(sx + d, max_x)

            [x0..x1 | ranges]
          end
        end)
        |> Enum.sort_by(&amp; &amp;1.first)
        |> Enum.reduce([], fn range, acc ->
          case acc do
            [] ->
              [range]

            [cur | rest] = acc ->
              if cur.last + 1 < range.first do
                [range | acc]
              else
                x0 = cur.first
                x1 = max(cur.last, range.last)
                [x0..x1 | rest]
              end
          end
        end)

      case ranges do
        [r1, _] ->
          {:halt, {r1.first - 1, y}}

        _ ->
          {:cont, nil}
      end
    end)
  end

  defp calculate_tuning_frequency({x, y}) do
    x * 4_000_000 + y
  end
end

Part 1

inputs = [
  puzzle: {input, 2_000_000},
  sample: {sample, 10}
]

select = Kino.Input.select("input", puzzle: "Puzzle", sample: "Sample")

Keyword.fetch!(inputs, Kino.Input.read(select))
|> A.part1()
|> IO.inspect()
|> then(&(MapSet.difference(&1.sensor_coverage_x, &1.beacons_at_target) |> Enum.count()))

Part 2

inputs = [
  puzzle: {input, 4_000_000},
  sample: {sample, 20}
]

select = Kino.Input.select("input", puzzle: "Puzzle", sample: "Sample")

inputs
|> Keyword.fetch!(Kino.Input.read(select))
|> A.part2()

Part 2 - using line segments

https://old.reddit.com/r/adventofcode/comments/zmcn64/2022_day_15_solutions/j0b90nr/?context=3

data =
  input
  |> String.split("\n", trim: true)
  |> Enum.map(fn line ->
    Regex.scan(~r/-?\d+/, line, capture: :first)
    |> List.flatten()
    |> Enum.map(fn s -> String.to_integer(s) end)
  end)

# manhattan distance
m_dist = fn {x1, y1}, {x2, y2} ->
  abs(x2 - x1) + abs(y2 - y1)
end

sensors =
  data
  |> Enum.map(fn [sx, sy, bx, by] ->
    # manhattan distance
    r = m_dist.({sx, sy}, {bx, by})
    {{sx, sy}, r}
  end)
  |> Enum.into(%{})

{a_coefficients, b_coefficients} =
  sensors
  |> Enum.reduce({MapSet.new(), MapSet.new()}, fn {{x, y}, r}, {a_coefficients, b_coefficients} ->
    # gradient 1  /
    a_coefficients =
      a_coefficients
      |> MapSet.put(y - x + r + 1)
      |> MapSet.put(y - x - r - 1)

    # gradient -1 \
    b_coefficients =
      b_coefficients
      |> MapSet.put(x + y + r + 1)
      |> MapSet.put(x + y - r - 1)

    {a_coefficients, b_coefficients}
  end)

bound = 4_000_000

for a <- a_coefficients,
    b <- b_coefficients,
    x = div(b - a, 2),
    y = div(a + b, 2),
    Enum.all?([x, y], &amp;(0 < &amp;1 &amp;&amp; &amp;1 < bound)) do
  {x, y}
end
|> Enum.find(fn p ->
  # find the intersection point where it's out of range of all the sensors
  sensors
  |> Enum.all?(fn {s, r} ->
    m_dist.(s, p) > r
  end)
end)
|> then(fn {x, y} ->
  4_000_000 * x + y
end)

Part 2 - using some matrices

https://elixirforum.com/t/advent-of-code-2022-day-15/52552/8

defmodule Aetherus do
  # matrix for turning left 45 degrees 
  # and stretch by the factor sqrt(2)
  @m {
    {1, -1},
    {1, 1}
  }

  # inverse of @m
  @inv_m {
    {0.5, 0.5},
    {-0.5, 0.5}
  }

  # `sensors` is a list of {xc, yc, r}
  # where `xc` and `yc` is the coordinate of the center of a sensor,
  # and `r` is its manhattan radius.
  def part2_v2(sensors) do
    sensors =
      sensors
      |> Enum.map(fn {xc, yc, r} ->
        {
          # left corner --> bottom-left corner
          mul(@m, {xc - r, yc}),
          # right corner --> top-right corner
          mul(@m, {xc + r, yc})
        }
      end)

    x_pairs =
      sensors
      |> Enum.flat_map(fn {{x1, _}, {x2, _}} ->
        [x1, x2]
      end)
      |> Enum.uniq()
      |> Enum.sort()
      |> Enum.chunk_every(2, 1, :discard)
      |> Enum.filter(fn [x1, x2] -> x2 - x1 == 2 end)

    y_pairs =
      sensors
      |> Enum.flat_map(fn {{_, y1}, {_, y2}} ->
        [y1, y2]
      end)
      |> Enum.uniq()
      |> Enum.sort()
      |> Enum.chunk_every(2, 1, :discard)
      |> Enum.filter(fn [y1, y2] -> y2 - y1 == 2 end)

    for [x1, x2] <- x_pairs,
        [y1, y2] <- y_pairs,
        x = div(x1 + x2, 2),
        y = div(y1 + y2, 2),
        p = {x, y},
        !Enum.any?(sensors, &amp;cover?(&amp;1, p)),
        {x, y} = mul(@inv_m, p),
        do: x * 4_000_000 + y
  end

  defp cover?({{x1, y1}, {x2, y2}}, {x, y}) do
    x in x1..x2 and y in y1..y2
  end

  defp mul(
         {
           {a, b},
           {c, d}
         },
         {x, y}
       ) do
    {
      trunc(a * x + b * y),
      trunc(c * x + d * y)
    }
  end
end

data =
  input
  |> String.split("\n", trim: true)
  |> Enum.map(fn line ->
    Regex.scan(~r/-?\d+/, line, capture: :first)
    |> List.flatten()
    |> Enum.map(fn s -> String.to_integer(s) end)
  end)

# manhattan distance
m_dist = fn {x1, y1}, {x2, y2} ->
  abs(x2 - x1) + abs(y2 - y1)
end

sensors =
  data
  |> Enum.map(fn [sx, sy, bx, by] ->
    # manhattan distance
    r = m_dist.({sx, sy}, {bx, by})
    {sx, sy, r}
  end)

Aetherus.part2_v2(sensors)