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.
146 lines
3.2 KiB
146 lines
3.2 KiB
#lang racket |
|
(require "lib/common.rkt" |
|
threading) |
|
|
|
(struct posn (x y) #:transparent) |
|
|
|
(define (posn+ p1 p2) |
|
(posn (+ (posn-x p1) (posn-x p2)) |
|
(+ (posn-y p1) (posn-y p2)))) |
|
|
|
(define (explode str) |
|
(map string (string->list str))) |
|
|
|
(define (parse str) |
|
(~>> str |
|
string-split |
|
(foldl string-append "") |
|
explode |
|
(map string->number) |
|
(apply vector))) |
|
|
|
;; boards are 10x10 |
|
(define (board-ref vec i j) |
|
(vector-ref vec (+ j (* 10 i)))) |
|
(define (board-set! vec i j val) |
|
(vector-set! vec (+ j (* 10 i)) val)) |
|
|
|
(define (adjacents x y) |
|
(define (valid? p) |
|
(match-define (posn x y) p) |
|
(not (or (< x 0) (< y 0) (>= x 10) (>= y 10)))) |
|
|
|
(for/list ([path (in-list (list (posn 1 1) (posn 1 0) (posn 1 -1) |
|
(posn 0 1) #|.........|# (posn 0 -1) |
|
(posn -1 1) (posn -1 0) (posn -1 -1)))] |
|
#:when (valid? (posn+ path (posn x y)))) |
|
(posn+ path (posn x y)))) |
|
|
|
(define (tick-board board) |
|
(define res (vector-copy board)) |
|
(vector-map! add1 res) |
|
|
|
(define seen (mutable-set)) |
|
(define (tick-until-stable) |
|
(cond [(for/and ([v (in-vector res)]) |
|
(not (>= v 10))) |
|
#f] |
|
[else |
|
(for* ([i (in-range 10)] |
|
[j (in-range 10)] |
|
#:when (>= (board-ref res i j) 10)) |
|
(set-add! seen (posn i j)) |
|
(for ([adj (in-list (adjacents i j))] |
|
#:when (not (set-member? seen adj))) |
|
(match-define (posn x y) adj) |
|
(board-set! res x y (add1 (board-ref res x y)))) |
|
(board-set! res i j 0)) |
|
(tick-until-stable)])) |
|
(tick-until-stable) |
|
|
|
res) |
|
|
|
(define (day11a board) |
|
(for/fold ([current-board board] |
|
[current-sum 0] |
|
#:result current-sum) |
|
([_ (in-range 100)]) |
|
(define r (tick-board current-board)) |
|
(values r (+ current-sum (vector-count zero? r))))) |
|
|
|
(define (day11b board) |
|
(let loop ([current-board board] |
|
[current-iter 0]) |
|
(cond [(for/and ([v (in-vector current-board)]) |
|
(zero? v)) |
|
current-iter] |
|
[else (loop (tick-board current-board) (add1 current-iter))]))) |
|
|
|
(module+ main |
|
(call-with-input-file "data/day11.txt" |
|
(λ (prt) |
|
(define board (parse (port->string prt))) |
|
(answer 11 1 (day11a board)) |
|
(answer 11 2 (day11b board))))) |
|
|
|
(module+ test |
|
(require rackunit) |
|
|
|
(define step0 #<<EOD |
|
5483143223 |
|
2745854711 |
|
5264556173 |
|
6141336146 |
|
6357385478 |
|
4167524645 |
|
2176841721 |
|
6882881134 |
|
4846848554 |
|
5283751526 |
|
EOD |
|
) |
|
(define step1 #<<EOD |
|
6594254334 |
|
3856965822 |
|
6375667284 |
|
7252447257 |
|
7468496589 |
|
5278635756 |
|
3287952832 |
|
7993992245 |
|
5957959665 |
|
6394862637 |
|
EOD |
|
) |
|
(define step2 #<<EOD |
|
8807476555 |
|
5089087054 |
|
8597889608 |
|
8485769600 |
|
8700908800 |
|
6600088989 |
|
6800005943 |
|
0000007456 |
|
9000000876 |
|
8700006848 |
|
EOD |
|
) |
|
(define step3 #<<EOD |
|
0050900866 |
|
8500800575 |
|
9900000039 |
|
9700000041 |
|
9935080063 |
|
7712300000 |
|
7911250009 |
|
2211130000 |
|
0421125000 |
|
0021119000 |
|
EOD |
|
) |
|
|
|
(check-equal? (tick-board (parse step0)) (parse step1)) |
|
(check-equal? (tick-board (parse step1)) (parse step2)) |
|
(check-equal? (tick-board (parse step2)) (parse step3)) |
|
(check-equal? (day11a (parse step0)) 1656) |
|
(check-equal? (day11b (parse step0)) 195))
|
|
|