Advent of Code 2025 - Python - Day 4
Today, we're continuing our descent into Santa's North Pole complex. Having repaired the escalators last time, we find ourselves in the printing department. They say they can help us get farther into the complex - there's a cafeteria on the other side of a brick wall, and they're willing to use one of their forklifts to help us bust down the wall. But they're pretty busy - it would be nice if we could help them optimize their forklift routes to free up some time so they can help us.
Their warehouse is laid out in a grid, and they have rolls of paper (@) and empty spaces (.):
..@@.@@@@.
@@@.@.@.@@
@@@@@.@.@@
@.@@@@..@.
@@.@@@@.@@
.@@@@@@@.@
.@.@.@.@@@
@.@@@.@@@@
.@@@@@@@@.
@.@.@@@.@.
Part 1
For our initial puzzle, we have to determine if their forklifts can access a roll of paper. A roll of paper is accessible if there are fewer than four rolls of paper in the eight adjacent positions (up, down, left, right, and the diagonals).
I'll assume that spots that are "off the map" count as not having a roll of paper - i.e., a roll of paper in a corner is automatically accessible because it can have at most three adjacent rolls.
First, we need to tackle parsing the input text, shown above. Unlike previous puzzles, this time our text is really a 2D map, even though it's still encoded in the form of lines of text. So, unlike previous puzzles, we're going to need to reference other "lines" while we're processing the current "line".
I'll start by doing the simple thing and parsing this into a list of lists, Python's most direct equivalent to a 2D array:
# Parse input into a list of lists
rawLines = []
with open("data/4.short", "r") as f:
rawLines = [line.strip() for line in f.readlines()]
warehouseMap = []
for line in rawLines:
warehouseMap.append([c for c in line])
I think this little "unpacking" comprehension is pretty cool. As I've said before, I really like Python list comprehensions.
This gives us:
[['.', '.', '@', '@', '.', '@', '@', '@', '@', '.'], ['@', '@', '@', '.', '@', '.', '@', '.', '@', '@'], ['@', '@', '@', '@', '@', '.', '@', '.', '@', '@'], ['@', '.', '@', '@', '@', '@', '.', '.', '@', '.'], ['@', '@', '.', '@', '@', '@', '@', '.', '@', '@'], ['.', '@', '@', '@', '@', '@', '@', '@', '.', '@'], ['.', '@', '.', '@', '.', '@', '.', '@', '@', '@'], ['@', '.', '@', '@', '@', '.', '@', '@', '@', '@'], ['.', '@', '@', '@', '@', '@', '@', '@', '@', '.'], ['@', '.', '@', '.', '@', '@', '@', '.', '@', '.']]
Tactically inserting some newlines in that one-line printout, we can see that we've successfully put each character of the map into its own spot:
[['.', '.', '@', '@', '.', '@', '@', '@', '@', '.'],
['@', '@', '@', '.', '@', '.', '@', '.', '@', '@'],
['@', '@', '@', '@', '@', '.', '@', '.', '@', '@'],
['@', '.', '@', '@', '@', '@', '.', '.', '@', '.'],
['@', '@', '.', '@', '@', '@', '@', '.', '@', '@'],
['.', '@', '@', '@', '@', '@', '@', '@', '.', '@'],
['.', '@', '.', '@', '.', '@', '.', '@', '@', '@'],
['@', '.', '@', '@', '@', '.', '@', '@', '@', '@'],
['.', '@', '@', '@', '@', '@', '@', '@', '@', '.'],
['@', '.', '@', '.', '@', '@', '@', '.', '@', '.']]
Now that our information is in a format we can work with, we can get started with a solution.
The question we're trying to answer - how many rolls of paper are accessible - is conceptually simple, and we could do it with a totally flat script like how we've done previous puzzles. But I can see the solution getting a little more complicated; instead of drowning in linked complexity, I think I'll start writing some functions and make our code a little cleaner.
We're going to start with a simple function - determining how many rolls are adjacent to the roll in the given position on the map. That's our output - a straightforward integer. To compute that, I know we'll need three things: the map, the X position in the map, and the Y position in the map. So that's our function signature:
getAdjacentRolls(layout, xPos, yPos)
Python actually supports type annotations in function signatures, so I'll add those with the typing module:
from typing import List
def getAdjacentRolls(layout: List[List[str]], xPos: int, yPos: int) -> int:
Having the types annotated at the function boundary like this gives us a kind of in-code documentation of what "contract" the function expects from the rest of the code. Here, that "contract" says something like "if you give me a layout, in the form of a list of list of strings; an X position, in the form of an integer; and a Y position, in the form of an integer, I will return to you an integer". While all of this could be captured in a comment, and the type annotations are in a sense superfluous, I always find them helpful. As I've said before, I'm a C programmer at heart so all this ducktyping seems wrong to begin with. Putting some bumpers in place here just feels right.
In this function, our first order of business is to determine what other xPos and yPos values we need to check - that is, what other positions are adjacent to the one we were given in the function call. This is simply the permutations of assigning adding 1, 0, and -1 to xPos and yPos, but we have to be a little more careful than that because going out-of-bounds (e.g., checking what's to the left of something in the leftmost column) will cause an error.
I'll make another function to retrieve the symbol from a given xPos and yPos. In that function is where we'll house the checks to make sure we don't access the layout in an invalid way:
def getLocationSymbol(layout: List[List[str]], xPos: int, yPos: int) -> str:
From this function we'll return a . if the location is empty, an @ if it has a roll of paper, and a B if it's invalid (for being out of "b"ounds). I haven't come across a convenient way to do enums in vanilla Python, so I'll just have to make a comment for what these three magic string values mean.
We'll tackle getLocationSymbol first:
# Returns:
# @ for paper roll
# . for empty
# B for out of bounds
def getLocationSymbol(layout: List[List[str]], xPos: int, yPos: int) -> str:
maxXPos = 9
maxYPos = 9
if xPos < 0:
return "B"
if yPos < 0:
return "B"
if xPos > maxXPos:
return "B"
if yPos > maxYPos:
return "B"
return layout[yPos][xPos]
This function performs a simple bounds check to make sure the position we're meant to retrieve isn't outside any of our four boundaries, and if it's not then it returns the symbol at the location requested. There are three notable things about how I've written this function:
- I like early returns, a lot. I think they're a great way to check for edge cases, so that the "meat" of your logic isn't nested ten indents deep inside a bunch of
elseclauses. Note that I don't needelseclauses here, since if we hit theifwe return and the function never gets past theifclause. This helps cut down on indentation. - The
maxXPosandmaxYPosare "configurable" in that it's easy to change the source code - having the values at the top of the function and in one place makes it easy to come back later and modify the logic if necessary. In this case it doesn't matter much (though it does make it clear what the values mean, and something likeif xPos > 9is definitively less clear thanif xPos > maxXPos), but in a case where we had to use that value multiple times in the function it makes sense to put it in a variable and make it obvious what the magic number does. - We have to return
layout[yPos][xPos], which seems backwards since we usually address things as(X, Y). But we need to remember the shape of the data we're working with:layoutis a list of lists of values, where each nested list is a row and each value is a "cell" inside our "table". The first thing we index into, when we index intolayoutis the correct row. The second thing is the item within that row. As such, the first value in our 2D index is the Y value - how many rows down from the top should we access - and the second value is the X value - how many items across from the left should we access.
With that function in place, getAdjacentRolls is now straightforward:
def getAdjacentRolls(layout: List[List[str]], xPos: int, yPos: int) -> int:
adjacentSymbols = []
for xAdj in [-1, 0, 1]:
for yAdj in [-1, 0, 1]:
if xAdj == 0 and yAdj == 0:
continue
adjacentSymbols.append(getLocationSymbol(layout,
xPos + xAdj,
yPos + yAdj))
return adjacentSymbols.count("@")
This function takes advantage of the way Python's for loops (which are basically a "foreach" loop) work under the hood - after the in keyword you provide something that is "iterable" (that Python can iterate over), and the variable between the for and in keywords takes on each value in the iterable collection in turn. This is conceptually true even for index-based loops using the range() builtin - range() just creates a generator (which is like a list where each element is lazily computed when it's needed) based on the parameters you pass it, so its result is an iterable just like the hardcoded lists in my code snippet.
So for every permutation of -1, 0, and 1 for both X and Y - excluding 0, 0 since that's not an adjacent position, that's the position we're looking at - we're calling our getLocationSymbol function and adding the X and Y adjustments as necessary. At the end, we get a list of the symbols adjacent to the position getAdjacentRolls is called for. Note that xPos=0, yPos=0 is the top-left item in our layout, not 1, 1.
If we run getAdjacentRolls on the top-left item in our sample data, shown at the top of the post, we correctly get 2, and if we print out the adjacent symbols list before returning it gives us:
['B', 'B', 'B', 'B', '@', 'B', '.', '@']
This is what we'd expect - we have two @s, a ., and five out-of-bounds positions.
With this working, the the path for the rest of Part 1 is now clear. We need to loop through our entire map, calling this function on every location, and keeping track of how many are accessible. To restate, "accessible" is defined by there being fewer than four adjacent rolls:
# Compute
accessibleCount = 0
for rowIdx, row in enumerate(warehouseMap):
for colIdx, symbol in enumerate(row):
# Don't check for accessibility if this location doesn't have a roll
if symbol != "@":
continue
if getAdjacentRolls(warehouseMap, colIdx, rowIdx) < 4:
accessibleCount += 1
The only two things to be careful about here are (1) that we don't care if a location is accessible if it doesn't have a roll in it, so we move on to the next loop iteration if symbol (the character at the location we're inspecting for accessibility) isn't a roll, and (2) that colIdx is from the inner loop, rowIdx is from the outer loop, and they map onto X and Y respectively. Getting the order wrong when passing them to the function will generate the wrong answer.
These parts all work for the smaller input, but they don't work for the larger input! There's a glaring issue here, listed above for all to see.
In getLocationSymbol, I hardcoded maxXPos and maxYPos. This means that when passed the larger layout (which is 138x138, not 10x10), the function doesn't work. Luckily, layout itself has all the information we need to be able to calculate the maximum values:
maxXPos = len(layout[0]) - 1
maxYPos = len(layout) - 1
Here we're again utilizing the way the data is laid out - layout[0] is the first row, "the length of the first row" is the number of columns we have, and we subtract one to make up for the fact that Python is zero-indexed. layout itself is a list of lists, and the length of the outer list is "the number of lists inside this list", i.e. the number of rows, i.e. the maximum Y position.
This gives us the final Part 1 solution:
from typing import List
# Returns:
# @ for paper roll
# . for empty
# B for out of bounds
def getLocationSymbol(layout: List[List[str]], xPos: int, yPos: int) -> str:
maxXPos = len(layout[0]) - 1
maxYPos = len(layout) - 1
if xPos < 0:
return "B"
if yPos < 0:
return "B"
if xPos > maxXPos:
return "B"
if yPos > maxYPos:
return "B"
return layout[yPos][xPos]
def getAdjacentRolls(layout: List[List[str]], xPos: int, yPos: int) -> int:
adjacentSymbols = []
for xAdj in [-1, 0, 1]:
for yAdj in [-1, 0, 1]:
if xAdj == 0 and yAdj == 0:
continue
adjacentSymbols.append(getLocationSymbol(layout,
xPos + xAdj,
yPos + yAdj))
return adjacentSymbols.count("@")
# Parse input into a list of lists
rawLines = []
with open("data/4.short", "r") as f:
rawLines = [line.strip() for line in f.readlines()]
warehouseMap = []
for line in rawLines:
warehouseMap.append([c for c in line])
# Compute
accessibleCount = 0
for rowIdx, row in enumerate(warehouseMap):
for colIdx, symbol in enumerate(row):
# Don't check for accessibility if this location doesn't have a roll
if symbol != "@":
continue
if getAdjacentRolls(warehouseMap, colIdx, rowIdx) < 4:
accessibleCount += 1
print(accessibleCount)
For the sample input, shown at the top of this post, this code correctly gives us the answer 13. For my full input, it correctly gives the answer 1491. This script runs in 0.031 seconds on the full input.
Part 2
Next, the elves ask the next logical question - once we remove all those rolls of paper, what new rolls are accessible now that those spaces have been opened up? The specific value we now need to compute is the total number of rolls of paper that can be removed by the elves with their forklifts.
(If it seems like they'd be able to remove all of them, I recommend you go solve Part 1 yourself to see the Part 2 prompt, where it shows an example layout that can't be fully removed).
Our code is fairly well-set-up to handle this twist. Our parsing logic doesn't need to change, and we're already able to compute how many rolls of paper can be removed for a given layout. We just need to add a layer of iteration on top - we're going to run our existing logic, modify the layout to remove the rolls that our code says can be removed, and then run it again. And again, and again, and again - until finally we run it and our code says that no rolls can be removed.
An interesting optimization might be to try to remove the rolls progressively, as we scan through the map, and take those removals into account for subsequent scans. This isn't strictly necessary, though - we'll get the right answer by "statically" scanning a fixed layout, modifying it, then scanning that layout, modifying it, etc. It'll just take more iterations. Computers are fast, so that's OK.
We have to make surprisingly few alterations to make our computation loop fit for purpose:
# Compute
accessibleCount = 0
accessibleCountDelta = -1
while accessibleCountDelta != 0:
accessibleCountDelta = 0
for rowIdx, row in enumerate(warehouseMap):
for colIdx, symbol in enumerate(row):
# Don't check if this location doesn't have a roll
if symbol != "@":
continue
if getAdjacentRolls(warehouseMap, colIdx, rowIdx) < 4:
accessibleCountDelta += 1
warehouseMap[rowIdx][colIdx] = "."
accessibleCount += accessibleCountDelta
First, notice that we're able to track how many rolls were accessible "this iteration" of the while loop with the addition of just one variable - accessibleCountDelta. By accumulating our per-loop count there, we can check that value in the while loop to see if anything changed. Once we get an accessibleCountDelta of zero, we know that nothing in the map is accessible and that the map is now fixed. That means we're done and can exit the loop.
Second, see that we have to initialize accessibleCountDelta to something nonzero before the loop starts - because the loop will check that value before it starts for the first time, we can't define it inside the loop itself. And we need it to have a nonzero value, otherwise it would be zero when the while loop checks for the first time and the loop would never run.
Finally, notice exactly how we modify our warehouseMap. We can't set symbol to the new value (even though that would be a pretty neat feature) because it's just a local variable which happens to have the same value as the symbol that's at the position we're looking at (or, in C parlance, it's an lvalue). We can't modify row for the same reason - it's just a list that happens to have the same value is the row we're looking at in warehouseMap. The easiest way to durably modify warehouseMap when we're deep in these foreach loops is to temporarily discard the foreach syntactic sugar and modify the value using indices. This gets directly at the actual underlying data and makes a change that'll stick around once we cycle through to the next while loop iteration.
Those are the only changes we have to make! Our full code is now:
from typing import List
# Returns:
# @ for paper roll
# . for empty
# B for out of bounds
def getLocationSymbol(layout: List[List[str]], xPos: int, yPos: int) -> str:
maxXPos = len(layout[0]) - 1
maxYPos = len(layout) - 1
if xPos < 0:
return "B"
if yPos < 0:
return "B"
if xPos > maxXPos:
return "B"
if yPos > maxYPos:
return "B"
return layout[yPos][xPos]
def getAdjacentRolls(layout: List[List[str]], xPos: int, yPos: int) -> int:
adjacentSymbols = []
for xAdj in [-1, 0, 1]:
for yAdj in [-1, 0, 1]:
if xAdj == 0 and yAdj == 0:
continue
adjacentSymbols.append(getLocationSymbol(layout,
xPos + xAdj,
yPos + yAdj))
return adjacentSymbols.count("@")
# Parse input into a list of lists
rawLines = []
with open("data/4.long", "r") as f:
rawLines = [line.strip() for line in f.readlines()]
warehouseMap = []
for line in rawLines:
warehouseMap.append([c for c in line])
# Compute
accessibleCount = 0
accessibleCountDelta = -1
while accessibleCountDelta != 0:
accessibleCountDelta = 0
for rowIdx, row in enumerate(warehouseMap):
for colIdx, symbol in enumerate(row):
# Don't check if this location doesn't have a roll
if symbol != "@":
continue
if getAdjacentRolls(warehouseMap, colIdx, rowIdx) < 4:
accessibleCountDelta += 1
warehouseMap[rowIdx][colIdx] = "."
accessibleCount += accessibleCountDelta
print(accessibleCount)
This gives the correct answer of 43 for the sample input, shown at the top of this post, and 8722 for my real input. This script takes 0.171 seconds to run for my real input.
I think there are some good takeaways here:
- Your program can be complex or simple just based on where you draw function boundaries. I think I chose good functions - our main computation loop can simply query
getAdjacentRollsto get a count of how many rolls are adjacent to this one, and our logic can go from there.getAdjacentRollsdoesn't need to worry about list boundaries or access violations, becausegetLocationSymbolhandles that for it. By boxing up this functionality we can ignore the complexity lying underneath, take the function at its word that it can compute what it says it can, and worry about higher-order problems (like what to do about the count of@symbols in adjacent cells, or which locations to callgetAdjacentRollson in the first place). - Python has a lot of affordances that make code like this pretty easy to write. In C, this code would be a lot more than 67 lines and would be doing a lot more out in the open. There's a lot of hidden complexity inside Python's for(each) loops and string handling.
- If you have the right abstractions, modifying your code to compute "something related but different" can be easy. It can also be hard - sometimes the "something different" cuts right through one of your abstractions and you have to refactor everything to surface information that you had previously kept inside one of those boxes. This can be luck of the draw, sometimes, but sometimes you make your own luck. This problem was extremely simple, in the grand scheme of things, but the point stands.
On to Part 5!