Index: day15.rkt
==================================================================
--- day15.rkt
+++ day15.rkt
@@ -1,20 +1,22 @@
-#lang debug racket/base
+#lang racket/base
 
 (require racket/match
          racket/function
          racket/list
          racket/vector
          racket/set
          threading)
 
+;; PRIMITIVES AND CONSTANTS ----------------------------------------------------
+
 ;; Good ol’ positions.
 (struct posn (x y) #:transparent)
 
 ;; The concept of “reading order” is an important one in this puzzle. Fighters move,
 ;; targets and paths are chosen in order of how you’d encounter them reading the grid
-;; left-to-right, top to bottom.
+;; top to bottom, left-to-right.
 ;;   The two functions below are going to do all the work of determining sort order
 ;; for us, whenever we need it.
 ;;   This is also where I mention that this program views 0,0 as “top left”.
 (define (posn<? p1 p2)
   (match-define (posn x1 y1) p1)
@@ -34,55 +36,45 @@
 ;; Making this a subtype of posn means we can pass a fighter to any function
 ;; that expects a posn.
 (struct fighter (type hp) #:super struct:posn #:transparent)
 (define ATTACK-POWER 3)
 (define STARTING-HP 200)
+
+;; Paths are also a subtype of posn. The path’s posn elements reflect the
+;; intended end-points of the path. This will allow us to sort lists of
+;; paths using reading-order. We don’t need to carry the complete list of
+;; steps in the path, just the candidates for first steps along it.
+(struct path (distance first-steps) #:super struct:posn #:transparent)
 
 ;; “The grid…a digital frontier. I tried to picture clusters of information as
 ;; they moved through the computer. What did they look like? …I kept dreaming
 ;; of a world I thought I’d never see. And then one day…I got in.”
 ;;   https://youtu.be/QBYr0k8dOtw?t=24
+(struct grid (vec rows cols) #:transparent)
 
 ;; Our “grid” is, behind the scenes, a one-dimensional vector with length ROWS*COLS.
-;; The “target” tracks the end-point of the path the grid describes (when used as a
-;; “path map”, see below
-(struct grid (vec rows cols start target) #:transparent)
-
-;; Translate between an x,y pair of coordinates and an index into the grid vector
+;; So we’ll need to translate between an x,y pair of coordinates and an index into
+;; the grid vector
 (define (posn→index g p)
   (+ (* (grid-cols g) (posn-y p)) (posn-x p)))
 
 (define (index→posn g i)
   (posn (modulo i (grid-cols g))
         (quotient i (grid-cols g))))
 
-;; This will come in handy later.
-;; A path-step is a sub-type of posn with 
-(struct path-step (dist) #:super struct:posn #:transparent)
+;; WORKING WITH GRIDS ----------------------------------------------------------
 
 ;; Create a grid from a list of strings each representing a row, filling each
 ;; spot with the corresponding character in the string
-(define (lines->grid line-strs)
+(define (lines→grid line-strs)
   (define row-count (length line-strs))
   (define col-count (string-length (first line-strs)))
   (grid (apply vector-append
                (map list->vector
                     (map string->list line-strs)))
         row-count
-        col-count
-        #f
-        #f))
-
-(define test-map
-  (lines->grid
-   '("#######"
-     "#E..G.#"
-     "#...#.#"
-     "#.G.#G#"
-     "#######")))
-
-;; Grids and Positions: put them together
+        col-count))
 
 ;; Reference the value at given position in a grid
 (define (grid-ref g p)
   (vector-ref (grid-vec g) (posn→index g p)))
 
@@ -95,13 +87,13 @@
 (define (grid-clear-at? g p)
   (equal? (grid-ref g p) #\.))
 
 ;; Make a blank grid of the same dimensions, for use in making “path grids” (see
 ;; further below)
-(define (copy-blank-grid g [start #f] [target #f])
-  (match-define (grid _ rows cols _) g)
-  (grid (make-vector (* rows cols) #f) rows cols start target))
+(define (copy-blank-grid g)
+  (match-define (grid _ rows cols) g)
+  (grid (make-vector (* rows cols) #f) rows cols))
 
 ;; (For debugging) Represent the grid as a square of single-character values
 (define (display-grid g [g2 #f])
   (define grid-size (* (grid-cols g) (grid-rows g)))
   (display
@@ -149,59 +141,49 @@
              flatten
              (filter (curry grid-clear-at? world) _)
              (set-subtract pos)
              remove-duplicates)]))
 
-;; “Path grids” are a specific use of grids where points are marked with integers
-;; indicated their distance from an origin point.
-;; A point has been checked when it is not equal to #false.
-(define (not-yet-checked? pmap pos)
-  (not (grid-ref pmap pos)))
-
-;; Find the most direct path(s) to a fighter from an end-position
-(define (path-grid world f end-pos)
-  (define result-grid (copy-blank-grid world f end-pos))
+;; Working with PATHS ----------------------------------------------------------
+
+;; Find the most direct path(s) to a fighter from an end-position.
+;; This is the function you are probably looking for if you are reading this file at all.
+;; The algorithm starts at the end position and works outwards, finding unoccupied positions
+;; and marking them (on a blank copy of the map) with their distance from the end-point.
+;; As soon as any of the considered points includes one or more free neighbors of the given
+;; fighter, recursion stops and returns a path.
+(define (build-path world f end-pos)
+  (define result-grid (copy-blank-grid world))
+  (define (not-yet-checked? pos) (not (grid-ref result-grid pos)))
   (define goal-pts (free-neighbors-of world f))
   (grid-mark! result-grid end-pos 0)
   
   (let loop ([pts-to-check (list end-pos)]
              [i 1])
     (define new-coords (~> (free-neighbors-of world pts-to-check)
-                           (filter (curry not-yet-checked? result-grid) _)))
-    (for-each (lambda (p) (grid-mark! result-grid p i)) new-coords)
+                           (filter not-yet-checked? _)))
+    (define maybe-first-steps (set-intersect new-coords goal-pts))
     (cond
-      [(not (empty? (set-intersect new-coords goal-pts))) result-grid]
+      [(not (empty? maybe-first-steps))
+       (path (posn-x end-pos) (posn-y end-pos) i maybe-first-steps)]
       [(empty? new-coords) #f]
-      [else (loop new-coords (+ 1 i))])))
-
-;; What is the distance of the path represented by a path-map?
-(define (path-distance pmap)
-  (~>> (neighbor-coords pmap (grid-start pmap))
-       (filter-map (curry grid-ref pmap)) ; Weeds out #f values
-       (apply min)))
-
-;; Get only the shortest path(s) from a list of path maps
+      [else
+       (for-each (lambda (p) (grid-mark! result-grid p i)) new-coords)
+       (loop new-coords (+ 1 i))])))
+
+;; Convenience: 
+(define (make-pathfinder world f)
+  (curry build-path world f))
+
+;; Get only the shortest path(s) from a list of paths
 (define (shortest plst)
-  (define shortest-distance (apply min (map (curry path-distance f) plst)))
+  (define shortest-distance (apply min (map path-distance plst)))
   (define (among-shortest? pmap) (equal? shortest-distance (path-distance pmap)))
   (filter among-shortest? plst))
 
-;; What is the actual next step a fighter should take along a particular path,
-;; breaking ties by reading order?
-(define (next-step pmap f)
-  (define (coord→step c) (cond [c (path-step (posn-x c) (posn-y c) (grid-ref pmap c))] [else #f]))
-  (define possibles
-    (~>> (neighbor-coords f)
-         (filter-map coord→step)))
-  (define min-dist (min (map path-step-dist possibles)))
-  (~>> (filter (λ (ps) (equal? min-dist (path-step-dist ps))) possibles)
-       reading-order
-       first))
-
-
-
-;;
+;; Working with FIGHTERS -------------------------------------------------------
+
 ;; Let’s start doing stuff with fighters
 
 ;; Make a list of fighters from a grid, with the results in reading order.
 (define (grid->fighters g)
   (for/fold ([fighters '()]
@@ -211,12 +193,13 @@
     (cond [(member val '(#\G #\E))
            (match-define (posn x y) (index→posn g idx))
            (cons (fighter x y val STARTING-HP) fighters)]
           [else fighters])))
 
-(define (fighter-located-in? f lst)
-  (not (empty? (filter (curry posn=? f) lst))))
+;; I’ll give you three guesses each what these do
+(define (fighter-located-in? f posns)
+  (not (empty? (filter (curry posn=? f) posns))))
 
 (define (enemies? f1 f2)
   (not (equal? (fighter-type f1) (fighter-type f2))))
 
 (define (enemies-of f1 flst)
@@ -227,16 +210,31 @@
   (filter (curryr fighter-located-in? adjacent-posns) all-enemies))
 
 (define (fighter-alive? f)
   (positive? (fighter-hp f)))
 
-(define (determine-next-move world f enemies)
-  #t)
-
-(define fs (grid->fighters test-map))
-(define f (first fs))
-(define es (enemies-of f fs))
-(define possible-targets (free-neighbors-of test-map es))
-(define possible-paths (filter-map (curry path-grid test-map f) possible-targets))
-
-
- 
+;; Here’s a proof of concept.
+;; As you can see, after all that work it is trivially easy to tie everything together.
+(module+ test
+  (require rackunit)
+  (define test-map
+    (lines→grid
+     '("#######"
+       "#E..G.#"
+       "#...#.#"
+       "#.G.#G#"
+       "#######")))
+  (define fs (grid->fighters test-map))
+  (define f (first fs))
+  (define es (enemies-of f fs))
+  
+  ;; Work through the algorithm specified in the problem description to find the next move
+  ;; for the elf at 1,1 (skipping the test for adjacent enemies):
+  (define possible-targets (free-neighbors-of test-map es))
+  (define possible-paths (filter-map (make-pathfinder test-map f) possible-targets))
+  (define shortest-paths (shortest possible-paths))
+  (define selected-path (first (reading-order shortest-paths)))
+  (define next-step (first (reading-order (path-first-steps selected-path))))
+
+  ;; Ta-da
+  (check-equal? next-step (posn 2 1)))
+