You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
59 lines
1.9 KiB
Racket
59 lines
1.9 KiB
Racket
#lang br
|
|
(require racket/file graph rackunit)
|
|
|
|
(define lines (file->lines "15.rktd"))
|
|
|
|
(define grid (for*/list ([(line ridx) (in-indexed lines)]
|
|
[(num cidx) (in-indexed (map string->number (regexp-match* #rx"." line)))])
|
|
(cons (make-rectangular cidx ridx) num)))
|
|
|
|
(define data (make-hash grid))
|
|
|
|
(define (row-length data) (add1 (apply max (map imag-part (hash-keys data)))))
|
|
(define (col-length data) (add1 (apply max (map real-part (hash-keys data)))))
|
|
|
|
(define (make-grid-graph data)
|
|
(define rows (row-length data))
|
|
(define cols (col-length data))
|
|
(define g (weighted-graph/directed null))
|
|
(for ([k (in-hash-keys data)])
|
|
(add-vertex! g k))
|
|
(define (edges-between pt0 pt1)
|
|
(add-directed-edge! g pt0 pt1 (hash-ref data pt1))
|
|
(add-directed-edge! g pt1 pt0 (hash-ref data pt0)))
|
|
(for ([v (in-vertices g)])
|
|
(unless (= (real-part v) (sub1 cols))
|
|
(edges-between v (add1 v)))
|
|
(unless (= (imag-part v) (sub1 rows))
|
|
(edges-between v (+ +i v))))
|
|
g)
|
|
|
|
(define (preds->path preds dest)
|
|
(for/fold ([path (list dest)])
|
|
([i (in-naturals)]
|
|
#:break (zero? (car path)))
|
|
(cons (hash-ref preds (car path)) path)))
|
|
|
|
(define (solve data)
|
|
(define g (make-grid-graph data))
|
|
(define-values (paths preds) (dijkstra g 0))
|
|
(define dest (make-rectangular (sub1 (col-length data)) (sub1 (row-length data))))
|
|
(hash-ref paths dest))
|
|
(check-equal? (solve data) 487)
|
|
|
|
(define big-data (make-hash))
|
|
(define rows (row-length data))
|
|
(define cols (col-length data))
|
|
|
|
(for* ([(k v) (in-hash data)]
|
|
[rowrepeat 5]
|
|
[colrepeat 5])
|
|
(define next-val (+ v colrepeat rowrepeat))
|
|
(hash-set! big-data (+ k (make-rectangular (+ (* colrepeat cols)) (+ (* rowrepeat rows))))
|
|
(cond
|
|
[(> next-val 9) (- next-val 9)]
|
|
[else next-val])))
|
|
|
|
;; graph library is too slow to solve big grid
|
|
;; needs dynamic programming
|
|
#;(solve big-data) |