blob: 431158a22f19fd3217da7b2a48097d67afc66bd3 (
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
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
|
(ql:quickload '(fiveam uiop arrows))
(defun parse-instructions (str &optional (start 0))
(multiple-value-bind (action str-pos)
(case (aref str start)
(#\R 'right)
(#\L 'left)
(t (parse-integer str :start start :junk-allowed t)))
(let ((next (or str-pos (1+ start))))
(if (= next (length str))
(list action)
(cons action (parse-instructions str next))))))
(defun create-field (filename)
(let* ((data (uiop:read-file-lines filename))
(map (butlast data 2))
(instructions (car (last data)))
(rows (length map))
(columns (reduce (lambda (a r) (max a (length r))) map :initial-value 0))
(field (make-array (list rows columns) :initial-element nil)))
(loop for row in map
for i from 0
do (loop for entry across row
for j from 0
do (setf (aref field i j)
(ecase entry
(#\. 'free)
(#\# 'wall)
(#\Space nil)))))
(values field (parse-instructions instructions))))
(defun get-start (field)
(loop for i from 0
until (aref field 0 i)
finally (return i)))
(defstruct state
x-pos y-pos direction)
(defun advance (field state)
(destructuring-bind (height width) (array-dimensions field)
(with-slots (direction x-pos y-pos) state
(destructuring-bind (new-x new-y)
(ecase direction
(north (list x-pos (mod (1- y-pos) height)))
(south (list x-pos (mod (1+ y-pos) height)))
(east (list (mod (1+ x-pos) width) y-pos))
(west (list (mod (1- x-pos) width) y-pos)))
(let ((new-state (make-state :x-pos new-x :y-pos new-y :direction direction)))
(if (aref field new-y new-x)
new-state
(advance field new-state)))))))
(defconstant +directions+ #(north east south west))
(defun new-direction (current-direction turn)
(svref +directions+
(mod
(+
(ecase turn
(left -1)
(right 1))
(position current-direction +directions+))
4)))
(defun walk (field state steps)
(if (zerop steps)
state
(let ((new-state (advance field state)))
(with-slots (x-pos y-pos) new-state
(ecase (aref field y-pos x-pos)
(free (walk field new-state (1- steps)))
(wall state))))))
(fiveam:test preparation
(fiveam:is (eq 'south (new-direction 'east 'right)))
(fiveam:is (eq 'west (new-direction 'north 'left)))
(fiveam:is (equal
(parse-instructions "10R5L5R10L4R5L5" )
'(10 RIGHT 5 LEFT 5 RIGHT 10 LEFT 4 RIGHT 5 LEFT 5))))
(defun decode-state (state)
(with-slots (x-pos y-pos direction) state
(+ (* 1000 (1+ y-pos))
(* 4 (1+ x-pos))
(ecase direction
(east 0)
(south 1)
(west 2)
(north 3)))))
(defun solver (filename)
(multiple-value-bind (field instructions) (create-field filename)
(let ((state (make-state :x-pos (get-start field) :y-pos 0 :direction 'east)))
(dolist (move instructions)
(if (numberp move)
(setf state (walk field state move))
(setf (state-direction state) (new-direction (state-direction state) move))))
(decode-state state))))
(fiveam:test solutions
(fiveam:is (= 6032 (solver "eg-in")))
(fiveam:is (= 159034 (solver "input"))))
|
