commit - c3dffd28b9750ff8439ddddc5b5fece451000406
commit + 1b302a53c5470abd327425fc42f12f543436a7e9
blob - /dev/null
blob + 32ebc415f27afb2e722dd23aa0935810a2f2ebe2 (mode 644)
--- /dev/null
+++ input/21.txt
@@ -0,0 +1,131 @@
+...................................................................................................................................
+.#.........#....#.....#...............#.................#..#...........#..........................#........#.......#..#.........#..
+......##.#.....#......#....##....#......................#.#............#.........#......#.....................#................#...
+....##.....##...........#.##......#.#....##.........#...................#......#.#....#...#..........#.........#........#......#...
+......#..................##..#..........#..#.......#..#..#......................#.................#......#..#......#........#..#...
+....#.........#..#..#.#......#.#.....#.#..#...........#.....................#......#......#........#....##...................#.....
+..#......#..#........#.#.#.....#.......#......#...#.............#...............#...................#.........#....#.#...........#.
+............#..................#...................#...........#..........................#............#.#.....#................#..
+..#......#.....#..........#.........#............#.#.........#.....................#......#.................................##.....
+...#.............................#.......#....................#....#.........................##........#...#................#......
+.........#.......#...#............#......#............................................#.....#..........#...#......#......#.........
+.....#.......#.................................................#..#.................#........#....##...............................
+....................#.#........#..............#..............#............................#................#.......#..#.........#..
+..........#.....#......#...........................................#...............#..##.....#.....#.#..............#..............
+.#..............#...#..........#.............................#..#..#....#............#....................#......................#.
+...###..............#.#.........#........................#...#..........................###...#.......#.#....................#.#...
+......#...............#.#..#.........................#......................#........#.....#......#.................#......#.......
+.............#................#............................#......#......#............#.....#....#....................#......##....
+........................##.#...##..........#...........#.#...##........#...#...........#............##...#....................#..#.
+.....#........#....#..#.................##................#....#....#.....#.................#.......#.#............................
+...........#......................#.................#..#.#.....##...#.#....#..#...............#...#.....#...#..#..##......#.#....#.
+...#...................#........................#......#................#..#.........................#..........#..................
+........##..#.#................#..#.......................#.....#...........................#........#....#........................
+...#............#.....#..........#.............##........#..#...#...........................#........#.##.....#..............#.....
+..#.#.........#.......#.....#........#.........#.#...#.....#...........#..........#.............#...............###...#............
+.........##........#...#....................#...#..#......#...........................#.............................#......#.......
+.........#....#...........##................#...........##...#..#..#.............#................#.........................#....#.
+.....#.....#...#.........#.......................#........#...#....#...#.........#.....#...............#...#.............#.........
+..#....#..##.......#...#.........#........#......#.................#...#.......................................#......#............
+.....................#....#..........................#..#...#......##....#.........#..#..............#..................#..........
+.............#...##..##..............................#..#..#......#.........................................#..##...#..............
+.......#.....#.........#...........................#........#...........#...........##...........................#.......#.........
+..................#.#...................#......#..............#..............#.....#..#.#...................#.#...#..........#.....
+.......................#...#.............#....#.##.###....##..........#......#..#.............#.........#......#..........#........
+.#............#...........#..........#...#....#....#........................................##.........#..#........#.........#.....
+....#...............................#......##............##.......#..............#......#....##...................#...#....#.......
+.....#....#...##....#.#.....................#......#............................##.......#......#................#...............#.
+..........#.#..#..#...........................#........#......#.................#...........................#..#......#...#........
+...#.....#......................#...#...............#.##........#.###..........##..................#.........#.....................
+..#..........#.......#.............#.........#....#...............#...#..#....#....#.#................................#.#...#......
+.......#.......##....................#.##.......#...#.............#.............#.#...#......#..#...............#....#.............
+..........#...................................#.......................##...#..............#.........#.....................#........
+............##..#.........................#................................#...#..#...#..........#...#................#..#.........
+..#.......##.#........................#..#....#....#..#.#.#........#...#........#................#.....#......................#.#..
+..#...#.#....................#.......#.......#.#.##..#.....#..........#..........#.............#......#.#.........#................
+....#....#.....#...........#.#.....#......#..................#..........#.......#................#................##...............
+.#......#.................#...#..##.......#..#..........#...............#..........#....#.#...#......#.........................#...
+..#.#.#...#...........#....#................##.............#..#..............#...#....#...##....#.........................#........
+..#.....#...#..............#.......#..#...........................#...........#..........#..........#...#..............#......#.#..
+..#...................#.........##............#....#..................#...............#..........#.......#.........................
+......................................#........................#...#.......................#.......#........................#......
+...#..#..#..........#.....#...........................................#.......#.............#......#.......#....#.........#........
+..##.........................#.....#.................#..................##...##.....#.......#.........#...#.....#..............#...
+..#.............#...##.#......................#....#.........##......#...........#..............#..#........#.....#.............##.
+.....................#.#......................#..........#...##...........#............#.....#....................#..............#.
+................#...#.......#............#.....#..#...##.#...#....#...#......#.#........#..........##........#.#....#..............
+.............#...........#..............#..#.....#.........#...................................#.#.................................
+.#..................#....#..........#.#..#........#.......................#..#.......#..................#.#.....................#..
+................#.......#............................#............#..#.................#.#...#.....................................
+............#.#............#........#.##........###..#........###......#.........................##.#.......#.......##.............
+............#.#.......#.......#..##....#....................#.......................................#.....#.........#...#..........
+...........##.....#..#...................#......................#.................#......#..#.......#...#...##.....................
+......................................#...#....................#...#.................#........#......#.....#...#....##.............
+.......................................#......................................#..............#......#........#.......#.............
+.............###.............##......#........#..#.#....#...###.#..............#..........#.........#...........#..#......#........
+.................................................................S.................................................................
+......##...#.....#........#.......#.#....#....#....#................#..#..#...................#.....#................#.#...#.......
+...............................#.....................#...##.......#........#.#.........#......................#....#...............
+........................#.......#.........#..........#............#....#...##.........#...#.#............................#.........
+........#..#..............##...........#....#.##..###.....................................#.##.....#................#..#...........
+............#...#.............##..............................#.#........#...#...............#............#.##.....##...#..........
+.................#......................................#..#..................#.....#............#.......#.......................#.
+..#...................#.................#.................#..#....#...#..#...........#.#.#...#..#.........#........#...............
+....#.........#....#...............##...............#.........#......................#...........#.............#...................
+..............##.............#.....#..................#.....#.#.....#................#...#..........#.........#......#.............
+..................#...#...###.........###..............#.............#................#...........#...#..#..#.....#................
+.#..#...............#..#...........................##...#...#...#........#..........##...#....#........#...........................
+...............................#............#....#..............#..#.....#............#.......#..#........................#........
+.....##............#.............##...#..#....#.......#............#..........#.................#...........#.................#....
+.....#............................#.....#...##.............#......#.....#..#.....##.......................#........................
+..#.....#..........................#.#............#........#.#.......#...#...#.....#......................##................#...#..
+.......#..............................#..................#.........................................#...#..................#.#..#...
+......#....#.............................#...#.......#.....#......................#.#..........#..............................#....
+.#..........................#........................#......#.........#......................#...#........#...........#...#........
+.............#............#................#.......................................#..###..#.....#.....#.#...............#.......#.
+.#........#..............................#........#...........#...........................#...........#...................#........
+.......##.#...##...............#.#...........##.......#.#..............................#.....#.......#...........#.................
+....#...###.#...............................#...........................#..................#..#.#...#............##.#..#....#......
+....##....##...#..#...................##..#...#.#.......#...#.......................#......##....................#....#........#...
+..............................#....#...#...#..................#.....#...................#....#.........................##...#......
+...........#.#....#................................#.....#..#.................#..##......#..#......#.........#........#...#......#.
+............................................#.#..........#...#.#....#.................#......#.#.#.#.........#........#......#.....
+....#..............................##........#............#......................#.#..........#..........................#.....#...
+.............#...##..#.............#........#.....#...#...............#..............#...........##..............................#.
+................#...............................#.#..................#...........#.............##........#.......#....#..###.......
+.#..........##.........................................#......#.#..#............................#...............##.#...#...........
+.##.................##...................#.....................#..............#.........#........................#.....#...#...#...
+.....................................................#..........#.#...........#.#..........#...............#.....#.......#...#.....
+.#.............#.....##......#........#....#......................#.#.....#......#.......#......................#.....#...#......#.
+........#...##.....#........#.........#.#..#............#...#.......................................#............#.................
+......##..............#...###...........#............#.....................#............#.#...........................#............
+..##.#......#......#....#......#.................#................#....................##..............#.......#.#.#....#..........
+..#.......#.#.....#.##.....#................#.#.........#.....#.......#............................#..............#................
+...#.#....#..#...........#......................................#.....#..................................#.......#...#..#..#.......
+...#....#..#........#.......#...............#.........#..#..#.##.....#................#............................................
+...........#...#.#.............##..............#.#.......#......#.........#.#......#..............#...................#............
+...#.....#..##.....#..#.........#................#...#..#............#..##.#....#..............#..#...............#................
+...#.#........##.........#..........#...........................#......#...#.......##...................#........#.#..##.........#.
+.#.....#....................##.#................#..#.##................#........#..................................#..#.#...#......
+.#..........#.....#....#..........#...................#........##............#.................#............#.....##...........#...
+...........#...#.........#.#.......##..............#.........#..........##......#................#............##..##...............
+.......#...#...#.....#....#.............##..............................................##...#................................#....
+.#....##.....#...........#..........#..#............#.....##.......##...............................#.#...........#....#.........#.
+.......#...#...............#........###....#..............................#............#..#...................#...#.........#......
+......#...#.....#..........#....####.......#.#..................................................###.......#......#..#............#.
+.#..#.......#..#.#....#....##......#........#.........##....................#......................................................
+...........#.#.................................................#..........#............##..#..............#......#...##....#...#...
+.#....................#......#.................................#.......................................#...#.......................
+...................#.....................#...............#.....#.......................#...........#..#............#...............
+...............#..#..#....#......#......#.........#............##..................................#.#..........##............#....
+......#.......#.......#...#.............#.......#..#........#......#...#...........#.......#....#..............#..#..#.............
+.....#......#.......##.#......................................#......##........#...#.............#...#..#......#............#......
+.#........#..#.............#..#....###.............#...............#..........#...#......#......#...#....#.#.........#..........#..
+........#....#....#.....#....#..#.................#.............................#............................#............#........
+.....#...............#...........#.##...........................................#.#......#.....#.#..#....#..............##...#.....
+..#..#....#..................................#.......#.#..........#........................#.........#.....................#.##....
+...#....#.............#...#............#..........#.#..#...........................#.............#...#.......#................#.#..
+..............#.....#......#.......#..........#....##..#................#.....#.....##.....#....#...........#......#...............
+......#..#........................#.........#.......##....#.............................................##.....##.......#......#...
+.....#..#.....#........................................#..............#............#...#...........................#........#......
+...................................................................................................................................
blob - /dev/null
blob + 0081dd0baadc0bd3e0aaed7bc4f5a62d9d74e9e4 (mode 644)
--- /dev/null
+++ src/day-21.lisp
@@ -0,0 +1,46 @@
+(defpackage #:aoc/day-21
+  (:use #:cl #:aoc/utils)
+  (:export #:day-21))
+(in-package #:aoc/day-21)
+
+(defun find-start-position (map)
+  (loop for y from 0 below (input-map-height map)
+        do (loop for x from 0 below (input-map-width map)
+                 for point = (cons x y)
+                 when (char= (map-cell map point) #\S)
+                   do (return-from find-start-position point))))
+
+(defun neighbouring-gardens (map width height position)
+  (loop for nd in (let (nds)
+                    (when (> (point-x position) 0)
+                      (push (cons -1 0) nds))
+                    (when (< (point-x position) (1- width))
+                      (push (cons 1 0) nds))
+                    (when (> (point-y position) 0)
+                      (push (cons 0 -1) nds))
+                    (when (< (point-y position) (1- height))
+                      (push (cons 0 1) nds))
+                    nds)
+        for n = (point+ position nd)
+        for cell = (map-cell map n)
+        when (or (char= cell #\.)
+                 (char= cell #\S))
+          collect n))
+
+(defun step-through-garden (map position steps)
+  (loop with todo = (list position)
+        with width = (input-map-width map)
+        with height = (input-map-height map)
+        for remaining-steps downfrom steps
+        when (= remaining-steps 0)
+          do (return (length todo))
+        do (setf todo
+                 (remove-duplicates
+                  (loop for position in todo
+                        nconc (neighbouring-gardens map width height position))
+                  :test #'equal))))
+
+(defun day-21 (input &optional (steps 64))
+  (let* ((map (make-map input))
+         (start-pos (find-start-position map)))
+    (step-through-garden map start-pos steps)))
blob - /dev/null
blob + d84a2a11ea8404d76e94160b11a86f0a9a8bc999 (mode 644)
--- /dev/null
+++ t/day-21.lisp
@@ -0,0 +1,19 @@
+(defpackage #:aoc-test/day-21
+  (:use #:cl #:lisp-unit2))
+(in-package #:aoc-test/day-21)
+
+(define-test test-day-21
+    ()
+  (multiple-value-bind (task-1)
+      (aoc:run-day 21 "...........
+.....###.#.
+.###.##..#.
+..#.#...#..
+....#.#....
+.##..S####.
+.##..#...#.
+.......##..
+.##.#.####.
+.##..##.##.
+..........." 6)
+    (assert= 16 task-1)))