🎄⌨️ Advent of Code 2018

Changes On Branch 722424adced3cc28

Changes In Branch day15 Through [722424] Excluding Merge-Ins

This is equivalent to a diff from 80485b to 722424

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
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.rkt version [219676].



















































































































































































































































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
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
#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 '()]
                     #: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)]))

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