Advent of Code 2024 - Day 8: Resonant Collinearity

:: programming, python, puzzle

 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
 
from advent import parse, grid_to_hash, defaultdict, combinations, gcd

lines         = parse(8)
width, height = len(lines[0]), len(lines)
antennas      = defaultdict(set)
valid_index   = lambda i: 0 <= i.real < width and 0 <= i.imag < height
solve         = lambda get_nodes: len({ n
                                        for s in antennas.values()
                                        for i, j in combinations(s, 2)
                                        for n in get_nodes(i, j, i - j) })

for pos, label in grid_to_hash(lines, elem_filter=lambda c: c != '.').items():
    antennas[label].add(pos)

def part1(i, j, diff):
    return filter(valid_index, [ i + diff, j - diff ])

def part2(i, j, diff):
    step = diff / gcd(int(diff.real), int(diff.imag))
    return filter(valid_index, { n * step + i for n in range(-width, width) })

# ---------------------------------------------------------------------------------------------

assert solve(part1) == 398
assert solve(part2) == 1333

Parsing

We’re given another grid for today’s puzzle. I want a dict with antenna labels as keys and a set of all the label’s positions as values. parse(8) gives us a list of lines. grid_to_hash() gives us a dictionary, but it’s not quite right yet - it has positions for keys and labels for values. So, a simple loop will give us what we need:

1
2
 
for pos, label in grid_to_hash(lines, elem_filter=lambda c: c != '.').items():
    antennas[label].add(pos)

Solution

The parts only differ in the algorithm for identifying antinodes, so we’ll pass in a higher order function for each of the parts to the solve() function. The key element of the solve() function is a set comprehension:

1
2
3
4
 
{ n
  for s in antennas.values()
  for i, j in combinations(s, 2)
  for n in get_nodes(i, j, i - j) }
  • Loop over the antenna labels, obtaining the set of positions
  • Loop over all pairs of combinations of antennas
  • Loop over the antinodes

For Part 1, we compute two positions. Let i & j be positions of two antennas:

  • Add the delta (i - j) to i
  • Subtract the delta (i - j) from j
  • Filter out any off-grid positions
1
2
 
def part1(i, j, diff):
    return filter(valid_index, [ i + diff, j - diff ])

For Part 2, we do something similar, but we want all of the positions obtained from these steps. To identify the step, we need to compute the greatest common divisor of the delta, to avoid using steps larger than we should.

A simple trick I used is instead of stepping away from the position positively and negatively until we’re off the grid, I simply compute a range I know is sufficient, and then filter out the off-grid positions.

1
2
3
 
def part2(i, j, diff):
    step = diff / gcd(int(diff.real), int(diff.imag))
    return filter(valid_index, { n * step + i for n in range(-width, width) })

New Python Concepts

  • filter()
  • math.gcd()

Conclusion

I thought Python’s comprehensions made this solution very straightforward.