🎄⌨️ Advent of Code 2018

Changes On Branch day15

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))