alexandria-ocasio-cortez axiom-of-choice area-of-concern american-orthodox-church almost-optimal-coset solutions in the year of our lord 2021, I guess
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

113 lines
3.0 KiB

#lang racket
(require "lib/common.rkt"
(struct posn (x y) #:transparent)
(define (explode str)
(map string (string->list str)))
(define (parse lines)
(~>> lines
(map explode)
(map (λ~>> (map string->number)
(apply vector)))
(apply vector)))
(define (board-dim board)
(cons (vector-length (vector-ref board 0))
(vector-length board)))
(define (board-ref board x y)
(vector-ref (vector-ref board y) x))
(define (adjacents board x y)
(match-define (cons xmax ymax) (board-dim board))
(define x-1 (- x 1))
(define x+1 (+ x 1))
(define y-1 (- y 1))
(define y+1 (+ y 1))
(for/list ([px (in-list (list x-1 x x+1 x))]
[py (in-list (list y y-1 y y+1))]
#:when (not (or (< px 0) (< py 0) (>= px xmax) (>= py ymax))))
(posn px py)))
(define (board-< board x1 y1 x2 y2)
(< (board-ref board x1 y1)
(board-ref board x2 y2)))
(define (lowest-points board)
(define (lowest? x y)
(define adjs (adjacents board x y))
(for/and ([adj (in-list adjs)])
(board-< board x y (posn-x adj) (posn-y adj))))
(match-define (cons m n) (board-dim board))
(for*/list ([i (in-range m)]
[j (in-range n)]
#:when (lowest? i j))
(posn i j)))
(define (day9a board)
(define heights (map (λ (p) (board-ref board (posn-x p) (posn-y p)))
(lowest-points board)))
(for/sum ([h (in-list heights)])
(add1 h)))
(define (day9b board)
(define lowest (lowest-points board))
(define (bound? p2)
(not (= (board-ref board (posn-x p2) (posn-y p2)) 9)))
(define (run-bfs i j)
(define seen (mutable-set))
(define parents (make-hash))
(define Q (make-queue))
(set-add! seen (posn i j))
(hash-set! parents (posn i j) (posn i j))
(enqueue! Q (posn i j))
(define (bfs/queue)
(cond [(queue-empty? Q) #f]
(define cur (dequeue! Q))
(for ([adj (in-list (adjacents board (posn-x cur) (posn-y cur)))]
#:when (and (not (set-member? seen adj))
(bound? adj)))
(hash-set! parents adj cur)
(enqueue! Q adj)
(set-add! seen adj))
(define sizes (map (λ (p) (hash-count (run-bfs (posn-x p) (posn-y p))))
(for/product ([s (in-list (take (sort sizes >) 3))])
(module+ main
(call-with-input-file "data/day9.txt"
(λ (prt)
(define board (parse (port->lines prt)))
(answer 9 1 (day9a board))
(answer 9 2 (day9b board)))))
(module+ test
(require rackunit)
(define test-input
(vector (vector 2 1 9 9 9 4 3 2 1 0)
(vector 3 9 8 7 8 9 4 9 2 1)
(vector 9 8 5 6 7 8 9 8 9 2)
(vector 8 7 6 7 8 9 6 7 8 9)
(vector 9 8 9 9 9 6 5 6 7 8)))
(check-equal? (day9a test-input) 15)
(check-equal? (day9b test-input) 1134))