Day 8: Resonant Collinearity

/* Advent of Code 2024
 * Day 08: Resonant Collinearity
 */

#import "Basic";
#import "File";
#import "Hash";
#import "Hash_Table";
#import "String";

Vector2_Int :: struct {
    x, y: int;
}

Vector2_Int_Set :: Table(
    Vector2_Int,
    void,
    (vector: Vector2_Int) -> u32 {
        return inline sdbm_hash(xx *vector, size_of(Vector2_Int));
    },
    (a: Vector2_Int, b: Vector2_Int) -> bool {
        return a.x == b.x && a.y == b.y;
    }
);

// Finds all valid antinodes, moving outwards from an antenna. This is called
// twice for each antenna pair.
find_antinodes :: (
    antenna: Vector2_Int,
    slope: Vector2_Int,
    width: int,
    height: int
) -> [] Vector2_Int {
    antinode := antenna;
    antinodes: [..] Vector2_Int;

    while true {
        array_add(*antinodes, antinode);

        antinode.x += slope.x;
        antinode.y += slope.y;

        if
            antinode.x < 0 || antinode.x >= width
            || antinode.y < 0 || antinode.y >= height
        {
            break;
        }
    }

    return antinodes;
}

// Adds the current antinode in a for loop to the correct tables. Saves some
// repetition lower down.
add_antinode :: () #expand {
    // The first antinode is on the antenna itself, so the second one is what is
    // relevant for part 1.
    if `it_index == 1 && !table_contains(*`antinodes_part_1, `it) {
        table_add(*`antinodes_part_1, `it, #run {});
    }

    if !table_contains(*`antinodes_part_2, `it) {
        table_add(*`antinodes_part_2, `it, #run {});
    }
}

main :: () {
    input, success := read_entire_file("inputs/day_08.txt");
    assert(success);

    lines := split(input, "\n");
    width := lines[0].count;
    height := lines.count - 1;

    antennas: Table(u8, [..] Vector2_Int);
    for line, y: lines {
        if line == "" {
            continue;
        }

        for char, x: line {
            if char == #char "." {
                continue;
            }

            antenna_group := table_find_pointer(*antennas, char);
            if antenna_group == null {
                new_group: [..] Vector2_Int;
                table_add(*antennas, char, new_group);
                antenna_group = table_find_pointer(*antennas, char);
            }

            array_add(antenna_group, .{x, y});
        }
    }

    antinodes_part_1, antinodes_part_2: Vector2_Int_Set;
    for antenna_group: antennas {
        for index_1: 0..antenna_group.count - 1 {
            for index_2: 0..antenna_group.count - 1 {
                if index_2 == index_1 {
                    continue;
                }

                antenna_1 := antenna_group[index_1];
                antenna_2 := antenna_group[index_2];

                for find_antinodes(
                    antenna_1,
                    .{antenna_1.x - antenna_2.x, antenna_1.y - antenna_2.y},
                    width,
                    height
                ) {
                    add_antinode();
                }

                for find_antinodes(
                    antenna_2,
                    .{antenna_2.x - antenna_1.x, antenna_2.y - antenna_1.y},
                    width,
                    height
                ) {
                    add_antinode();
                }
            }
        }

        array_free(antenna_group);
    }

    print(
        "Part 1: %\nPart 2: %\n",
        antinodes_part_1.count,
        antinodes_part_2.count
    );
}

import "utils" as utils;

let input = utils::get_input(8, false);

let grid = new_grid(input.split("\n").map(|line| line.to_chars()));

let antennas = #{};
for pos in grid.cell_positions() {
    let cell = grid.cell(pos).to_string();
    if cell == "." {
        continue;
    }
    let positions = antennas.get(cell) ?? [];
    positions.push(pos);
    antennas.set(cell, positions);
}

// PART 1
let antinodes = #{};
for frequency in antennas.keys() {
    let positions = antennas.get(frequency);
    for pair in positions.combinations(2) {
        let diff = new_point(pair[0].x - pair[1].x, pair[0].y - pair[1].y);
        for point in [pair[0] - diff, pair[0] + diff, pair[1] - diff, pair[1] + diff] {
            if point == pair[0] || point == pair[1] || !grid.is_valid(point) {
                continue;
            }
            antinodes.set(point.to_string(), true);
        }
    }
}

print(`part 1: ${antinodes.len()}`);

// PART 2
let antinodes = #{};
for frequency in antennas.keys() {
    let positions = antennas.get(frequency);
    for pair in positions.combinations(2) {
        let diff = new_point(pair[0].x - pair[1].x, pair[0].y - pair[1].y);
        for situation in 0..4 {
            let point = switch situation {
                0 | 1 => pair[0],
                2 | 3 => pair[1],
            };

            loop {
                if !grid.is_valid(point) {
                    break;
                }
                antinodes.set(point.to_string(), true);
                switch situation {
                    0 | 2 => point -= diff,
                    1 | 3 => point += diff,
                }
            }
        }
    }
}

print(`part 2: ${antinodes.len()}`);

pub fn part1(input: &PuzzleInput) -> String {
    let antennas = frequencies(&input.grid);
    let mut total = HashSet::new();

    for frequency in antennas {
        let coordinates = antenna_coordinates(&input.grid, frequency);
        let antinodes = antinodes(
            input.grid.width() as i32,
            input.grid.height() as i32,
            &coordinates,
        );

        total.extend(antinodes);
    }

    total.len().to_string()
}

pub fn frequencies(grid: &Grid2D<char>) -> HashSet<char> {
    grid.iter()
        // Don't forget to filter out the '#' signs in the test input,
        // otherwise those count as antennas too...
        .filter(|(_, c)| **c != '.' && **c != '#')
        .map(|(_, c)| c.clone())
        .collect()
}

pub fn antenna_coordinates(grid: &Grid2D<char>, antenna: char) -> HashSet<Coordinate> {
    grid.iter()
        .filter(|(_, c)| **c == antenna)
        .map(|(coord, _)| coord.clone())
        .collect()
}

pub fn antinode(a: &Coordinate, b: &Coordinate) -> [Coordinate; 2] {
    let dx = a.x - b.x;
    let dy = a.y - b.y;

    [
        Coordinate::new(a.x + dx as i32, a.y + dy as i32),
        Coordinate::new(b.x - dx as i32, b.y - dy as i32),
    ]
}

pub fn antinodes(w: i32, h: i32, coordinates: &HashSet<Coordinate>) -> HashSet<Coordinate> {
    coordinates
        .iter()
        .cloned()
        .combinations(2)
        .flat_map(|x| antinode(&x[0], &x[1]))
        .filter(|c| c.x >= 0 && c.x < w && c.y >= 0 && c.y < h)
        .collect()
}

The only change was to the antinode function.

pub fn antinode(a: &Coordinate, b: &Coordinate, width: i32, height: i32) -> Vec<Coordinate> {
    let dx = a.x - b.x;
    let dy = a.y - b.y;

    let mut result = Vec::new();

    for i in 0.. {
        let c = Coordinate::new(a.x + dx * i as i32, a.y + dy * i as i32);
        if c.x >= 0 && c.x < width && c.y >= 0 && c.y < height {
            result.push(c);
        } else {
            break;
        }
    }

    for i in 0.. {
        let c = Coordinate::new(b.x - dx * i as i32, b.y - dy * i as i32);
        if c.x >= 0 && c.x < width && c.y >= 0 && c.y < height {
            result.push(c);
        } else {
            break;
        }
    }

    result
}

I went a little over the top abstracting my code so both parts can reuse a single solve/2 function...

defmodule AdventOfCode.Solution.Year2024.Day08 do
  use AdventOfCode.Solution.SharedParse

  alias AdventOfCode.Grid, as: G

  @impl true
  def parse(input), do: G.from_input(input)

  def part1(grid), do: solve(grid, &Enum.slice(&1, 1, 1))
  def part2(grid), do: solve(grid)

  defp solve(grid, stream_limiter \\ &Function.identity/1) do
    grid
    |> antenna_groups()
    |> Enum.map(&antinode_streams/1)
    |> List.flatten()
    |> Enum.map(stream_limiter)
    |> Enum.flat_map(fn s -> Enum.take_while(s, &G.in_bounds?(grid, &1)) end)
    |> MapSet.new()
    |> MapSet.size()
  end

  defp antenna_groups(grid) do
    grid
    |> G.filter_cells(fn {_coords, char} -> char != ?. end)
    |> Enum.group_by(
      fn {_coords, char} -> char end,
      fn {coords, _char} -> coords end
    )
    |> Map.values()
  end

  # Produces pairs of streams that step outward from 2 antennae, forever
  defp antinode_streams(coords) do
    for {c1, i} <- Enum.with_index(coords), c2 <- Enum.drop(coords, i + 1) do
      diff_forwards = subtract(c2, c1)
      diff_backwards = invert(diff_forwards)

      [
        Stream.iterate(c2, &add(&1, diff_forwards)),
        Stream.iterate(c1, &add(&1, diff_backwards))
      ]
    end
  end

  defp add({x1, y1}, {x2, y2}), do: {x1 + x2, y1 + y2}
  defp subtract({x1, y1}, {x2, y2}), do: {x1 - x2, y1 - y2}
  defp invert({x, y}), do: {-x, -y}
end

#! /usr/bin/env racket
#lang racket

(require "common.rkt")

(module+ test
  (require rackunit))

;; return the antinodes for pairs p1 and p2
;; TODO: This could be cleaned up a lot so there's less repeated code
(define (antinodes p1 p2 [in-map '()] [repeat #f])
  ;; helper that can tell whether to add or subtract dx from x1 based on x1/x2
  (define (calc-new x1 x2 dx)
    (cond
      [(> x1 x2) (+ x1 dx)]
      [else (- x1 dx)]))
  ;; helper for part2, this could be removed if I cleaned things up
  (define (calc-dir x1 x2 dx)
    (cond
      [(> x1 x2) dx]
      [else (* dx -1)]))
  ;; helper for part2
  ;; returns a list of antinodes until the boundary of the map
  (define (calc-repeats i j di dj [lst '()])
    (cond
      [(out-of-bounds? in-map i j) lst]
      [else (calc-repeats (+ i di) (+ j dj) di dj (cons (list i j) lst))]))
  ;; get individual coordinates
  (let* ([i1 (first p1)]
         [j1 (second p1)]
         [i2 (first p2)]
         [j2 (second p2)]
         [di (abs (- i1 i2))]
         [dj (abs (- j1 j2))])
    (append
     ;; these are the regular antinodes
     (list (list (calc-new i1 i2 di) (calc-new j1 j2 dj))
           (list (calc-new i2 i1 di) (calc-new j2 j1 dj)))
     ;; if repeat, then we calculate the repeating ones, too
     (cond
       [repeat (append
                (calc-repeats i1 j1 (calc-dir i1 i2 di) (calc-dir j1 j2 dj))
                (calc-repeats i2 j2 (calc-dir i2 i1 di) (calc-dir j2 j1 dj)))]
       [else '()]))))

(module+ test
  (check-equal? (antinodes (list 3 4) (list 5 5))
                (list (list 1 3) (list 7 6))
                "Test antinodes: basic")
  (check-equal? (antinodes (list 0 4) (list 0 5))
                (list (list 0 3) (list 0 6))
                "Test antinodes: same i"))

(define (antenna-coords in-map)
  (for*/fold ([antenna-coords '()])
             ([i (length in-map)]
              [j (length (list-ref in-map i))])
    (let ([freq (map-ref in-map i j)])
      (cond
        [(not (equal? freq #\.)) (cons (list freq (list i j)) antenna-coords)]
        [else antenna-coords]))))

(define (day08/run-part01 in-map)
  (let* ([coords (antenna-coords in-map)]
         [freqs (list->set (map first coords))])
    ;; these isn't very efficient but oh well
    (set-count
     (list->set
      (for/fold ([antinds '()])
                ([freq (in-set freqs)])
        ;; get all the coordinates for antennas on freq
        (append (let ([freq-coords (map second (filter (lambda (p) (eq? (first p) freq)) coords))])
                  ;; calculate all antinodes, then filter out out-of-bounds ones
                  (filter (lambda (p) (not (out-of-bounds? in-map (first p) (second p))))
                          (for*/fold ([antinds '()])
                                     ([m (sub1 (length freq-coords))]
                                      [n (in-range (add1 m) (length freq-coords))])
                            (append (antinodes (list-ref freq-coords m) (list-ref freq-coords n)) antinds))))
                antinds))))))
(define (day08/run-part02 in-map)
  (let* ([coords (antenna-coords in-map)]
         [freqs (list->set (map first coords))])
    ;; these isn't very efficient but oh well
    (let ([x
           (list->set
            (for/fold ([antinds '()])
                      ([freq (in-set freqs)])
              ;; get all the coordinates for antennas on freq
              (append (let ([freq-coords (map second (filter (lambda (p) (eq? (first p) freq)) coords))])
                        ;; calculate all antinodes, then filter out out-of-bounds ones
                        (filter (lambda (p) (not (out-of-bounds? in-map (first p) (second p))))
                                (for*/fold ([antinds '()])
                                           ([m (sub1 (length freq-coords))]
                                            [n (in-range (add1 m) (length freq-coords))])
                                  (append (antinodes (list-ref freq-coords m) (list-ref freq-coords n) in-map #t) antinds))))
                      antinds)))])
      (set-count x))))

;; Test examples from the problem
(module+ test
  (check-equal? (day08/run-part01 (input->list (open-input-file "examples/day08_1.in")))  4 "Test part 1: simple")
  (check-equal? (day08/run-part01 (input->list (open-input-file "examples/day08_2.in"))) 14 "Test part 1: less simple")
  (check-equal? (day08/run-part02 (input->list (open-input-file "examples/day08_3.in")))  9 "Test part 2: simple")
  (check-equal? (day08/run-part02 (input->list (open-input-file "examples/day08_2.in"))) 34 "Test part 2: less simple")
  (check-equal? (day08/run-part02 (input->list (open-input-file "examples/day08_1.in")))  8 "Test part 2: ???"))

;; Run against my input and print the results
(module+ main
  (let* ([in-port (open-input-file "inputs/day08.in")]
         [in-map (input->list in-port)]
         [part1 (day08/run-part01 in-map)]
         [part2 (day08/run-part02 in-map)])
    (printf "Part 1: ~a, Part 2: ~a\n" part1 part2)))

Lots of nested loops here! Well we're walking though a grid, so that's one for each axis to start. My solution assembles an object with a different property key corresponding to each frequency char in the map. Every time it finds one it hasn't seen before, it begins a second walk (nesting two more loops) from that point forward to identify the locations of all antennas with that frequency.

Once all the locations have been cataloged, it loops through them to find the antinodes for each pair associated with the same frequency. So, outer loop iterates through frequencies; next level walks through each position within that set; the third level advances through all of the subsequent positions following whichever is being considered in the level above. At this level I have two positions to compare so I grab their row/column deltas to figure out the slope of the line connecting them.

For Part 1 I just evaluate the validity of two possible antinode positions: posA - delta, and posB + delta. If either is in bounds I push it to an array to track unique positions. To speed up the uniqueness check I'm actually casting these to strings first. For Part 2 I added another loop with a multiplier that increases each iteration. I keep generating new possible antinode positions, posA - delta * multiplier and posB + delta * multiplier until both are out of bounds. And I have an ugly hack to count the initial positions as antinodes, if isPart2 is true only.

type InputData = string[][];
type Position = [number, number];
type Frequencies = Record<string, Position[]>;

function formatInput(input: string): InputData {
  return input
    .trim()
    .split('\n')
    .map(line => line.split(''));
}

export function run(input: string): string[] {
  const data = formatInput(input);

  const countUniqueAntinodes = (map: InputData, isPart2 = false): number => {
    const frequencies: Frequencies = {};
    for (let row = 0; row < map.length; row++) {
      for (let col = 0; col < map[0].length; col++) {
        if (map[row][col] !== '.' && !Object.prototype.hasOwnProperty.call(frequencies, map[row][col])) {
          frequencies[map[row][col]] = [];
          for (let seekRow = row; seekRow < map.length; seekRow++) {
            for (let seekCol = seekRow === row ? col : 0; seekCol < map[0].length; seekCol++) {
              if (map[seekRow][seekCol] === map[row][col]) {
                frequencies[map[row][col]].push([seekRow, seekCol]);
              }
            }
          }
        }
      }
    }
    const antinodePositions: string[] = [];
    for (const frequency in frequencies) {
      for (let i = 0; i < frequencies[frequency].length; i++) {
        for (let j = i + 1; j < frequencies[frequency].length; j++) {
          const [firstRow, firstCol] = frequencies[frequency][i];
          const [secondRow, secondCol] = frequencies[frequency][j];
          const [rowChange, colChange] = [secondRow - firstRow, secondCol - firstCol];
          for (let multiplier = 1, invalidPositionCount = 0; invalidPositionCount < 2; multiplier++) {
            invalidPositionCount = 0;
            const possiblePositions = [
              [firstRow - rowChange * multiplier, firstCol - colChange * multiplier],
              [secondRow + rowChange * multiplier, secondCol + colChange * multiplier],
            ];
            if (isPart2) {
              possiblePositions.push([firstRow, firstCol], [secondRow, secondCol]);
            }
            for (const [row, col] of possiblePositions) {
              if (row >= 0 && row < map.length && col >= 0 && col < map[0].length) {
                const positionAsString = `[${row}, ${col}]`;
                if (!antinodePositions.includes(positionAsString)) {
                  antinodePositions.push(positionAsString);
                }
              } else {
                invalidPositionCount++;
              }
            }
            if (!isPart2) {
              break;
            }
          }
        }
      }
    }
    return antinodePositions.length;
  };

  return [`${countUniqueAntinodes(data)}`, `${countUniqueAntinodes(data, true)}`];
}

from collections import defaultdict
import itertools
import sys

def antinodes_in_bounds(w: int, h: int, z1: complex, z2: complex) -> list[complex]:
    a1 = 2 * z1 - z2
    a2 = 2 * z2 - z1
    return [a for a in (a1, a2) if 0 <= a.real < w and 0 >= a.imag > -h]

w, h = 0, 0
freqs = defaultdict[str, list[complex]](list)
for b, line in enumerate(sys.stdin):
    w = len(line.strip())
    h += 1
    for a, char in enumerate(line.strip()):
        if char != '.':
            freqs[char].append(complex(a, -b))

antinodes = set()
for antennae in freqs.values():
    for z1, z2 in itertools.combinations(antennae, 2):
        antinodes.update(antinodes_in_bounds(w, h, z1, z2))

print(len(antinodes))

from collections import defaultdict
import itertools
import sys

def antinodes_in_bounds(w: int, h: int, z1: complex, z2: complex) -> list[complex]:
    # place bounds on t for the parametrized line f(t) = (z2 - z1) * t + z1
    top = -z1.imag / (z2 - z1).imag
    bottom = (-(h - 1) - z1.imag) / (z2 - z1).imag
    left = -z1.real / (z2 - z1).real
    right = ((w - 1) - z1.real) / (z2 - z1).real
    t1, t2 = map(int, sorted((top, bottom, left, right))[1:3])

    # compute f(t) at integer values of t in [t1, t2]
    return [(z2 - z1) * t + z1 for t in range(t1, t2 + 1)]

w, h = 0, 0
freqs = defaultdict[str, list[complex]](list)
for b, line in enumerate(sys.stdin):
    w = len(line.strip())
    h += 1
    for a, char in enumerate(line.strip()):
        if char != '.':
            freqs[char].append(complex(a, -b))

antinodes = set()
for antennae in freqs.values():
    for z1, z2 in itertools.combinations(antennae, 2):
        antinodes.update(antinodes_in_bounds(w, h, z1, z2))

print(len(antinodes))