Jesper Dramsch , , read in 5 minutes

Oh no. Please no beacons. Those beacons broke me last year.

What is Advent of Code?

In this little series, I want to write about the thought processes I have behind solving the puzzles presented in Advent of Code.

During the Advent of Code small coding puzzles are presented with varying levels of difficulty. They're always Christmas-themed text puzzles where you help elves out of some mess to save the holidays. The puzzles are deliberately ambiguous to not bias puzzlers into a certain solution, they always have an example input in the text to explain some details and an input file for each day that comes in the form of a text file you can download. The solution is a simple number or a string you enter, which is checked by the website automatically. After you finish part 1, part 2 unlocks, which is a variation on part 2. This can be a little twist on part 1 or a large twist that changes the problem formulation into a problem that would take brute force solutions to compute longer than the heat death of the universe would take.

Find my solutions here: github.com/JesperDramsch/advent-of-code

These descriptions won't be a perfect narrative, but rather how I think about these problems and where I see different solutions. I apologise for the possibility of rambling!

The example input

Oh my, I hope I can get my triangles on point...

Sensor at x=2, y=18: closest beacon is at x=-2, y=15
Sensor at x=9, y=16: closest beacon is at x=10, y=16
Sensor at x=13, y=2: closest beacon is at x=15, y=3
Sensor at x=12, y=14: closest beacon is at x=10, y=16
Sensor at x=10, y=20: closest beacon is at x=10, y=16
Sensor at x=14, y=17: closest beacon is at x=10, y=16
Sensor at x=8, y=7: closest beacon is at x=2, y=10
Sensor at x=2, y=0: closest beacon is at x=2, y=10
Sensor at x=0, y=11: closest beacon is at x=2, y=10
Sensor at x=20, y=14: closest beacon is at x=25, y=17
Sensor at x=17, y=20: closest beacon is at x=21, y=22
Sensor at x=16, y=7: closest beacon is at x=15, y=3
Sensor at x=14, y=3: closest beacon is at x=15, y=3
Sensor at x=20, y=1: closest beacon is at x=15, y=3

The implementation

For this parser, I think a classic regex will do.

Probably nice to add a regex parser to my Parser class too... Let's see.

If you need to debug your regex, I can highly recommend the fantastic Regex 101 which is less of a 101 and more of a full on visualization tool!

regex = re.compile(r"[Sa-z ]+x\=(-?\d+), y\=(-?\d+):[a-z ]+x\=(-?\d+), y\=(-?\d+)")

Key here is to not forget that negative numbers exist!

This is one of those problems you have to find a sparse solution. Adding every point that is blocked by sensor-beacon pair, will give a gigantic matrix.

I first thought complex numbers would be good, but in the second half of the problem I switched over to simple tuples.

So I needed to add the start and end points for each blocked row (since we're looking at rows later).

def clock(sensor, distance, blocked, y, part):
    left, right = sensor[1] - distance, sensor[1] + distance + 1
    if part == 1 and not (left <= y[0] < right or left < y[1] <= right):
        return blocked
    for i in range(distance + 1):
        if sensor[1] + i not in blocked:
            blocked[sensor[1] + i] = set()
        if sensor[1] - i not in blocked:
            blocked[sensor[1] - i] = set()
        blocked[sensor[1] - i].add(
            (sensor[0] - distance + i, sensor[0] + distance - i + 1)
        )
        blocked[sensor[1] + i].add(
            (sensor[0] - distance + i, sensor[0] + distance - i + 1)
        )

    return blocked

When I have all of these, I want to find overlaps and merge them with:

def merge(a, b):
    if a[1] < b[0] or b[1] < a[0]:
        return a, b
    return (min(a[0], b[0]), max(a[1], b[1])), None

this code is terribly slow, but it works, so I'm keeping it.

Part Deux

For this part I need to find that singular spot in the field.

for row, ranges in blocked.items():
    if len(ranges) > 1:
        if y[0] <= sorted(ranges)[1][0] < y[1] and y[0] <= row < y[1]:
            return sorted(ranges, key=lambda x: x[0])[0][1] * 4000000 + row

the code is slow, but not slow enough to not brute force this one.

It's not pretty, but it works.

Error Log

Got a few for this one, but really struggled on getting the right answer on part 2. Too many zeros.

  • day.data = (complex(a, b), complex(c, d) for a, b, c, d in day.data) SyntaxError: invalid syntax oops. Those tuple parentheses. One day I will learn.
  • return block(8+7j, 9) NameError: name 'block' is not defined. Did you mean: 'clock'? yes I did..
  • blocked = set(sensor) TypeError: 'complex' object is not iterable One day I'll learn.
  • blocked = set.union(clock(sensor, manhattan(sensor, beacon)) for sensor, beacon in day.data) TypeError: descriptor 'union' for 'set' objects doesn't apply to a 'generator' object hm...
  • for i in range(distance+1): TypeError: 'float' object cannot be interpreted as an integer ah the distance measure should return an int.
  • a, b = merge(a, b) ValueError: too many values to unpack (expected 2) Didn't tuple the tuple.
  • return blocked[y] KeyError: 2000000 hehe, still on the easy stuff not the big problem.
  • Technically not an error, but I got the wrong answer, because I didn't check the x dimension initially.