For this day, I used Python.
Parsing
Each line in the input has the position and velocity of a robot given as x,y coordinates. We split on lines, and then extract the position and velocity numbers from each line and store it in a nested list.
def parse_input(inp):
return [parse_line(line) for line in inp.strip().splitlines()]
def parse_line(line):
pos_s, vel_s = line.split(" ")
pos = [int(x) for x in pos_s.split("=")[1].split(",")]
vel = [int(x) for x in vel_s.split("=")[1].split(",")]
return [pos, vel]Part One
We need to simulate the robots’s movement for 100 seconds. Each second, every robot moves from its original position by the amount specified in its velocity, wrapping around the grid edges. The grid has a constant width of 101 and a constant height of 103. The robots can also overlap.
After 100 seconds of simulation we need to find the safety factor of the grid. The safety factor is obtained by counting the number of robots in each quadrant of the grid (ignoring the robots on the boundary between quadrants) and finding the product of the 4 counts.
def part1(inp):
inp = copy.deepcopy(inp)
width = 101
height = 103
for i in range(100):
for j in range(len(inp)):
pos_x, pos_y = inp[j][0]
vel_x, vel_y = inp[j][1]
new_pos = [(pos_x + vel_x) % width, (pos_y + vel_y) % height]
inp[j][0] = new_pos
quadrant_counts = [0 for x in range(4)]
for pos, vel in inp:
pos_x, pos_y = pos
if pos_x < width // 2 and pos_y < height // 2:
quadrant_counts[0] += 1
elif pos_x < width // 2 and pos_y > height // 2:
quadrant_counts[1] += 1
elif pos_x > width // 2 and pos_y < height // 2:
quadrant_counts[2] += 1
elif pos_x > width // 2 and pos_y > height // 2:
quadrant_counts[3] += 1
product = 1
for c in quadrant_counts:
product *= c
return productNote the copy.deepcopy at the start of the function. This is done to isolate the the part 1 robots list from the part 2 robots list. This is required because lists in python are reference types and not value types, meaning that modifying a list argument of a function will change that list outside the function too.
Part Two
Now, we need to find the amount of time it takes for the grid to display an easter egg of a picture of a Christmas tree.
There are quite a few ways that people found to detect a tree inside the grid. I initially tried manually searching for the tree but got tired of that at around 3000 iterations. During this time, I noticed that the inputs showed a pattern of vertical lines after every 101 iterations and a pattern of horizontal lines after every 103 iterations. This is an effect of the modulo math used to calculate the new positions of each robot. I guessed (correctly) that the tree would appear when both the conditions for horizontal and vertical lines are satisfied.
To programmatically find the indexes of the vertical and horizontal line patterns, I calculate the variance of the x and y coordinates of the positions. The vertical/horizontal lines appear when the x/y variance is the lowest.
def part2(inp):
inp = copy.deepcopy(inp)
width = 101
height = 103
x_lines_i = None
min_x_variance = None
y_lines_i = None
min_y_variance = None
i = 1
while True:
for j in range(len(inp)):
pos_x, pos_y = inp[j][0]
vel_x, vel_y = inp[j][1]
new_pos = [(pos_x + vel_x) % width, (pos_y + vel_y) % height]
inp[j][0] = new_pos
if i < width:
x_variance = statistics.pvariance([x[0][0] for x in inp])
if x_lines_i is None or x_variance < min_x_variance:
x_lines_i = i
min_x_variance = x_variance
if i < height:
y_variance = statistics.pvariance([x[0][1] for x in inp])
if y_lines_i is None or y_variance < min_y_variance:
y_lines_i = i
min_y_variance = y_variance
if i > max(width, height):
if i % width == x_lines_i and i % height == y_lines_i:
display_robots(inp)
break
i += 1
return i
def display_robots(robots):
width = 101
height = 103
grid = {}
for x in range(width):
for y in range(height):
grid[(x, y)] = False
for pos, vel in robots:
grid[tuple(pos)] = True
for y in range(height):
for x in range(width):
if grid[(x, y)]:
print("@", end="")
else:
print(" ", end="")
print()