aboutsummaryrefslogtreecommitdiffstats
path: root/AoC2023/day10
diff options
context:
space:
mode:
authorOscar Najera <hi@oscarnajera.com>2023-12-14 09:16:15 +0100
committerOscar Najera <hi@oscarnajera.com>2023-12-14 09:16:15 +0100
commitbd3d108d004bd2322f3b4b8d4e2cfcf1044dadfb (patch)
tree47ce55611bc7b4e755639812d0008c0d77b245ac /AoC2023/day10
parent4ced0399644ff2b75b53ce26d6afb0688e78b264 (diff)
downloadscratch-bd3d108d004bd2322f3b4b8d4e2cfcf1044dadfb.tar.gz
scratch-bd3d108d004bd2322f3b4b8d4e2cfcf1044dadfb.tar.bz2
scratch-bd3d108d004bd2322f3b4b8d4e2cfcf1044dadfb.zip
optimization hash-table instead of list 10x better
Diffstat (limited to 'AoC2023/day10')
-rw-r--r--AoC2023/day10/solver.lisp27
1 files changed, 13 insertions, 14 deletions
diff --git a/AoC2023/day10/solver.lisp b/AoC2023/day10/solver.lisp
index d93617a..11bd41c 100644
--- a/AoC2023/day10/solver.lisp
+++ b/AoC2023/day10/solver.lisp
@@ -71,20 +71,22 @@ LJ.LJ")
(let* ((start (find-start map))
(options (start-neighbors map start))
(last start)
- (cur (car options)))
- (cons cur
- (loop
- for next = (advance-next map cur last)
- do (setf last cur
- cur next)
- collect next
- until (equal next start)))))
+ (cur (car options))
+ (loop-tiles (make-hash-table :test #'equal)))
+ (setf (gethash cur loop-tiles) t)
+ (loop
+ for next = (advance-next map cur last)
+ do (setf last cur
+ cur next
+ (gethash next loop-tiles) t)
+ until (equal next start))
+ loop-tiles))
;; (get-loop
;; (uiop:split-string eg-input :separator '(#\Newline)))
(defun solver1 (rows)
(let ((map (make-array (length rows) :initial-contents rows)))
- (floor (length (get-loop map)) 2)))
+ (floor (hash-table-count (get-loop map)) 2)))
;; To know if a point is inside a loop, I need to count how often a ray crosses
;; until it reaches the boundary. I can just count to the right.
@@ -93,9 +95,6 @@ LJ.LJ")
;; those 2 cells taking the point a bit lower, would mean only counting pipes
;; with down component thus F,|,7. The rest L,-,J are irrelevant.
-(defun in-loop-p (point loop)
- (member point loop :test #'equal))
-
(defun rassoc-get (item list)
(car (rassoc item list :test #'equal)))
@@ -122,10 +121,10 @@ LJ.LJ")
(loop for col across row
for x from 0
for point = (list y x)
- when (and (in-loop-p point loop-tiles)
+ when (and (gethash point loop-tiles)
(member col '(#\F #\| #\7)))
do (setf insidep (not insidep))
- count (and (not (in-loop-p point loop-tiles))
+ count (and (not (gethash point loop-tiles))
insidep)))))
(fiveam:test solution