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

  • CameronDev@programming.devOPM
    link
    fedilink
    arrow-up
    8
    ·
    edit-2
    23 days ago

    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());
        }
    }
    
    • Rin@lemm.ee
      link
      fedilink
      arrow-up
      4
      ·
      22 days ago

      Any solution that solves the problem is a good solution :D

  • VegOwOtenks@lemmy.world
    link
    fedilink
    English
    arrow-up
    5
    ·
    edit-2
    23 days ago

    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
    
    • lwhjp@lemmy.sdf.org
      link
      fedilink
      arrow-up
      2
      ·
      23 days ago

      D’oh. Computing antinodes in a single direction and permuting pairs is a much neater approach that what I did!

  • hades@lemm.ee
    link
    fedilink
    arrow-up
    4
    ·
    23 days ago

    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();
      }
    }
    
  • lwhjp@lemmy.sdf.org
    link
    fedilink
    arrow-up
    4
    ·
    23 days ago

    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
    
  • Quant@programming.dev
    link
    fedilink
    arrow-up
    4
    ·
    22 days ago

    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
    
  • mykl@lemmy.world
    link
    fedilink
    arrow-up
    3
    ·
    23 days ago

    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);
    
    • janAkali@lemmy.one
      link
      fedilink
      English
      arrow-up
      4
      ·
      edit-2
      23 days ago

      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?

  • Karmmah@lemmy.world
    link
    fedilink
    arrow-up
    2
    ·
    22 days ago

    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)")
    
  • TunaCowboy@lemmy.world
    link
    fedilink
    arrow-up
    2
    ·
    edit-2
    22 days ago

    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()
    
  • wer2@lemm.ee
    link
    fedilink
    arrow-up
    2
    ·
    edit-2
    22 days ago

    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))))))
    
    
  • sjmulder@lemmy.sdf.org
    link
    fedilink
    English
    arrow-up
    2
    ·
    22 days ago

    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;
    }
    

    https://github.com/sjmulder/aoc/blob/master/2024/c/day08.c

  • mykl@lemmy.world
    link
    fedilink
    arrow-up
    2
    ·
    edit-2
    22 days ago

    Uiua

    Getting closer to an elegant solution, but still a way to go…

    How to read this

    Try it live!

    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 12 Pairs
    &p InGrid AntiNodes 050 Pairs
    
  • the_beber@lemm.ee
    link
    fedilink
    arrow-up
    1
    ·
    19 days ago

    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) }
                }
            }
        }
    }
    
    
  • Ananace@lemmy.ananace.dev
    link
    fedilink
    arrow-up
    1
    ·
    23 days ago

    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;
      }
    }
    
  • LeixB@lemmy.world
    link
    fedilink
    arrow-up
    1
    ·
    22 days ago

    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
    
  • janAkali@lemmy.one
    link
    fedilink
    English
    arrow-up
    1
    ·
    edit-2
    22 days ago

    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 us

    type 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
    
    

    Codeberg repo