🎄⌨️ Advent of Code 2018

#lang debug racket/base
#lang racket/base

(require racket/match
         racket/function
         racket/list
         racket/vector
         racket/set
         threading)

;; PRIMITIVES AND CONSTANTS ----------------------------------------------------

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

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

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

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

;; This will come in handy later.
;; WORKING WITH GRIDS ----------------------------------------------------------
;; 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 (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
        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))
(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 '()]

        [(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
;; Working with PATHS ----------------------------------------------------------
;; 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))
;; 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))
  (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)
                           (filter not-yet-checked? _)))
    (define maybe-first-steps (set-intersect new-coords goal-pts))
    (cond
      [(not (empty? (set-intersect new-coords goal-pts))) result-grid]
      [(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)
      [else (loop new-coords (+ 1 i))])))
       (loop new-coords (+ 1 i))])))

;; What is the distance of the path represented by a path-map?
(define (path-distance pmap)
;; Convenience: 
(define (make-pathfinder world f)
  (~>> (neighbor-coords pmap (grid-start pmap))
       (filter-map (curry grid-ref pmap)) ; Weeds out #f values
  (curry build-path world f))
       (apply min)))

;; Get only the shortest path(s) from a list of path maps
;; Get only the shortest path(s) from a list of paths
(define (shortest plst)
  (define shortest-distance (apply min (map (curry path-distance f) plst)))
  (define shortest-distance (apply min (map path-distance 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))

;; 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 lst)
  (not (empty? (filter (curry posn=? f) lst))))
(define (fighter-located-in? f posns)
  (not (empty? (filter (curry posn=? f) posns))))

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

;; Here’s a proof of concept.
;; As you can see, after all that work it is trivially easy to tie everything together.
(module+ test
  (require rackunit)
(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))

  (define test-map
    (lines→grid
     '("#######"
       "#E..G.#"
       "#...#.#"
       "#.G.#G#"
       "#######")))
  (define fs (grid->fighters test-map))
  (define f (first fs))
  (define es (enemies-of f fs))
  
  ;; Work through the algorithm specified in the problem description to find the next move
  ;; for the elf at 1,1 (skipping the test for adjacent enemies):
  (define possible-targets (free-neighbors-of test-map es))
  (define possible-paths (filter-map (make-pathfinder test-map f) possible-targets))
  (define shortest-paths (shortest possible-paths))
  (define selected-path (first (reading-order shortest-paths)))
  (define next-step (first (reading-order (path-first-steps selected-path))))

  ;; Ta-da
  (check-equal? next-step (posn 2 1)))