Advent of Code Day 4 was a bit of a word search on steroids. The puzzle input was a very large grid of X, M, A, and Ss. In part 1 we were looking for all of the “XMAS” matches in the puzzle going vertical, horizontal, and diagonal both forwards and backwards. On top of it, letters could be shared with multiple instances of the word and they had to count seperately.
I decided to start off by trying to narrow down my search significantly. No matter what direction the word was going, it was always going to start with an “X” so I decided to start by making a list of the coordinates of all of the Xs in the puzzle.
for y, line in enumerate(data):
indeces = [i for i, y in enumerate(line) if y == "X"]
Once I had that, I had a good starting point. Because of the variety in directions that the word could go, I ended up with a total of 8 different step sequences that I had to look against.
L = (-1,0) R = (1,0) U = (0,-1) D = (0,1) UL = (-1,-1) UR = (1,-1) DL = (-1,1) DR = (1,1) SEQUENCES = [L, R, U, D, UL, UR, DL, DR]
Then I went through each X, and stepped through each sequence against it, checking each new letter against the overall “XMAS” pattern. That way, it would fail immediately as soon as an incorrect letter in the sequence was found.
def find_xmas(grid, x, y):
total = 0
for sequence in SEQUENCES:
valid = True
for i in range(len(WORD)):
cx = i * sequence[0]
cy = i * sequence[1]
if (0<= x + cx < len(grid[0])) and (0 <= y + cy < len(grid)):
if grid[y + cy][x + cx] != WORD[i]:
valid = False
break
else:
valid = False
break
if valid:
total += 1
return total
By doing it this way, it was also very easy to handle the same letter being used in multiple instances of the word. Because I check all directions, always starting with the X, I didn’t have to worry about a word getting missed, or counted twice accidently.
Part 2
This was an interesting little twist. Turns out that the instructions were wrong. Instead of looking for “XMAS” we were looking for two instances of “MAS”, in a cross like.
S?M ?A? S?M
I took the same basic idea that I had used for part one, but modified it a little bit. This time to start, I looked for all of the instances of “A” and checked against those (since each match would only have a single A in it). What changed this time though was the fact that I only had to look at the two diagonals since horizontal and vertical matches wouldn’t meet the condition.
After that, I just take the values of above and left and below and right and make sure that there is a “M” and a “S” in it, and then do the same with below and left and above and right.
def find_x_mas(grid, x, y):
if y < 1 or y > (len(grid) - 2) or x < 1 or x > (len(grid[0]) - 2):
return 0
tmp = []
tmp.append(grid[y - 1][x - 1])
tmp.append(grid[y + 1][x + 1])
if (not 'M' in tmp) or (not 'S' in tmp):
return 0
tmp = []
tmp.append(grid[y + 1][x - 1])
tmp.append(grid[y - 1][x + 1])
if (not 'M' in tmp) or (not 'S' in tmp):
return 0
else:
return 1
You can see my entire code on my github.