Advent of Code 2024 - Day 8

Not the most efficient way to do it (especially part 2) but it takes like 1ms to run anyway so it literally doesn’t matter

https://github.com/sevenseacat/advent_of_code/blob/main/lib/y2024/day08.ex

Now back to doing previous year puzzles that I never completed…

I used Enum.dedup/1 instead of Enum.uniq/1 when attempting to solve part 1. This mistake hid another bug, and so I got the correct result for the example but not for my input.

The following solution is refactored to share most of the code for the solution:

https://github.com/bjorng/advent-of-code/blob/main/2024/day08/lib/day08.ex

#!/usr/bin/env elixir

# AoC 2024. day 8.

###########################################################
# Setup

{coords2antennas, nrows, ncols} = File.stream!("../day08.txt")
  |> Stream.with_index(1)
  |> Enum.reduce({%{}, 0, 0}, fn {line, row}, {map, nrows, ncols} ->
    line
    |> String.trim_trailing()
    |> String.to_charlist()
    |> Enum.with_index(1)
    |> Enum.reduce({map, nrows, ncols}, fn {c, col}, {map, nrows, ncols} ->
      map = (if c != ?., do: Map.put(map, {row,col}, c), else: map)
      {map, max(nrows, row), max(ncols, col)}
    end)
  end)

defmodule M do
  # values become keys and vice-versa. values are stored in a list.
  def inside_out(map) do
    map |> Enum.reduce(%{}, fn {k,v}, res ->
      Map.update(res, v, [k], fn lst -> [k|lst] end)
    end)
  end
  def offset({r1,c1}, {r2,c2}), do: {r2-r1,c2-c1}
  def add({r,c},{ro,co}), do: {r+ro,c+co}
  def sub({r,c},{ro,co}), do: {r-ro,c-co}
  def inside({r,c}, nrows, ncols), do: r >= 1 && r <= nrows && c >= 1 && c <= ncols
  def pairs([]), do: []
  def pairs([x | rest]), do: Enum.map(rest, fn y -> {x,y} end) ++ pairs(rest)
end

###########################################################
# Part 1

coords2antennas
|> M.inside_out()
|> Enum.reduce(MapSet.new(), fn {_antenna, coords}, set ->
  pairs = M.pairs(coords)
  Enum.reduce(pairs, set, fn {coord1, coord2}, set ->
    offset = M.offset(coord1, coord2)
    set
    |> then(fn set ->
      anti = M.sub(coord1, offset)
      if M.inside(anti, nrows, ncols), do: MapSet.put(set, anti), else: set
    end)
    |> then(fn set ->
      anti = M.add(coord2, offset)
      if M.inside(anti, nrows, ncols), do: MapSet.put(set, anti), else: set
    end)
  end)
end)
|> tap(fn set -> IO.puts("Part 1. Number of antinodes: #{MapSet.size(set)}") end)

###########################################################
# Part 2

coords2antennas
|> M.inside_out()
|> Enum.reduce(MapSet.new(), fn {_antenna, coords}, set ->
  pairs = M.pairs(coords)
  Enum.reduce(pairs, set, fn {coord1, coord2}, set ->
    offset = M.offset(coord1, coord2)
    set = Stream.unfold(coord1, fn coord ->
        anti = M.sub(coord, offset)
        if M.inside(anti, nrows, ncols), do: {anti, anti}
      end)
      |> Enum.reduce(set, fn anti, set -> MapSet.put(set, anti) end)
    Stream.unfold(coord2, fn coord ->
      anti = M.add(coord, offset)
      if M.inside(anti, nrows, ncols), do: {anti, anti}
    end)
    |> Enum.reduce(set, fn anti, set -> MapSet.put(set, anti) end)
    |> MapSet.put(coord1)
    |> MapSet.put(coord2)
  end)
end)
|> tap(fn set -> IO.puts("Part 2. Number of antinodes: #{MapSet.size(set)}") end)

Fun day! Finally less bruteforce thinking!

Both solutions were pretty fast to run:

===== YEAR 2024 DAY 8 PART 1 =====
Result: 
Took: 5ms
===== YEAR 2024 DAY 8 PART 2 =====
Result: 
Took: 2ms

Solution (still working to generalize it):

