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.
This repo is archived. You can view files and clone it, but cannot push or open issues/pull-requests.

59 lines
1.9 KiB

#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))))
(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))))
[(> next-val 9) (- next-val 9)]
[else next-val])))
;; graph library is too slow to solve big grid
;; needs dynamic programming
#;(solve big-data)