Advent of Code 2020 11-15

9/15/2024

Preamble

I've started doing some of the older (year 2020) advent of code problems for fun / preparation for this years AoC. Here are my solutions to days 11-15.

You can find:

1-5 here
6-10 here

Day 11

(define seats (~> (fetch-aoc-input (find-session) 2020 11)
                  (string-split "
")
                  (map (compose list->vector string->list) _)
                  list->vector))

;; Define a structure to hold adjacent values in clockwise order starting from North
(struct adjacents (n ne e se s sw w nw) #:transparent)

;; Define the grid class
(define grid%
  (class object%
    (init-field [grid #f])
    (field [current-iteration 0]
           [previous-state #f]
           [num-rows (vector-length grid)]
           [num-cols (vector-length (vector-ref grid 0))])

    ;; Method to get the value at (x, y)
    (define/public (get-value x y)
      (if (and (<= 0 x (- num-cols 1))
               (<= 0 y (- num-rows 1)))
          (vector-ref (vector-ref grid y) x)
          #f))

    ;; Method to get adjacents at (x, y)
    (define/public (get-adjacents x y)
      (define (safe-get x y)
        (if (and (<= 0 x (- num-cols 1))
                 (<= 0 y (- num-rows 1)))
            (vector-ref (vector-ref grid y) x)
            #f))

      ;; Collect adjacent values in clockwise order starting from North
      (define n  (safe-get x       (- y 1)))    ; N
      (define ne (safe-get (+ x 1) (- y 1)))    ; NE
      (define e  (safe-get (+ x 1) y))          ; E
      (define se (safe-get (+ x 1) (+ y 1)))    ; SE
      (define s  (safe-get x       (+ y 1)))    ; S
      (define sw (safe-get (- x 1) (+ y 1)))    ; SW
      (define w  (safe-get (- x 1) y))          ; W
      (define nw (safe-get (- x 1) (- y 1)))    ; NW

      ;; Return the adjacents structure
      (adjacents n ne e se s sw w nw))

    (define/public (compute-next-step x y)
      (let* ([curr-val (get-value x y)]
             [curr-adj (get-adjacents x y)]
             [occ-adj (vector-count (curry equal? ##) (struct->vector curr-adj))])
        (match curr-val
          [#L (if (zero? occ-adj) ## #L)]
          [## (if (<= 4 occ-adj) #L ##)]
          [_ curr-val])))

    (define/public (compute-next-state)
      (define new-grid
        (for/vector ([y (in-range num-rows)])
          (for/vector ([x (in-range num-cols)])
            (compute-next-step x y))))
      ;; Update the current state and increase the iteration count
      (set! previous-state grid)
      (set! grid new-grid)
      (set! current-iteration (add1 current-iteration))
      grid)

    ;; Public accessors for the attributes
    (define/public (get-current-iteration) current-iteration)
    (define/public (get-current-state) grid)
    (define/public (get-previous-state) previous-state)

    (super-new)))

;; Create an instance of the grid class
(define (get-occupied-seats grid)
  (let loop ()
  (if (equal? (send my-grid get-previous-state) (send my-grid get-current-state))
      (apply + (vector->list (vector-map (curry vector-count (curry equal? ##)) (send my-grid get-current-state))))
      (begin
        (send my-grid compute-next-state)
        (loop)))))

;; part 1
(define seat-grid (new grid% [grid seats]))
(get-occupied-seats seat-grid)

;; pt 2
(define visibility-grid%
  (class grid%
    (super-new)
    (inherit-field num-cols num-rows)

    ;; Override get-adjacents with get-visible-adjacents
    (define/override (get-adjacents x y)
      ;; Method to get the first seat visible in a direction (dx, dy)
      (define (get-first-seat x y dx dy)
        (let loop ([x (+ x dx)] [y (+ y dy)])
          (if (or (< x 0) (>= x num-cols) (< y 0) (>= y num-rows))
              #f ; Reached the edge
              (let ([val (send this get-value x y)])
                (if (equal? val #.) ; If floor, continue in same direction
                    (loop (+ x dx) (+ y dy))
                    val)))))

      (define n  (get-first-seat x y  0 -1))   ; N
      (define ne (get-first-seat x y  1 -1))   ; NE
      (define e  (get-first-seat x y  1  0))   ; E
      (define se (get-first-seat x y  1  1))   ; SE
      (define s  (get-first-seat x y  0  1))   ; S
      (define sw (get-first-seat x y -1  1))   ; SW
      (define w  (get-first-seat x y -1  0))   ; W
      (define nw (get-first-seat x y -1 -1))   ; NW

      (adjacents n ne e se s sw w nw))

    ;; Override compute-next-step to adjust occupancy threshold
    (define/override (compute-next-step x y)
      (let* ([curr-val (send this get-value x y)]
             [curr-adj (get-adjacents x y)]
             [occ-adj (vector-count (curry equal? ##) (struct->vector curr-adj))])
        (match curr-val
          [#L (if (zero? occ-adj) ## #L)]
          [## (if (<= 5 occ-adj) #L ##)]  ; Threshold adjusted to 5
          [_ curr-val])))))

(define seat-grid (new visibility-grid% [grid seats]))
(get-occupied-seats seat-grid)

Notes

I almost never build classes and objects in Racket. In this case I got to explore how racket extends classes. Everything seems very explicit which is nice, but leads to some documentation-digging since I'm more familiar with python's relaxed approach to sub-classing.

note the define/public, define/private, define/override keywords.

I think this is my longest solution yet

Day 12

(define pa
  (~>>
   (fetch-aoc-input (find-session) 2020 12)
   (string-split _ "
")
   (map (λ (instruction)
          (let ([rem (regexp-match #px"^([A-Z])([0-9]+)$" instruction)])
            (list (second rem) (string->number (third rem))))))))

(define (append-values . fns-and-extras)
  (define (collect-values fns)
    ;; Helper function to collect values from each function
    (apply append
           (map (lambda (fn) (call-with-values fn list)) fns)))

  ;; Separate functions from extra values
  (define fns (filter procedure? fns-and-extras))
  (define extras (filter (lambda (x) (not (procedure? x))) fns-and-extras))

  ;; Collect the values from all functions and append extras
  (apply values (append (collect-values fns) extras)))


;; part 1
(define (turn curr-dir turn-dir amt)
  (define directions '("N" "E" "S" "W"))  ; Order of cardinal directions
  (define curr-index (index-of directions curr-dir))  ; Get the current direction index
  (define steps (/ amt 90)) ; calc number of steps

  ;; Adjust the steps based on the turn direction (right = forward, left = backward)
  (define new-index
    (if (equal? turn-dir "R")
        (modulo (+ curr-index steps) 4)  ; "R"
        (modulo (- curr-index steps) 4)))  ; "L"

  ;; Return the new direction
  (list-ref directions new-index))

(define (move-in-direction dir x y amt)
  (match dir
    ["N" (values x (+ y amt))]
    ["S" (values x (- y amt))]
    ["E" (values (+ x amt) y)]
    ["W" (values (- x amt) y)]))

(for/fold ([x 0] [y 0] [facing-dir "E"]
           #:result (+ (abs x) (abs y)))
          ([instruction pa])
  (match-let ([(list dir amt) instruction])
    (match dir
      [(or "N" "S" "E" "W")
       (append-values (λ () (move-in-direction dir x y amt)) facing-dir)]
      [(or "R" "L") (values x y (turn facing-dir dir amt))]
      ["F" (append-values (λ () (move-in-direction facing-dir x y amt)) facing-dir)])))


;; part 2
(define (rotate-waypoint x y direction theta)
  (match (list direction theta)
    ;; Clockwise rotations ("R")
    [(list "R" 90)  (values y (- x))]
    [(list "R" 180) (values (- x) (- y))]
    [(list "R" 270) (values (- y) x)]
    ;; Counterclockwise rotations ("L")
    [(list "L" 90)  (values (- y) x)]
    [(list "L" 180) (values (- x) (- y))]
    [(list "L" 270) (values y (- x))]))

(for/fold ([wx 10] [wy 1]
           [sx 0] [sy 0]
           #:result (+ (abs sx) (abs sy)))
          ([instruction pa])
  (match-let ([(list dir amt) instruction])
    (match dir
      [(or "N" "S" "E" "W")
       (append-values (λ () (move-in-direction dir wx wy amt)) sx sy)]
      [(or "R" "L")
       (append-values (λ () (rotate-waypoint wx wy dir amt)) sx sy)]
      ["F"
       (values wx wy (+ sx (* amt wx)) (+ sy (* amt wy)))])))

Notes

This problem had a little bit of math in it! We used the simple case where $\theta$ is always a multiple of 90 degrees which simplifies nicely from:

$x' = x \cdot \cos(\theta) - y \cdot \sin(\theta)$

$x' = -y$ for the counter-clockwise and $x' = y$ for the clockwise direction.

Day 13

(require racket
         threading
         advent-of-code
         (only-in srfi/1 map))

(define bus
  (~>>
   (fetch-aoc-input (find-session) 2020 13)
   (string-split _ "
")
   ((λ (p)
     (list
      (string->number (first p))
      (for/list ([num (string-split (second p) ",")]
                 #:when (not (equal? "x" num)))
        (string->number num)))))))

;; part 1
(match-let ([(list dep-time buses) bus])
  (~>
   (map (λ (v)
          (cons v (+ v (- (remainder dep-time v)))))
        buses)
   (sort < #:key cdr)
   first
   ((λ (p) (* (car p) (cdr p))))))

;; part 2
(define bus
  (~>>
   (fetch-aoc-input (find-session) 2020 13)
   (string-split _ "
")
   ((λ (p)
      (for/list ([num (string-split (second p) ",")]
                 [idx (in-naturals)]
                 #:when (not (equal? "x" num)))
        (list idx (string->number num)))))))


;; Extended Euclidean Algorithm to find gcd and coefficients
(define (extended-gcd a b)
  (if (= a 0)
      (values b 0 1) ; Return gcd, x, and y
      (let-values ([(gcd x1 y1) (extended-gcd (modulo b a) a)])
        (values gcd (- y1 (* (quotient b a) x1)) x1))))

;; Function to find the modular inverse of Ni modulo mod
(define (mod-inverse Ni mod)
  (let-values ([(gcd x y) (extended-gcd Ni mod)])
    (if (= gcd 1)
        (modulo x mod) ; The inverse is x % mod
        (error "No inverse exists for" Ni "modulo" mod))))

;; calculate product of all moduli
(define N (apply * (map second bus)))

;; calculate total product divided by modulus
(define Ni (map (λ (v) (/ N v)) (map second bus)))

(define modular-inverses (map (λ (a b) (mod-inverse a b)) Ni (map second bus)))

(define (solve-crt remainders Nis inverses N)
  (define total 0)  ; Initialize the sum
  ;; Sum up all r_i * N_i * M_i
  (for ([r remainders] [Ni Nis] [Mi inverses])
    (set! total (+ total (* r Ni Mi))))
  ;; Return the result modulo the product of all moduli (N)
  (modulo total N))

(solve-crt (map (compose - first) bus)
           Ni
           modular-inverses
           N)

Notes

This is my first time using the Chinese Remainder Theorem in a program. Very neat! It helps that racket has gcd built-in. This could be re-written to be cleaner / more elegant.

Day 14

#lang racket
(require racket threading advent-of-code)

(define init-pr
  (~>>
   (fetch-aoc-input (find-session) 2020 14)
   (string-split _ "mask = ")
   (map (compose
         (λ (p)
           (list (string-trim (first p) "mask = ")
                 (map (λ (inst)
                        (match-let ([(list _ addr val) (regexp-match #rx"([0-9]+)] = ([0-9]+)" inst)])
                          (map string->number (list addr val))))
                      (rest p))))
         (curryr string-split "
")))))

(define mask-len 36)
(define memory-block (make-hash))

(define (make-bit-vec num)
  (let ([num-str (number->string num 2)])
    ((compose list->vector string->list)
     (string-append (make-string (- mask-len (string-length num-str)) #) num-str))))

;; part 1
(for ([instr-block init-pr])
  (let* ([mask (string->list (car instr-block))]
         [mask-indices (indexes-where mask (curry (compose not equal?) #X))])
    (for ([mem-setter (second instr-block)])
      (match-let* ([(list mem-loc mem-val) mem-setter]
                   [num-bit (make-bit-vec mem-val)])
        (for ([idx mask-indices])
          (vector-set! num-bit idx (list-ref mask idx)))
        (hash-set! memory-block mem-loc ((compose (curryr string->number 2) list->string vector->list) num-bit))))))

(apply + (hash-values memory-block))

;; part 2
(define (apply-mask num-bit mask)
  (for/vector #:length 36 ([mele mask] [ele num-bit])
    (match mele
      [#\0 ele]
      [#\1 #\1]
      [#\X #\X])))

(define (get-binary-reps n)
  (for/list ([val (in-inclusive-range 0 (sub1 (expt 2 n)))])
    (let* ([bin-rep (number->string val 2)]
           [brsl (string-length bin-rep)])
      (if (> n brsl)
          (string->list (string-append (make-string (- n brsl) #) bin-rep))
          (string->list bin-rep)))))

(define (get-floating-addresses res)
  (let* ([floating-idxs (indexes-where (vector->list res) (curry equal? #X))]
         [binary-reps (get-binary-reps (length floating-idxs))]
         [res/copy (vector-copy res)])
    (for/list ([bin binary-reps])
      (for ([bin-val bin]
            [idx floating-idxs])
        (vector-set! res/copy idx bin-val))
      (string->number (list->string (vector->list res/copy)) 2))))

(for ([instr-block init-pr])
  (let ([mask (string->list (car instr-block))])
    (for ([mem-setter (second instr-block)])
      (match-let* ([(list mem-loc mem-val) mem-setter])
        (define num-bit (make-bit-vec mem-loc))
        (define result (apply-mask num-bit mask))
        (define new-mem-locs (get-floating-addresses result))
        (for-each (λ (pos) (hash-set! memory-block pos mem-val)) new-mem-locs)))))

(apply + (hash-values memory-block))

Notes

My answer here didn't use any fancy bit-shift operations. I'm wondering if it could have. One interesting tidbit is the function get-binary-reps. Instead of finding the powerset of binary choices for n variables, we can translate 2n - 1 to binary and then take the binary representation of each number to get all the possible choices.

Day 15

(define starting-numbers '(0 1 5 10 3 12 19))
(define nth-num 2020)

(define (index-of/2 ls v)
  (let loop ([ls ls] [i 0] [found-indices '()])
    (cond
      [(or (null? ls) (>= (length found-indices) 2)) found-indices]
      [(equal? (car ls) v) (loop (cdr ls) (add1 i) (cons i found-indices))]
      [else (loop (cdr ls) (add1 i) found-indices)])))

(define (idx-of/2/abs-diff ls v)
  (apply (compose abs +) (index-of/2 ls v)))

;; part 1
(let ([seen (list->mutable-set starting-numbers)])
  (for/fold ([nums (reverse starting-numbers)]
             #:result (cadr nums))
            ([idx (in-inclusive-range 0 (- nth-num (length starting-numbers)))])
  (let ([recent (car nums)])
    (cond [(false? (set-member? seen recent)) (begin (set-add! seen recent) (cons 0 nums))]
          [else (cons (idx-of/2/abs-diff nums recent) nums)]))))

;; part 2
(define nth-num 30000000)

(let ([seen (make-hash '([0 . 1] [1 . 2] [5 . 3] [10 . 4] [3 . 5] [12 . 6] [19 . 7]))])
  (for/fold ([prev-number (last starting-numbers)])
            ([idx (in-inclusive-range (add1 (length starting-numbers)) nth-num)])
    (let ([prev-turn (hash-ref seen prev-number #f)])
      (begin
        (hash-set! seen prev-number (sub1 idx))
        (match prev-turn
          [#f 0]
          [_ (- (sub1 idx) prev-turn)])))))

Notes

This one was shorter, but it took me a while. My approach in the first part didn't scale very well for the second part. My assumption is that I'm inefficient in index-of/2 when searching for the first 2 indices of a given number.

The second solution can also be used for the first part as well, but I've left the first approach up. The second part uses a hash for everything, so there is no linear time search for indices.