blob: 5643690b11d6068f991267b28c2556b8732e859e (
plain) (
blame)
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
106
107
108
109
110
111
112
|
(defun read-map (filespec)
(with-open-file (stream filespec)
(let ((lines (loop for line = (read-line stream nil) while line collect line)))
(make-array (list (length lines) (length (first lines))) :initial-contents lines))))
(defun next-pos-right (pos map)
(let* ((i (car pos))
(j (cdr pos))
(n (array-dimension map 0))
(m (array-dimension map 1))
(c (aref map i j)))
(cond
((equal c #\/) (unless (= i 0) (list (cons (cons (1- i) j) #\U))))
((equal c #\\) (unless (= (1+ i) n) (list (cons (cons (1+ i) j) #\D))))
((equal c #\|) (cond ((and (> i 0) (< (1+ i) n))
(list (cons (cons (1- i) j) #\U)
(cons (cons (1+ i) j) #\D)))
((> i 0) (list (cons (cons (1- i) j) #\U)))
((< (1+ i) n) (list (cons (cons (1+ i) j) #\D)))))
(t (unless (= (1+ j) m) (list (cons (cons i (1+ j)) #\R)))))))
;; Could reduce reptition from above by merging functions
(defun next-pos-left (pos map)
(let* ((i (car pos))
(j (cdr pos))
(n (array-dimension map 0))
(c (aref map i j)))
(cond
((equal c #\\) (unless (= i 0) (list (cons (cons (1- i) j) #\U))))
((equal c #\/) (unless (= (1+ i) n) (list (cons (cons (1+ i) j) #\D))))
((equal c #\|) (cond ((and (> i 0) (< (1+ i) n))
(list (cons (cons (1- i) j) #\U)
(cons (cons (1+ i) j) #\D)))
((> i 0) (list (cons (cons (1- i) j) #\U)))
((< (1+ i) n) (list (cons (cons (1+ i) j) #\D)))))
(t (unless (= j 0) (list (cons (cons i (1- j)) #\L)))))))
(defun next-pos-up (pos map)
(let* ((i (car pos))
(j (cdr pos))
(m (array-dimension map 1))
(c (aref map i j)))
(cond
((equal c #\/) (unless (= (1+ j) m) (list (cons (cons i (1+ j)) #\R))))
((equal c #\\) (unless (= j 0) (list (cons (cons i (1- j)) #\L))))
((equal c #\-) (cond ((and (> j 0) (< (1+ j) m))
(list (cons (cons i (1- j)) #\L)
(cons (cons i (1+ j)) #\R)))
((> j 0) (list (cons (cons i (1- j)) #\L)))
((< (1+ j) m) (list (cons (cons i (1+ j)) #\R)))))
(t (unless (= i 0) (list (cons (cons (1- i) j) #\U)))))))
(defun next-pos-down (pos map)
(let* ((i (car pos))
(j (cdr pos))
(n (array-dimension map 0))
(m (array-dimension map 1))
(c (aref map i j)))
(cond
((equal c #\\) (unless (= (1+ j) m) (list (cons (cons i (1+ j)) #\R))))
((equal c #\/) (unless (= j 0) (list (cons (cons i (1- j)) #\L))))
((equal c #\-) (cond ((and (> j 0) (< (1+ j) m))
(list (cons (cons i (1- j)) #\L)
(cons (cons i (1+ j)) #\R)))
((> j 0) (list (cons (cons i (1- j)) #\L)))
((< (1+ j) m) (list (cons (cons i (1+ j)) #\R)))))
(t (unless (= (1+ i) n) (list (cons (cons (1+ i) j) #\D)))))))
(defun next-pos (pos dir map)
(cond ((equal dir #\R) (next-pos-right pos map))
((equal dir #\L) (next-pos-left pos map))
((equal dir #\U) (next-pos-up pos map))
((equal dir #\D) (next-pos-down pos map))))
(defun solve (map &optional (start '((0 . 0) . #\R)))
(let ((visited (make-hash-table :test #'equal))
(visited2 (make-hash-table :test #'equal)))
(loop for ray = start then (car stack)
for stack = () then (cdr stack)
while ray
as pos = (car ray)
as dir = (cdr ray)
sum (if (gethash pos visited) 0 (setf (gethash pos visited) 1))
do (unless (gethash ray visited2)
(setf (gethash ray visited2) 1)
(loop for r in (next-pos pos dir map) do (setf stack (cons r stack)))))))
(defun solve1 (filespec)
(solve (read-map filespec)))
;; Could possibly be optimized by merging sets of visited tiles from
;; each position/direction. But this is fast enough
(defun solve2 (filespec)
(let* ((map (read-map filespec))
(n (array-dimension map 0))
(m (array-dimension map 1)))
(max
(loop for i below n
maximize (max (solve map (cons (cons i 0) #\R))
(solve map (cons (cons i (1- m)) #\L))))
(loop for j below m
maximize (max (solve map (cons (cons 0 j) #\D))
(solve map (cons (cons (1- n) j) #\U)))))))
(print (solve1 "data/16/example.txt")) ;; 46
(print (solve1 "data/16/input.txt")) ;; 7046
(print (solve2 "data/16/example.txt")) ;; 51
(print (solve2 "data/16/input.txt")) ;; 7313
|
