Overview
Comment: | evolution |
---|---|
Downloads: | Tarball | ZIP archive | SQL archive |
Timelines: | family | ancestors | descendants | both | day15 |
Files: | files | file ages | folders |
SHA3-256: |
722424adced3cc280da31d2b8a4cb72d |
User & Date: | joel on 2019-11-28 16:08:15 |
Other Links: | branch diff | manifest | tags |
Context
2019-11-28
| ||
17:03 | Much better... check-in: 6389c1 user: joel tags: day15 | |
16:08 | evolution check-in: 722424 user: joel tags: day15 | |
2019-11-27
| ||
19:07 | fix backwardity check-in: 96ef01 user: joel tags: day15 | |
Changes
Modified day15.rkt from [266d98] to [219676].
1 2 3 4 5 6 7 8 9 10 11 12 | #lang debug racket/base (require racket/match racket/function racket/list racket/vector racket/set threading) ;; Good ol’ positions. (struct posn (x y) #:transparent) | | | | > > | > > > > > > > | > > < > > > | > | | > > > > > > > > | > > < | < | | | | | 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 | #lang debug racket/base (require racket/match racket/function racket/list racket/vector racket/set threading) ;; 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. ;; 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) ;; “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 ;; 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 (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) ;; 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 #f #f)) (define test-map (lines->grid '("#######" "#E..G.#" "#...#.#" "#.G.#G#" "#######"))) ;; Grids and Positions: put them together ;; 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 [start #f] [target #f]) (match-define (grid _ rows cols _) g) (grid (make-vector (* rows cols) #f) rows cols start target)) ;; (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 '()] |
︙ | ︙ | |||
114 115 116 117 118 119 120 | (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. | | | | | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 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 | (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)])) ;; “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)) (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) (cond [(not (empty? (set-intersect new-coords goal-pts))) result-grid] [(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 (define (shortest plst) (define shortest-distance (apply min (map (curry path-distance f) 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)) ;; ;; 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]))) (define (fighter-located-in? f lst) (not (empty? (filter (curry posn=? f) lst)))) (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))) (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)) |