day 23 racket with comments

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)])