blob: 05c4c7442bcf587e8a4ae8829f7e6d25aaa6fd05 (
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
|
(ql:quickload '(fiveam))
(defpackage :day21
(:use :cl :fiveam))
(in-package :day21)
;;22:55
;;23:32
(defun find-start (field)
(destructuring-bind (rows cols)
(array-dimensions field)
(loop for row below rows do
(loop for col below cols do
(when (eq (aref field row col) #\S)
(return-from find-start (list row col)))))))
(defun solver1 (lines step-count)
(let* ((field (make-array (list (length lines) (length (car lines)))
:initial-contents lines))
pending
(end-positions (make-hash-table :test #'equal))
(visited (make-hash-table :test #'equal))
(start (find-start field)))
(destructuring-bind (rows cols)
(array-dimensions field)
(push (cons step-count start) pending)
(setf (gethash start visited) step-count)
(loop while pending
for (steps-left row col) = (pop pending)
;; an even number of steps left means it is possible
;; to go and return to the place in the steps available
;; Thus count to the solution.
when (evenp steps-left)
do (setf (gethash (list row col) end-positions) t)
unless (zerop steps-left)
do (loop
for (dr dc) in '((-1 0) (0 -1) (1 0) (0 1))
for nr = (+ row dr)
for nc = (+ col dc)
for new-pos = (list nr nc)
when (and (< (gethash new-pos visited -1) (1- steps-left))
(< -1 nr rows)
(< -1 nc cols)
(not (eq #\# (aref field nr nc))))
do (setf (gethash new-pos visited) (1- steps-left))
(push (cons (1- steps-left) new-pos) pending))))
(hash-table-count end-positions)))
(test solutions
(is (= 16 (solver1 (uiop:read-file-lines "eg-in") 6)))
(is (= 3574 (solver1 (uiop:read-file-lines "input") 64))))
|
