Advent of Code 2024 (Days 7, 8, 9, 10)
Here is my private leaderboard code if you want to come join the fun: 1598637-22d94a1d.
It seems that the challenge I am going for this year is to minimize the time between Part A and Part B.
Looking good except for that sneaky Day 6 problem.
6 06:33:40 33389 0 08:41:14 22241 0
5 07:14:06 37867 0 07:44:01 30632 0
4 11:01:41 53346 0 11:07:18 46074 0
I ended up solving Day 10’s Part B even before seeing the problem. Too bad I didn’t keep the code and had to recode it again.
Day 7 : Additions, Multiplications, and Concatenations
Here is the link to the problem.
The time between my Part A and Part B solve was like 4 minutes.
Part A
For me, this was more like a follow the instructions problem.
import itertools
def solution_07a(data=None, filename=None):
if not data:
cases = parse_07(filename)
else:
cases = data
def evaluate(nums, opers):
ret = nums[0]
for i in range(len(opers)):
if opers[i] == '+':
ret += nums[i+1]
else:
ret *= nums[i+1]
return ret
def is_test_case_valid(case):
target, nums = case
for opers in itertools.product(['+', '*'], repeat=len(nums)-1):
if target == evaluate(nums, opers):
return True
return False
ret = 0
for case in cases:
if is_test_case_valid(case):
target, nums = case
ret += target
return(ret)
Part B
Part B was more of the same, except that I tried being more 🧐 and added this early abort1 that stopped trying to evaluate if we’ve arrived at a number past the target:
if limit and ret > limit:
return -1
Day 8: Equation of a Line on a Grid
Here is the link to the problem.
The time between my Part A and Part B solve was like 6 minutes.
Part A
I ended up NOT using my patent-pending padding trick discussed in this 2023 problem and adapted to Day 4’s Problem because it seemed that we can go out of bounds quite quickly.
So I had to code an outside_grid function like a 1890s peasant.
def solution_08a(data=None, filename=None):
if not data:
lines = parse_08(filename)
else:
lines = data
height = len(lines)
width = len(lines[0])
def outside_grid(cur_pos):
return cur_pos[0] < 0 or cur_pos[1] < 0 or cur_pos[0] >= height or cur_pos[1] >= width
def is_occupied(grid, pos):
i, j = pos
return grid[i][j] != '.'
def get_antenna_locations(grid):
ret = defaultdict(lambda: [])
for i, line in enumerate(grid):
for j, char in enumerate(line):
if char != '.':
ret[char].append((i, j))
And why not throw in a couple of helper functions to begin?
This is my first iteration of the get_antipodes function, which… SPOILER ALERT… ended up being easily modifiable in Part B:
from collections import defaultdict
import itertools
def solution_08a(data=None, filename=None):
# ... #
def get_antipodes(pos1, pos2):
a, b = pos1
x, y = pos2
di, dj = x-a, y-b
return [(a-di, b-dj), (x+di, y+dj)]
def get_antipode_locations(grid):
ret = set()
ant_locs = get_antenna_locations(grid)
for char in ant_locs:
for pos1, pos2 in itertools.combinations(ant_locs[char], 2):
for ant in get_antipodes(pos1, pos2):
if outside_grid(ant):
continue
ret.add(ant)
return ret
return ( len(get_antipode_locations(lines) ))
Part B
As promised, here is the quick edit to get_antipodes which brings us from Part A solution to Part B solution quite quickly.
def get_antipodes(pos1, pos2):
ret = []
a, b = pos1
x, y = pos2
di, dj = x-a, y-b
lim = max(height, width) + 1
for k in range(lim):
i, j = a-k*di, b-k*dj
pos = i, j
if outside_grid(pos):
break
ret.append((i, j))
for k in range(lim):
i, j = x+k*di, y+k*dj
pos = i, j
if outside_grid(pos):
break
ret.append((i, j))
return ret
Day 9: Random Compression Algorithm
Here is the link to the problem.
The time between my Part A and Part B solve was like 26 minutes. 💀
Could be worse.
Part A
I knew I could just follow the instructions as written and I could wait for the code to run, but where is the fun in that? Let’s overengineer it!
First I keep track of things using two lists — occupied and empty. The elements of each list would be a triple (k, i, j) where k is the index of the file (-1 for all empty spots) and (i, j) are the range of its contents. I did this range thing early on just in case Part B would be like well actually… you need to deal with huge contiguous spaces!
def solution_09a(data=None, filename=None):
if not data:
line = parse_09(filename)
else:
line = data
def determine_file_positions_from_line(line):
ctr = 0
occupied = []
empty = []
file_id = 0
for i, char in enumerate(line):
if i%2 == 0:
occupied.append( (file_id, ctr, ctr+int(char)-1) )
file_id += 1
else:
if int(char) == 0:
continue
empty.append( (-1, ctr, ctr+int(char)-1) )
ctr += int(char)
return occupied, empty
Below is where the magic happens. The compress function. It modifies occupied, empty, and a new list called filled. What it does is it takes the last occupied range (removes it from the occupied list), counts the number of spaces it occupies, and puts it in space_to_fill.
def solution_09a(data=None, filename=None):
# ... #
def compress(occupied, empty, filled):
file_id, a, b = occupied.pop()
space_to_fill = b - a + 1
while space_to_fill > 0 and len(empty) > 0:
_, c, d = empty.pop(0)
if c > a:
empty.insert(0, (-1, c, d))
break
if space_to_fill > d-c+1:
filled.append((file_id, c, d))
space_to_fill -= d-c+1
return True
else:
filled.append((file_id, c, c+space_to_fill-1))
if c+space_to_fill <= d:
empty.insert(0, (-1, c+space_to_fill, d))
space_to_fill = 0
if space_to_fill > 0:
occupied.append((file_id, a, a+space_to_fill-1))
return False
return True
It’s kind of a mess, so let’s discuss how it works.
While there is still space_to_fill and empty slots still exist, we take the leftmost empty spot (hence, empty.pop(0)) and then figure out if we need to fill that whole empty range (when space_to_fill > d-c+1) just a bit (else). In the latter case, we put the remaining empty space back in the list via empty.insert(0, (-1, c+space_to_fill, d)).
The if c > a clause is basically how it knows to stop. If the empty space (which starts at c) is to the right of the occupied space (which starts at a) we are trying to put it, that means we are done and we exit the loop.
The compress function returns True or False depending on if it actually did anything or not. If we exit the while loop and there are no more empty ranges but still space to fill then that means the program has to take the L and put the thing it was processing back to occupied.
With this behavior, continuously_compress could know when it has to break out of its while loop.
def solution_09a(data=None, filename=None):
# ... #
def continuously_compress(occupied, empty, filled):
while len(occupied) > 0 and len(empty) > 0:
if not compress(occupied, empty, filled):
break
occupied, empty = determine_file_positions_from_line(line)
filled = []
continuously_compress(occupied, empty, filled)
ret = 0
for file_id, a, b in occupied + filled:
n = b-a+1
s = int(n*(n+1)/2+(a-1)*n)
ret += file_id*s
return ret
Still paranoid that we might need to deal with enormous ranges, we overoptimize the part where we get the checksum by actually using the mathematical formula for an arithmetic sequence.
It works and we get the answer!
Part B
Well, the Part B twist was not enormous ranges.
Wanting to build up on top of my previous solution, I decided to modify compress by adding a new unmoved list. This is for when we try to move an occupied range to an empty space. But none of the empty space could accommodate it. In retrospect, perhaps unmovable would have been a better name.
Instead of removing the first empty slot and potentially putting it back, I decided on abandoning that step and keep the empty ranges where they are until they are completely used up.
Now, we loop over entries of empty to see where things fit.
def compress(occupied, empty, filled, unmoved):
if len(occupied) == 0:
return False
file_id, a, b = occupied.pop()
space_to_fill = b - a + 1
for i in range(len(empty)):
_, c, d = empty[i]
if c > a or space_to_fill > d-c+1:
continue
if space_to_fill > d-c+1:
filled.append((file_id, c, d))
space_to_fill -= d-c+1
empty.pop(i)
return True
else:
filled.append((file_id, c, c+space_to_fill-1))
if c+space_to_fill <= d:
empty[i]= (-1, c+space_to_fill, d)
return True
else:
empty.pop(i)
return True
space_to_fill = 0
unmoved.append((file_id, a, b))
return True
It is at this point that I lose my credibility with all the dogmatic religious coders looking at all the modifications I am doing to the empty array and saying noOoOooOoo you shouldn’t modify the size of a list when you’re looping through it. And to which I reply: Chill out, it’s perfectly safe. When I change the size of the list, we get out of the loop immediately. Plus it’s a programming contest for fun.
Day 10: A Graph From A Hiking Grid
Here is the link to the problem.
The time between my Part A and Part B solve was like 5 minutes. Back on track baby!
Part A
We start with our patent-pending grid-padding trick.
from collections import defaultdict
def solution_10a(data=None, filename=None):
if not data:
lines = parse_10(filename)
else:
lines = data
def pad_lines(lines):
ret = []
for line in lines:
ret.append(line+'.')
ret.append('.'*len(ret[0]))
return ret
I’m guessing the most straightforward way to do this would be to make a Graph class or something? But we’re feeling creative today.
The first order of business is to have a list of the locations of each digit:
from collections import defaultdict
def solution_10a(data=None, filename=None):
# ... #
def number_locations(grid):
ret = defaultdict(lambda: [])
for i, line in enumerate(grid):
for j, char in enumerate(line):
ret[char].append((i, j))
return ret
This gives me a dictionary giving all the coordinates of the 0’s and 1’s, etc.
The next step was to make another dictionary of what I realize now are the edges of the graph.
from collections import defaultdict
def solution_10a(data=None, filename=None):
# ... #
def get_next_step_dic(grid, num_locs):
ret = defaultdict(lambda: set())
for n in range(8, -1, -1):
for i, j in num_locs[str(n)]:
for d in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
di, dj = d
if (i+di, j+dj) in num_locs[str(n+1)]:
ret[(i, j)].add((i+di, j+dj))
return ret
This is a dictionary with coordinates as keys and the entries are the the positions you can go to if you started from the position indicated by the key.
By the way, my first version of this looked like:
def get_next_step_dic(grid, num_locs):
ret = defaultdict(lambda: 0)
for n in range(9, -1, -1):
for i, j in num_locs[str(n)]:
if n == 9:
ret[(i, j)] = 1
continue
for d in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
di, dj = d
if grid[i+di][j+dj] == str(n+1):
ret[(i, j)] += ret[(i+di, j+dj)]
Which solved a different problem. But that’s not what we’re here for.
Now that we know all the edges, then we can traverse the graph. By taking unions of sets?
def solution_10a(data=None, filename=None):
# ... #
def get_reachable_from_loc(grid, next_step, loc):
if len(next_step[loc]) == 0:
return {loc}
else:
ret = set()
for i, j in next_step[loc]:
ret = ret | get_reachable_from_loc(grid, next_step, (i, j))
return ret
Once we have all the reachable spots from a location, we just take all the reachable spots of the 0-spots and check which of those spots are 9.
from collections import defaultdict
def solution_10a(data=None, filename=None):
# ... #
def num_reachable(grid, next_step, loc, nine_locs):
ret = 0
reachable_from_loc = get_reachable_from_loc(grid, next_step, loc)
for i, j in nine_locs:
if (i, j) in reachable_from_loc:
ret += 1
return ret
padded_grid = pad_lines(lines)
num_locs = number_locations(padded_grid)
next_step = get_next_step_dic(padded_grid, num_locs)
ret = 0
for loc in num_locs['0']:
ret += ( num_reachable(lines, next_step, loc, num_locs['9']) )
return ret
Part B
Part B, after talking with Seba, seemed to be easier than Part A today and I think I agree.
I’ve already solved Part B by eagerly using dynamic programming principles.
The following is the exact same code from my wrong version of get_next_step_dic.
def get_rating(grid, num_locs):
ret = defaultdict(lambda: 0)
for n in range(9, -1, -1):
for i, j in num_locs[str(n)]:
if n == 9:
ret[(i, j)] = 1
continue
for d in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
di, dj = d
if grid[i+di][j+dj] == str(n+1):
ret[(i, j)] += ret[(i+di, j+dj)]
And that solves Day 10!
Footnotes
-
Doing this might be illegal in some American states. ↩