Day 8: Resonant Collinearity

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

1 point

Kotlin

A bit late to the party, but hereโ€™s my solution. I donโ€™t know, if you even need to search for the smallest integer vector in the same direction in part 2, but I did it anyway.

Code:
import kotlin.math.abs
import kotlin.math.pow

fun main() {
    fun part1(input: List<String>): Int {
        val inputMap = Day08Map(input)
        return inputMap.isoFrequencyNodeVectorsByLocations
            .flatMap { (location, vectors) ->
                vectors.map { (2.0 scaleVec it) + location }
            }
            .toSet()
            .count { inputMap.isInGrid(it) }
    }

    fun part2(input: List<String>): Int {
        val inputMap = Day08Map(input)
        return buildSet {
            inputMap.isoFrequencyNodeVectorsByLocations.forEach { (location, vectors) ->
                vectors.forEach { vector ->
                    var i = 0.0
                    val scaledDownVector = smallestIntegerVectorInSameDirection2D(vector)
                    while (inputMap.isInGrid(location + (i scaleVec scaledDownVector))) {
                        add(location + (i scaleVec scaledDownVector))
                        i++
                    }
                }
            }
        }.count()
    }

    val testInput = readInput("Day08_test")
    check(part1(testInput) == 14)
    check(part2(testInput) == 34)

    val input = readInput("Day08")
    part1(input).println()
    part2(input).println()
}

tailrec fun gcdEuclid(a: Int, b: Int): Int =
    if (b == 0) a
    else if (a == 0) b
    else if (a > b) gcdEuclid(a - b, b)
    else gcdEuclid(a, b - a)

fun smallestIntegerVectorInSameDirection2D(vec: VecNReal): VecNReal {
    assert(vec.dimension == 2)  // Only works in two dimensions.
    assert(vec == vec.roundComponents())  // Only works on integer vectors.

    return (gcdEuclid(abs(vec[0].toInt()), abs(vec[1].toInt())).toDouble().pow(-1) scaleVec vec).roundComponents()
}

class Day08Map(input: List<String>): Grid2D<Char>(input.reversed().map { it.toList() }) {
    init {
        transpose()
    }

    val isoFrequencyNodesLocations = asIterable().toSet().filter { it != '.' }.map { frequency -> asIterable().indicesWhere { frequency == it } }
    val isoFrequencyNodeVectorsByLocations = buildMap {
        isoFrequencyNodesLocations.forEach { isoFrequencyLocationList ->
            isoFrequencyLocationList.mapIndexed { index, nodeLocation ->
                this[VecNReal(nodeLocation)] = isoFrequencyLocationList
                    .slice((0 until index) + ((index + 1)..isoFrequencyLocationList.lastIndex))
                    .map { VecNReal(it) - VecNReal(nodeLocation) }
            }
        }
    }
}

permalink
report
reply
1 point

J

J really doesnโ€™t have hashes! Or anything like hashes! And itโ€™s really annoying after a while!

What it does have is automatic internal optimization via hashing of the โ€œindex ofโ€ operation m i. n where m is a fixed list (the object being searched) and n is the query, which can vary. But as soon as you update m the hash table is thrown away. And you still have to choose some kind of numeric key, or store a list of boxed pairs where the first coordinate is the key โ€“ effectively this is an old-style Lisp association list, but with extra steps because you have to use boxing to defeat Jโ€™s automatic array concatenation and reshaping. If you want non-cubical shapes (J calls these โ€œragged arraysโ€), or heterogeneous lists, you end up writing u &amp;.> a lot โ€“ this means โ€œunbox, apply u then reboxโ€. J arrays are required to be rectangular and homogeneous, but a boxed anything is a single atom just like a number is.

Itโ€™s just a really bad choice of language if you want data structures other than essentially-cubical arrays. On the other hand, once you beat the list manipulation primitives into producing your 1970s Lisp data structure of choice, the rest of the program is as nice as it usually is.

data_file_name =: '8.data'
grid =: ,. > cutopen fread data_file_name
'rsize csize' =: $ grid
inbounds =: monad : '(*/ y >: 0 0) * (*/ y &lt; rsize, csize)'
antenna_types =: (#~ (~: &amp; '.')) ~. , grid
NB. list_antennas gives a list of boxed matrices of shape 2 n_k in cell k, where
NB. n_k is the number of antennas of type k and the rows are coordinates of that type
list_antennas =: monad define
   antenna_locs =. (# antenna_types) $ a:
   for_r. i. rsize do.
      for_c. i. csize do.
         cell =. y {~ &lt;(r, c)
         if. '.' ~: cell do.
            at =. antenna_types i. cell
            antenna_locs =. ((&lt;(r, c)) ,&amp;.> at { antenna_locs) at} antenna_locs
         end.
      end.
   end.
   NB. _2 ]\ l reshapes l into length 2 rows without finding its length ahead of time
   (_2 &amp; (]\))&amp;.> antenna_locs
)
NB. a1 pair_antinodes a2 gives the two antinodes from that pair
pair_antinodes =: dyad : '(#~ inbounds"1) ((2 * x) - y) ,: (2 * y) - x'
NB. if u is a symmetric dyad expecting rank 1 arguments, u on_pairs is a monad
NB. expecting a list of rank 1 arguments, and yields the concatenation of x u y
NB. where (x, y) is drawn from the (unordered) pairs of elements of the argument
NB. see page_pairs in 5.ijs for a non-point-free version of pair enumeration
on_pairs =: adverb define
   ; @: (&lt; @: u/"2) @: ({~ (; @: (&lt; @: (,~"0 i.)"0) @: i. @: #))
)
NB. antinodes antennas gives a list (may contain duplicates) of all the antinodes from
NB. that set of antennas
antinodes =: pair_antinodes on_pairs
NB. on_antennas concatenates and uniquifies result lists from all antennas
on_antennas =: adverb define
   ~. @: ; @: (u &amp;.>) @: list_antennas
)
result1 =: # antinodes on_antennas grid

