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)")

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

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()

use euclid::default::*;

const N_ANTENNAS: usize = (b'z' - b'0') as usize + 1;
// For each frequency (from b'0' to b'z') the list of antenna positions
type Antennas = Box<[Vec<Point2D<i32>>]>;

fn parse(input: String) -> (Antennas, Rect<i32>) {
    let mut antennas = vec![Vec::new(); N_ANTENNAS].into_boxed_slice();
    let mut width = 0;
    let mut height = 0;
    for (y, l) in input.lines().enumerate() {
        height = y + 1;
        if width == 0 {
            width = l.len()
        } else {
            assert!(width == l.len())
        }
        for (x, b) in l.bytes().enumerate().filter(|(_, b)| *b != b'.') {
            antennas[(b - b'0') as usize].push(Point2D::new(x, y).to_i32())
        }
    }
    let bounds = Rect::new(Point2D::origin(), Size2D::new(width, height).to_i32());
    (antennas, bounds)
}

fn part1(input: String) {
    let (antennas, bounds) = parse(input);
    let mut antinodes = vec![vec![false; bounds.width() as usize]; bounds.height() as usize];
    for list in antennas.iter().filter(|l| !l.is_empty()) {
        for (i, &a) in list.iter().enumerate().skip(1) {
            for &b in list.iter().take(i) {
                let diff = b - a;
                let ax = a - diff;
                if bounds.contains(ax) {
                    antinodes[ax.y as usize][ax.x as usize] = true;
                }
                let bx = b + diff;
                if bounds.contains(bx) {
                    antinodes[bx.y as usize][bx.x as usize] = true;
                }
            }
        }
    }
    let sum = antinodes
        .iter()
        .map(|row| row.iter().map(|b| u32::from(*b)).sum::<u32>())
        .sum::<u32>();
    println!("{sum}");
}

fn part2(input: String) {
    let (antennas, bounds) = parse(input);
    let mut antinodes = vec![vec![false; bounds.width() as usize]; bounds.height() as usize];
    for list in antennas.iter().filter(|l| !l.is_empty()) {
        for (i, &a) in list.iter().enumerate().skip(1) {
            for &b in list.iter().take(i) {
                let diff = b - a;
                // Start at antenna a, keep going until hitting bounds
                let mut ax = a;
                while bounds.contains(ax) {
                    antinodes[ax.y as usize][ax.x as usize] = true;
                    ax -= diff;
                }
                let mut bx = b;
                while bounds.contains(bx) {
                    antinodes[bx.y as usize][bx.x as usize] = true;
                    bx += diff;
                }
            }
        }
    }
    let sum = antinodes
        .iter()
        .map(|row| row.iter().map(|b| u32::from(*b)).sum::<u32>())
        .sum::<u32>();
    println!("{sum}");
}

util::aoc_main!();

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

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

(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))))))

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