commit 9055450a2534d9e5140fcc4bdaef19664c75ff28 parent f043bd101b4535f56722f0072e154273233128e4 Author: Lukas Henkel <lh@entf.net> Date: Mon, 18 Dec 2023 07:10:48 +0100 Day 18 task 2 Diffstat:
| M | src/day-18.lisp | | | 90 | ++++++++++++++++++++++++++++++++++++++++--------------------------------------- |
| M | t/day-18.lisp | | | 5 | +++-- |
2 files changed, 49 insertions(+), 46 deletions(-)
diff --git a/src/day-18.lisp b/src/day-18.lisp @@ -4,61 +4,63 @@ (in-package #:aoc/day-18) (defun parse-line (line) - (multiple-value-bind (dig-length) + (multiple-value-bind (dig-length end) (parse-integer line :start 2 :junk-allowed t) (list (switch ((aref line 0)) (#\U :up) (#\L :left) (#\R :right) (#\D :down)) - dig-length))) + dig-length + (switch ((aref line (+ end 3 5))) + (#\0 :right) + (#\1 :down) + (#\2 :left) + (#\3 :up)) + (parse-integer line + :start (+ end 3) + :end (+ end 3 5) + :radix 16)))) -(defun dir-diff (dir) +(defun dir-diff (dir length) (ecase dir - (:up '(0 . -1)) - (:left '(-1 . 0)) - (:right '(1 . 0)) - (:down '(0 . 1)))) + (:up (cons 0 (- length))) + (:left (cons (- length) 0)) + (:right (cons length 0)) + (:down (cons 0 length)))) -(defun fill-lagoon (map start-pos) - (loop with todo = (list start-pos) - while todo - for current = (pop todo) - do (setf (gethash current map) t) - do (loop for n in '(:up :left :right :down) - for n-pos = (point+ current (dir-diff n)) - unless (gethash n-pos map) - do (push n-pos todo)))) +(declaim (ftype (function ((simple-array cons)) fixnum) shoelace)) +(defun shoelace (vertices) + (loop with n = (- (length vertices) 2) + repeat n + for i from 0 + for j = (1+ i) + for x-1 fixnum = (car (aref vertices i)) + for y-1 fixnum = (cdr (aref vertices i)) + for x-2 fixnum = (car (aref vertices j)) + for y-2 fixnum = (cdr (aref vertices j)) + sum (the fixnum (* x-1 y-2)) into sum-1 fixnum + sum (the fixnum (* x-2 y-1)) into sum-2 fixnum + finally (return (/ (the fixnum (abs (- sum-1 sum-2))) 2)))) -(defun find-start-pos (map min-x min-y) - (loop for x from min-x - for y from min-y - for pos = (cons x y) - when (gethash pos map) - do (return (point+ pos (cons 1 1))))) - -(defun lagoon-size (map) - (multiple-value-bind (min-x min-y) - (loop for key being the hash-keys of map - for (x . y) = key - minimize x into min-x - minimize y into min-y - maximize x into max-x - maximize y into max-y - finally (return (values min-x min-y max-x max-y))) - (let ((start-pos (find-start-pos map min-x min-y))) - (fill-lagoon map start-pos) - (hash-table-count map)))) (defun day-18 (input) - (loop with map = (let ((ht (make-hash-table :test 'equal))) - (setf (gethash (cons 0 0) ht) t) - ht) - with current = (cons 0 0) + (loop with vertices-1 = (list (cons 0 0)) + with vertices-2 = (list (cons 0 0)) + with current-1 = (cons 0 0) + with current-2 = (cons 0 0) for line = (read-line input nil) while line - for (dir length) = (parse-line line) - do (loop for i from 0 below length - do (setf current (point+ current (dir-diff dir))) - do (setf (gethash current map) t)) - finally (return (lagoon-size map)))) + for (dir-1 length-1 dir-2 length-2) = (parse-line line) + sum length-1 into length-1-sum + sum length-2 into length-2-sum + do (setf current-1 (point+ current-1 (dir-diff dir-1 length-1))) + do (setf current-2 (point+ current-2 (dir-diff dir-2 length-2))) + do (push current-1 vertices-1) + do (push current-2 vertices-2) + finally (return (values (+ (shoelace (coerce (nreverse vertices-1) 'vector)) + (/ length-1-sum 2) + 1) + (+ (shoelace (coerce (nreverse vertices-2) 'vector)) + (/ length-2-sum 2) + 1))))) diff --git a/t/day-18.lisp b/t/day-18.lisp @@ -4,7 +4,7 @@ (define-test test-day-18 () - (multiple-value-bind (task-1) + (multiple-value-bind (task-1 task-2) (aoc:run-day 18 "R 6 (#70c710) D 5 (#0dc571) L 2 (#5713f0) @@ -19,4 +19,5 @@ R 2 (#7807d2) U 3 (#a77fa3) L 2 (#015232) U 2 (#7a21e3)") - (assert= 62 task-1))) + (assert= 62 task-1) + (assert= 952408144115 task-2)))