Changes In Branch day15 Excluding Merge-Ins
This is equivalent to a diff from 80485b to 78e73e
2019-11-29
| ||
15:47 | Getting closer… Leaf check-in: 78e73e user: joel tags: day15 | |
2019-11-28
| ||
17:03 | Much better... check-in: 6389c1 user: joel tags: day15 | |
2019-11-25
| ||
13:27 | Day 15 first steps check-in: 440bf0 user: joel tags: day15 | |
2018-12-24
| ||
13:29 | Add Day 14 solutions Leaf check-in: 80485b user: joel tags: trunk | |
2018-12-22
| ||
19:04 | Add Day 13 solutions check-in: 381699 user: joel tags: trunk | |
Added day15-input.txt version [a14673].
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 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 version [67cb46].
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 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 (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 (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 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 ;; 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) (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) (+ (* (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) 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)) |