Fork me on GitHub
#adventofcode
<
2020-12-29
>
Jeff Evans19:12:23

it seems for day 11, the most efficient solution is just to keep the input in string form (so you can repeatedly do charAt to check the various cells in constant time). see, ex: https://www.youtube.com/watch?v=1t6Monx_dsk does anyone have an approach where they actually parse the input into a grid structure, then operate efficiently on that grid? I’m trying to figure out if my solution there (which is orders of magnitude slower than all of my previous days’ solutions) can be made faster

holymackerels21:12:31

my solution uses a grid (a map of [y x] -> seat-type), I don't remember if it was fast or not, let me try re-running it

holymackerels21:12:57

😬 nope mine is very slow 8s/14s for part1/2

Jeff Evans21:12:45

ha, phew, not just me then 😆

Jeff Evans21:12:02

ah, cool, so I was basically on the right track. memoized the “find nearest line of sight neighbors” function for part 2, and used transient to update the grid: https://github.com/jeff303/advent-of-code-2020/blob/master/src/advent_of_code/day11.clj

Jeff Evans21:12:26

granted I shoehorned a transducer into here, probably not really any good reason for that, but I wanted to learn more about them

Max Deineko10:12:17

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

Max Deineko10:12:42

@U0183EZCD0D 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]))

Jeff Evans15:12:53

thanks, @U9TGHG3LP. extremely helpful!

👍 1
kingcode14:01:31

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]...)

holymackerels02:01:12

> 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"

Jeff Evans02:01:07

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. 😁