NB. a1 res_antinodes a2 gives the list of antinodes from that pair with resonance
res_antinodes =: dyad define
   step =. (% +./) x - y
   NB. lazy: max_steps doesn't take location of x into account
   max_steps =. &lt;. (rsize % 1 >. | 0 { step) &lt;. (csize % 1 >. 1 { step)
   (#~ inbounds"1) x +"1 step *"1 0 i: max_steps
)
result2 =: # res_antinodes on_pairs on_antennas grid
permalink
report
reply
1 point

Raku

Solution
sub MAIN($input) {
    my $file = open $input;
    my @map = $file.slurp.lines>>.comb>>.List.List;
    my %freqs;
    for 0..^@map.elems -> $row {
        for 0..^@map[0].elems -> $col {
            if @map[$row; $col] ne "." {
                my $freq = @map[$row; $col];
                %freqs{$freq} = [] if %freqs{$freq}:!exists;
                %freqs{$freq}.push(($row, $col));
            }
        }
    }
    my %antinodes is SetHash;
    for %freqs.kv -> $freq, @locations {
        for (0..^@locations.elems) X (0..^@locations.elems) -> ($loc1, $loc2) {
            next if $loc1 == $loc2;
            my @base = @locations[$loc1].List;
            my @vector = @locations[$loc2].List Z- @base;
            my @antinode1 = @base Z+ @vector.map(* * 2);
            %antinodes{@antinode1.List.raku}++ if point-is-in-map(@map, @antinode1);
            my @antinode2 = @base Z+ @vector.map(* * -1);
            %antinodes{@antinode2.List.raku}++ if point-is-in-map(@map, @antinode2);
        }
    }
    my $part1-solution = %antinodes.elems;
    say "part 1: $part1-solution";


    my %antinodes2 is SetHash;
    for %freqs.kv -> $freq, @locations {
        for (0..^@locations.elems) X (0..^@locations.elems) -> ($loc1, $loc2) {
            next if $loc1 == $loc2;
            my @base = @locations[$loc1].List;
            my @vector = @locations[$loc2].List Z- @base;
            # make integer unit-ish vector
            for 2..@vector[0] -> $divisor {
                if @vector[0] %% $divisor and @vector[1] %% $divisor {
                    @vector[0] = @vector[0] div $divisor;
                    @vector[1] = @vector[1] div $divisor;
                }
            }
            for 0..max(@map.elems, @map[0].elems) -> $length {
                my @antinode = @base Z+ @vector.map(* * $length);
                if point-is-in-map(@map, @antinode) {
                    %antinodes2{@antinode.List.raku}++ 
                } else {
                    last
                }
            }
            for 1..max(@map.elems, @map[0].elems) -> $length {
                my @antinode = @base Z+ @vector.map(* * -$length);
                if point-is-in-map(@map, @antinode) {
                    %antinodes2{@antinode.List.raku}++ 
                } else {
                    last
                }
            }
        }
    }
    my $part2-solution = %antinodes2.elems;
    say "part 2: $part2-solution";
}

sub point-is-in-map(@map, @point) {
    return False if !(0 <= @point[0] < @map.elems);
    return False if !(0 <= @point[1] < @map[0].elems);
    return True;
}
permalink
report
reply
2 points
*

Lisp

Could probably just write points right to the results instead of to an intermediate list, but it runs instantly, so my motivation to do so was low.

Code
(defun p1-process-line (line)
   (to-symbols line 'advt2024-d8))
  
(defun count-results (results)
  (loop for i from 0 below (array-total-size results)
        count (row-major-aref results i)))

(defun place-annode (pos results)
  (let ((x (first pos)) (y (second pos)))
    (when (in-map results x y) 
      (setf (aref results y x) t))))

(defun create-annodes-p1 (x1 y1 x2 y2)
  (let ((delta-x (- x2 x1)) (delta-y (- y2 y1)))
    (list (list (- x1 delta-x) (- y1 delta-y)) (list (+ x2 delta-x) (+ y2 delta-y)))))

(defun place-annodes (positions results create-annodes)
  (when positions
     (loop with a = (car positions)
           with x1 = (first a)
           with y1 = (second a)
           for b in (cdr positions)
           for ans = (funcall create-annodes x1 y1 (first b) (second b))
           do (dolist (a ans) (place-annode a results)))
     (place-annodes (cdr positions) results create-annodes)))

(defun place-all-annodes (xmits map &optional (create-annodes #'create-annodes-p1))
  (let ((results (make-array (array-dimensions map) :element-type 'boolean :initial-element nil)))
    (loop for k being the hash-key of xmits
          do (place-annodes (gethash k xmits) results create-annodes))
    results))

(defun find-transmitters (map)
  "look throught the map and record where the transmitters are in a hash map"
  (let ((h (make-hash-table)))
    (destructuring-bind (rows cols) (array-dimensions map)
      (loop for j from 0 below rows
            do (loop for i from 0 below cols
                     for v = (aref map j i)
                     unless (eql v '|.|)
                       do (push (list i j) (gethash v h))
                     )))
    h))

(defun run-p1 (file) 
  (let* ((map (list-to-2d-array (read-file file #'p1-process-line))))
    (count-results (place-all-annodes (find-transmitters map) map))
    ))

(defun create-annodes-2 (x1 y1 x2 y2 map)
  (destructuring-bind (rows cols) (array-dimensions map)
    (let* ((m (/ (- y2 y1) (- x2 x1) ))
           (b (- y2 (* m x2))))
      (loop for x from 0 below cols
            for y = (+ b (* x m))
            for r = (nth-value 1 (floor y))
            when (and (= r 0) (>= y 0) (< y rows))
              collect (list x y)))))

(defun run-p2 (file) 
  (let* ((map (list-to-2d-array (read-file file #'p1-process-line))))
    (count-results (place-all-annodes (find-transmitters map) map
                                      (lambda (x1 y1 x2 y2)
                                        (create-annodes-2 x1 y1 x2 y2 map))))))

permalink
report
reply
1 point

Rust

Pretty happy with my solution today. I took my time today as it was a bit of a slow day and did it in Rust instead of python. Having proper Vec2 types is very nice.

Tap for spoiler
use std::{collections::HashMap, error::Error, io::Read};

use glam::{IVec2, Vec2};

fn permutations_of_size_two(antennas: &[Vec2]) -> Vec<[&Vec2; 2]> {
    let mut permutations = vec![];
    for (i, antenna) in antennas.iter().enumerate() {
        for j in 0..antennas.len() {
            if i == j {
                continue;
            }
            permutations.push([antenna, &antennas[j]])
        }
    }
    permutations
}

fn main() -> Result<(), Box<dyn Error>> {
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input)?;

    let height = input.lines().count() as i32;
    let width = input.lines().next().unwrap().len() as i32;

    let antenna_positions = input
        .lines()
        .enumerate()
        .flat_map(|(y, l)| 
            l.chars().enumerate().map(move |(x, c)| (Vec2::new(x as f32, y as f32), c))
        )
        .filter(|(_v, c)| *c != '.')
        .fold(HashMap::new(), |mut acc: HashMap<char, Vec<_>> , current| {
            acc.entry(current.1).or_default().push(current.0);
            acc
        });

    let mut antinodes = vec![];
    for (_c, antennas) in antenna_positions {
        let perms = permutations_of_size_two(&antennas);
        for [first, second] in perms {
            let mut i = 1.;
            loop {
                let antinode = (first + (second-first) * i).round();
                if (0..height).contains(&(antinode.x as i32)) &&
                    (0..width).contains(&(antinode.y as i32)) {
                        antinodes.push(antinode);
                } else {
                    break;
                }
                i += 1.;
            }
        }
    }

    let mut antinode_count = 0;
    let map = input
        .lines()
        .enumerate()
        .map(|(y, l)| 
            l.chars().enumerate().map(|(x, c)| {
                if antinodes.contains(&Vec2::new(x as f32, y as f32)) {
                    println!("({x},{y})");
                    antinode_count += 1;
                    return '#';
                }
                c
            }).collect::<String>()
        )
        .collect::<Vec<_>>()
        .join("\n");

    println!("{map}");
    println!("{antinode_count}");

    Ok(())
}
permalink
report
reply

Advent Of Code

!advent_of_code@programming.dev

Create post

An unofficial home for the advent of code community on programming.dev!

Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

AoC 2024

Solution Threads

M T W T F S S
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25

Rules/Guidelines

  • Follow the programming.dev instance rules
  • Keep all content related to advent of code in some way
  • If what youre posting relates to a day, put in brackets the year and then day number in front of the post title (e.g. [2024 Day 10])
  • When an event is running, keep solutions in the solution megathread to avoid the community getting spammed with posts

Relevant Communities

Relevant Links

Credits

Icon base by Lorc under CC BY 3.0 with modifications to add a gradient

console.log('Hello World')

Community stats

  • 479

    Monthly active users

  • 109

    Posts

  • 1.1K

    Comments