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.

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-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.

## 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 <= 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.

## 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 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 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.