Advent of Code 2023 - Day 3: Gear Ratios

:: programming, puzzle, racket

1
2
 
#lang iracket/lang #:require racket
(require "../advent.rkt" threading)

Day 3 involves some two dimensional analysis, so we’ll use complex numbers as a convenient two dimensional index:

1
 
(define neighbors '(0-i 1-i 1 1+i 0+i -1+i -1 -1-i))

Most of the work today is in the input parsing. Our input looks like this:

467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..

Our goal in parsing is to create two lists - a list of numbers and a list of symbols. The elements of each list will be a pair. The first element of the pair is a two dimensional index, represented by a complex number, and the second element is a token. For numbers, the token will be a string representation of the number (to easily allow iterating over each digit), and for symbols, the token will be a character.

While I could’ve created both lists in a single pass, I chose instead to first create a single list containing both numbers and symbols, and then use filter to create each of the final lists from the single intermediate list.

I’ve broken the parsing up into a number of functions, and I’ll cover them in a “bottom up” fashion. First, we’ll define a couple example lines to illustrate some parsing functions:

1
2
 
(define num-line '(#\4 #\6 #\7 #\. #\. #\1 #\1 #\4 #\. #\.))
(define sym-line '(#\. #\. #\. #\* #\. #\. #\. #\. #\. #\.))

The lower level parsing functions accept a list of characters, line, that begins with the token to be parsed, and an index into the current line of input, col. The function returns two values, the token parsed, and the index into the current input line just passed the token. For example:

1
2
3
4
 
(define (parse-sym  line col)
  (values (car line) (add1 col)))

(parse-sym (drop sym-line 3) 3) ; e.g. input line after we've consumed the first three . characters

#*

4

For the other types of tokens (dots and numbers), we’ll need a generalized function to parse characters:

1
2
3
4
5
6
7
8
9
 
(define (parse-chars line col pred? [ convert identity ])
  (let ([ pos (or (index-where line pred?) (length line)) ])
    (values (convert (take line pos)) (+ col pos))))

(define (parse-dots line col)
  (parse-chars line col (λ (ch) (not (char=? #\. ch))) (const #f)))

(define (parse-num  line col)
  (parse-chars line col (λ (ch) (not (char-numeric? ch))) list->string))

The only reason we’re parsing the dots is to consume enough of the input to get to the next token, so parse-dots returns #f for the token (no use allocating a string to hold the dots, since we’ll ignore them):

1
 
(parse-dots sym-line 0)

#f

3

We do care about numbers, so parse-num will return the parsed number:

1
 
(parse-num num-line 0)

“467”

3

1
 
(parse-num (drop num-line 5) 5)

“114”

8

Now we can write the general parse-token:

1
2
3
4
5
6
7
 
(define (parse-token line col)
  (let ([ ch (car line) ])
    (cond [ (char=? #\. ch)    (parse-dots line col) ]
          [ (char-numeric? ch) (parse-num line col)  ]
          [ else               (parse-sym line col)  ])))

(parse-token num-line 0)

“467”

3

The parse-tokens function will parse all of the input and return a list of tokens along with the two dimensional index of the token. Tokens will either be strings, for numbers, or characters, for symbols, or #f for dots:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
 
(define (parse-tokens lines)
  (let next-line ([ lines lines ][ row 0 ][ tokens '() ])
    (if (null? lines)
        tokens
        (let next-token ([ line (car lines) ][ col 0 ][ tokens tokens ])
          (if (null? line)
              (next-line (cdr lines) (add1 row) tokens)
              (let-values ([ (token new-col) (parse-token line col) ])
                (next-token (drop line (- new-col col))
                            new-col
                            (cons (cons (make-rectangular col row) token) tokens))))))))

(define lines (parse-aoc 3 string->list))

(take (parse-tokens lines) 7)

----------------------------------------------------------------------------------------------------
day03.txt -> 110 chars, 10 lines; first 3 lines; last 2 lines:
----------------------------------------------------------------------------------------------------
467..114..
...*......
..35..633.
...
...$.*....
.664.598..
----------------------------------------------------------------------------------------------------
(parse 3) -> 10 entries:
----------------------------------------------------------------------------------------------------
((#\4 #\6 #\7 #\. #\. #\1 #\1 #\4 #\. #\.)
(#\. #\. #\. #\* #\. #\. #\. #\. #\. #\.)
...
(#\. #\6 #\6 #\4 #\. #\5 #\9 #\8 #\. #\.))
----------------------------------------------------------------------------------------------------

’((8+9i . #f) (5+9i . “598”) (4+9i . #f) (1+9i . “664”) (0+9i . #f) (6+8i . #f) (5+8i . #*))

Here we see that the number "598 is at row 9, col 5 (zero based), and the symbol * is at row 8, col 5.

Now we’ll simply filter the list into two separate lists - one for numbers and one for symbols:

1
2
3
4
5
6
7
 
(define (parse-input tokens)
  (values (filter (compose1 string? cdr) tokens)
          (filter (compose1 char? cdr) tokens)))

(define-values (nums syms) (parse-input (parse-tokens lines)))

(take nums 3)

’((5+9i . “598”) (1+9i . “664”) (6+7i . “755”))

1
 
(take syms 3)

’((5+8i . #*) (3+8i . #$) (5+5i . #+))

The hard part of parsing is over! Now we’ll define four helper functions. adjacent? will indicate whether two indices are adjacent i.e. within a distance of 1 in the vertical, horizontal or diagonal directions:

1
2
3
4
 
(define (adjacent? pos1 pos2)
  (ormap (λ (n) (= (+ pos1 n) pos2)) neighbors))

(adjacent? (make-rectangular 3 4) (make-rectangular 4 4))

#t

num-adjacent-so-sym? indicates whether the number num-str at index num-pos is adjacent to the symbol at index sym-pos. To do this, we iterate over the index of the digits in num-str to see if any of them are adjacent to the symbol index:

1
2
3
4
5
6
 
(define (num-adjacent-to-sym? num-str num-pos sym-pos)
  (ormap (λ (n)
           (adjacent? (+ num-pos n) sym-pos))
         (range (string-length num-str))))

(num-adjacent-to-sym? "592" 2+6i 5+5i) ; number beginning at (6,2), symbol at (5,5)

#t

is-part-number? indicates whether the number, num-str, at index, num-pos is adjacent to any symbol. To do that, we’ll iterate over all the symbols to see if any are adjacent to the number:

1
2
3
4
5
6
 
(define (is-part-number? num-str pos syms)
  (ormap (λ (sym-pair)
           (num-adjacent-to-sym? num-str pos (car sym-pair)))
         syms))

(is-part-number? "592" 2+6i syms)

#t

Lastly, gear-with-nums accepts a * symbol index, pos, and returns a list of numbers adjacent to that symbol:

1
2
3
4
5
6
7
 
(define (gear-with-nums pos)
  (~> (filter (λ (pair)
                (num-adjacent-to-sym? (cdr pair) (car pair) pos))
              nums)
      (map (compose1 string->number cdr) _)))

(gear-with-nums 3+1i)

’(35 467)

Now, all that’s left is the individual part functions. For Part 1:

  1. Filter the list of number pairs to only those that are part numbers
  2. For each pair, grab the actual number string and convert to an integer
  3. Sum all of the numbers in the list
1
2
3
4
5
6
7
8
 
(define (part1)
  (~> (filter (λ (pair)
                (is-part-number? (cdr pair) (car pair) syms))
              nums)
      (map (compose1 string->number cdr) _)
      (list-sum _)))

(part1)

4361

For Part 2:

  1. Filter the list of symbols to only those that are *
  2. For each of those, associate a list of numbers that are adjacent
  3. Filter that list to only those that have exactly 2 numbers
  4. Compute the product for each
  5. Sum all the products
1
2
3
4
5
6
7
8
 
(define (part2)
  (~> (filter (compose1 (curry char=? #\*) cdr) syms)
      (map (compose1 gear-with-nums car) _)
      (filter (compose1 (curry = 2) length) _)
      (map list-prod _)
      list-sum))

(part2)

467835