Advent of Code 2024 (Days 11, 12)
Here is my private leaderboard code if you want to come join the fun: 1598637-22d94a1d.
The de-facto challenge I ended up going for this year is to minimize the time between Part A and Part B.
Day 11 : Additions, Multiplications, and Concatenations
Here is the link to the problem.
The time between my Part A and Part B solve was like 14 seconds. A record!
Part A
It can’t be as simple as following instructions, right?
For Part A, that was the case. But since we are optimizing for the eventual surprise that Part B gives, I used the cache decorator from functools and it worked like a charm.
from functools import cache
def solution_11a(data=None, filename=None):
if not data:
lst = parse_11(filename)
else:
lst = data
@cache
def follow_rule(n, x):
s = str(n)
len_s = len(s)
if x == 0:
return 1
if n == 0:
return follow_rule(1, x-1)
elif len_s%2 == 0:
a = s[:len_s//2]
b = s[len_s//2:]
return follow_rule(int(a), x-1) + follow_rule(int(b), x-1)
else:
return follow_rule(n*2024, x-1)
return sum([follow_rule(n, x=25) for n in lst])
Part B
The seconds between submissions was a matter of replacing 25 with 75 and waiting for the answer.
Feeling guilty that I have “cheated” somehow by using this library, I implemented the caching myself right after submitting:
def solution_11b(data=None, filename=None):
if not data:
lst = parse_11(filename)
else:
lst = data
answers = {}
ct = []
def follow_rule(n, x):
s = str(n)
len_s = len(s)
if (n, x) in answers:
return answers[(n, x)]
if x == 0:
return 1
if n == 0:
ret = follow_rule(1, x-1)
answers[(1, x-1)] = ret
return ret
elif len_s%2 == 0:
a = s[:len_s//2]
b = s[len_s//2:]
ret_a = follow_rule(int(a), x-1)
answers[(int(a), x-1)] = ret_a
ret_b = follow_rule(int(b), x-1)
answers[(int(b), x-1)] = ret_b
return ret_a + ret_b
else:
ret = follow_rule(n*2024, x-1)
answers[(n*2024, x-1)] = ret
return ret
ret = sum([follow_rule(n, x=75) for n in lst])
return ret
Day 12: Perimeter, Area, and Sides
Here is the link to the problem.
The time between my Part A and Part B solve was like 1 hour and 35 minutes. A new record! 🙃
Part A
Part A had two parts: find the area and find the perimter.
Finding the area was a classic flood fill problem.
Finding the perimeter was also a classic flood fill problem but you have to count properly.
The way I found the perimeter was drawing a square around each cell, and removing the edges that are shared between adjacent positions.
So for example, we had:
....
.AA.
.A..
I draw a square around each A, so now I have 12 edges.
.......
.+-+-+.
.|A|A|.
.+-+-+.
.|A|...
.+-+...
Then I remove the edges between each adjacent A.
.......
.+-+-+.
.|A A|.
.+ +-+.
.|A|...
.+-+...
And that’s how I figure out the perimeter in Part A.
def solution_12a(data=None, filename=None):
if not data:
grid = parse_12(filename)
else:
grid = data
height = len(grid)
width = len(grid[0])
class Region:
def __init__(self, grid, i, j):
self.coordinates = set()
visited = set()
to_visit = [(i, j)]
self.coordinates.add((i, j))
while len(to_visit) > 0:
a, b = to_visit.pop()
visited.add((a, b))
for di, dj in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
x, y = a+di, b+dj
if (x, y) in visited:
continue
if x not in range(0, height):
continue
if y not in range(0, width):
continue
if grid[x][y] == grid[i][j]:
self.coordinates.add((x, y))
to_visit.append((x, y))
def __repr__(self):
return self.coordinates.__repr__()
def get_area(self):
return len(self.coordinates)
def get_perimeter(self):
ret = self.get_area()*4
for (i, j) in self.coordinates:
for di, dj in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
x, y = i+di, j+dj
if x not in range(0, height):
continue
if y not in range(0, width):
continue
if (x, y) in self.coordinates:
ret -= 1
return int(ret)
def get_sides(self):
start = min(self.coordinates)
d_index = 0
dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)]
visited = set()
to_visit = [start + (d_index)]
while len(to_visit) > 0:
def get_regions(grid):
regions = []
covered_cells = set()
for i in range(0, height):
for j in range(0, width):
if (i, j) in covered_cells:
continue
new_region = Region(grid, i, j)
covered_cells = new_region.coordinates | covered_cells
regions.append(new_region)
return regions
regions = get_regions(grid)
ret = 0
for r in regions:
ret += r.get_area() * r.get_perimeter()
return ret
I tried organizing the code using a Region class this time, but I hadn’t prepared enough for the next question.
Part B
It took some time but I eventually ended up with a solution that needed more memory than initially needed.
The first step I did was to blow up the figure so that the corners would stick out.
So something like
..X..
XXXXX
...XX
would be “blown” up to be this:
....X....
....X....
XXXXXXXXX
......X.X
......XXX
Counting only the outline of the exterior, this would have the same number of sides as the original polygon.
This is why I then wrote a function get_outline, which gives us this:
....XXX....
....X.X....
XXXXX.XXXXX
X.........X
XXXXXXX.X.X
......X...X
......XXXXX
It does give a lone X somewhere in the middle, but our side-counting will not pay heed to that.
The idea was that counting the number of elbows (i. e. corners) of the outline of the blown-up version of the original figure is equal to the number of sides.
And my code worked well for most cases.
Except for this rather nasty case, which was thankfully part of the samples.
XXXXXX
XXX..X
XXX..X
X..XXX
X..XXX
XXXXXX
Using my same get_outline function of the blown-up version results in this:
XXXXXXXXXXXXX
X...........X
X.X.X.XXXXX.X
X.....X...X.X
X.X.X.X...X.X
X.....X...X.X
X.XXXXXXXXX.X
X.X...X.....X
X.X...X.X.X.X
X.X...X.....X
X.XXXXX.X.X.X
X...........X
XXXXXXXXXXXXX
The corner counting conjecture still works here but my code was counting the central intersection four times, instead of two. Correcting this bug resulted in the correct number of “elbows” (or turns) for me. Thus, giving me the correct number of sides.
I feel like my solution for this one was quite ad hoc. It also hinged on several educated guesses on how I should count the sides.
I haven’t really sat down yet to convince myself why it should work, but it looks like it does.
And using this slightly messy code…
def solution_12b(data=None, filename=None):
if not data:
grid = parse_12(filename)
else:
grid = data
height = len(grid)
width = len(grid[0])
class Region:
def __init__(self, grid, i, j):
self.coordinates = set()
visited = set()
to_visit = [(i, j)]
self.coordinates.add((i, j))
while len(to_visit) > 0:
a, b = to_visit.pop()
visited.add((a, b))
for di, dj in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
x, y = a+di, b+dj
if (x, y) in visited:
continue
if x not in range(0, height):
continue
if y not in range(0, width):
continue
if grid[x][y] == grid[i][j]:
self.coordinates.add((x, y))
to_visit.append((x, y))
def __repr__(self):
return self.coordinates.__repr__()
def get_area(self):
return len(self.coordinates)
def get_perimeter(self):
ret = self.get_area()*4
for (i, j) in self.coordinates:
for di, dj in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
x, y = i+di, j+dj
if x not in range(0, height):
continue
if y not in range(0, width):
continue
if (x, y) in self.coordinates:
ret -= 1
return int(ret)
def zoom_in(self, coords=None):
ret = set()
if coords is None:
coords = self.coordinates
for (i, j) in coords:
ret.add((2*i, 2*j))
if (i+1, j) in coords:
ret.add((2*i+1, 2*j))
if (i,j+1) in coords:
ret.add((2*i, 2*j+1))
return ret
def get_outline(self, coords):
ret = set()
for (i, j) in coords:
for di, dj in [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]:
x, y = i+di, j+dj
if (x, y) not in coords:
ret.add((x, y))
return ret
def get_elbows(self, coords):
ret = []
for (i, j) in coords:
ct = 0
if (i+1, j) in coords and (i, j+1) in coords:
ret.append((i, j))
ct += 1
if (i-1, j) in coords and (i, j-1) in coords:
ret.append((i, j))
ct += 1
if ct >= 2:
continue
if (i+1, j) in coords and (i, j-1) in coords:
ret.append((i, j))
ct += 1
if ct >= 2:
continue
if (i-1, j) in coords and (i, j+1) in coords:
ret.append((i, j))
ct += 1
if ct >= 2:
continue
return ret
def get_regions(grid):
regions = []
covered_cells = set()
for i in range(0, height):
for j in range(0, width):
if (i, j) in covered_cells:
continue
new_region = Region(grid, i, j)
covered_cells = new_region.coordinates | covered_cells
regions.append(new_region)
return regions
regions = get_regions(grid)
ret = 0
for r in regions:
ret += r.get_area() * len(r.get_elbows(r.get_outline(r.zoom_in())))
return ret
we get the answer.
If anyone has a good way to explain it, or if you did it in a completely different way, don’t hesitate to contact me!