Rules: no spoilers.

The other rules are made up as we go along.

Share code by link to a forge, home page, pastebin (Eric Wastl has one here) or code section in a comment.

  • datarama@awful.systems
    link
    fedilink
    English
    arrow-up
    5
    ·
    1 year ago

    Day 3: Gear Ratios

    Scheme code and explanations

    To avoid annoying special cases for dealing with reading past the edges of the schematic, I start by adding one cell of padding on all sides.

    (define (pad-schematic lines)
      (let* ((width (string-length (car lines)))
             (empty-line (make-string (+ width 2) #\.)))
        (append (list empty-line)
                (map (lambda (str) (string-append "." str ".")) lines)
                (list empty-line))))
    

    I’m also going to define a few utility functions. The schematic-pos function reads what’s on the x,y position of the schematic, and is here to compensate for Scheme being awkward for dealing with two-dimensional structures. The two others check whether some position is a symbol (other than .) or a digit.

    (define (schematic-pos s x y)
      (string-ref (list-ref s y) x))
    
    (define (pos-symbol? s x y)
      (let ((chr (schematic-pos s x y)))
        (and (not (char=? chr #\.))
             (not (char-set-contains? char-set:digit chr)))))
    
    (define (pos-digit? s x y)
      (let ((chr (schematic-pos s x y)))
        (char-set-contains? char-set:digit chr)))
    

    I want a list of all positions of symbols in the schematic, so I can check them for adjacent numbers. I could also have gone with a list of numbers instead, but symbols seemed easier to find adjacencies for.

    (define (symbol-positions s)
      (let ((width (string-length (car s)))  (height (length s)))
        (let loop ((x 0) (y 0) (syms '()))
          (cond ((>= y height) syms)
                ((>= x width) (loop 0 (+ y 1) syms))
                ((pos-symbol? s x y)
                 (loop (+ x 1) y (cons (cons x y) syms)))
                (else (loop (+ x 1) y syms))))))
    

    This produces a list of (x y) pairs, one for each symbol. Finding adjacent numbers is a bit tricky: Since there are three relevant positions above and below the symbol’s own position, there could be one or two numbers above or below, and if there are two, then I might be reading the same number twice. I accept this, and keep the numbers in an lset (which means that a duplicate simply won’t be inserted). The number reader itself produces triples on the form (x y n), where x is the position of the first character in the number, and n is a string containing the number itself. The coordinates are stored to ensure that if there are several instances of the same number in different positions in the schematic, they get treated separately.

    (define (get-number-pos s x y)
      (letrec
        ((num_l (lambda (x) (if (pos-digit? s x y) (num_l (- x 1)) (+ x 1))))
         (num_r (lambda (x) (if (pos-digit? s x y) (num_r (+ x 1)) x))))
        (list (num_l x) y (string-copy (list-ref s y) (num_l x) (num_r x)))))
    
    (define (get-adjacent-numbers s xpos ypos)
      (let loop ((x (- xpos 1)) (y (- ypos 1)) (nums '()))
        (cond
          ((> y (+ ypos 1)) nums)
          ((> x (+ xpos 1)) (loop (- xpos 1) (+ y 1) nums))
          ((pos-digit? s x y)
           (loop (+ x 1) y (lset-adjoin equal? nums (get-number-pos s x y))))
          (else (loop (+ x 1) y nums)))))
    

    From here, solving the two parts is easy. For part 1, we get all the lists of number adjacencies and unpack them into a single list:

    (define (get-part-numbers s)
      (let ((sym-nums (map (lambda (c) (get-adjacent-numbers s (car c) (cdr c)))
                           (symbol-positions s))))
        (let loop ((curr (car sym-nums)) (syms (cdr sym-nums)) (nums '()))
          (cond ((and (null? curr) (null? syms)) nums)
                ((null? curr) (loop (car syms) (cdr syms) nums))
                (else (loop (cdr curr) syms (cons (car curr) nums)))))))
    
    (define (solve-part-1 schematic)
      (apply + (map (lambda (x) (string->number (caddr x)))
                    (get-part-numbers schematic))))
    

    For part 2, we need a list of gears. We can just get all the symbols, filter out everything that isn’t a *, and then filter out everything that doesn’t have exactly two adjacencies.

    (define (gears s)
      (filter (lambda (x) (= (length x) 2))
              (map (lambda (x) (get-adjacent-numbers s (car x) (cdr x)))
                   (filter
                     (lambda (x) (char=? (schematic-pos s (car x) (cdr x)) #\*))
                     (symbol-positions s)))))
    
    (define (solve-part-2 s)
      (apply + (map (lambda (y) (* (string->number (caddr (car y)))
                                   (string->number (caddr (cadr y)))))
                    (gears s))))
    

    I could probably have written nicer code if I weren’t still a bit sick (though I’m getting better!). However, the moment I realized this one would be about mucking around with two-dimensional structures, I knew Scheme was going to be a bit awkward. But here you have it.