commit eb6b4b70ef991fc68c6610326d52e178e29355b2 parent 4af8595fb520002054c5e07b0661b6135c69420b Author: Lukas Henkel <lh@entf.net> Date: Fri, 8 Dec 2023 17:21:21 +0100 Optimize day 8 - Convert locations to numbers - Use those numbers to index an array, rather than a hashtable Diffstat:
| M | src/day-8.lisp | | | 48 | ++++++++++++++++++++++++++++++++---------------- |
1 file changed, 32 insertions(+), 16 deletions(-)
diff --git a/src/day-8.lisp b/src/day-8.lisp @@ -3,6 +3,14 @@ (:export #:day-8)) (in-package #:aoc/day-8) +(declaim (ftype (function (simple-string) fixnum) convert-field-to-number)) +(defun convert-field-to-number (field) + (loop for char across field + for shift fixnum from 0 + sum (the fixnum (ash (- (char-code char) (if (char>= char #\A) 65 48)) + (the fixnum (* shift 5)))) fixnum)) + +(declaim (ftype (function (simple-string) list) parse-line)) (defun parse-line (line) (let* ((equal-pos (position #\= line)) (key (subseq line 0 (1- equal-pos))) @@ -11,39 +19,47 @@ (left (subseq line (1+ paren-open-pos) comma-pos)) (paren-close-pos (position #\) line :start comma-pos)) (right (subseq line (+ comma-pos 2) paren-close-pos))) - (list key (list left right)))) + (list (convert-field-to-number key) + (list (convert-field-to-number left) + (convert-field-to-number right))))) +(declaim (ftype (function (stream) (simple-array list)) read-map)) (defun read-map (input) (read-line input) - (loop with map = (make-hash-table :test 'equal) + (loop with map = (make-array 26426 :initial-element nil) for line = (read-line input nil) while line for (key left-right) = (parse-line line) - do (setf (gethash key map) left-right) + do (setf (aref map key) left-right) finally (return map))) -(defun walk-to-destination (instructions map starting-point test-fun) - (loop with current = starting-point - for steps from 0 +(declaim (ftype (function (simple-string + (simple-array list) + fixnum + &optional (or null fixnum)) + fixnum) + walk-to-destination)) +(defun walk-to-destination (instructions map starting-point &optional destination) + (loop with current fixnum = starting-point + for steps fixnum from 0 for direction = (aref instructions (mod steps (length instructions))) - for (left right) = (gethash current map) + for (left right) = (aref map current) do (setf current (ecase direction (#\L left) (#\R right))) - when (funcall test-fun current) + when (if destination + (= current destination) + (>= current 25600)) do (return (1+ steps)))) -(defun destination-p (field) - (char= (last-elt field) #\Z)) - (defun day-8 (input) (let ((instructions (read-line input)) (map (read-map input))) - (values (if (gethash "AAA" map) - (walk-to-destination instructions map "AAA" (curry #'equal "ZZZ")) + (values (if (aref map 0) + (walk-to-destination instructions map 0 26425) 0) (apply #'lcm - (loop for field string being the hash-key of map - when (char= (last-elt field) #\A) - collect (walk-to-destination instructions map field #'destination-p)))))) + (loop for field fixnum from 0 to 825 + when (aref map field) + collect (walk-to-destination instructions map field))))))