ADDED   day15.rkt
Index: day15.rkt
==================================================================
--- day15.rkt
+++ day15.rkt
@@ -0,0 +1,240 @@
+#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
+;; 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)
+  (match-define (posn x2 y2) p2)
+  (or (< y1 y2)
+      (and (<= y1 y2)
+           (<= x1 x2))))
+
+(define (reading-order lst)
+  (sort lst posn<?))
+
+(define (posn=? p1 p2)
+  (and (equal? (posn-x p1) (posn-x p2))
+       (equal? (posn-y p1) (posn-y p2))))
+
+;; Keeping track of elves and gnomes. We’ll have separate lists for each group.
+;; 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.
+;; 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))))
+
+;; 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 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))
+
+;; Reference the value at given position in a grid
+(define (grid-ref g p)
+  (vector-ref (grid-vec g) (posn→index g p)))
+
+;; Change the value at given position
+(define (grid-mark! g pos v)
+  (vector-set! (grid-vec g) (posn→index g pos) v))
+
+;; Used to determine if a fighter could move into a given spot.
+;; Anything besides "." counts as an obstruction (incl. other fighters)
+(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)
+  (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
+   (apply string-append
+          (for/fold ([lst '()]
+                     #:result (reverse (cons "\n" lst)))
+                    ([val (in-vector (grid-vec g))]
+                     [i (in-naturals 1)])
+            (define ch
+              (cond [(number? val) (number->string (modulo val 10))]
+                    [(boolean? val) "-"]
+                    [(string? val) val]
+                    [else (format "~a" val)]))
+            (cond [(and (equal? 0 (modulo i (grid-cols g)))
+                        (< i grid-size))
+                   (cons "\n" (cons ch lst))]
+                  [else (cons ch lst)])))))
+
+;; Is point p inside grid g? Film at 11
+(define (inside-grid? g p)
+  (match-define (posn px py) p)
+  (and (>= px 0)
+       (>= py 0)
+       (< px (grid-cols g))
+       (< py (grid-rows g))))
+
+;; Get a list of a positions neighboring points, ensuring none are out of bounds
+(define (neighbor-coords g pos)
+  (match-define (posn x y) pos)
+  (filter (curry inside-grid? g)
+          (list (posn (- x 1) y)
+                (posn x (+ y 1))
+                (posn (+ x 1) y)
+                (posn x (- y 1)))))
+
+;; Get all the EMPTY neighboring points of a given spot OR list of spots.
+;; If a (listof posn?) is passed, ensures the returned list does not include
+;; any of the original positions.
+(define (free-neighbors-of world pos)
+  (cond [(posn? pos)
+         (~> (neighbor-coords world pos)
+             (filter (curry grid-clear-at? world) _))]
+        [(list? pos)
+         (~> (map (curry neighbor-coords world) pos)
+             flatten
+             (filter (curry grid-clear-at? world) _)
+             (set-subtract pos)
+             remove-duplicates)]))
+
+;; 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 not-yet-checked? _)))
+    (define maybe-first-steps (set-intersect new-coords goal-pts))
+    (cond
+      [(not (empty? maybe-first-steps))
+       (path (posn-x end-pos) (posn-y end-pos) i maybe-first-steps)]
+      [(empty? new-coords) #f]
+      [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 path-distance plst)))
+  (define (among-shortest? pmap) (equal? shortest-distance (path-distance pmap)))
+  (filter among-shortest? plst))
+
+;; 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 '()]
+             #:result (reading-order fighters))
+            ([val (in-vector (grid-vec g))]
+             [idx (in-naturals)])
+    (cond [(member val '(#\G #\E))
+           (match-define (posn x y) (index→posn g idx))
+           (cons (fighter x y val STARTING-HP) fighters)]
+          [else fighters])))
+
+;; 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)
+  (filter (curry enemies? f1) flst))
+
+(define (adjacent-enemies world f all-enemies)
+  (define adjacent-posns (neighbor-coords world f))
+  (filter (curryr fighter-located-in? adjacent-posns) all-enemies))
+
+(define (fighter-alive? f)
+  (positive? (fighter-hp f)))
+
+;; 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)))
+