commit 1b302a53c5470abd327425fc42f12f543436a7e9 parent c3dffd28b9750ff8439ddddc5b5fece451000406 Author: Lukas Henkel <lh@entf.net> Date: Thu, 21 Dec 2023 11:31:54 +0100 Day 21 task 1 Diffstat:
| A | input/21.txt | | | 131 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | src/day-21.lisp | | | 46 | ++++++++++++++++++++++++++++++++++++++++++++++ |
| A | t/day-21.lisp | | | 19 | +++++++++++++++++++ |
3 files changed, 196 insertions(+), 0 deletions(-)
diff --git a/input/21.txt b/input/21.txt @@ -0,0 +1,131 @@ +................................................................................................................................... +.#.........#....#.....#...............#.................#..#...........#..........................#........#.......#..#.........#.. +......##.#.....#......#....##....#......................#.#............#.........#......#.....................#................#... +....##.....##...........#.##......#.#....##.........#...................#......#.#....#...#..........#.........#........#......#... +......#..................##..#..........#..#.......#..#..#......................#.................#......#..#......#........#..#... +....#.........#..#..#.#......#.#.....#.#..#...........#.....................#......#......#........#....##...................#..... +..#......#..#........#.#.#.....#.......#......#...#.............#...............#...................#.........#....#.#...........#. +............#..................#...................#...........#..........................#............#.#.....#................#.. +..#......#.....#..........#.........#............#.#.........#.....................#......#.................................##..... +...#.............................#.......#....................#....#.........................##........#...#................#...... +.........#.......#...#............#......#............................................#.....#..........#...#......#......#......... +.....#.......#.................................................#..#.................#........#....##............................... +....................#.#........#..............#..............#............................#................#.......#..#.........#.. +..........#.....#......#...........................................#...............#..##.....#.....#.#..............#.............. +.#..............#...#..........#.............................#..#..#....#............#....................#......................#. +...###..............#.#.........#........................#...#..........................###...#.......#.#....................#.#... +......#...............#.#..#.........................#......................#........#.....#......#.................#......#....... +.............#................#............................#......#......#............#.....#....#....................#......##.... +........................##.#...##..........#...........#.#...##........#...#...........#............##...#....................#..#. +.....#........#....#..#.................##................#....#....#.....#.................#.......#.#............................ +...........#......................#.................#..#.#.....##...#.#....#..#...............#...#.....#...#..#..##......#.#....#. +...#...................#........................#......#................#..#.........................#..........#.................. +........##..#.#................#..#.......................#.....#...........................#........#....#........................ +...#............#.....#..........#.............##........#..#...#...........................#........#.##.....#..............#..... +..#.#.........#.......#.....#........#.........#.#...#.....#...........#..........#.............#...............###...#............ +.........##........#...#....................#...#..#......#...........................#.............................#......#....... +.........#....#...........##................#...........##...#..#..#.............#................#.........................#....#. +.....#.....#...#.........#.......................#........#...#....#...#.........#.....#...............#...#.............#......... +..#....#..##.......#...#.........#........#......#.................#...#.......................................#......#............ +.....................#....#..........................#..#...#......##....#.........#..#..............#..................#.......... +.............#...##..##..............................#..#..#......#.........................................#..##...#.............. +.......#.....#.........#...........................#........#...........#...........##...........................#.......#......... +..................#.#...................#......#..............#..............#.....#..#.#...................#.#...#..........#..... +.......................#...#.............#....#.##.###....##..........#......#..#.............#.........#......#..........#........ +.#............#...........#..........#...#....#....#........................................##.........#..#........#.........#..... +....#...............................#......##............##.......#..............#......#....##...................#...#....#....... +.....#....#...##....#.#.....................#......#............................##.......#......#................#...............#. +..........#.#..#..#...........................#........#......#.................#...........................#..#......#...#........ +...#.....#......................#...#...............#.##........#.###..........##..................#.........#..................... +..#..........#.......#.............#.........#....#...............#...#..#....#....#.#................................#.#...#...... +.......#.......##....................#.##.......#...#.............#.............#.#...#......#..#...............#....#............. +..........#...................................#.......................##...#..............#.........#.....................#........ +............##..#.........................#................................#...#..#...#..........#...#................#..#......... +..#.......##.#........................#..#....#....#..#.#.#........#...#........#................#.....#......................#.#.. +..#...#.#....................#.......#.......#.#.##..#.....#..........#..........#.............#......#.#.........#................ +....#....#.....#...........#.#.....#......#..................#..........#.......#................#................##............... +.#......#.................#...#..##.......#..#..........#...............#..........#....#.#...#......#.........................#... +..#.#.#...#...........#....#................##.............#..#..............#...#....#...##....#.........................#........ +..#.....#...#..............#.......#..#...........................#...........#..........#..........#...#..............#......#.#.. +..#...................#.........##............#....#..................#...............#..........#.......#......................... +......................................#........................#...#.......................#.......#........................#...... +...#..#..#..........#.....#...........................................#.......#.............#......#.......#....#.........#........ +..##.........................#.....#.................#..................##...##.....#.......#.........#...#.....#..............#... +..#.............#...##.#......................#....#.........##......#...........#..............#..#........#.....#.............##. +.....................#.#......................#..........#...##...........#............#.....#....................#..............#. +................#...#.......#............#.....#..#...##.#...#....#...#......#.#........#..........##........#.#....#.............. +.............#...........#..............#..#.....#.........#...................................#.#................................. +.#..................#....#..........#.#..#........#.......................#..#.......#..................#.#.....................#.. +................#.......#............................#............#..#.................#.#...#..................................... +............#.#............#........#.##........###..#........###......#.........................##.#.......#.......##............. +............#.#.......#.......#..##....#....................#.......................................#.....#.........#...#.......... +...........##.....#..#...................#......................#.................#......#..#.......#...#...##..................... +......................................#...#....................#...#.................#........#......#.....#...#....##............. +.......................................#......................................#..............#......#........#.......#............. +.............###.............##......#........#..#.#....#...###.#..............#..........#.........#...........#..#......#........ +.................................................................S................................................................. +......##...#.....#........#.......#.#....#....#....#................#..#..#...................#.....#................#.#...#....... +...............................#.....................#...##.......#........#.#.........#......................#....#............... +........................#.......#.........#..........#............#....#...##.........#...#.#............................#......... +........#..#..............##...........#....#.##..###.....................................#.##.....#................#..#........... +............#...#.............##..............................#.#........#...#...............#............#.##.....##...#.......... +.................#......................................#..#..................#.....#............#.......#.......................#. +..#...................#.................#.................#..#....#...#..#...........#.#.#...#..#.........#........#............... +....#.........#....#...............##...............#.........#......................#...........#.............#................... +..............##.............#.....#..................#.....#.#.....#................#...#..........#.........#......#............. +..................#...#...###.........###..............#.............#................#...........#...#..#..#.....#................ +.#..#...............#..#...........................##...#...#...#........#..........##...#....#........#........................... +...............................#............#....#..............#..#.....#............#.......#..#........................#........ +.....##............#.............##...#..#....#.......#............#..........#.................#...........#.................#.... +.....#............................#.....#...##.............#......#.....#..#.....##.......................#........................ +..#.....#..........................#.#............#........#.#.......#...#...#.....#......................##................#...#.. +.......#..............................#..................#.........................................#...#..................#.#..#... +......#....#.............................#...#.......#.....#......................#.#..........#..............................#.... +.#..........................#........................#......#.........#......................#...#........#...........#...#........ +.............#............#................#.......................................#..###..#.....#.....#.#...............#.......#. +.#........#..............................#........#...........#...........................#...........#...................#........ +.......##.#...##...............#.#...........##.......#.#..............................#.....#.......#...........#................. +....#...###.#...............................#...........................#..................#..#.#...#............##.#..#....#...... +....##....##...#..#...................##..#...#.#.......#...#.......................#......##....................#....#........#... +..............................#....#...#...#..................#.....#...................#....#.........................##...#...... +...........#.#....#................................#.....#..#.................#..##......#..#......#.........#........#...#......#. +............................................#.#..........#...#.#....#.................#......#.#.#.#.........#........#......#..... +....#..............................##........#............#......................#.#..........#..........................#.....#... +.............#...##..#.............#........#.....#...#...............#..............#...........##..............................#. +................#...............................#.#..................#...........#.............##........#.......#....#..###....... +.#..........##.........................................#......#.#..#............................#...............##.#...#........... +.##.................##...................#.....................#..............#.........#........................#.....#...#...#... +.....................................................#..........#.#...........#.#..........#...............#.....#.......#...#..... +.#.............#.....##......#........#....#......................#.#.....#......#.......#......................#.....#...#......#. +........#...##.....#........#.........#.#..#............#...#.......................................#............#................. +......##..............#...###...........#............#.....................#............#.#...........................#............ +..##.#......#......#....#......#.................#................#....................##..............#.......#.#.#....#.......... +..#.......#.#.....#.##.....#................#.#.........#.....#.......#............................#..............#................ +...#.#....#..#...........#......................................#.....#..................................#.......#...#..#..#....... +...#....#..#........#.......#...............#.........#..#..#.##.....#................#............................................ +...........#...#.#.............##..............#.#.......#......#.........#.#......#..............#...................#............ +...#.....#..##.....#..#.........#................#...#..#............#..##.#....#..............#..#...............#................ +...#.#........##.........#..........#...........................#......#...#.......##...................#........#.#..##.........#. +.#.....#....................##.#................#..#.##................#........#..................................#..#.#...#...... +.#..........#.....#....#..........#...................#........##............#.................#............#.....##...........#... +...........#...#.........#.#.......##..............#.........#..........##......#................#............##..##............... +.......#...#...#.....#....#.............##..............................................##...#................................#.... +.#....##.....#...........#..........#..#............#.....##.......##...............................#.#...........#....#.........#. +.......#...#...............#........###....#..............................#............#..#...................#...#.........#...... +......#...#.....#..........#....####.......#.#..................................................###.......#......#..#............#. +.#..#.......#..#.#....#....##......#........#.........##....................#...................................................... +...........#.#.................................................#..........#............##..#..............#......#...##....#...#... +.#....................#......#.................................#.......................................#...#....................... +...................#.....................#...............#.....#.......................#...........#..#............#............... +...............#..#..#....#......#......#.........#............##..................................#.#..........##............#.... +......#.......#.......#...#.............#.......#..#........#......#...#...........#.......#....#..............#..#..#............. +.....#......#.......##.#......................................#......##........#...#.............#...#..#......#............#...... +.#........#..#.............#..#....###.............#...............#..........#...#......#......#...#....#.#.........#..........#.. +........#....#....#.....#....#..#.................#.............................#............................#............#........ +.....#...............#...........#.##...........................................#.#......#.....#.#..#....#..............##...#..... +..#..#....#..................................#.......#.#..........#........................#.........#.....................#.##.... +...#....#.............#...#............#..........#.#..#...........................#.............#...#.......#................#.#.. +..............#.....#......#.......#..........#....##..#................#.....#.....##.....#....#...........#......#............... +......#..#........................#.........#.......##....#.............................................##.....##.......#......#... +.....#..#.....#........................................#..............#............#...#...........................#........#...... +................................................................................................................................... diff --git a/src/day-21.lisp b/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))) diff --git a/t/day-21.lisp b/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)))