Advent of Code 2024 - Day 4: Ceres Search

:: programming, python, puzzle

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
from advent import parse

input = parse(4)
width, height = len(input[0]), len(input)
dirs = (1, 1+1j, 1j, -1+1j, -1, -1-1j, -1j, 1-1j)
(e, se, s, sw, w, nw, n, ne) = dirs

def get(c):
    x, y = int(c.real), int(c.imag)
    return input[y][x] if 0 <= x < width and 0 <= y < height else None

def part1():
    check = lambda c, dir: ['X','M','A','S'] == [ get(c+n*dir) for n in range(4) ]

    return sum(check(complex(x, y), dir) for dir in dirs for x in range(width) for y in range(height))

def part2():
    check = lambda c, dir: ['M','A','S'] == [ get(c+n*dir) for n in (-1, 0, 1) ]
    is_x  = lambda c: (check(c, ne) or check(c, sw)) and (check(c, nw) or check(c, se))

    return sum(is_x(complex(x, y)) for x in range(width) for y in range(height))

# ---------------------------------------------------------------------------------------------

assert part1() == 2297
assert part2() == 1745

Parsing

The parse() function gives us our input in a reasonable way - a tuple of strings. Python allows direct indexing into both tuples and strings, so we have our grid. The width of the grid is the length of any of the lines, and the height is the number of lines:

1
2
 
input = parse(4, print_lines=None)
width, height = len(input[0]), len(input)

Part 1

Part 1 is a typical word search (I should probably create an Advent of Code library function for this!). The word can appear in a horizontal, vertical or diagonal orientation, either forward or backward.

I find it convenient to use complex numbers for this kind of grid-based puzzle - it simplifies the 8 directions we need to navigate in. We’ll need a helper function, get() to retrieve the character in the xth column and yth row, where we represent (x, y) as a complex number complex(x, y):

1
2
3
4
5
6
 
dirs = (1, 1+1j, 1j, -1+1j, -1, -1-1j, -1j, 1-1j)
(e, se, s, sw, w, nw, n, ne) = dirs

def get(c):
    x, y = int(c.real), int(c.imag)
    return input[y][x] if 0 <= x < width and 0 <= y < height else None

The check() function indicates whether “XMAS” exists in the starting position, c, and orientation, dir:

1
 
check = lambda c, dir: ['X','M','A','S'] == [ get(c+n*dir) for n in range(4) ]

Finally, we use a generator expression to generate a boolean for every direction and position in the grid to indicate whether the word exists. Python’s sum() function treats True as a 1 and False as a 0.

1
 
return sum(check(complex(x, y), dir) for dir in dirs for x in range(width) for y in range(height))

Part 2

For part 2, the task is to find pairs of words, “MAS”, in an X configuration of opposing diagonals. The check() function is similar to part 1, but instead of checking from the beginning of the word, we check from the middle i.e. the ‘A’:

1
 
check = lambda c, dir: ['M','A','S'] == [ get(c+n*dir) for n in (-1, 0, 1) ]

Another helper function, is_x() indicates whether we have a match by indicating whether we meet the following two criteria:

  • “MAS” exists on the northeast-southwest diagonal, forward or backward
  • “MAS” exists on the northwest-southeast diagonal, forward or backward
1
 
is_x  = lambda c: (check(c, ne) or check(c, sw)) and (check(c, nw) or check(c, se))

Finally, we check all the (x, y) positions for a valid X:

1
 
return sum(is_x(complex(x, y)) for x in range(width) for y in range(height))

Postscript

Since searching for a word in a grid in various orientations is so common in Advent of Code puzzles, I added a grid_word_search() function to my advent library.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
 
def grid_word_search(grid, word, dirs=(1, 1+1j, 1j, -1+1j, -1, -1-1j, -1j, 1-1j), offset=0):
    """Generate (x, y, direction) tuples for words in the grid. The
       dirs parameter specifies the allowable orientations, and the
       offset parameter allows shifting the word. Consider a 3-letter
       word. Using an offset of 0 would be typical and match words
       starting at (x, y). Using an offset of -1 would match words
       with the 2nd letter at (x, y)."""
    width     = len(grid[0])
    height    = len(grid)
    word_list = list(word)

    def get(c):
        x, y = int(c.real), int(c.imag)
        return grid[y][x] if 0 <= x < width and 0 <= y < height else None

    for dir in dirs:
        for x in range(width):
            for y in range(height):
                if word_list == [ get(complex(x,y) + (n + offset) * dir) for n in range(len(word)) ]:
                    yield (x, y, dir)

Using this new function, today’s solution is quite concise!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
 
from advent import parse, grid_word_search

input = parse(4)
(se, sw, nw, ne) = (1+1j, -1+1j, -1-1j, 1-1j)

def part1():
    return len(list(grid_word_search(input, "XMAS")))

def part2():
    diag1 = { (x, y) for (x, y, d) in grid_word_search(input, "MAS", (ne, sw), -1) }
    diag2 = { (x, y) for (x, y, d) in grid_word_search(input, "MAS", (se, nw), -1) }
    return len(diag1 & diag2)

# ---------------------------------------------------------------------------------------------

assert part1() == 2297
assert part2() == 1745

New Python Concepts

  • complex()
  • range()
  • set.intersection()
  • Complex numbers
  • Default parameters
  • Set comprehensions
  • sets
  • Ternary operator x if expr else y

Conclusion

I think parts 1 and 2 could be unified more by parameterizing the starting index of the word i.e. 0 for part 1 and 1 for part 2, but I don’t feel it’s worth it :) Another easy day - still waiting for the hammer to drop!