Advent of Code 2024 - Day 10: Hoof It

• Table of Contents
• Github
• Day 10

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

from advent import parse, digits, compose, defaultdict, grid_to_hash

grid  = defaultdict(lambda: None, grid_to_hash(parse(10, digits)))
solve = lambda score: sum([ score(dfs(head, -1, [])) for head, level in grid.copy().items() if level == 0 ])

def dfs(pos, prev, result):
    level = grid[pos]
    if level != prev + 1:
        return result
    elif level == 9:
        return result + [ pos ]
    else:
        for dir in (1, 1j, -1, -1j):
            result = dfs(pos + dir, level, result)
        return result

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

assert solve(compose(len,set)) == 644
assert solve(len) == 1366

Parsing

We’re given a file of the form:

89010123
78121874
87430965
96549874
45678903
32019012
01329801
10456732

We’d like a two dimensional data structure with direct access, so we’ll parse the file into a dict with position (as a complex number) as the key and the digit as the value:

1

grid  = defaultdict(lambda: None, grid_to_hash(parse(10, digits)))

Solution

Today’s parts are nearly identical. Our first function is our depth first search. It simply searches in each of the 4 directions, using a complex number to indicate east, south, west or north. Every time we reach a 9 we append it to the result list:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def dfs(pos, prev, result):
    level = grid[pos]
    if level != prev + 1:
        return result
    elif level == 9:
        return result + [ pos ]
    else:
        for dir in (1, 1j, -1, -1j):
            result = dfs(pos + dir, level, result)
        return result

To solve the puzzle, we search from each of the trailheads and sum the score of the results. The score() function is the only thing unique to each part:

1

solve = lambda score: sum([ score(dfs(head, -1, [])) for head, level in grid.copy().items() if level == 0 ])

For part 1, we only want unique positions, so the score function uses set() to obtain the unique positions, and then counts them with len(). For part 2, we want to know how many ways we can get to a 9, so we simply count them:

1
2

solve(compose(len,set)) # Part 1
solve(len)              # Part 2

New Python Concepts

• Assignment expressions e.g. (x := int(c.real))

Conclusion

I think every Advent of Code has at least one of these search puzzles, so being comfortable with searching (depth first, breadth first, etc.) is helpful. Python does well for this puzzle.

Postscript

I decided to port the Python code to Racket. I think Racket did well here:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#lang racket

(require "./advent.rkt")
(define grid (grid->hash (parse-aoc 10 digits)))

(define (solve score)
  (for/sum ([ (head level) (in-hash grid) ] #:when (= level 0))
    (score (dfs head -1 '()))))

(define (dfs pos prev result)
  (let ([ level (hash-ref grid pos -1) ])
    (cond [ (not (= level (add1 prev)))  result ]
          [ (= level 9)                  (cons pos result) ]
          [ else                         (for/fold ([ result result ])
                                                   ([ dir (in-list '(1 +i -1 -i)) ])
                                           (dfs (+ pos dir) level result)) ])))

;; --------------------------------------------------------------------------------------------

(check-equal? (solve (compose set-count list->set)) 644)
(check-equal? (solve length) 1366)