diff options
author | HJ <thechairman@thechairman.info> | 2023-12-23 11:43:37 -0500 |
---|---|---|
committer | HJ <thechairman@thechairman.info> | 2023-12-23 11:43:37 -0500 |
commit | fa21c8c8b1d261d527e40dc07f12a2522740a896 (patch) | |
tree | fd74ecc1ea395ad7f19de0de141acd69ce1844c0 | |
parent | fcf2ad8776a124274b9c80a7df1f49ee7e3b363c (diff) | |
download | gleam_aoc-fa21c8c8b1d261d527e40dc07f12a2522740a896.tar.gz gleam_aoc-fa21c8c8b1d261d527e40dc07f12a2522740a896.zip |
day 23 racket with comments
-rw-r--r-- | aoc2023-other/day-23/day-23.rkt | 36 |
1 files changed, 22 insertions, 14 deletions
diff --git a/aoc2023-other/day-23/day-23.rkt b/aoc2023-other/day-23/day-23.rkt index 0430255..3840187 100644 --- a/aoc2023-other/day-23/day-23.rkt +++ b/aoc2023-other/day-23/day-23.rkt @@ -9,10 +9,11 @@ (for*/hash ([(row r) (in-indexed (string-split input "\n"))] [(col c) (in-indexed row)] #:when (not (equal? col #\#))) - (values (cons (add1 r) (add1 c)) - (match col - [#\. 'trail] - [_ 'slope])))) + ; for now, we don't actually need to detect paths and slopes, just not-rocks + ; in part 1, all forks in the road go left or down, so we can just infer the path + ; direction from the shape of the junction and form a network of junctions from there + ; in part 2, the slopes are removed anyway + (values (cons (add1 r) (add1 c)) col))) (define max-row (~> input (string-split "\n") length)) @@ -22,15 +23,15 @@ (define (get-neighbors posn type) (match-define (cons r c) posn) (match type - ['trail + ['junction (~> (set (cons (add1 r) c) (cons r (add1 c))))] + [_ (~> (list (cons (add1 r) c) (cons (sub1 r) c) (cons r (add1 c)) (cons r (sub1 c))) (filter (curry hash-has-key? trails) _) - list->set)] - ['junction (~> (set (cons (add1 r) c) (cons r (add1 c))))])) + list->set)])) (define junction-points - (for/set ([(k v) (in-hash trails)] #:when (and (equal? v 'trail) - (not (= (set-count (get-neighbors k v)) 2)))) + (for/set ([(k v) (in-hash trails)] + #:when (not (= (set-count (get-neighbors k v)) 2))) k)) (define trails-with-junctions @@ -42,8 +43,10 @@ (define (walk-to-next-junction start current [length 1] [seen (set start)]) (define next (~> current (get-neighbors _ 'trail) (set-subtract seen) set-first)) (cond - [(equal? (hash-ref trails-with-junctions next) 'junction) (list (- (add1 length)) start next)] - [else (walk-to-next-junction start next (add1 length) (set-add seen current))])) + [(equal? (hash-ref trails-with-junctions next) 'junction) + (list (- (add1 length)) start next)] ; weird format is due to graph library + [else + (walk-to-next-junction start next (add1 length) (set-add seen current))])) (define routes-to-junctions (for*/list ([j (in-set junction-points)] @@ -52,11 +55,16 @@ (walk-to-next-junction j neighbor))) ;; part 1 -- using graph library for Bellman-Ford on negative weighted graph +;; Bellman-Ford finds the shortest path, but negating all the path weights +;; will give us the longest path instead +;; +;; unlike Dijkstra which can't handle negative path lengths, Bellman-Ford +;; works as long as the graph is currently directed and acyclic (define slippery-trail (weighted-graph/directed routes-to-junctions)) (match-define-values (distances _) (bellman-ford slippery-trail start)) (- (hash-ref distances end)) -;; part 2 -- rolling my own DFS +;; part 2 -- rolling my own DFS that can reject seen junctions and dead ends (define routes-to-junctions-with-traction (for/fold ([trails (hash)]) ([route (in-list routes-to-junctions)]) (match-define (list (app - weight) from to) route) @@ -68,8 +76,8 @@ (cond [(equal? from to) acc] [else - (define choices (~> (hash-ref g from) (filter (λ (path) (not (set-member? seen (car path)))) _))) - (if (empty? choices) 0 + (define choices (filter (λ (path) (not (set-member? seen (car path)))) (hash-ref g from))) + (if (empty? choices) 0 ;; long dead-ends don't count (for/fold ([best acc]) ([path (in-list choices)] #:do [(match-define (cons next dist) path)]) |