Clojurians Log v2

Yes, day 11 was the one where I had to learn a little about profiling clojure 🙂. Going from maps with coordinates as keys to vectors for storage (both state and precomputed neighbours mappings) did speed up things for me, but it took some tinkering to bring the time down to under 1s¹. Haven't tried the vector-of-vectors grid storage though. I'm surprised to see that manipulating strings as in the linked video is so fast -- but then again, I'm also rather new to java. ¹ https://github.com/next-mad-hatter/adventofcode/blob/master/src/aoc_2020/day_11.clj

@jeffrey.wayne.evans I could speed your solution up slightly with these minor edits: • Memoizing the seat counting function actually makes it slower • Neither of get-neighbours functions actually depends on the grid state, only on seat locations, which are invariant for all grid generations -- so one can memoize partial versions of those using the initial grid • Reducing + after map where latter would create a potentially expensive sequence is slower than reducing over original collection -- adapted count-neighbor-seats* accordingly. hth fwiw :)

diff --git a/src/advent_of_code/day11.clj b/src/advent_of_code/day11.clj
index a893320..bd0f1cc 100644
--- a/src/advent_of_code/day11.clj
+++ b/src/advent_of_code/day11.clj
@@ -67,12 +67,11 @@

 (defn count-neighbor-seats* [grid get-neighbors-fn seat-pred max-row max-col row col]
   (reduce
-    +
-    (map
-      #(count-seats grid seat-pred %)
-      (get-neighbors-fn grid max-row max-col row col))))
+   (fn [s e] (+ s (count-seats grid seat-pred e)))
+    0
+    (get-neighbors-fn max-row max-col row col)))

-(def count-neighbor-seats (memoize count-neighbor-seats*))
+(def count-neighbor-seats count-neighbor-seats*)

 (defn input-line-to-grid-row [line]
   (into
@@ -118,7 +117,7 @@
                                (let [impacted-neighbors
                                      (filter
                                        some?
-                                       (get-neighbors-fn grid max-row max-col row col))]
+                                       (get-neighbors-fn max-row max-col row col))]
                                  #(into % impacted-neighbors)))
            check-next (:check-next acc)
            update-fns (:update-fns acc)
@@ -191,7 +190,7 @@
    (day11-part1 "input_day11"))
   ([input-res]
    (let [grid (get-input-grid input-res)
-         [rounds final-grid] (run-until-stable grid get-adjacent-neighbors 4)
+         [rounds final-grid] (run-until-stable grid (memoize (partial get-adjacent-neighbors grid)) 4)
          final-counts (for [i (range 0 (count final-grid))
                             j (range 0 (count (first final-grid)))]
                         (count-seats final-grid #(= :occupied %) [i j]))
@@ -203,7 +202,7 @@
    (day11-part2 "input_day11"))
   ([input-res]
    (let [grid (get-input-grid input-res)
-         [rounds final-grid] (run-until-stable grid (memoize get-line-of-sight-neighbors) 5)
+         [rounds final-grid] (run-until-stable grid (memoize (partial get-line-of-sight-neighbors grid)) 5)
          final-counts (for [i (range 0 (count final-grid))
                             j (range 0 (count (first final-grid)))]
                         (count-seats final-grid #(= :occupied %) [i j]))

thanks, @max.deineko. extremely helpful!

I used a sparse map together with dimensions in a duple e.g. [{[ 4 5] :floor [7 2] :taken …}, dims] storing only the floor and taken seats. Part 1 was fast enough, but Part 2 took 66 seconds: interestingly if I use transducers in pipelines the time goes up to 88+ seconds, because the lists are deltas (<= 8 size colls). So unless you have to iterate on an entire 2D grid, they are probably not worth it. At some point I regretted not sticking to the string format bc it’s much easier to debug with graphic printouts, but writing a rendering fn wasn’t so bad, and the map format made the logic cleaner it seems. I find the fun part of most challenges especially this one, is refactoring the Part 1 code to reuse it with tweaking:

(defn surrounding-occupants [[grid dims] seat]...)
(defn visible-occupants ...)
(defn stabilize [plan occupancy-fn crowd-siz]...)

> I find the fun part of most challenges especially this one, is refactoring the Part 1 code to reuse it with tweaking: I like this part too. I have a love/hate view towards the part 2's that simply scale the problem up so that you need to have an efficient solution (either by 'getting the trick' or writing it a way focused on performance). On one hand its fun to be forced to think about optimization. On the other hand it ends up being (for me at least) "part 2: throw away all that terrible code you wrote for part1 and do it better"

I get the sense that the "part 1 refactoring" bit is much easier in Clojure as compared to, say, Java. Well, as is doing part 1 in the first place. 😁