After yesterday’s math puzzle, I was delighted to see today’s puzzle and get working on it. It was quite a lot of fun.
We’ve reached the Easter Bunny Headquarters which we are very familiar with from 2016 where the entire month was spent finding passwords and hacking office doors in Mrs. Bunny’s office. Today, we needed to calculate the safety factor of robots guarding the bathrooms. I fell off a bit from the lore here but that’s okay.
Read input
Our input is a list of starting positions and velocities for robots:
p=0,4 v=3,-3
p=6,3 v=-1,-3
p=10,3 v=-1,2
p=2,0 v=2,-1
p=0,0 v=1,3
p=3,0 v=-2,-2
p=7,6 v=-1,-3
p=3,0 v=-1,-2
p=9,3 v=2,3
p=7,3 v=-1,2
p=2,4 v=2,-3
p=9,5 v=-3,-3On each line, p is an (x,y) coordinate where the robot starts when we enter the bathroom area and v is an (dx,dy) pair of how much a robot moves each second.
from typing import NamedTuple
from utils import Coordinate
class Velocity(NamedTuple):
dx: int
dy: int
class Robot(NamedTuple):
position: Coordinate
velocity: Velocity
def map_fn(line: str) -> Robot:
numbers = [int(num) for num in re.findall(r"-?\d+", line)]
return Robot(Coordinate(numbers[0], numbers[1]), Velocity(numbers[2], numbers[3]))These past couple of days I’ve been experimenting with types in Python so today’s namedtuples are done with the typed NamedTuple syntax. I’ve also moved my Coordinate namedtuple into my utility library since it seems to be a very popular one this year.
I do have to say though that I vastly prefer the non-typed construction of namedtuples over this class inheritance one. I really wish there was a way to add types to those.
We had a great chat with Mina yesterday in Mastodon about regexes and my document-heavy approach. I really like to spell out the entire line in the pattern and use named capture groups to document the patterns.
To show other variations, I’m doing a slightly different one today and we can contrast these approaches with each other.
Here’s what I used today to parse the input line:
line = 'p=9,5 v=-3,-3'
numbers = [int(num) for num in re.findall(r"-?\d+", line)]
return Robot(Coordinate(numbers[0], numbers[1]), Velocity(numbers[2], numbers[3]))It finds all the numbers (and that they may or may not start with - sign) and converts them to integers.
Normally, I would have done
re_robot = r'p=(?P<x>\d+),(?P<y>\d+) v=(?P<dx>-?\d+),(?P<dy>-?\d+)'
line = 'p=9,5 v=-3,-3'
robot = re.match(re_robot, line).groupdict()
return Robot(Coordinate(robot['x'], robot['y']), Velocity(robot['dx'], robot['dy']))Which one someone likes more is a question of preference. For simpler ones, I don’t care so much (and for Advent of Code even less) but I’m a strong believer that if I’d return to this piece of code in production years from now, the second one would cause less confusion.
I’ve especially grown to dislike numerical index based access because unless those numbers are extracted into well named variables, it requires me to go back and build a mental model of what is where.
In the second one, I can see the full line of the input in the pattern and I rarely need to take a look at the pattern when the Robot construction line tells me exactly what’s being extracted from the input.
Part 1
In the first part, we need to follow the robots’ movements for 100 seconds and see where they finish. If a robot would walk outside the bathroom hall, they teleport to the other side.
Since each robot only moves to a single direction and same distance every time, we don’t actually need to observe them for 100 seconds. We can calculate the final positions by multiplying their velocity with 100 and adding it to their starting position.
And since the robots can’t collide, all robots move independent of anyone else.
def part_1():
robots = read_input(14, map_fn)
width, height = 101, 103
seconds = 100
quadrants = [0] * 4
for robot in robots:
start_position = robot.position
velocity = robot.velocity
final_position = Coordinate(
(start_position.x + (velocity.dx * seconds)) % width,
(start_position.y + (velocity.dy * seconds)) % height,
)To account for the teleportation, we take the modulo of width and height respectively.
To then calculate the safety factor, we need to put these robots into quadrants. To calculate which sides a position lands, I made a few helpers:
is_left = final_position.x < width // 2
is_right = final_position.x > width // 2
is_top = final_position.y < height // 2
is_bottom = final_position.y > height // 2I use the integer division a//b here since the width and height are both odd numbers and with < and >, we don’t have to worry about the lines that fit smack in the middle as we were instructed to ignore them.
Then, based on these locations, we store the number of bots in right quadrants:
if is_left and is_top:
quadrants[0] += 1
elif is_right and is_top:
quadrants[1] += 1
elif is_left and is_bottom:
quadrants[2] += 1
elif is_right and is_bottom:
quadrants[3] += 1Finally, the result is calculated by multiplying each quadrant’s robot amount with each other which we can do with math.prod:
safety_factor = math.prod(quadrants)
print(f"Part 1: {safety_factor}")Part 2
Part 2 was quite a twist. My guess was that we’d have to care about robots colliding but we got something completely different.
very rarely, most of the robots should arrange themselves into a picture of a Christmas tree
We need to calculate the minimum amount of seconds after which the robots are lined up as a Christmas tree.
For part 1, I had already created a debug printer:
def print_grid(positions: List[Coordinate], width: int, height: int) -> None:
c = Counter(positions)
for y in range(height):
for x in range(width):
if cell := c.get((x, y)):
print(cell, end="")
else:
print(" ", end="")
print()I took the very straight-forward position: I looped through each second, printed out the grid and then painstakingly went through thousands and thousands of pictures to find a Christmas tree. Originally, I thought they’d only put us through maybe a few dozen pictures so I did the first 100 and found no trees. It turned out to be quite a many more rounds.
def part_2():
robots = read_input(14, map_fn)
width, height = 101, 103
for seconds in range(width * height):
for idx, robot in enumerate(robots):
new_pos = Coordinate(
(robot.position.x + robot.velocity.dx) % width,
(robot.position.y + robot.velocity.dy) % height,
)
robots[idx] = Robot(new_pos, robot.velocity)
print_grid([r.position for r in robots], width, height)Click to see what my tree looked like (spoilers)
1111111111111111111111111111111 1 1 1 1 1 1 1 1 1 1 1 1 111 1 1 11111 1 1 1111111 1 1 111111111 1 1 11111 1 1 1111111 1 1 111111111 1 1 11111111111 1 1 1111111111111 1 1 111111111 1 1 11111111111 1 1 1111111111111 1 1 111111111111111 1 1 11111111111111111 1 1 1111111111111 1 1 111111111111111 1 1 11111111111111111 1 1 1111111111111111111 1 1 111111111111111111111 1 1 111 1 1 111 1 1 111 1 1 1 1 1 1 1 1 1 1111111111111111111111111111111
I cut out the excess to make it more readable on the web.
Most of the work today went into browsing through thousands of pictures of random noise. Not the most productive or fun thing I’ve ever done on a Saturday morning.
I did consider if I could write some sort of programmatic check but given that I had no clue what this Christmas tree looked like, I decided to take the manual route. And I’m happy I did because the picture was very different from what I had imagined so my code would have never found it anyway.
In general, these “print out the grid and you’ll see the result” types of puzzles can be fun, I’m just a bit stickler to the fact that I can’t easily write assertions that double check my code is still correct. Once I have a result and then I start refactoring, I need to manually inspect the print to see that everything still works. Other than that, they are fine and fun.
I’m very happy with how readable my code ended up once again. Namedtuples really are worth every penny. Just compare these two functionally identical lines:
new_pos = (
(robot[0][0] + robot[1][0]) % width,
(robot[0][1] + robot[1][1]) % height
)
# compared to
new_pos = Coordinate(
(robot.position.x + robot.velocity.dx) % width,
(robot.position.y + robot.velocity.dy) % height,
)Imagine coming back to code like this in production after a year. The second one tells you a clear story of what the data structures are about and what we are calculating. In the first one, you’d have to go back to where the robot was constructed and build a mental model to remember what’s where.
And if you’d introduce a bug, it would be easier to spot than with numerical indices into tuples of tuples:
new_pos = (
(robot[0][0] + robot[1][0]) % width,
(robot[1][0] + robot[1][1]) % height
)
# compared to
new_pos = Coordinate(
(robot.position.x + robot.velocity.dx) % width,
(robot.velocity.dx + robot.velocity.dy) % height,
)With 14th day in the bag, we’re now at 28 stars out of the 50.