diff options
| -rw-r--r-- | data/16/example.txt | 10 | ||||
| -rw-r--r-- | data/16/input.txt | 110 | ||||
| -rw-r--r-- | day16.lisp | 112 |
3 files changed, 232 insertions, 0 deletions
diff --git a/data/16/example.txt b/data/16/example.txt new file mode 100644 index 0000000..d6805ce --- /dev/null +++ b/data/16/example.txt @@ -0,0 +1,10 @@ +.|...\.... +|.-.\..... +.....|-... +........|. +.......... +.........\ +..../.\\.. +.-.-/..|.. +.|....-|.\ +..//.|.... diff --git a/data/16/input.txt b/data/16/input.txt new file mode 100644 index 0000000..23cf91c --- /dev/null +++ b/data/16/input.txt @@ -0,0 +1,110 @@ +\..............................................................-......-.............-........\-............... +./.........................-..-............................../..........|..|.-\..|.|.../.................-.... +|......|...\./|....\............./-..........\|............./..../.....|....\.......................-....../.. +.......-.....\.........\../............-.-.................|....-\.....\..\......|./.......................... +................................./..-.................-\............/......|..../..|.....\|................... +.....|......../.....|...-.............../......\................................\........|.....\......./...... +............\............|..........\......\...../......................|.........................\........... +...........................\.......-..|..../.............\........//.................../..-............|...... +..................\......................./....-..../........./\.......|................./............/.\..... +.\......./..........\.......\./..--...|..............-..........\.\...../.../....../.-./........./....\....... +..../......./.........|...........................\....................|.............../|.../.../...\..\...../ +...-.\|\.....-............................-........................\...............\....-..................../ +........\....|.....-...-..|..\..-./..........|.............|..............................\................... +.....\......................................./...........-.........................-....................../... +....\...............................-...........\............\.........-|..-..|........../..-.....|.../......| +........\.......-./...-.../...................................-.......|........./............|.\.............. +............\...........-.....\..|.......................|.......|.............\......./...........|.......... +.|.....|...................-...|.................................../\....../..../..........|.............|./.. +...............|......./......................../......................./.....-.............../.............\. +...\..-/.........-........................-............................/\.\.......-..|..............-......... +...-........./......\..\..............-............/.............-......-.........|................/........-. +............\..\...|.........|..................../\........../..\.....................\............../....... +........\.................................../..../..................|........-................................ +...|.../............\-..-....\..|....|........-./.............................\............................... +......-.\.-......\......../.|..........\.|..../..\....................../..\/./...../--...................|... +.......\|............/...|...|.........../........../...........|........./................................... +\........\...........................-/.......................-............-..|......|..............\......... +......................../|............\.............../......|.-\..\.......|../...........-..............-.... +.............................\.....-..............|...........|/...../.....-..................../.....-..-/.-- +.|...........................-.........|....-/.-.....\.........../.........|......\..../.\.\...............|.. +...................\.........................\...................|..../...........-..............-............ +...............-.....-.......\.............|........../-.........../..........\.....|............|.../.....-.. +..........|.-...................................-............|../.............................|../............ +...|..........\.......\....\..........|........./.........-|-............|.................................... +./\..../.......|........|....|......../............/............/................................|............ +..........................\........................../........|.........................\\................-... +....../....|.../..\.-..|....././|-.....|........................................-.....................-....... +.\.-............./...|..../|........./|...........-\..|.................|.../......................./......... +.........|........../.........\.........../............../..............\....\..............-|................ +....-...../...\...........................\.-......|........\...-...|..............|......|.\.....-........... +...-.............................-\.........-..../.\..........-..../......--............................\..... +.................-........|..................-.|................|....-....\...|....../....\................... +...\.........\..........|................/..........|....\./..................../-............./.............. +/........\....-......-.-|...........|../........\.|.......|...........|.................-.............|....... +......../....../.......\...............\.......-....................../..................|.../.........\...... +.\....../.........|...................................|-.|../.../...........-.-.............\................- +/-..\/.......-........\../.....-..|..................\................|......./............................... +......../.................-..../.................-...-|.........|............../...........|.................. +..|......../.....\......................|.....|/...../.............-.|-...-...|......................-........ +......|........|.\.........\............-........-/......./.............../......./......................|...\ +....|...............\...../.............../......|......../............|/...|........./...../..........-.\.--. +..|.........|......|.............................|...........-....|...-.............../................/...... +.....................|........./............./........................................../.........|........... +.....\........................|../.....................-.......|.-........................../../......-....... +..........................-....../.......\.............................-....\................/................ +................................-...../.........//.........-...|../....\..................................-... +...........................-................|/|.||............................................\...\.....|..... +..|..........-................/...................-.......|..................................-...............\ +../....-.........-...............................................\.....\...........|-............./.......|... +......\...|......../........................./...........................................|.................... +.-..................../...-..|.-..\...../.........-............./..........\.................................. +....-....-...........-........-........|......................\................................./\....-....... +..........|...................................\.../....../...-......|../............|......|................\. +.-.|.|.|.........-........-....\.........|......../..-.........../............\......-\.......|.......|....... +........|......../.............|...\.\......../...-........\.......\......-........-......./.../.............. +..../..........-............/././.........|.-...........|.........../.........................\-....|......... +........\......................../................-................|..\........./...\.......\.\............... +.............\........|....\....../..........|..\................./...||......./|..\................\.....\... +./.|.................................../...|....................|...................|...../.\............../.. +.../....................\..........|.-...............................\.........|....|\./.../.\.\.............. +\|........./.\...-......\..............\..........|...........\.|\............/...........-................... +....................../..\...\..........................|-..........-\................\......./.-............. +................................/.....................|././......../............/.\...|....................... +.............................-./............|.............|.-.............../..........|.../................./ +...............-........................//........././............/...../...-......-\\........................ +-././.........../..-....|.......-......./..................-...........|......./......./....|................. +........../.............................\...-............|.............\..-........../......./.\.../.........\ +..................|\..........................|..........|....................|...\...........\............... +.....-.....\../....|.|....|.|........|.-..-........................../.........................-........-..... +.....\......\............./..............-.....|........................................\......|...\........|. +..|......../..................................\..........-.............\..............\......|.....-.......... +.\....................................|.|.././.-../-..............................|.|........\........./...... +....................-.../.../...../......\....|........./........-../...................|..................-.. +\...........|...\....-...-..\....................................-.|./..........................\............. +.........\..........\.................-...........-........-....-.-..................\.-........|.-....\...... +..........................................|........|..........................\......\......\.-.|...\../...\.. +..-..................\.\..-........................................\.........-..|...../......|................ +.../....../......\./.\|.../.-........-............-../...........-.......-.........\.|................-....... +..|\..../.|........................|........-/.........-..|......|..........-.....|.......\.../..-......-..... +............................................................../.................\..|...-./............|...../. +..\.|.....-............-/\.............|.............\...............|....../........../....-/..\../......\... +............................/....-.../...................|.....-........|.../....\........-.....-...|...|..... +../..../.............|..\...||......-..-...................-...........\...-.....\.....|.........||..//....... +............................/.....\..\....-................/..../........\....\.................-|............ +...-........-..../..........|.......-...|........|....-.......\...|....../...//...|...........\.......|-...... +......./.........|../.........../...\............\................/..|..\.\.....................\...|......... +....-.............../.|.../............\..........--...........................|........./......|............. +............./.................\............/......-................/|.............\./........\..|....\....... +............\.............|..|.|\....-...-|/|...\...........................-....../.......|.................. +./...../|...\........\|....-...............\\.........../........-../................................-........ +-......-.\...|...\..|.|..../.........-...........|...................-.|..............-../............../..... +..|..........|/......................................\.........|............./.................-..|-.......... +..\.......\................\...\....................\............................-......|......\....-.....-... +..||................................-...\.-.....|................./......|..............|.....\............... +..................-......../.....|..\.......--.../...../.\-.............-........................../.........\ +-.......\............./............/...|...-.../...........\.................|.....\....\.\....-..../..-...... +-............/.......\........................................................\..-.....................\...... +.../................................................../.........../....|.........\.....................-...... +...................|.......\......././................|..-......\....-.....-|...|.....-....................... +..........................-.......................-.....-......-............\.....\....\.-.................... diff --git a/day16.lisp b/day16.lisp new file mode 100644 index 0000000..5643690 --- /dev/null +++ b/day16.lisp @@ -0,0 +1,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 + + + |