Advent of Code Day 8 – Resonant Collinearity

This was surprisingly easy! The part 1 of today’s task was correct on the first run, which is the first time this has happened to me! Usually I make stupid mistakes, not reading the puzzle carefully enough, and rushing to coding with too little planning ahead.

The puzzle part 1 was to find out positions on a map to place antinodes to prevent antennas to emit a signal that makes people 0.1% more likely to buy Easter Bunny brand Imitation Mediocre Chocolate as a Christmas gift.

Calculate the impact of the signal. How many unique locations within the bounds of the map contain an antinode?

A map looks like this:

............
........0...
.....0......
.......0....
....0.......
......A.....
............
............
........A...
.........A..
............
............

Where 0 and A are antennas that are sending on a same frequency, A antennas on their own and 0 antennas theirs, respectively. To prevent their signals, the antinodes ( #)must be placed in line of the antennas, after the first and last pair of antennas, like this:

......#....#
...#....0...
....#0....#.
..#....0....
....0....#..
.#....A.....
...#........
#......#....
........A...
.........A..
..........#.
..........#.

To solve the problem, I implented a Dictionary with key-value -pairs (the [Character: [Point]] below), where the key is an antenna with a specific frequency and value is an array of (x, y) positions on the map where that kind of antennas are placed.

var antinodes: Set<Point> = []
let matrix: Matrix<Character> = parse(data: data)
let antennaMap: [Character: [Point]] = parseAntennaMap(matrix)

After parsing the antennas and their positions into a Matrix, and extracting the antennas and their positions into the dictionary, I could print out the dictionary keys (antennas) with the values (a list of positions for the antennas with the same frequency ):

Antenna A
  5:6
  8:8
  9:9
Antenna 0
  1:8
  2:5
  3:7
  4:4

So I could verify that everything is in order for the next step of the puzzle.

I already had a Point structure, having the x and y coordinates, as well as operations to calculate the difference of two points in the coordinate (the distance between them) as well as add together two coordinate points to extrapolate the line between two antennas to position the antinodes inline with the antennas.

So what to do with these? First I needed to handle all the antennas with the same frequency in pairs, to extrapolate the line between them to both directions to add the antinodes. The permutations(ofCount:) algorithm did that. For each pair of antennas, I determined which comes first (point is upper on the map compared to the other) and vice versa.

After that I counted the difference between the first and last point, because the antinode must be place an equal distance away from the antennas. Then I added a point above the first point (first - difference) and below the last point (last + difference).

Then I just added these two antinodes into a Set to get a number of antinodes placed on the map:

for (_, points) in antennaMap {
  let permutations = points.permutations(ofCount: 2)
  for permutation in permutations {
     let first =
     permutation.first! < permutation.last! ? permutation.first! : permutation.last!
    let last = first == permutation.first! ? permutation.last! : permutation.first!
    let difference = last - first
    antinodes.insert(first - difference)
    antinodes.insert(last + difference)
  }
}
antinodes = antinodes.filter({ matrix.contains(y: $0.y, x: $0.x) })
return antinodes.count

Finally I made sure no antinodes were placed outside the map coordinates (using filter to include only those points in the area of the matrix coordinates) and finally returning the count of antinodes placed (the puzzle answer).

Part 2 was just an addition to part 1. Instead of placing one antinode before and after the line of two antennas, place them so that the antinodes are repeated with equal spacing along the line formed by a pair of antennas, until to the edge of the map.

What I first missed in the puzzle instructions was that the positions of the antennas also count in the final answer, not just the antinodes. I did get that the unique positions only are counted (that is why the Set<Point> is used for antinode positions). As I realized this, I just formed a union of antinode and antenna positions, and count of those was the correct answer!

In total, this didn’t take long to solve, thanks to the existing data structures and algorithms, both from Swift, Swift libraries (Swift Algorithms) and my own utilities from previous years. Performance is also OK:

$ swift run -c release AdventOfCode 8 --benchmark
Building for production...
Build of product 'AdventOfCode' complete! (0.28s)
Executing Advent of Code challenge 8...
Part 1: 259
Part 2: 927
Part 1 took 0.000727958 seconds, part 2 took 0.000798333 seconds.