Advent of Code 2024 (Days 1, 2, 3, 4)
For this first batch, for the sake of organization, I separated the input parser and the problem solver into two functions. This means that we will have at least three functions for each day, one whose name will be of the form parse_00 and two others whose names will be of the form solution_00a and solution_00b.
Since I did this in one sitting, like maybe within a span of two hours, I feel like I optimized for minimum code change from Part A to Part B. So far, so good !
Here is my private leaderboard code if you want to come join the fun: 1598637-22d94a1d.
Day 1 : The Artificial List Problem
Here is the link to the problem.
Part A
Expected this to be easy, and it was. Aside from the reading! I couldn’t be bothered reading the whole story so I skimmed through it and eventually figured out what the problem was trying to ask. Sorry, NOI.PH Elimination Round participants for all the stories you probably weren’t interested in!
def solution_01a(data=None):
if not data:
list1, list2 = parse_01()
else:
list1, list2 = data
list1 = sorted(list1)
list2 = sorted(list2)
ret = 0
for i in range(len(list1)):
ret += abs(list1[i] - list2[i])
return ret
Part B
I was tempted to just do Part B as it was written. Make a dictionary on how many times each number appears on the second list, then add it. But that meant having to rewrite a lot of the code. So, using some… math… I figured this would do the trick:
def solution_01b(data=None):
if not data:
list1, list2 = parse_01()
else:
list1, list2 = data
ret = 0
for i in list1:
for j in list2:
if i == j:
ret += i
return ret
Granted, this might not be the most optimal solution but hey, it’s waitable and it gets the job done!
Day 2 : Safe and Unsafe Strictly Monotonic Sequences
Here is the link to the problem.
Part A
Here is my quick and dirty solution:
def solution_02a(data=None):
if not data:
grid = parse_02()
else:
grid = data
def process_row(row):
if row[0] == row[1]:
return False
sign = (row[0]-row[1]) / abs(row[0]-row[1])
for n, m in zip(row, row[1:]):
if abs(n-m) <= 0 or abs(n-m) > 3:
return 0
if sign != (n-m)/abs(n-m):
return 0
return 1
return sum([process_row(row) for row in grid])
What I did was that I assigned to sign either 1 or -1 depending on whether or not the first pair increases or decreases.
Then I returned 0 if it was unsafe and 1 if it was safe. Summing up the results of this process_row function gives the number of safe sequences.
I’ve seen other solutions where it did a pass to check if it was strictly increasing or strictly decreasing before proceding. While that may be more readable, this one uses just one for loop.
In the end, the solution has the same algorithmic complexity. But in mine, I get to flex this sign function
And because math is pedantic, I had to make sure that x isn’t 0. I may or may not have gotten an error like that.
Part B
Part B is like Part A, but excluding one would have been acceptable. I didn’t immediately think of a quick elegant solution, so I just did the brute-force method:
def solution_02b(data=None):
if not data:
grid = parse_02()
else:
grid = data
def process_row(row):
if row[0] == row[1]:
return False
sign = (row[0]-row[1]) / abs(row[0]-row[1])
for n, m in zip(row, row[1:]):
if abs(n-m) <= 0 or abs(n-m) > 3:
return 0
if sign != (n-m)/abs(n-m):
return 0
return 1
def process_row_with_tolerance(row):
if process_row(row) == 1:
return 1
for i in range(len(row)):
skipped_i = row[0:i] + row[i+1:]
if process_row(skipped_i) == 1:
return 1
return 0
return sum([process_row_with_tolerance(row) for row in grid])
Day 3 : Mul String Parsing Problem
Here is the link to the problem.
Part A
Finally imported a library, the regex one.
import re
def solution_03a(data=None):
if not data:
lines = parse_03()
else:
lines = data
ret = 0
for line in lines:
matches = re.findall(r"mul\(([0-9]+),([0-9]+)\)", line)
for match in matches:
a, b = match
ret += int(a) * int(b)
return ret
It was a good refresher on capture groups. And I was reminded of the r prefix on strings to tell Python it’s a regex.
Part B
At this point, I knew how to edit the regex but I didn’t know how the results of findall would be returned.
def solution_03b(data=None):
if not data:
lines = parse_03()
else:
lines = data
ret = 0
enabled = True
for line in lines:
matches = re.findall(r"(do)\(\)|(don't)\(\)|mul\(([0-9]+),([0-9]+)\)", line)
for match in matches:
a, b, c, d = match
if a == 'do':
enabled = True
elif b == "don't":
enabled = False
else:
if enabled:
ret += int(c) * int(d)
return ret
So apparently, findall returns all capture groups even if they are delimited with |. Super interesting find.
In the end, I was left with three cases:
- one where the first capture group is
doand the rest blank, - one where the second capture group is
don'tand the rest blank, and - finally, one where the last two capture groups are strings representing integers
With minimal code changes from the first, I managed.
Day 4 : X-MAS Word Search
Here is the link to the problem.
Part A
A classic word search and just like last year’s Day 3, where we use padding again.
def solution_04a(data=None):
if not data:
grid = parse_04()
else:
grid = data
ret = 0
def get_padded_grid(grid, pad=3):
new_grid = []
for row in grid:
new_grid.append(row+('.'*pad))
for i in range(3):
new_grid.append('.'*len(new_grid[0]))
return new_grid
def can_read_string(grid, start, direction, s):
i_start, j_start = start
i_delta, j_delta = direction
for k in range(len(s)):
i = i_start + k*i_delta
j = j_start + k*j_delta
if grid[i][j] != s[k]:
return False
return True
n_rows = len(grid)
n_cols = len(grid[0])
padded_grid = get_padded_grid(grid)
ret = 0
for i in range(n_rows):
for j in range(n_cols):
for d in [(0, 1), (1, 0), (1, 1), (-1, 1)]:
if can_read_string(padded_grid, (i, j), d, "XMAS"):
ret += 1
if can_read_string(padded_grid, (i, j), d, "SAMX"):
ret += 1
return ret
This year, I was smart and organized enough to use a direction parameter which I was quite proud of. Not crafty enough to not need to hardcode the reverse of the string. Ehh. Maybe next year.
One surprising thing that worked was that a direction with negative values worked despite me forgetting to pad the left and the top.
After some thought, I realized that since this is Python, the negative indices wrap around and hit my right and bottom paddings!
The code would not work without the padding (I tried!) because, well, the index would be out of bounds!
Part B
Thankfully, the Part B did not require a lot of modification from my original code. It’s a miracle that I could reuse my can_read_string function all the way up to here. The challenge was simply to figure out how to “detect” all these X-MAS’s.
After some thought, here’s my final code with the appropriate modifications.
def solution_04b(data=None):
if not data:
grid = parse_04()
else:
grid = data
ret = 0
def get_padded_grid(grid, pad=3):
new_grid = []
for row in grid:
new_grid.append(row+('.'*pad))
for i in range(3):
new_grid.append('.'*len(new_grid[0]))
return new_grid
def can_read_string(grid, start, direction, s):
i_start, j_start = start
i_delta, j_delta = direction
for k in range(len(s)):
i = i_start + k*i_delta
j = j_start + k*j_delta
if grid[i][j] != s[k]:
return False
return True
n_rows = len(grid)
n_cols = len(grid[0])
padded_grid = get_padded_grid(grid)
ret = 0
for i in range(n_rows):
for j in range(n_cols):
if can_read_string(padded_grid, (i, j), (1, 1), "MAS") and can_read_string(padded_grid, (i, j+2), (1, -1), "MAS"):
ret += 1
if can_read_string(padded_grid, (i, j), (1, 1), "MAS") and can_read_string(padded_grid, (i, j+2), (1, -1), "SAM"):
ret += 1
if can_read_string(padded_grid, (i, j), (1, 1), "SAM") and can_read_string(padded_grid, (i, j+2), (1, -1), "SAM"):
ret += 1
if can_read_string(padded_grid, (i, j), (1, 1), "SAM") and can_read_string(padded_grid, (i, j+2), (1, -1), "MAS"):
ret += 1
return ret
Detour : Interesting Things I Found Today
Also, not related but here are a few things people might find interesting:
- A classy-sounding Gen Z adaptation (?) of Jingle Bells
- Jet Lag Season 12 Hide + Seek in Japan is out now on Nebula. I have two one-week trial invites to give out if anyone is interested. Contact me for them.