#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
;; 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 (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)
;; 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.
;; 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) #\.))
;; 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))
(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))])))
;; Convenience:
(define (make-pathfinder world f)
(curry build-path world f))
;; Get only the shortest path(s) from a list of paths
(define (shortest plst)
(define shortest-distance (apply min (map path-distance plst)))
(define (among-shortest? pmap) (equal? shortest-distance (path-distance pmap)))
(filter among-shortest? plst))
;; 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)
(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 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)))