From bd3d108d004bd2322f3b4b8d4e2cfcf1044dadfb Mon Sep 17 00:00:00 2001
From: Oscar Najera <hi@oscarnajera.com>
Date: Thu, 14 Dec 2023 09:16:15 +0100
Subject: optimization hash-table instead of list 10x better

---
 AoC2023/day10/solver.lisp | 27 +++++++++++++--------------
 1 file 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
-- 
cgit v1.2.3