day 17 racket complete

3 files changed, 92 insertions, 62 deletions

diff --git a/aoc2023-other/day-17/day-17.rkt b/aoc2023-other/day-17/day-17.rkt
index 8a1fc02..7d8c108 100644
--- a/aoc2023-other/day-17/day-17.rkt
+++ b/aoc2023-other/day-17/day-17.rkt
@@ -1,51 +1,83 @@
 #lang racket
 
 (require advent-of-code
-         threading)
+         threading
+         data/heap)
 
+(struct state (p heat-lost previous history) #:transparent)
 (struct posn (r c) #:transparent)
-(struct to (posn dir) #:transparent)
-(struct edge (from to dir) #:transparent)
-
-(define input
-  "2413432311323
-3215453535623
-3255245654254
-3446585845452
-4546657867536
-1438598798454
-4457876987766
-3637877979653
-4654967986887
-4564679986453
-1224686865563
-2546548887735
-4322674655533")
+
+(define/match (add _p1 _p2)
+  [((posn r1 c1) (posn r2 c2)) (posn (+ r1 r2) (+ c1 c2))])
+
+(define deltas (list (posn 0 1) (posn 0 -1) (posn 1 0) (posn -1 0)))
+
+(define input (fetch-aoc-input (find-session) 2023 17 #:cache #true))
 
 (define grid
   (for*/hash ([(row r) (in-indexed (in-list (string-split input "\n")))]
               [(col c) (in-indexed (in-string row))])
     (values (posn r c) (~> col string string->number))))
 
-(define grid-nodes (hash-keys grid))
-(match-define (posn rmax cmax) (argmax (λ (p) (+ (posn-r p) (posn-c p))) grid-nodes))
+(define goal-posn (~>> grid hash-keys (argmax (λ (p) (+ (posn-r p) (posn-c p))))))
+
+(define (make-key s)
+  (cons (state-p s) (same-dir s)))
+
+(define (goal? n s)
+  (and (equal? goal-posn (state-p s)) (>= (length (same-dir s)) n)))
+
+(define (same-dir s)
+  (define history (state-history s))
+  (if (empty? history) '() (takef history (λ (n) (equal? n (car history))))))
+
+(define (find-good-neighbors min-dist max-dist s)
+  (match-define (state p hl prev hist) s)
+
+  (define (eliminate-bad-neighbors delta)
+    (define neighbor (add p delta))
+    (cond
+      [(or (equal? neighbor prev) (not (hash-has-key? grid neighbor))) #false]
+      [else
+       (define same (same-dir s))
+       (define l (length same))
+       (cond
+         [(= max-dist l) (not (equal? delta (car same)))]
+         [(= l 0) #true]
+         [(< l min-dist) (equal? delta (car same))]
+         [else #t])]))
+
+  (define (make-state delta)
+    (define neighbor (add p delta))
+    (define new-loss (+ hl (hash-ref grid neighbor)))
+    (state neighbor new-loss p (cons delta hist)))
+
+  (~>> deltas (filter eliminate-bad-neighbors) (map make-state)))
 
-(define/match (find-edge-cost e prev-two)
-  [((edge _ _ d) (list d d)) 1e10]
-  [(_ _) (hash-ref edges e)])
+(define (find-path neighbor-fn goal-fn)
+  (define seen (mutable-set))
+  (define queue (make-heap (λ (a b) (<= (state-heat-lost a) (state-heat-lost b)))))
+  (heap-add! queue (state (posn 0 0) 0 'none '()))
 
-(define (find-node-cost p)
-  (match-define (posn r c) p)
-  (+ (- rmax r) (- cmax c)))
+  (let bfs ()
+    (define s (heap-min queue))
+    (heap-remove-min! queue)
+    (define key (make-key s))
+    (cond
+      [(set-member? seen key) (bfs)]
+      [else
+       (set-add! seen key)
+       (define neighbors (neighbor-fn s))
+       (define final (findf goal-fn neighbors))
+       (if final
+           (state-heat-lost final)
+           (begin
+             (for ([n (in-list neighbors)])
+               (heap-add! queue n))
+             (bfs)))])))
 
-(define (neighbors p)
-  (match-define (posn r c) p)
-  (~>> (list (to (posn (sub1 r) c) 'north)
-             (to (posn (add1 r) c) 'south)
-             (to (posn r (add1 c)) 'east)
-             (to (posn r (sub1 c)) 'west))
-       (filter (λ (p) (hash-has-key? grid (to-posn p))))))
+;; part 1
+(find-path (curry find-good-neighbors 0 3) (curry goal? 1))
 
-(define edges
-  (for*/hash ([(k v) (in-hash grid)] [neighbor (in-list (neighbors k))])
-    (values (edge k (to-posn neighbor) (to-dir neighbor)) v)))
+;; part 2
+(find-path (curry find-good-neighbors 4 10) (curry goal? 4))
\ No newline at end of file
diff --git a/aoc2023/src/day17/solve.gleam b/aoc2023/src/day17/solve.gleam
index 3ed632c..431dcc7 100644
--- a/aoc2023/src/day17/solve.gleam
+++ b/aoc2023/src/day17/solve.gleam
@@ -1,36 +1,17 @@
 import adglent.{First, Second}
 import gleam/io
+import gleam/string
 import utilities/array2d.{type Posn, Posn}
 
-type Direction {
-  North
-  South
-  East
-  West
-}
-
-fn turn_dirs(dir: Direction) {
-  case dir {
-    North | South -> [East, West]
-    East | West -> [North, South]
-  }
-}
-
-fn delta(dir: Direction) {
-  case dir {
-    North -> Posn(-1, 0)
-    South -> Posn(1, 0)
-    East -> Posn(0, 1)
-    West -> Posn(0, -1)
-  }
-}
-
 pub fn part1(input: String) {
-  todo as "Implement solution to part 1"
+  input
+  |> array2d.parse_grid
+  |> string.inspect
 }
 
 pub fn part2(input: String) {
-  todo as "Implement solution to part 2"
+  input
+  |> string.inspect
 }
 
 pub fn main() {
diff --git a/aoc2023/test/day17/day17_test.gleam b/aoc2023/test/day17/day17_test.gleam
index cf624fb..c1ebd22 100644
--- a/aoc2023/test/day17/day17_test.gleam
+++ b/aoc2023/test/day17/day17_test.gleam
@@ -13,7 +13,24 @@ type Problem2AnswerType =
 /// ```gleam
 ///const part1_examples: List(Example(Problem1AnswerType)) = [Example("some input", "")]
 /// ```
-const part1_examples: List(Example(Problem1AnswerType)) = []
+const part1_examples: List(Example(Problem1AnswerType)) = [
+  Example(
+    "2413432311323
+3215453535623
+3255245654254
+3446585845452
+4546657867536
+1438598798454
+4457876987766
+3637877979653
+4654967986887
+4564679986453
+1224686865563
+2546548887735
+4322674655533",
+    "102",
+  ),
+]
 
 /// Add examples for part 2 here:
 /// ```gleam