blob: e0320c39f65b27228e517fc05ea46bc44e4229f2 (
plain)
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
|
(ql:quickload '(fiveam uiop))
(defstruct land
elevation
neighbors)
(defun possible-directions (width height)
;; point on grid is p=x+y*width
(lambda (pos)
(let ((x (mod pos width))
(y (floor pos width)))
(delete nil
(list
(when (< -1 x (1- width)) (1+ pos)) ;; right move
(when (< -1 y (1- height)) (+ pos width)) ;; down move
(when (< 0 x width) (1- pos)) ;; left move
(when (< 0 y height) (- pos width))) ;; up move
:test #'eq))))
(defun elevation (chr)
(case chr
(#\S 0)
(#\E 27)
(t (- (char-code chr) 96))))
(defun land (input-file)
(let ((data (uiop:read-file-lines input-file)))
(make-land :elevation (map 'vector #'elevation (apply #'concatenate 'string data))
:neighbors (possible-directions (length (car data)) (length data)))))
(defun appropriate (place elevation land paths)
(and (not (gethash place paths)) ;; not visited
(>= elevation (aref (land-elevation land) place))))
(defun next-steps (place land paths)
(let ((elevation (aref (land-elevation land) place)))
(unless (= 27 elevation)
(loop :for option :in (funcall (land-neighbors land) place)
:when (appropriate option (1+ elevation) land paths)
:do (setf (gethash option paths) (cons option (gethash place paths)))
:and collect option))))
(defun shortest-path (starts land paths)
(let ((next (mapcan (lambda (place) (next-steps place land paths)) starts)))
(when next
(shortest-path next land paths))))
(defun solver (input-file start-p)
(let* ((land (land input-file))
(paths (make-hash-table :test #'eq))
(finish (position 27 (land-elevation land) :test #'eq))
(starts (loop for i from 0
for el across (land-elevation land)
when (funcall start-p el)
do (setf (gethash i paths) (list i))
and collect i)))
(shortest-path starts land paths)
(1- (length (gethash finish paths)))))
(fiveam:test solver
(fiveam:is (= 31 (solver "eg-in" (lambda (x) (= x 0)))))
(fiveam:is (= 29 (solver "eg-in" (lambda (x) (<= x 1)))))
(fiveam:is (= 361 (solver "input" (lambda (x) (= x 0)))))
(fiveam:is (= 354 (solver "input" (lambda (x) (<= x 1))))))
(fiveam:run-all-tests)
|
