blob: cd0402f5b42d2d0bd6937f0fcbd387992d5d12d4 (
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
|
(defstruct grid data dim0 dim1)
(defstruct point i j)
(defstruct pdir point dir)
(defun parse-grid (filespec)
(with-open-file (stream filespec)
(let ((lines (loop for line = (read-line stream nil)
while line
collect line)))
(make-grid :data (apply #'concatenate 'string lines)
:dim0 (length lines)
:dim1 (length (first lines))))))
(defun grid-character (grid i j)
(aref (grid-data grid) (+ (* i (grid-dim1 grid)) j)))
(defun grid-character-update (grid i j item)
(setf (aref (grid-data grid) (+ (* i (grid-dim1 grid)) j)) item))
(defun grid-point (grid item)
(let ((pos (position item (grid-data grid))))
(when pos
(multiple-value-bind (i j) (truncate pos (grid-dim1 grid))
(make-point :i i :j j)))))
(defun point-in-grid (point grid)
(and (and (>= (point-i point) 0) (< (point-i point) (grid-dim0 grid)))
(and (>= (point-j point) 0) (< (point-j point) (grid-dim1 grid)))))
(defun next-pdir (grid pdir)
(let* ((i (point-i (pdir-point pdir)))
(j (point-j (pdir-point pdir)))
(dir (pdir-dir pdir))
(next-point (cond ((= dir 0) (make-point :i (1- i) :j j)) ; up
((= dir 1) (make-point :i i :j (1+ j))) ; right
((= dir 2) (make-point :i (1+ i) :j j)) ; down
((= dir 3) (make-point :i i :j (1- j))))) ; left
(i (point-i next-point))
(j (point-j next-point)))
(when (point-in-grid next-point grid)
(let* ((next-char (grid-character grid i j))
(next-dir (cond ((equal next-char #\S) dir)
((= dir 0) (cond ((equal next-char #\7) 3)
((equal next-char #\F) 1)
((equal next-char #\|) dir)))
((= dir 1) (cond ((equal next-char #\7) 2)
((equal next-char #\J) 0)
((equal next-char #\-) dir)))
((= dir 2) (cond ((equal next-char #\L) 1)
((equal next-char #\J) 3)
((equal next-char #\|) dir)))
((= dir 3) (cond ((equal next-char #\L) 0)
((equal next-char #\F) 2)
((equal next-char #\-) dir))))))
(when next-dir
(make-pdir :point next-point :dir next-dir))))))
(defun grid-loop (grid start pdir &optional (count 0) visited)
(if (and (equalp start (pdir-point pdir)) (/= count 0))
visited
(let* ((visited (cons pdir visited))
(pdir (next-pdir grid pdir)))
(when pdir
;; Updating the grid for a quick visited check
(let* ((i (point-i (pdir-point pdir)))
(j (point-j (pdir-point pdir)))
(c (grid-character grid i j)))
(unless (equal c #\S)
(grid-character-update grid i j #\.)))
(grid-loop grid start pdir (1+ count) visited)))))
(defun solve1 (filespec)
(let* ((grid (parse-grid filespec))
(start (grid-point grid #\S))
(positions (or (grid-loop grid start (make-pdir :point start :dir 0))
(grid-loop grid start (make-pdir :point start :dir 1))
(grid-loop grid start (make-pdir :point start :dir 2))
(grid-loop grid start (make-pdir :point start :dir 3)))))
(ash (length positions) -1)))
(defun solve2 (filespec)
(let* ((grid (parse-grid filespec))
(start (grid-point grid #\S))
(positions (or (grid-loop grid start (make-pdir :point start :dir 0))
(grid-loop grid start (make-pdir :point start :dir 1))
(grid-loop grid start (make-pdir :point start :dir 2))
(grid-loop grid start (make-pdir :point start :dir 3)))))
(let* ((area (loop for cur in (append (cdr positions) (list (car positions)))
for prv in positions
as curi = (point-i (pdir-point cur))
as curj = (point-j (pdir-point cur))
as prvi = (point-i (pdir-point prv))
as prvj = (point-j (pdir-point prv))
sum (- (* prvi curj) (* prvj curi))))
(iarea (- (abs area) (length positions))))
(1+ (ash iarea -1)))))
(print (solve1 "data/10/example1.txt")) ;; 4
(print (solve1 "data/10/example2.txt")) ;; 8
(print (solve1 "data/10/input.txt")) ;; 6690
(print (solve2 "data/10/example3.txt")) ;; 4
(print (solve2 "data/10/example4.txt")) ;; 8
(print (solve2 "data/10/example5.txt")) ;; 10
(print (solve2 "data/10/input.txt")) ;; 525
|
