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
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-distance, sensor+distance+1 if part == 1 and not (left <= y < right or left < y <= right): return blocked for i in range(distance+1): if sensor + i not in blocked: blocked[sensor + i] = set() if sensor - i not in blocked: blocked[sensor - i] = set() blocked[sensor - i].add((sensor - distance + i, sensor + distance - i + 1)) blocked[sensor + i].add((sensor - distance + i, sensor + 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 < b or b < a: return a, b return (min(a, b), max(a, b)), None
this code is terribly slow, but it works, so I'm keeping it.
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 <= sorted(ranges) < y and y <= row < y: return sorted(ranges, key=lambda x: x) * 4000000 + row
the code is slow, but not slow enough to not brute force this one.
It's not pretty, but it works.
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 syntaxoops. Those tuple parantheses. 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 iterableOne 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' objecthm...
for i in range(distance+1): TypeError: 'float' object cannot be interpreted as an integerah 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: 2000000hehe, 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.