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
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
Rust
For the first time, I can post my solution, because I actually solved it on the day :D Probably not the cleanest or optimal solution, but it does solve the problem.
Very long, looking forward to someone solving it in 5 lines of unicode :D
#[cfg(test)] mod tests { fn get_frequences(input: &str) -> Vec<char> { let mut freq = vec![]; for char in input.chars() { if char == '.' { continue; } if !freq.contains(&char) { freq.push(char); } } freq } fn find_antennas(board: &Vec<Vec<char>>, freq: char) -> Vec<(isize, isize)> { let mut antennas = vec![]; for (i, line) in board.iter().enumerate() { for (j, char) in line.iter().enumerate() { if *char == freq { antennas.push((i as isize, j as isize)); } } } antennas } fn calc_antinodes(first: &(isize, isize), second: &(isize, isize)) -> Vec<(isize, isize)> { let deltax = second.0 - first.0; let deltay = second.1 - first.1; if deltax == 0 && deltay == 0 { return vec![]; } vec![ (first.0 - deltax, first.1 - deltay), (second.0 + deltax, second.1 + deltay), ] } #[test] fn test_calc_antinodes() { let expected = vec![(0, -1), (0, 2)]; let actual = calc_antinodes(&(0, 0), &(0, 1)); for i in &expected { assert!(actual.contains(i)); } let actual = calc_antinodes(&(0, 1), &(0, 0)); for i in &expected { assert!(actual.contains(i)); } } fn calc_all_antinodes(board: &Vec<Vec<char>>, freq: char) -> Vec<(isize, isize)> { let antennas = find_antennas(&board, freq); let mut antinodes = vec![]; for (i, first) in antennas.iter().enumerate() { for second in antennas[i..].iter() { antinodes.extend(calc_antinodes(first, second)); } } antinodes } fn prune_nodes( nodes: &Vec<(isize, isize)>, height: isize, width: isize, ) -> Vec<(isize, isize)> { let mut pruned = vec![]; for node in nodes { if pruned.contains(node) { continue; } if node.0 < 0 || node.0 >= height { continue; } if node.1 < 0 || node.1 >= width { continue; } pruned.push(node.clone()); } pruned } fn print_board(board: &Vec<Vec<char>>, pruned: &Vec<(isize, isize)>) { for (i, line) in board.iter().enumerate() { for (j, char) in line.iter().enumerate() { if pruned.contains(&(i as isize, j as isize)) { print!("#"); } else { print!("{char}"); } } println!(); } } #[test] fn day8_part1_test() { let input: String = std::fs::read_to_string("src/input/day_8.txt").unwrap(); let frequencies = get_frequences(&input); let board = input .trim() .split('\n') .map(|line| line.chars().collect::<Vec<char>>()) .collect::<Vec<Vec<char>>>(); let mut all_nodes = vec![]; for freq in frequencies { let nodes = calc_all_antinodes(&board, freq); all_nodes.extend(nodes); } let height = board.len() as isize; let width = board[0].len() as isize; let pruned = prune_nodes(&all_nodes, height, width); println!("{:?}", pruned); print_board(&board, &pruned); println!("{}", pruned.len()); // 14 in test } fn calc_antinodes2(first: &(isize, isize), second: &(isize, isize)) -> Vec<(isize, isize)> { let deltax = second.0 - first.0; let deltay = second.1 - first.1; if deltax == 0 && deltay == 0 { return vec![]; } let mut nodes = vec![]; for n in 0..50 { nodes.push((first.0 - deltax * n, first.1 - deltay * n)); nodes.push((second.0 + deltax * n, second.1 + deltay * n)); } nodes } fn calc_all_antinodes2(board: &Vec<Vec<char>>, freq: char) -> Vec<(isize, isize)> { let antennas = find_antennas(&board, freq); let mut antinodes = vec![]; for (i, first) in antennas.iter().enumerate() { for second in antennas[i..].iter() { antinodes.extend(calc_antinodes2(first, second)); } } antinodes } #[test] fn day8_part2_test() { let input: String = std::fs::read_to_string("src/input/day_8.txt").unwrap(); let frequencies = get_frequences(&input); let board = input .trim() .split('\n') .map(|line| line.chars().collect::<Vec<char>>()) .collect::<Vec<Vec<char>>>(); let mut all_nodes = vec![]; for freq in frequencies { let nodes = calc_all_antinodes2(&board, freq); all_nodes.extend(nodes); } let height = board.len() as isize; let width = board[0].len() as isize; let pruned = prune_nodes(&all_nodes, height, width); println!("{:?}", pruned); print_board(&board, &pruned); println!("{}", pruned.len()); } }
Any solution that solves the problem is a good solution :D
Haskell
I overslept 26 minutes (AoC starts at 06:00 here) which upsets me more than it should.
I thought this one was going to be hard on performance or memory but it was surprisingly easy.import Control.Arrow hiding (first, second) import Data.Bifunctor import Data.Array.Unboxed (UArray) import qualified Data.List as List import qualified Data.Set as Set import qualified Data.Array.Unboxed as Array parse :: String -> UArray (Int, Int) Char parse s = Array.listArray ((1, 1), (n, m)) . filter (/= '\n') $ s :: UArray (Int, Int) Char where n = takeWhile (/= '\n') >>> length $ s m = List.filter (== '\n') >>> length >>> pred $ s groupSnd:: Eq b => (a, b) -> (a', b) -> Bool groupSnd = curry (uncurry (==) <<< snd *** snd) cartesianProduct xs ys = [(x, y) | x <- xs, y <- ys] calculateAntitone ((y1, x1), (y2, x2)) = (y1 + dy, x1 + dx) where dy = y1 - y2 dx = x1 - x2 antennaCombinations = Array.assocs >>> List.filter (snd >>> (/= '.')) >>> List.sortOn snd >>> List.groupBy groupSnd >>> map (map fst) >>> map (\ xs -> cartesianProduct xs xs) >>> map (filter (uncurry (/=))) part1 a = antennaCombinations >>> List.concatMap (map calculateAntitone) >>> List.filter (Array.inRange (Array.bounds a)) >>> Set.fromList >>> Set.size $ a calculateAntitones ((y1, x1), (y2, x2)) = iterate (bimap (+dy) (+dx)) (y1, x1) where dy = y1 - y2 dx = x1 - x2 part2 a = antennaCombinations >>> List.map (map calculateAntitones) >>> List.concatMap (List.concatMap (takeWhile (Array.inRange (Array.bounds a)))) >>> Set.fromList >>> Set.size $ a main = getContents >>= print . (part1 &&& part2) . parse
D’oh. Computing antinodes in a single direction and permuting pairs is a much neater approach that what I did!
Haskell
Not a very pretty solution today, I’m afraid.
import Control.Arrow import Control.Monad import Data.Biapplicative import Data.Ix import Data.Map (Map) import Data.Map qualified as Map import Data.Set qualified as Set type Coords = (Int, Int) readInput :: String -> Map Coords Char readInput s = Map.fromAscList [ ((i, j), c) | (i, l) <- zip [0 ..] (lines s), (j, c) <- zip [0 ..] l ] (.+.), (.-.) :: Coords -> Coords -> Coords (.+.) = join biliftA2 (+) (.-.) = join biliftA2 (-) part1, part2 :: (Coords -> Bool) -> (Coords, Coords) -> [Coords] part1 valid (p1, p2) = let s = p2 .-. p1 in filter valid [p1 .-. s, p2 .+. s] part2 valid (p1, p2) = let (si, sj) = p2 .-. p1 d = gcd si sj s = (si `div` d, sj `div` d) in takeWhile valid (iterate (.+. s) p1) ++ takeWhile valid (drop 1 $ iterate (.-. s) p2) pairs (x : xs) = map (x,) xs ++ pairs xs pairs _ = [] main = do input <- readInput <$> readFile "input08" let antennas = Map.filter (/= '.') input antennaGroups = Map.foldrWithKey (\p c m -> Map.insertWith (++) c [p] m) Map.empty antennas valid = inRange . (Set.findMin &&& Set.findMax) $ Map.keysSet input antiNodes model = Set.fromList . concatMap (concatMap (model valid) . pairs) $ antennaGroups print . Set.size $ antiNodes part1 print . Set.size $ antiNodes part2
Whaaat? It is possible to declare mutliple signatures on one line? 🤯
Does that function (.+.
) add tuples/coordinates?Yup, that’s right! The function monad is a bit of a mind-bender, but
(join f) x == f x x
is a useful thing to remember.This is so cool, it’s going to replace the lambda in my function pipeline for calculating pairs.
BTW, for more in-depth vector stuff I usually use the Linear package.
Uiua
Adapting the part one solution for part two took me longer than part one did today, but I didn’t want to change much anymore.
I even got scolded by the interpreter to split the evaluating line onto multiple ones because it got too long.
Can’t say it’s pretty but it does it’s job ^^’Run with example input here
PartOne ← ( &rs ∞ &fo "input-8.txt" ⟜(▽¬∈".\n".◴) ⊜∘≠@\n. :¤⟜(:¤-1△) ≡(□⊚⌕) ◴/◇⊂⍚(≡(-:⟜-°⊟)⧅≠2) ⧻▽¬:⊙(/+⍉+)⟜⊓><,0 ) PartTwo ← ( &rs ∞ &fo "input-8.txt" ⟜(▽¬∈".\n".◴⟜¤ ▽:⟜≡(>1⧻⊚⌕) ) ⊜∘≠@\n. :¤⟜(:¤-1△) ≡(□⊚⌕) ⊸⍚( ⧅≠2⊙¤ ≡(:¤⟜-°⊟ ⍢(⊙⊂⟜-⊙⊸⊢ | ⋅(=0/++⊓><,0⊢)) □⊙◌◌ ) ) ◴/◇⊂/◇⊂ ⧻▽¬:⊙(/+⍉+)⟜⊓><,0 ) &p "Day 8:" &pf "Part 1: " &p PartOne &pf "Part 2: " &p PartTwo
C#
public class Day08 : Solver { private ImmutableArray<string> data; private int width, height; public void Presolve(string input) { data = input.Trim().Split("\n").ToImmutableArray(); width = data[0].Length; height = data.Length; } public string SolveFirst() { Dictionary<char, List<(int, int)>> antennae = []; HashSet<(int, int)> antinodes = []; for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { if ('.' == data[j][i]) continue; antennae.TryAdd(data[j][i], []); foreach (var (oi, oj) in antennae[data[j][i]]) { int di = i - oi; int dj = j - oj; int ai = i + di; int aj = j + dj; if (ai >= 0 && aj >= 0 && ai < width && aj < height) { antinodes.Add((ai, aj)); } ai = oi - di; aj = oj - dj; if (ai >= 0 && aj >= 0 && ai < width && aj < height) { antinodes.Add((ai, aj)); } } antennae[data[j][i]].Add((i, j)); } } return antinodes.Count.ToString(); } public string SolveSecond() { Dictionary<char, List<(int, int)>> antennae = []; HashSet<(int, int)> antinodes = []; for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { if ('.' == data[j][i]) continue; antennae.TryAdd(data[j][i], []); foreach (var (oi, oj) in antennae[data[j][i]]) { int di = i - oi; int dj = j - oj; for (int ai = i, aj = j; ai >= 0 && aj >= 0 && ai < width && aj < height; ai += di, aj +=dj) { antinodes.Add((ai, aj)); } for (int ai = oi, aj = oj; ai >= 0 && aj >= 0 && ai < width && aj < height; ai -= di, aj -=dj) { antinodes.Add((ai, aj)); } } antennae[data[j][i]].Add((i, j)); } } return antinodes.Count.ToString(); } }
Dart
This really does feel like a weekend break this year, maybe Eric and co have begun to realise that family time is more precious than work time :-)
import 'dart:math'; import 'package:more/more.dart'; solve(List<String> lines, int min, int max) { var map = ListMultimap<String, Point<int>>(); for (var r in lines.indices()) { for (var ci in lines[r].split('').indexed()) { if (ci.value != '.') map[ci.value].add(Point(ci.index, r)); } } var anti = <Point<int>>{}; for (var k in map.keys) { for (var p in map[k].combinations(2, repetitions: false)) { var diff = p.last - p.first; for (var m in min.to(max)) { anti.addAll([p.first - diff * m, p.last + diff * m]); } } } return anti.count((e) => e.x.between(0, lines.first.length - 1) && e.y.between(0, lines.length - 1)); } part1(List<String> lines) => solve(lines, 1, 2); part2(List<String> lines) => solve(lines, 0, 50);
maybe Eric and co have begun to realise that family time is more precious than work time
Last year the difficulty was fluctuating from 0 to 100 each day.
This year all problems so far are suspiciously easy. Maybe the second half of the month will be extra hard?Maybe we’ve been good all year :-)
Julia
I was surprised when my solution worked for part 2 since I thought you also had to include fractions of antenna distances, but apparently not.
Code
function readInput(inputFile::String)::Matrix{Char} f = open(inputFile,"r") lines::Vector{String} = readlines(f) close(f) cityMap = Matrix{Char}(undef,length(lines),length(lines[1])) for (i,l) in enumerate(lines) cityMap[i,:] = collect(l) end return cityMap end function getAntennaLocations(cityMap::Matrix{Char})::Dict antennaLocations = Dict{Char,Vector{Vector{Int}}}() for l=1 : size(cityMap)[1] for c=1 : size(cityMap)[2] cityMap[l,c]=='.' ? continue : nothing if !haskey(antennaLocations,cityMap[l,c]) antennaLocations[cityMap[l,c]] = [] end push!(antennaLocations[cityMap[l,c]],[l,c]) end end return antennaLocations end function countAntinodes(cityMap::Matrix{Char},antLoc::Dict{Char,Vector{Vector{Int}}},withHarmonics::Bool)::Int #antLoc: antenna locations lBounds = 1:size(cityMap)[1]; cBounds = 1:size(cityMap)[2] anodeLocs::Matrix{Bool} = zeros(size(cityMap)) for key in keys(antLoc) for i=1 : length(antLoc[key]) withHarmonics&&length(antLoc[key])>1 ? anodeLocs[antLoc[key][i][1],antLoc[key][i][2]]=1 : nothing #add antenna locations as antinodes #should also add fractions of antenna distances, but works without for j=i+1 : length(antLoc[key]) harmonic::Int = 1 while true n1l = antLoc[key][i][1]+harmonic*(antLoc[key][i][1]-antLoc[key][j][1]) n1c = antLoc[key][i][2]+harmonic*(antLoc[key][i][2]-antLoc[key][j][2]) n2l = antLoc[key][j][1]+harmonic*(antLoc[key][j][1]-antLoc[key][i][1]) n2c = antLoc[key][j][2]+harmonic*(antLoc[key][j][2]-antLoc[key][i][2]) if n1l in lBounds && n1c in cBounds anodeLocs[n1l,n1c] = 1 end if n2l in lBounds && n2c in cBounds anodeLocs[n2l,n2c] = 1 end withHarmonics ? nothing : break !(n1l in lBounds) && !(n1c in cBounds) && !(n2l in lBounds) && !(n2c in cBounds) ? break : harmonic+=1 end end end end return sum(anodeLocs) end @info "Part 1" println("antinode count $(countAntinodes(getAntennaLocations(readInput("day08Input"))),false)") @info "Part 2" println("antinode count $(countAntinodes(getAntennaLocations(readInput("day08Input"))),faltrue)")
python
solution
import aoc def setup(): lines = aoc.get_lines(8, stripped=True) ll = len(lines) fm = {f: [(x, y) for y, r in enumerate(lines) for x, z in enumerate(r) if z == f] for f in {z for r in lines for z in r if z != '.'}} return ll, fm def fa(fm, ll, rh=False): ans = set() for cd in fm.values(): l = len(cd) for i in range(l): x1, y1 = cd[i] for j in range(i + 1, l): x2, y2 = cd[j] dx, dy = x2 - x1, y2 - y1 if rh: for k in range(-ll, ll): x, y = x1 + k * dx, y1 + k * dy if 0 <= x < ll and 0 <= y < ll: ans.add((x, y)) else: x3, y3, x4, y4 = x1 - dx, y1 - dy, x2 + dx, y2 + dy if 0 <= x3 < ll and 0 <= y3 < ll: ans.add((x3, y3)) if 0 <= x4 < ll and 0 <= y4 < ll: ans.add((x4, y4)) return len(ans) def one(): ll, fm = setup() print(fa(fm, ll)) def two(): ll, fm = setup() print(fa(fm, ll, rh=True)) one() two()
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))))))
C
Not hard but a little fiddly.
Code
#include "common.h" #define GZ 52 static char g[GZ][GZ]; #define ANTI_P1 1 #define ANTI_P2 2 static uint8_t anti[GZ][GZ]; static int w,h; int main(int argc, char **argv) { int p1=0,p2=0, x,y, x1,y1, ax,ay, i; char *lf; if (argc > 1) DISCARD(freopen(argv[1], "r", stdin)); for (h=0; h<GZ && fgets(g[h], GZ, stdin); h++) ; assert(feof(stdin)); lf = strchr(g[0], '\n'); assert(lf); w = lf - g[0]; /* * Find antenna pairs, then project backwards from the first, * forwards from the second. Don't like the repetition but it * makes for easy code. */ for (y=0; y<h; y++) for (x=0; x<w; x++) { if (!isalnum(g[y][x])) continue; for (y1=y; y1<h; y1++) for (x1=(y==y1?x+1:0); x1<w; x1++) { if (g[y][x] != g[y1][x1]) continue; for (i=0; ; i++) { if ((ax = x-(x1-x)*i) <0 || ax>w || (ay = y-(y1-y)*i) <0 || ay>h) break; anti[ay][ax] |= ANTI_P1 * i==1; anti[ay][ax] |= ANTI_P2; } for (i=0; ; i++) { if ((ax = x1+(x1-x)*i) <0 || ax>w || (ay = y1+(y1-y)*i) <0 || ay>h) break; anti[ay][ax] |= ANTI_P1 * i==1; anti[ay][ax] |= ANTI_P2; } } } for (y=0; y<h; y++) for (x=0; x<w; x++) { p1 += !!(anti[y][x] & ANTI_P1); p2 += !!(anti[y][x] & ANTI_P2); } printf("08: %d %d\n", p1, p2); return 0; }
Uiua
Getting closer to an elegant solution, but still a way to go…
Grid ← ⊜∘⊸≠@\n "............\n........0...\n.....0......\n.......0....\n....0.......\n......A.....\n............\n............\n........A...\n.........A..\n............\n............" Pairs ← ∧(⊂⧅≠2⊚⌕)⊙¤⊸(◴▽⊸≠@.♭)Grid[] # get pairs of nodes in grid (both ways round). InGrid ← ▽≡/××<⧻Grid:≥0.. # (posns) Keeps those in range. AntiNodes ← ↯∞_2≡(+¤⊙(פ)⊃⊣/-):¤ # (range, pairs) Find antinodes by taking offset, mul by range, add to last node, check it's in grid. &p ⧻InGrid◴ AntiNodes ↘1⇡2 Pairs &p ⧻InGrid◴ AntiNodes ↘0⇡50 Pairs
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) } } } } }
And I of course misread and wasted a bunch of time debugging the second part, entirely missed the fact that antinodes occurred on top of the emanating antennae as well…
C#
public static class LINQExt { public static IEnumerable<(T,T)> PermutatePairs<T>(this IEnumerable<T> source) { return source.SelectMany(k => source.Where(v => !v?.Equals(k) ?? false).Select(v => (k, v))); } } struct Antenna { public int X, Y; public char Frequency; } List<Antenna> antennae = new List<Antenna>(); int width, height; public void Input(IEnumerable<string> lines) { char[] map = string.Join("", lines).ToCharArray(); width = lines.First().Length; height = lines.Count(); for (int y = 0; y < height; ++y) for (int x = 0; x < width; ++x) { char at = map[y * width + x]; if (at == '.') continue; antennae.Add(new Antenna{ X = x, Y = y, Frequency = at }); } } public void Part1() { HashSet<(int, int)> antinodes = new HashSet<(int, int)>(); foreach (var antinode in antennae.GroupBy(k => k.Frequency).SelectMany(g => g.PermutatePairs()).SelectMany(v => GetOpposing(v.Item1, v.Item2)).Where(InRange)) antinodes.Add(antinode); Console.WriteLine($"Unique antinodes: {antinodes.Count}"); } public void Part2() { HashSet<(int, int)> antinodes = new HashSet<(int, int)>(); foreach (var antennaePair in antennae.GroupBy(k => k.Frequency).SelectMany(g => g.PermutatePairs())) { // Iterate separately, to make the handling of bound exit easier foreach (var antinode in GetAllOpposing(antennaePair.Item1, antennaePair.Item2).TakeWhile(InRange)) antinodes.Add(antinode); foreach (var antinode in GetAllOpposing(antennaePair.Item2, antennaePair.Item1).TakeWhile(InRange)) antinodes.Add(antinode); } Console.WriteLine($"Unique antinodes: {antinodes.Count}"); } bool InRange((int, int) point) { return point.Item1 >= 0 && point.Item1 < width && point.Item2 >= 0 && point.Item2 < height; } (int, int)[] GetOpposing(Antenna a, Antenna b) { return new[] { (a.X + (a.X - b.X), a.Y + (a.Y - b.Y)), (b.X + (b.X - a.X), b.Y + (b.Y - a.Y)) }; } IEnumerable<(int, int)> GetAllOpposing(Antenna a, Antenna b) { (int, int) diff = (a.X - b.X, a.Y - b.Y); (int, int) at = (a.X, a.Y); yield return at; while (true) { at.Item1 += diff.Item1; at.Item2 += diff.Item2; yield return at; } }
Haskell
import Control.Arrow import Control.Monad import Data.List import Data.Map qualified as M type Pos = [Int] parse :: String -> (Pos, [(Char, Pos)]) parse s = ([n, m], [(c, [i, j]) | i <- [0 .. n], j <- [0 .. m], c <- [l !! i !! j], c /= '.']) where l = lines s n = pred $ length $ head l m = pred $ length l buildMap :: [(Char, Pos)] -> M.Map Char [Pos] buildMap = M.fromListWith (++) . fmap (second pure) allPairs :: [Pos] -> [(Pos, Pos)] allPairs l = [(x, y) | (x : xs) <- tails l, y <- xs] add = zipWith (+) sub = zipWith (-) antinodes :: Pos -> Pos -> [Pos] antinodes a b = [a `sub` ab, b `add` ab] where ab = b `sub` a inBounds [x', y'] [x, y] = x >= 0 && y >= 0 && x <= x' && y <= y' antinodes' :: Pos -> Pos -> Pos -> [Pos] antinodes' l a b = al ++ bl where ab = b `sub` a al = takeWhile (inBounds l) $ iterate (`sub` ab) a bl = takeWhile (inBounds l) $ iterate (`add` ab) b part1 l = length . nub . filter (inBounds l) . concat . M.elems . fmap (allPairs >=> uncurry antinodes) part2 l = length . nub . concat . M.elems . fmap (allPairs >=> uncurry (antinodes' l)) main = getContents >>= print . (uncurry part1 &&& uncurry part2) . second buildMap . parse
Nim
Overall really simple puzzle, but description is so confusing, that I mostly solved it based on example diagrams.
Edit: much shorter and faster one-pass solution. Runtime: 132 ustype Vec2 = tuple[x,y: int] func delta(a, b: Vec2): Vec2 = (a.x-b.x, a.y-b.y) func outOfBounds[T: openarray | string](pos: Vec2, grid: seq[T]): bool = pos.x < 0 or pos.y < 0 or pos.x > grid[0].high or pos.y > grid.high proc solve(input: string): AOCSolution[int, int] = var grid = input.splitLines() var antennas: Table[char, seq[Vec2]] for y, line in grid: for x, c in line: if c != '.': discard antennas.hasKeyOrPut(c, newSeq[Vec2]()) antennas[c].add (x, y) var antinodesP1: HashSet[Vec2] var antinodesP2: HashSet[Vec2] for _, list in antennas: for ind, ant1 in list: antinodesP2.incl ant1 # each antenna is antinode for ant2 in list.toOpenArray(ind+1, list.high): let d = delta(ant1, ant2) for dir in [-1, 1]: var i = dir while true: let antinode = (x: ant1.x+d.x*i, y: ant1.y+d.y*i) if antinode.outOfBounds(grid): break if i in [1, -2]: antinodesP1.incl antinode antinodesP2.incl antinode i += dir result.part1 = antinodesP1.len result.part2 = antinodesP2.len