“Looks like the Chief’s not here. Next!”
Disappointing! We still haven’t found the Chief and it’s already the 4th. Will we find him by Christmas?
But today’s adventure to Ceres monitoring station isn’t all wasted. A local elf needs our help to find XMAS!
It’s the traditional word search puzzle from magazines. We are given a word puzzle like
MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASXand we need to find how many times XMAS is written there, in any direction, backwards or forwards.
Read input
Today we need to do input reading in two steps because our isolated lines reader doesn’t allow neat tricks like these.
When I’m faced with a grid-based puzzle in Advent of Code, my default solution is to populate a dictionary where keys are coordinates and values are the corresponding values.
Dictionaries are better than lists of lists in my experience for a couple of reason:
- We can create sparse grids where not every coordinate exists and still operate as if it was a full grid.
- We don’t have to check for index boundaries: if we go beyond the coordinates, we get
Noneback.
Today we don’t have any sparseness to worry about but we get the second benefit.
def create_grid(rows):
"""Turns a list of strings into
a dictionary where keys are the coordinates
and values are the letters."""
grid = {}
for y, row in enumerate(rows):
for x, cell in enumerate(row):
grid[(x, y)] = cell
return gridInstead of a map function to be run per line, I read the data in as a list of strings and then use this helper grid creator to turn them into a dictionary.
rows = read_input(4, str)
grid = create_grid(rows)Part 1
Today’s puzzle was the first one this year where I didn’t immediately know the right solution. I had to think. My final solution took quite a few rounds of refactoring. I have previously written about my iterative approach in my blog. Basically: first I dig deep to get a working result by any means necessary and then start to climb back improving the code.
It really helps me to know I have a result I can compare to to make sure my refactoring and other changes don’t break the functionality. That’s why in my full code, you can see an assert result == [number] line at the bottom of each part. If I make a mistake, it will trip the code and raise an AssertionError.
The goal today is to count how many XMAS strings there are in the grid. They can be in any of the 8 cardinal and intercardinal directions. And they can be written forwards (XMAS) or backwards (SAMX).
Initially, I looked through every item in the grid and if it was X or S, I checked if it’s part of XMAS. When refactoring, I realised that I don’t have to check for ones starting with S because I was already checking all directions.
To check if a given index, in a given direction forms the word XMAS, I walk from starting direction to the desired direction and if I find something along the line that doesn’t fit the word, I return 0. If we get through the 3 remaining letters and they are M, A and S in that order, we return 1:
def check_direction(start, direction, grid):
"""Given a starting index,
a direction and a grid of letters, checks
if rest of the word forms MAS in the given direction."""
sx, sy = start
directions = {
"nw": (-1, -1),
"n": (0, -1),
"ne": (1, -1),
"e": (1, 0),
"se": (1, 1),
"s": (0, 1),
"sw": (-1, 1),
"w": (-1, 0),
}
letters = ("M", "A", "S")
for i in range(1, 4):
new_index = (
sx + directions[direction][0] * i,
sy + directions[direction][1] * i,
)
if grid.get(new_index) != letters[i - 1]:
return 0
return 1I then have a function that takes and index, checks if it points to an X and if it does, checks for the word in every of the 8 directions.
def check_for_xmas(index, grid):
"""Checks if a given index is a starting point
for a word XMAS in any direction."""
current = grid.get(index)
if current != "X":
return 0
found = 0
for direction in ["nw", "n", "ne", "e", "se", "s", "sw", "w"]:
found += check_direction(index, direction, grid)
return foundAnd finally, the wrapping around it for the part 1:
def part_1():
rows = read_input(4, str)
grid = create_grid(rows)
found = 0
for index in grid:
found += check_for_xmas(index, grid)
print(f"Part 1: {found}")Part 2
For the first time that I remember, the second part was simpler than the original.
This time we needed to check for any diagonal crosses that form two MASs:
M.S
.A.
S.MHere, I loop through all indices like last time but only act on ones that point to A:
def part_2():
rows = read_input(4, str)
grid = create_grid(rows)
found = 0
for index in grid:
if grid.get(index) == "A":
found += is_part_of_cross(index, grid)
print(f"Part 2: {found}")and then for each of those, check if the ones in diagonally adjacent coordinates form a cross as instructed:
def is_part_of_cross(index, grid):
"""Checks if the given index is in the middle of
a diagonal cross with M and S in opposite sides.
For example:
M.S
.A.
M.S
where the index points to A
"""
sx, sy = index
top_left = grid.get((sx - 1, sy - 1))
bottom_right = grid.get((sx + 1, sy + 1))
bottom_left = grid.get((sx + 1, sy - 1))
top_right = grid.get((sx - 1, sy + 1))
downwards_mas = (
top_left == "S" and bottom_right == "M") or (
top_left == "M" and bottom_right == "S"
)
upwards_mas = (
bottom_left == "S" and top_right == "M") or (
bottom_left == "M" and top_right == "S"
)
if downwards_mas and upwards_mas:
return 1
else:
return 0I really liked today’s puzzle. A good warmup for the more complex grid puzzles that are surely to come: ones with sparse grids, infinite grids or grids with moving items.
⭐️ 8 out of 8 stars but no sight of the Chief Historian.