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.