Advent of Racket 2023/03 - Gear Ratios

Let's get right into day three. The first part of the puzzle today is to find any numbers adjacent to a non-numeric, non-period symbol in a table and add them all up. The example input looks like this:


The first thing I did was count the number of columns and rows. I noticed the example input was a square, so I took a peek at my own input and it, too, was square. So, I decided to read the whole input into a unidimensional vector:

(define table
  (call-with-input-file "day03.txt"
    (lambda (in)
      (for*/vector ([line (in-lines in)]
                    [char (in-string line)])

Since we're going to be looking for adjacent positions, we need to know what the table's stride is. Since the input table is square, that's easy:

(define s (sqrt (vector-length table)))
(define -s (- s))

Next, we can define a function to match special symbols:

(define (engine-symbol? c)
  (and (not (eqv? c #\.))
       (not (char-numeric? c))))

And a function to determine if a position has any adjacent special symbols:

(define (has-adjacent? t pos [ok? engine-symbol?])
  (for*/first ([d (in-list (list (- -s 1) -s (+ -s 1)
                                      -1           1
                                 (-  s 1)  s (+  s 1)))]
               [idx (in-value (+ pos d))]
               #:when (and (>= idx 0)
                           (<  idx (vector-length t))
                           (ok? (vector-ref t idx))))

For any given index into the table, has-adjacent? checks its 8 adjacent indexes for a position for which ok? returns #t, returning the first match or #f if no matches are found.

To compute part one, all we have to do is iterate over the table, piece any run of digits into a number and add any number for which we've found an adjacent symbol to the total:

(for/fold ([num 0]
           [ok? #f]
           [total 0]
           #:result (if ok? (+ num total) total))
          ([(c idx) (in-indexed (in-vector table))])
  (if (char-numeric? c)
      (values (+ (* num 10) (char->decimal c))
              (or ok? (has-adjacent? table idx))
      (values 0 #f (if ok? (+ num total) total))))

The one edge case to watch out for here is that a table may end in a number, so we need to make sure the final result accounts for that and add the last-collected number to the total if necessary. That case is covered by the #:result clause above.

As in day two, the second part of today's puzzle flips the problem on its head and asks us to instead find any two numbers that are adjacent to a * symbol, multiply them together and sum them up.

To solve part two, we can just iterate over the table and whenever we see a * symbol, check if it has any adjacent numbers. If it has exactly two of them, we can multiply them together and add them to the total. It would be nice if we had a variant of has-adjacent? that returns the indexes of adjacent symbols, so let's go ahead and write that function:

(define-syntax-rule (define-finder id for*-id)
  (define (id t pos [ok? engine-symbol?])
    (for*-id ([d (in-list (list (- -s 1) -s (+ -s 1)
                                     -1           1
                                (-  s 1)  s (+  s 1)))]
              [idx (in-value (+ pos d))]
              #:when (and (>= idx 0)
                          (<  idx (vector-length t))
                          (ok? (vector-ref t idx))))

(define-finder find-adjacent for*/list)
(define-finder has-adjacent? for*/first)

I wanted to preserve the short-circuiting behavior of has-adjacent?, so I decided to abstract over its implementation using a macro. In this case, the define-finder macro lets us plug in different for loop behaviors into the same implementation. So, find-adjacent works the same way as has-adjacent?, but it returns all the adjacent positions for which ok? is true instead of just the first one.

One problem to consider, though, is that a symbol may be adjacent to multiple digits belonging to the same number. For example:


Given the above example, the find-adjacent procedure would return the position of every digit surrounding the * symbol. So, we need a way get the numbers at a given set of positions that is aware of this issue and skips redundant positions.

; invariant: indexes always start out as valid digit positions in the table
(define (get-numbers t is)
  (let loop ([is is]
             [nums null])
      [(null? is) nums]
       (define-values (num rem-is)
         (let get-number ([i (car is)])
           (if (or (< i 0)
                   (not (char-numeric? (vector-ref t i))))
               (for/fold ([n 0] [rem-is is])
                         ([(c idx) (in-indexed (in-vector t (add1 i)))])
                 #:break (not (char-numeric? c))
                  (+ (* n 10) (char->decimal c))
                  (remq (+ (add1 i) idx) rem-is)))
               (get-number (sub1 i)))))
       (loop rem-is (cons num nums))])))

The get-numbers procedure takes a table and a list of indexes into that table. It then tries the indexes in order and walks backwards from each index to find the start of a number, then it reads the number forwards, removing any indexes that it sees along the way from the pending list of indexes, and collecting the numbers into a list.

> (define t
    (vector #\1 #\2 #\.
            #\3 #\4 #\.))
> (get-numbers t '())
> (get-numbers t '(0))
> (get-numbers t '(1))
> (get-numbers t '(0 1))
> (get-numbers t '(0 1 3))
'(34 12)
> (get-numbers t '(0 1 3 4))
'(34 12)

With find-adjacent and get-numbers in hand, we can just iterate over the table and compute the result:

(for/fold ([total 0])
          ([(c idx) (in-indexed (in-vector table))]
           #:when (eqv? c #\*))
  (define adjacent-numbers
    (get-numbers table (find-adjacent table idx char-numeric?)))
  (if (= (length adjacent-numbers) 2)
      (+ total (apply * adjacent-numbers))

Any time we see a *, we find all the adjacent numeric positions and get the numbers at those positions. If we have exactly two adjacent numbers, then we multiply them together and add them to the sum. Easy peasy.