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....#######....##### +#########...##..########...##### +################################ ADDED day15.rkt Index: day15.rkt ================================================================== --- day15.rkt +++ day15.rkt @@ -0,0 +1,336 @@ +#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 #: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 +;; for us, whenever we need it. +;; This is also where I mention that this program views 0,0 as “top left”. +(define (posnvector + (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) 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) + (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)) + + (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) + (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) + (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 (alive? f) + (positive? (fighter-hp f))) + +(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 + '("#########" + "#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))