Advent of Code 2024 (Days 5, 6)
Here is my private leaderboard code if you want to come join the fun: 1598637-22d94a1d.
I got stuck on Day 6. Thankfully, I managed despite not having a stepsibling to help me out.
Day 5 : Sorting Pages with a Custom Order
Here is the link to the problem.
Part A
We need to keep track of the rules and the updates (which are practically the test cases).
Translating the Rules into Code
Basically, we need to keep track of which pages could be before or after which page.
We keep track of this using a dictionary which I call nodes_after. We set it up so that nodes_after[a] are all the node labels (i.e. page numbers) that are allowed to be after node (i.e. page number) a.
from collections import defaultdict
import itertools
def solution_05a(data=None):
if not data:
rules, updates = parse_05()
else:
rules, updates = data
nodes_after = defaultdict(lambda: [])
for rule in rules:
a, b = rule
nodes_after[a].append(b)
Is The List Sorted ?
The next part is to make a helper function that figures out if the list is already sorted, according to the rules.
I’ve named it is_update_good, following the terminology of the problem statement (as I understood it).
This checks if any pair in the given list violates any of the rules.
I did this by using the fancy itertools library. The output is itertools.combinations(update, 2) is tuples of size 2 representing combinations of 2 elements on the list ordered according to their original order in the list.
The emphasized part is important. This way, we know that x comes before y in the given list for any pair of x and y we treat.
If y is not allowed to be after x, that is y is not listed in nodes_after[x], then the list is not good and we return False.
If we see no violations over all pairs, we output True.
from collections import defaultdict
import itertools
def solution_05a(data=None):
#...#
def is_update_good(update):
for x, y in itertools.combinations(update, 2):
if y not in nodes_after[x]:
return False
return True
Going Through the Test Cases
Now that the hard work is done, we simply find the middle of each update and return the sum of the middles of the good ones, as required by the problem.
from collections import defaultdict
import itertools
def solution_05a(data=None):
#...#
def middle_of_update(update):
return int(update[len(update)//2])
ret = 0
for update in updates:
if is_update_good(update):
ret += middle_of_update(update)
return ret
Part B
Part B asks to sort the lists which weren’t sorted according to the proposed order.
Trees
Since I’ve been helping Pierre with his NSI notes on trees (soon-to-go-out), this is literally the first thing that came out of my mind when I realized I needed to sort.
from collections import defaultdict
import itertools
def solution_05b(data=None):
#...#
class Tree:
def __init__(self,v=None):
self.v = v
self.l = None
self.r = None
def add(self, v):
if self.v in nodes_after[v]:
if self.l is None:
self.l = Tree(v)
else:
self.l.add(v)
else:
if self.r is None:
self.r = Tree(v)
else:
self.r.add(v)
def get_infix(self):
l_contrib = self.l.get_infix() if self.l is not None else []
r_contrib = self.r.get_infix() if self.r is not None else []
return l_contrib + [self.v] + r_contrib
def fix_update(update):
bst = Tree(update[0])
for u in update[1:]:
bst.add(u)
return bst.get_infix()
Granted, I probably could have made a custom sort function using the rules, but at the time of writing this was the most intuitive for me.
This uses the fact that the in-order traversal of a binary search tree ends up sorting the list.
Call it pretentious or a flex, but this worked for me so I ended up with this.
Rest of the Code
Here is the rest of the code, which is straightforward.
from collections import defaultdict
import itertools
def solution_05b(data=None):
#...#
ret = 0
for update in updates:
if not is_update_good(update):
fixed_update = fix_update(update)
ret += middle_of_update(fixed_update)
return ret
Day 6 : Cycle Detection
Here is the link to the problem.
Part A
Part A was quite straightforward. Here is my code:
def solution_06a(data=None, filename=None):
if not data:
lines = parse_06(filename)
else:
lines = data
def get_start_position(lines):
start = None
for i, line in enumerate(lines):
for j, char in enumerate(line):
if char == '^':
return (i, j)
def follow_dir(cur_pos, cur_dir):
return (cur_pos[0] + cur_dir[0], cur_pos[1] + cur_dir[1])
def outside_grid(cur_pos, height, width):
return cur_pos[0] < 0 or cur_pos[1] < 0 or cur_pos[0] >= height or cur_pos[1] >= width
def cell_pointed_to(grid, cur_pos, cur_dir):
i, j = follow_dir(cur_pos, cur_dir)
if outside_grid(cur_pos, len(grid), len(grid[0])):
return '.'
return grid[i][j]
def turn_90(cur_dir):
dic = {
(-1, 0): (0, 1),
(0, 1): (1, 0),
(1, 0): (0, -1),
(0, -1): (-1, 0)
}
return dic[cur_dir]
def get_visited(grid, start):
cur_pos = start
cur_dir = (-1, 0)
height = len(grid)
width = len(grid[0])
visited = set()
while True:
visited.add(cur_pos)
if outside_grid(follow_dir(cur_pos, cur_dir), height, width):
return visited
if cell_pointed_to(grid, cur_pos, cur_dir) == '#':
cur_dir = turn_90(cur_dir)
else:
cur_pos = follow_dir(cur_pos, cur_dir)
start = get_start_position(lines)
visited = get_visited(lines, start)
return len(visited)
Getting Stuck 🙈
I did, unfortunately, get stuck somewhere on Part A. I was getting 38 instead of 41.
After debugging several times, I decided to YOLO it and use my program to solve my big input.
It worked!
Looking back, here was the sample input I had:
....#.....
....^....#
..........
..#.......
.......#..
..........
.#........
........#.
#.........
......#...
The answer to this was definitely 38. But this was NOT the sample input the problem statement was talking about when it said 41. So some time was wasted.
Part B
Thankfully, not enough time was wasted on Part A because… Part B.
Choose Your Own Adventure
At this point, I saw two possible solutions. The first one was to loop through all the . cells in the grid, put the new obstacle on it and then simulate the trajectory of the guard.
The big input was in the order of . This means that there would be places where to put the obstacle. I ended up overestimating the amount of time this would take and wound up looking for an alternate “smarter” (debatable) way to go through it.
I put “smarter” in quotes because the solution I end up with is indeed faster but at the cost of potentially more bugs. And more bugs we will have.
Here is my “smarter” but almost equally brute-forcey way to do it: put the obstacle in front of the guard at its every step. We know that the guard had around 5000 steps before it fell off the grid in Part A. So this should be three faster than the other solution. If we do it right.
Get Visited : Revisited
We need to revisit the function that keeps track of the path. Instead of only keeping track of the position, we need to keep track of the direction the guard is facing so that we know where to put the new obstacle.
def solution_06b(data=None, filename=None):
# ... #
def get_grid_dimensions(grid):
height = len(grid)
width = len(grid[0])
return height, width
def get_visited_with_dir(grid, start):
cur_pos = start
cur_dir = (-1, 0)
height, width = get_grid_dimensions()
visited_with_dir = set()
while True:
visited_with_dir.add((cur_pos, cur_dir))
if outside_grid(follow_dir(cur_pos, cur_dir), height, width):
return visited_with_dir_list
if cell_pointed_to(grid, cur_pos, cur_dir) == '#':
cur_dir = turn_90(cur_dir)
else:
cur_pos = follow_dir(cur_pos, cur_dir)
The Actual Cycle Detection
No matter the solution we chose in the Choose Your Own Adventure step, we need to have a cycle detection helper function.
I initially wrote a function detect_if_goes_out which is the opposite of a cycle detection function, but nonetheless useful. For the sake of readability, I converted it to a proper detect_cycle function as follows:
def solution_06b(data=None, filename=None):
# ... #
def detect_cycle(grid, start_pos, start_dir):
visited = set()
cur_pos = start_pos
cur_dir = start_dir
height, width = get_grid_dimensions(grid)
while True:
if (cur_pos, cur_dir) in visited:
return True
visited.add((cur_pos, cur_dir))
if outside_grid(follow_dir(cur_pos, cur_dir), height, width):
return False
if cell_pointed_to(grid, cur_pos, cur_dir) == '#':
cur_dir = turn_90(cur_dir)
else:
cur_pos = follow_dir(cur_pos, cur_dir)
Simulating the Walks
As established, we go through each step of the guard in its walk. At each step, we “put” a new obstacle in front of it and see if the guard still manages to walk out of the grid or ends up in a cycle.
def solution_06b(data=None, filename=None):
# ... #
def get_new_grid_with_wall_in_front(grid, elt_pos, elt_dir):
new_grid = [[c for c in g] for g in grid]
new_wall = follow_dir(elt_pos, elt_dir)
height, width = get_grid_dimensions(grid)
if not outside_grid(new_wall, height, width) and new_grid[new_wall[0]][new_wall[1]] == '.':
new_grid[new_wall[0]][new_wall[1]] = '#'
return new_wall, new_grid
return False
def get_starting_spaces_which_end_up_in_a_cycle(grid, visited_with_dir):
start_state_which_ends_up_in_a_cycle = set()
for elt in visited_with_dir:
elt_pos, elt_dir = elt
height, width = get_grid_dimensions(grid)
can_put_wall = get_new_grid_with_wall_in_front(grid, elt_pos, elt_dir)
if not can_put_wall:
continue
If we cannot put a wall in front of the guard it means one of the following things:
- the guard is already in front of a wall
- the guard is already on the edge of the grid, about to fall
- the starting position marked with
^is in front of the guard.
The first case and second case would not result in a cycle because we are sure that the guard falls off the grid eventually (hence does not enter in a loop) if we do not modify the grid.
The third case would not be valid because it was explicitly forbidden to put the wall on the guard.
Continuing the the code, we end up with this:
def solution_06b(data=None, filename=None):
# ... #
def get_starting_spaces_which_end_up_in_a_cycle(grid, visited_with_dir):
start_state_which_ends_up_in_a_cycle = set()
for elt in visited_with_dir:
# ... #
new_wall, new_grid = can_put_wall
start_pos = elt_pos
start_dir = turn_90(elt_dir)
result = detect_cycle(new_grid, start_pos, start_dir)
if result:
start_state_which_ends_up_in_a_cycle.add(new_wall)
return start_state_which_ends_up_in_a_cycle
Note that we start every cycle detection in front of the newly created wall so that we don’t have to follow the good part of the path again.
But It Works On The Sample Input!
Putting all the code together and feeding it the sample input results in the correct answer for the sample input: 6. However, using this code on the big stepbro input does not result in the correct answer.
Here is a setup in which the code does not work properly.
.##..
....#
#^.#.
Putting a wall / obstacle on (1, 0) would definitely result in a cycle, so there is at least one spot.
.##..
O...#
#^.#.
Our code as it is now also believes that putting an obstacle on (1, 1) will result in a cycle when it would clearly exit through the bottom of the grid:
.##..
.O..#
#^.#.
Do you know why our code thinks that? Here is your last chance to avoid the spoiler.
The reason why this happens is that the original path in the original graph goes like this:
.##..
.>>>#
#^.#.
then
.##..
...v#
#..#.
and finally
.##..
<<<<#
#..#.
We put the wall on (1, 1) during the first step
.##..
.O..#
#^.#.
which as we know does not result in a cycle. But we also put a wall on (1, 1) at this step:
.##..
.O<.#
#..#.
which does. Our attempt to optimize has been our downfall.
The optimization wherein we decided to start in the middle of the good path let us effectively ignore the obstacle the first time and just encounter it the second time we were supposed to bumped into it. However, this shouldn’t have happened.
Fixing It
Well, the most straightforward way to fix it would be to just remove that optimization.
However, we can push with that by simply adding a set tried_positions_of_the_wall, which keeps track of the positions of the wall that we have already tried.
def solution_06b(data=None, filename=None):
# ... #
def get_starting_spaces_which_end_up_in_a_cycle(grid, visited_with_dir):
start_state_which_ends_up_in_a_cycle = set()
tried_positions_of_the_wall = set()
for elt in visited_with_dir:
# ... #
new_wall, new_grid = can_put_wall
if new_wall in tried_positions_of_the_wall:
continue
tried_positions_of_the_wall.add(new_wall)
# ... #
This would work assuming that we are going through the steps of the original path in order. But are we? I’ll leave that as an exercise to the reader.