ADDED   day15-input.txt
Index: day15-input.txt
==================================================================
--- day15-input.txt
+++ day15-input.txt
@@ -0,0 +1,32 @@
+################################
+#######################.########
+######################....######
+#######################.....####
+##################..##......####
+###################.##.....#####
+###################.....G..#####
+##################.....G...#####
+############.....GG.G...#..#####
+##############...##....##.######
+############...#..G............#
+###########......E.............#
+###########...#####..E........##
+#...#######..#######.......#####
+#..#..G....G#########.........##
+#..#....G...#########..#....####
+##.....G....#########.E......###
+#####G.....G#########..E.....###
+#####.......#########....#.....#
+#####G#G....G#######.......#..E#
+###.....G.....#####....#.#######
+###......G.....G.G.......#######
+###..................#..########
+#####...................########
+#####..............#...#########
+####......G........#.E.#E..#####
+####.###.........E...#E...######
+####..##........#...##.....#####
+########.#......######.....#####
+########...E....#######....#####
+#########...##..########...#####
+################################

Index: day15.rkt
==================================================================
--- day15.rkt
+++ day15.rkt
@@ -1,18 +1,25 @@
-#lang racket/base
+#lang debug racket/base
 
 (require racket/match
          racket/function
          racket/list
          racket/vector
          racket/set
+         racket/file
          threading)
 
 ;; PRIMITIVES AND CONSTANTS ----------------------------------------------------
 
+;; Select the “lowest” somethings from a list, with “lowest what” being determined
+;; by the key-procedure.
+(define (select-minimums lst key-pred)
+  (define minval (apply min (map key-pred lst)))
+  (filter (lambda (x) (equal? minval (key-pred x))) lst))
+
 ;; Good ol’ positions.
-(struct posn (x y) #:transparent)
+(struct posn (x y) #:transparent #:mutable)
 
 ;; 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
@@ -26,18 +33,21 @@
            (<= x1 x2))))
 
 (define (reading-order lst)
   (sort lst posn<?))
 
+(define (first-by-reading-order lst)
+  (first (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)
+(struct fighter posn (type hp) #:transparent #:mutable)
 (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
@@ -48,10 +58,12 @@
 ;; “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)
+
+(define EMPTY #\.)
 
 ;; 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)
@@ -83,11 +95,11 @@
   (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) #\.))
+  (equal? (grid-ref g p) EMPTY))
 
 ;; 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)
@@ -153,41 +165,38 @@
 ;; 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))
+  
+  (cond
+    [(member end-pos goal-pts)
+     (path (posn-x end-pos) (posn-y end-pos) 0 (list end-pos))]
+    [else
+     (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))]))]))
+
+(define (reachable-paths-to world f targets)
+  (filter-map (curry build-path world f) targets))
 
 ;; 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)
+(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))
@@ -198,43 +207,130 @@
 ;; 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))))
+  (and (alive? 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)
+(define (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.
+(define (move-fighter! world f to-pos)
+  (match-define (posn new-x new-y) to-pos)
+  (grid-mark! world f EMPTY)
+  (grid-mark! world to-pos (fighter-type f))
+  (set-posn-x! f new-x)
+  (set-posn-y! f new-y))
+
+;; If the attack proves fatal, return the killed fighter so the grid can be
+;; updated.
+(define (attack! victim)
+  (define new-hp (- (fighter-hp victim) ATTACK-POWER))
+  (set-fighter-hp! victim new-hp)
+  (cond [(<= new-hp 0) victim]
+        [else #f]))
+
+;; The OVERALL LOGIC of the fight ----------------------------------------------
+
+;; Taking a turn:
+;; “If the unit is already in range of a target, it does not move, but continues
+;; its turn with an ATTACK. Otherwise, since it is not in range of a target, it
+;; MOVES. To MOVE the unit must:
+;;   1) “Consider the squares that are in range [of a target]”
+;;   2) “Determine which of those squares it could reach in the fewest steps.”
+;;      • “If the unit cannot reach (find an open path to) any of the squares
+;         that are in range, it ends its turn.”
+;;      • “If multiple squares are in range and tied for being reachable in the
+;;        fewest steps, the square which is first in reading order is chosen.”
+;;   3) “Take a single step toward the chosen square along the shortest path to
+;;      that square.”
+;;      • “If multiple steps would put the unit equally closer to its destination,
+;;        the unit chooses the step which is first in reading order.”
+;; To ATTACK a unit must:
+;;   1) “Determine all of the targets that are in range of it by being immediately
+;;      adjacent to it.”
+;;      • “If there are no such targets, the unit ends its turn.”
+;;      • “Otherwise, the adjacent target with the fewest hit points is selected;
+;;        in a tie, the adjacent target with the fewest hit points which is first
+;;        in reading order is selected.”
+;;    2) “The unit deals damage equal to its attack power to the selected target,
+;;       reducing its hit points by that amount. If this reduces its hit points
+;;       to 0 or fewer, the selected target dies.”
+(define (fighter-take-turn! world f enemies)
+  (unless (not (empty? (adjacent-enemies world f enemies)))
+    (define viable-paths (~> (free-neighbors-of world enemies)
+                             (reachable-paths-to world f _)))
+    (when (not (empty? viable-paths))
+      (define next-step (~> (select-minimums viable-paths path-distance)
+                            first-by-reading-order
+                            path-first-steps
+                            first-by-reading-order))
+      (move-fighter! world f next-step)))
+  (define attackable-foes (adjacent-enemies world f enemies))
+  (when (not (empty? attackable-foes))
+    (define fighter-killed
+      (~> (select-minimums attackable-foes fighter-hp)
+          reading-order
+          first
+          attack!))
+    (when fighter-killed (grid-mark! world fighter-killed EMPTY))))
+
+(define (do-round world fighters)
+  (for/and ([f (in-list (reading-order fighters))]) ; will break on first #f result
+    (cond [(not (alive? f)) #t] ; silently skip anyone who died this round
+          [else
+           (define enemies (enemies-of f fighters))
+           (cond [(not (empty? enemies))
+                  (fighter-take-turn! world f enemies)
+                  #t]
+                 [else #f])])))
+
+(define (FIGHT!! input-grid)
+  (define initial-fighters (grid→fighters input-grid))
+  (let another-round ([completed-rounds 0]
+                      [fighters initial-fighters])
+    ;#R completed-rounds
+    ;#R (reading-order fighters)
+    ;(display-grid input-grid fighters)
+      
+    (cond [(do-round input-grid fighters)
+           (another-round (+ completed-rounds 1)
+                          (filter alive? fighters))]
+          [else (values completed-rounds (filter alive? fighters))])))
+
+(define (total-hp fighters)
+  (apply + (map fighter-hp fighters)))
+
+(define (day15-part1 input-grid)
+  (define-values (rounds survivors) (FIGHT!! input-grid))
+  (apply * rounds (map fighter-hp survivors)))
+
 (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)))
-
+     '("#########"
+       "#G......#"
+       "#.E.#...#"
+       "#..##..G#"
+       "#...##..#"
+       "#...#...#"
+       "#.G...G.#"
+       "#.....G.#"
+       "#########" )))
+
+  (define-values (rounds fighters) (FIGHT!! test-map))
+  (check-equal? rounds 20)
+
+  (define actual-input
+    (lines→grid (file->lines "day15-input.txt")))
+  (display-grid actual-input)
+  (grid→fighters actual-input)
+  #;(check-equal? (day15-part1 actual-input) 1))