Day 9 Solution

;; Language: Racket Intermediate Student with Lambda

(require 2htdp/batch-io)

;; day 9 part 1
;; find low points of grid

;; get-risk-level-sum : String -> Number
;; gets the sum of the risk levels from the lowest points
;; in the grid in the given file

(check-expect (get-risk-level-sum "advent-smoke-1.txt") 15)

(define (get-risk-level-sum filename)
  (local [(define GRID (los->grid (read-lines filename)))]
    (foldr
     (λ (height sum) (+ 1 height sum))
     0
     (map
      (λ (p) (find-num-at-coordinates GRID p))
      (find-low-points GRID)))))

;; los->grid : [List-of String] -> [List-of [List-of Number]]
;; converts the strings to a grid

(check-expect (los->grid (list "123" "456" "789"))
              (list (list 1 2 3)
                    (list 4 5 6)
                    (list 7 8 9)))
(check-expect (los->grid (list "36" "43"))
              (list (list 3 6)
                    (list 4 3)))

(define (los->grid los)
  (map (λ (str) (map string->number (explode str))) los))

;; find-low-points : [List-of [List-of Number]] -> [List-of Position]
;; find the low points in the grid

(check-expect (find-low-points (list (list 1 2 3)
                                     (list 1 2 3)
                                     (list 1 2 3)))
              '())
(check-expect (find-low-points (list (list 1 2 3)
                                     (list 4 5 6)
                                     (list 7 8 9)))
              (list (make-posn 0 0)))
(check-expect (find-low-points (list (list 1 2 3)
                                     (list 4 5 6)
                                     (list 7 8 5)))
              (list (make-posn 0 0) (make-posn 2 2)))

(define (find-low-points grid)
  (local [(define HEIGHT (length grid))
          (define WIDTH (length (first grid)))

          ;; find-low-points/acc : Nat Nat -> [List-of Number]
          ;; finds the low points in the grid
          ;; Accumulator: the x and y coordinates of the current number
          (define (find-low-points/acc x y)
            (cond
              [(= x WIDTH) (find-low-points/acc 0 (add1 y))]
              [(= y HEIGHT) '()]
              [else
               (local [(define CURR (list-ref (list-ref grid y) x))
                       (define PREV (find-low-points/acc (add1 x) y))
                       (define POSN (make-posn x y))]
                 (if (all-less-than? CURR (find-adjacent grid POSN))
                     (cons POSN PREV)
                     PREV))]))]
    (find-low-points/acc 0 0)))

;; all-less-than? : Number [List-of Number] -> Boolean
;; is the number lower than all numbers in the list?

(check-expect (all-less-than? 4 (list 5 6 7)) #true)
(check-expect (all-less-than? 4 (list 1 6 7)) #false)
(check-expect (all-less-than? 4 (list 4 6 7)) #false)

(define (all-less-than? num lon)
  (andmap (λ (n) (< num n)) lon))

;; find-adjacent : [List-of [List-of Number]] Position -> [List-of Number]
;; find the adjacent points to the current point
;; points off the grid are considered to be 9

(check-expect (find-adjacent (list (list 1 2 3)
                                   (list 4 5 6)
                                   (list 7 8 9))
                             (make-posn 1 1))
              (list 2 4 6 8))
(check-expect (find-adjacent (list (list 1 2 3)
                                   (list 4 5 6)
                                   (list 7 8 9))
                             (make-posn 1 0))
              (list 9 1 3 5))
(check-expect (find-adjacent (list (list 1 2 3)
                                   (list 4 5 6)
                                   (list 7 8 9))
                             (make-posn 2 2))
              (list 6 8 9 9))

(define (find-adjacent grid posn)
  (map
   (λ (p) (find-num-at-coordinates grid (add-posns posn p)))
   ADJACENCY-LIST))

(define ADJACENCY-LIST (list (make-posn 0 -1)
                             (make-posn -1 0)
                             (make-posn 1 0)
                             (make-posn 0 1)))

;; add-posns : Position Position -> Position
;; adds the positions like vectors

(check-expect (add-posns (make-posn 1 2) (make-posn 0 0)) (make-posn 1 2))
(check-expect (add-posns (make-posn 2 5) (make-posn -1 2)) (make-posn 1 7))

(define (add-posns posn1 posn2)
  (make-posn (+ (posn-x posn1) (posn-x posn2))
             (+ (posn-y posn1) (posn-y posn2))))

;; find-num-at-coordinates : [List-of [List-of Number]] Position -> Number
;; returns the number at the coordinates or 9 if no such number exists

(check-expect (find-num-at-coordinates (list (list 1 2 3)
                                             (list 4 5 6)
                                             (list 7 8 9))
                                       (make-posn 1 1))
              5)
(check-expect (find-num-at-coordinates (list (list 1 2 3)
                                             (list 4 5 6)
                                             (list 7 8 9))
                                       (make-posn -1 1))
              9)

(define (find-num-at-coordinates grid posn)
  (local [(define HEIGHT (length grid))
          (define WIDTH (length (first grid)))
          (define X (posn-x posn))
          (define Y (posn-y posn))]
    (cond
      [(or (negative? X) (>= X WIDTH)) 9]
      [(or (negative? Y) (>= Y HEIGHT)) 9]
      [else
       (list-ref (list-ref grid Y) X)])))

;; day 9 part 2
;; size of basins

;; get-basin-size-product : String -> Number
;; gets the product of the sizes from the 3 largest basins
;; in the grid in the given file

(check-expect (get-basin-size-product "advent-smoke-1.txt") 1134)

(define (get-basin-size-product filename)
  (local [(define GRID (los->grid (read-lines filename)))]
    (foldr * 1
           ((λ (L) (list (first L) (second L) (third L)))
            (quicksort
             (map
              (λ (p) (find-size-of-basin GRID p))
              (find-low-points GRID))
             >=)))))

;; find-size-of-basin : Grid Position -> Nat
;; given the grid and the lowest position in the basin,
;; how many numbers are in the basin

(check-expect (find-size-of-basin (list (list 0 1 9 0)
                                        (list 2 9 2 1)
                                        (list 3 9 9 5)
                                        (list 9 0 1 9))
                                  (make-posn 0 0))
              4)
(check-expect (find-size-of-basin (list (list 0 1 9 0)
                                        (list 2 9 2 1)
                                        (list 3 9 9 5)
                                        (list 9 0 1 9))
                                  (make-posn 3 0))
              4)
(check-expect (find-size-of-basin (list (list 0 1 9 0)
                                        (list 2 9 2 1)
                                        (list 3 9 9 5)
                                        (list 9 0 1 9))
                                  (make-posn 1 3))
              2)

(define (find-size-of-basin grid lowest)
  (local [;; find-posns-above : Position Number -> [List-of Position]
          ;; given a position and the height of the previous position,
          ;; if the current position is above the previous position
          ;; returns a list of the current positions and all positions
          ;; above it, stopping at and excluding positions with height 9.
          (define (find-posns-above posn prev-height)
            (local [(define HEIGHT (find-num-at-coordinates grid posn))
                    (define NEIGHBORS (map (λ (p) (add-posns posn p)) ADJACENCY-LIST))]
              (cond
                [(or (= HEIGHT 9) (<= HEIGHT prev-height)) '()]
                [else
                 (cons posn (foldr append '()
                                   (map (λ (p) (find-posns-above p HEIGHT)) NEIGHBORS)))])))

          ;; remove-duplicate-posns : [List-of Position] -> [List-of Position]
          ;; removes duplicate positions from the list
          (define (remove-duplicate-posns lop)
            (foldr
             (λ (curr prev)
               (cons curr
                     (filter
                      (λ (p) (not (and (= (posn-x p) (posn-x curr))
                                       (= (posn-y p) (posn-y curr)))))
                      prev)))
             '()
             lop))]
    (length (remove-duplicate-posns (find-posns-above lowest -1)))))