defmodule AOC.Y2024.Day8 do
  @moduledoc false

  use AOC.Solution

  @impl true
  def load_data() do
    Data.load_day_as_grid(2024, 8)
    |> then(fn {grid, m, n} ->
      antennas =
        grid
        |> Enum.filter(fn {_, v} -> v != "." end)
        |> Enum.group_by(fn {_, v} -> v end, fn {k, _} -> k end)

      {antennas, m, n}
    end)
  end

  @impl true
  def part_one({antennas, m, n}) do
    solve(antennas, m, n, &find_antinodes/3)
  end

  @impl true
  def part_two({antennas, m, n}) do
    solve(antennas, m, n, &find_antinodes2/3)
  end

  defp solve(antennas, m, n, func) do
    antennas
    |> Enum.flat_map(fn {_, coords} ->
      func.(coords, m, n)
    end)
    |> Enum.uniq()
    |> Enum.count()
  end

  defp find_antinodes(coords, m, n) do
    coords
    |> Enum.with_index(1)
    |> Enum.flat_map(fn {coord, i} ->
      coords |> Enum.slice(i..-1//1) |> Enum.map(fn other -> {coord, other} end)
    end)
    |> Enum.flat_map(fn {{a, b}, {c, d}} ->
      da = abs(a - c)
      db = abs(b - d)
      da_sign = div(a - c, abs(a - c))
      db_sign = div(b - d, abs(b - d))
      nx = {a + da * da_sign, b + db * db_sign}
      ny = {c + da * -da_sign, d + db * -db_sign}
      [nx, ny]
    end)
    |> Enum.filter(fn {a, b} ->
      a in 0..(m - 1) and b in 0..(n - 1)
    end)
  end

  defp find_antinodes2(coords, m, n) do
    coords
    |> Enum.with_index(1)
    |> Enum.flat_map(fn {coord, i} ->
      coords |> Enum.slice(i..-1//1) |> Enum.map(fn other -> {coord, other} end)
    end)
    |> Enum.flat_map(fn {x, y} ->
      inf_antinodes(x, y, m, n)
    end)
  end

  defp inf_antinodes({a, b}, {c, d}, m, n) do
    da = abs(a - c)
    db = abs(b - d)
    da_sign = div(a - c, abs(a - c))
    db_sign = div(b - d, abs(b - d))

    Stream.iterate({a, b}, fn {x, y} ->
      {x + da * da_sign, y + db * db_sign}
    end)
    |> Stream.take_while(fn {x, y} -> x in 0..(m - 1) and y in 0..(n - 1) end)
    |> Stream.concat(
      Stream.iterate({c, d}, fn {x, y} ->
        {x + da * -da_sign, y + db * -db_sign}
      end)
      |> Stream.take_while(fn {x, y} -> x in 0..(m - 1) and y in 0..(n - 1) end)
    )
    |> Enum.to_list()
    |> Enum.uniq()
  end
end

I struggled way more than expected with my x and y calculations

Part 1

defmodule Advent.Y2024.Day08.Part1 do
  @grid_size 49

  def run(puzzle) do
    puzzle
    |> parse()
    |> find_antinodes(&antinodes/2)
    |> Enum.count()
  end

  def parse(puzzle) do
    for {line, y} <- puzzle |> String.split("\n") |> Enum.with_index(), reduce: %{} do
      acc ->
        for {c, x} <- line |> String.graphemes() |> Enum.with_index(), c != ".", reduce: acc do
          acc -> Map.update(acc, c, [{x, y}], fn pos -> [{x, y} | pos] end)
        end
    end
  end

  def find_antinodes(g, fun) do
    for {_, pos} <- g, a1 <- pos, a2 <- pos, a1 != a2, n <- fun.(a1, a2), reduce: MapSet.new() do
      nodes -> MapSet.put(nodes, n)
    end
  end

  defp antinodes({x1, y1}, {x2, y2}) do
    dx = abs(x1 - x2)
    dy = abs(y1 - y2)

    Enum.filter(
      [
        {if(x1 > x2, do: x1 + dx, else: x1 - dx), if(y1 > y2, do: y1 + dy, else: y1 - dy)},
        {if(x2 > x1, do: x2 + dx, else: x2 - dx), if(y2 > y1, do: y2 + dy, else: y2 - dy)}
      ],
      fn {x, y} -> x in 0..@grid_size and y in 0..@grid_size end
    )
  end
end

Part 2

defmodule Advent.Y2024.Day08.Part2 do
  @grid_size 49

  alias Advent.Y2024.Day08.Part1

  def run(puzzle) do
    puzzle
    |> Part1.parse()
    |> Part1.find_antinodes(&antinodes/2)
    |> Enum.count()
  end

  defp antinodes({x1, y1}, {x2, y2}) do
    dx = abs(x1 - x2)
    dy = abs(y1 - y2)

    [{x1, y1}, {x2, y2}] ++
      in_direction({x1, y1}, {if(x1 > x2, do: dx, else: -dx), if(y1 > y2, do: dy, else: -dy)}) ++
      in_direction({x2, y2}, {if(x2 > x1, do: dx, else: -dx), if(y2 > y1, do: dy, else: -dy)})
  end

  defp in_direction({x, y}, {dx, dy}, acc \\ []) do
    {nx, ny} = {x + dx, y + dy}

    if nx in 0..@grid_size and ny in 0..@grid_size do
      in_direction({nx, ny}, {dx, dy}, [{nx, ny} | acc])
    else
      acc
    end
  end
end

Pretty tame after Friday’s loop detection, I was expecting worse for Sunday (although I took a break yesterday so I’m not sure how that was).

Each part completes in under a millisecond.

def calc_resonant_harmonics({{x_a, y_a}, {x_b, y_b}}, max_x, max_y) do
  dx = x_a - x_b
  dy = y_a - y_b

  [{x_a, y_a}, {x_b, y_b}] ++
    resonate(x_a, y_a, dx, dy, max_x, max_y) ++
    resonate(x_b, y_b, dx * -1, dy * -1, max_x, max_y)
end

def resonate(x, y, dx, dy, max_x, max_y, multiplier \\ 1) do
  next_x = x + dx * multiplier
  next_y = y + dy * multiplier

  if next_x < 0 or next_x >= max_x or next_y < 0 or next_y >= max_y do
    []
  else
    [{next_x, next_y} | resonate(x, y, dx, dy, max_x, max_y, multiplier + 1)]
  end
end

https://git.adamu.jp/adam/AdventOfCode/src/branch/main/2024/day8.exs

Sundays are supposed to be harder but today was quite easy:)

defmodule AdventOfCode.Solutions.Y24.Day08 do
  alias AdventOfCode.Grid
  alias AoC.Input

  def parse(input, _part) do
    {_grid, _bounds} =
      input
      |> Input.stream!()
      |> Grid.parse_lines(fn
        _, ?. -> :ignore
        _, ?\n -> raise "parses new line"
        _, c -> {:ok, c}
      end)
  end

  def part_one({grid, bounds}) do
    for({xy_l, l} <- grid, {xy_r, r} <- grid, l == r, xy_l < xy_r, do: antinodes_p1(xy_l, xy_r))
    |> :lists.flatten()
    |> Enum.uniq()
    |> Enum.filter(&in_bounds?(&1, bounds))
    |> length()
  end

  defp antinodes_p1({xl, yl}, {xr, yr}) do
    x_diff = xr - xl
    y_diff = yr - yl

    [
      # Lower node
      {xl - x_diff, yl - y_diff},

      # Higher node
      {xr + x_diff, yr + y_diff}
    ]
  end

  defp in_bounds?({x, y}, {xa, xo, ya, yo}) do
    x >= xa and x <= xo and
      y >= ya and y <= yo
  end

  def part_two({grid, bounds}) do
    for(
      {xy_l, l} <- grid,
      {xy_r, r} <- grid,
      l == r,
      xy_l < xy_r,
      do: antinodes_p2(xy_l, xy_r, bounds)
    )
    |> :lists.flatten()
    |> Enum.uniq()
    |> length()
  end

  defp antinodes_p2({xl, yl}, {xr, yr}, bounds) do
    x_diff = xr - xl
    y_diff = yr - yl

    higher =
      {xr, yr}
      |> Stream.iterate(fn {x, y} -> {x + x_diff, y + y_diff} end)
      |> Enum.take_while(&in_bounds?(&1, bounds))

    lower =
      {xl, yl}
      |> Stream.iterate(fn {x, y} -> {x - x_diff, y - y_diff} end)
      |> Enum.take_while(&in_bounds?(&1, bounds))

    [higher, lower]
  end
end

No optimization at all its under 1ms as well.

My solution today:

https://github.com/Flo0807/adventofcode/blob/main/2024/08.livemd

That’s a clever way of iterating through the grid.

I did a Map.values() into a MapSet to get possible values, then did a Map.filter() on each to get the matching tower locations, which seems messy in comparison .

The grid ones are tricky to golf.

LOC: 23

defmodule Aoc2024.Day08 do
  import Enum

  def part1(file), do: main(file, 1..1)
  def part2(file), do: main(file)

  def main(file, range \\ nil) do
    {grid, n} = file_to_charmap_grid(file)

    for {{x1, y1}, z1} <- grid, {{x2, y2}, z2} <- grid, z1 == z2, z1 != ?., x1 < x2 do
      map(range || -n..n, fn m -> {m * (x2 - x1), m * (y2 - y1)} end)
      |> flat_map(fn {dx, dy} -> [[x1 - dx, y1 - dy], [x2 + dx, y2 + dy]] end)
      |> filter(fn coor -> all?(coor, &(&1 in 0..(n - 1))) end)
    end
    |> reduce(MapSet.new(), &MapSet.union(&2, MapSet.new(&1)))
    |> MapSet.size()
  end

  def file_to_charmap_grid(f) do
    r = f |> File.read!() |> String.trim() |> String.split("\n") |> map(&String.to_charlist/1)
    {for({s, i} <- with_index(r), {x, j} <- with_index(s), into: %{}, do: {{i, j}, x}), length(r)}
  end
end

This one made me wish I could reach for the extra comprehension powers hinted at in the for let proposal.