commit d7b2a01d551e821e13e7d0e2dfd2e37f6c8adf63
parent aea08906c977042acf39efeca6007b925df85f0c
Author: Lukas Henkel <lh@entf.net>
Date: Sat, 14 Dec 2024 20:33:10 +0100
Optimize and cleanup day 14
- Don't move robots, instead calculate new robot position
- Calculate safety factor inline
- Early return for overlap detection
Diffstat:
3 files changed, 51 insertions(+), 46 deletions(-)
diff --git a/src/day-14.lisp b/src/day-14.lisp
@@ -2,7 +2,7 @@
(:use #:cl #:aoc/utils)
(:export
#:parse-robots
- #:run
+ #:task-1
#:day-14))
(in-package #:aoc/day-14)
@@ -20,51 +20,42 @@
(list (cons (first p) (second p))
(cons (first v) (second v)))))
-(defun safety-factor (robots width height)
- (loop with hmiddle = (floor width 2)
+(declaim (inline robot-after))
+
+(defun robot-after (robot seconds bounds)
+ (point-mod (point+ (first robot)
+ (point* (second robot) (cons seconds seconds)))
+ bounds))
+
+(defun task-1 (robots width height)
+ (loop with bounds = (cons width height)
+ with hmiddle = (floor width 2)
with vmiddle = (floor height 2)
- with ul = 0
- with ur = 0
- with bl = 0
- with br = 0
+ with quadrants = (list 0 0 0 0)
for robot in robots
- for pos = (first robot)
- for x = (point-x pos)
- for y = (point-y pos)
- do (cond
- ((and (< x hmiddle) (< y vmiddle))
- (incf ul))
- ((and (> x hmiddle) (< y vmiddle))
- (incf ur))
- ((and (< x hmiddle) (> y vmiddle))
- (incf bl))
- ((and (> x hmiddle) (> y vmiddle))
- (incf br)))
- finally (return (* ul ur bl br))))
+ for new-pos = (robot-after robot 100 bounds)
+ for x = (point-x new-pos)
+ for y = (point-y new-pos)
+ unless (or (= x hmiddle) (= y vmiddle))
+ do (incf (nth (+ (* (round x width) 2)
+ (round y height))
+ quadrants))
+ finally (return (apply #'* quadrants))))
-(defun run (robots width height &optional with-task-2)
- (loop with task-1 = nil
- for i from 1
- for overlap-set = (make-hash-table :test #'equal)
- for overlaps? = nil
- do (loop for robot in robots
- for pos = (first robot)
- for velocity = (second robot)
- for new-pos = (point+ pos velocity)
- do (setf (point-x new-pos)
- (mod (point-x new-pos) width)
- (point-y new-pos)
- (mod (point-y new-pos) height)
- (first robot) new-pos)
- (unless overlaps?
- (setf overlaps? (gethash new-pos overlap-set)
- (gethash new-pos overlap-set) t)))
- unless overlaps?
- do (return (values task-1 i))
- when (= i 100)
- do (setf task-1 (safety-factor robots width height))
- and unless with-task-2
- do (return task-1)))
+(defun task-2 (robots width height)
+ (loop with bounds = (cons width height)
+ for seconds from 1
+ for map = (make-hash-table :test #'equal)
+ when (loop for robot in robots
+ for new-pos = (robot-after robot seconds bounds)
+ when (gethash new-pos map)
+ do (return nil)
+ do (setf (gethash new-pos map) t)
+ finally (return t))
+ do (return seconds)))
(defun day-14 (input)
- (run (parse-robots input) 101 103 t))
+ (let ((robots (parse-robots input)))
+ (values
+ (task-1 robots 101 103)
+ (task-2 robots 101 103))))
diff --git a/src/utils.lisp b/src/utils.lisp
@@ -18,6 +18,8 @@
#:map-integer-at
#:point+
#:point-
+ #:point*
+ #:point-mod
#:point-x
#:point-y
#:point-in-bounds-p
@@ -116,7 +118,7 @@
(loop for y from 0 below (input-map-height map)
do (format stream "~A~%" (aref (input-map-data map) y))))
-(declaim (inline point+ point- point-x point-y)
+(declaim (inline point+ point- point* point-mod point-x point-y)
(ftype (function (cons) fixnum) point-x point-y))
(defun point-x (point)
@@ -143,6 +145,18 @@
(the fixnum (- (point-y point-a)
(point-y point-b)))))
+(defun point* (point-a point-factor)
+ (cons (the fixnum (* (point-x point-a)
+ (point-x point-factor)))
+ (the fixnum (* (point-y point-a)
+ (point-y point-factor)))))
+
+(defun point-mod (point-a point-divisor)
+ (cons (the fixnum (mod (point-x point-a)
+ (point-x point-divisor)))
+ (the fixnum (mod (point-y point-a)
+ (point-y point-divisor)))))
+
(declaim (inline point-in-bounds-p point-in-map-p))
(defun point-in-bounds-p (point width height)
(destructuring-bind (x . y) point
diff --git a/t/day-14.lisp b/t/day-14.lisp
@@ -17,4 +17,4 @@ p=9,3 v=2,3
p=7,3 v=-1,2
p=2,4 v=2,-3
p=9,5 v=-3,-3")
- (assert= 12 (aoc/day-14:run (aoc/day-14:parse-robots s) 11 7))))
+ (assert= 12 (aoc/day-14:task-1 (aoc/day-14:parse-robots s) 11 7))))
