Clojurians Log v2

Yup, I decided to do it in haskell yesterday and I really don't want to add mutation to it.

Tried the "precompute 8 layers" approach, haven't finished it yet, but calculating the layers takes about 1ms per layer or 8-10ms for all ten. Still feels like it should be possible to do that faster.

Can we see how you did?

I'll push it, trying to wrap it up. Also surprising find, looking up in 2-dimensional array is twice as slow as lookup in a two-dimensional vector

(defn getxy ^long [grid x y]
  (.nth ^clojure.lang.PersistentVector (.nth ^clojure.lang.PersistentVector grid x) y))

(defn agetxy [^"[[J" arr ^long x ^long y]
  (java.lang.reflect.Array/get (java.lang.reflect.Array/get arr x) y))

(let [dim 1000
      arr (array-grid dim dim)]
  (time
   (doseq [x (range dim)
           y (range dim)]
     (agetxy arr x y))))
;; This takes ~150ms

(let [dim 1000
      arr (mapv vec (array-grid dim dim))]
  (time
   (doseq [x (range dim)
           y (range dim)]
     (getxy arr x y))))
;; This only take ~75ms

seems there not really any way to generate direct array lookup bytecode

@vincent.cantin https://github.com/lambdaisland/aoc_2020/blob/main/src/lambdaisland/aoc_2020/puzzle11_alt.clj Here it is, a lot of effort, and in the end still slower than my first solution. Then I went back and just ported the optimized nested vector lookup, and it cut the time for my original solution in half. So now I'm at 500ms for part 2, or about 1.5s with the "8 layers" approach

I think that the lack of eccentricity of the input data implies that the simple implementation is working fast enough.

The optimization is only saving some time when the lookup of the neighbors is costly, and it does not seem to be the case here.

I give up on trying to improve my solution any further, it makes the code look like ugly C, it’s unreadable and not interesting.

Thank you for spending the time to look into it.

A last cheap optimization to be considered: having the grid on a 1 dimensional vector. PRO: faster look up CONS: need to manually write code to make sure that the col index is correct + it looks ugly as hell. … tried and rolled back :face_vomiting:

@plexus I fixed your array access function, it should look like that instead:

(defn agetxy ^long [^"[[J" arr x y]
  (aget ^"[J" (aget arr x) y))

The benchmarking has a problem too, the result of the operation needs to be used, otherwise the JVM will just drop the body using dead code elimination.

Probably, the DCE is triggered when the read expression is fully understood statically and that’s why the reflective calls where not removed - but they were slow anyway.

@plexus This is the correct way to bench, and even with the addition and transducing process overhead, it is still faster than your previous fastest.

(set! *unchecked-math* :warn-on-boxed)

(defn agetxy ^long [^"[[J" arr x y]
  (aget ^"[J" (aget arr x) y))

(let [dim 1000
      arr (make-array Long/TYPE dim dim)
      _ (doseq [x (range dim)
                y (range dim)]
          #_ (aset ^"[[J" arr x y 1) ;; super slow - don't use this!
          (aset ^"[J" (aget ^"[[J" arr x) y 1))
      result (time
               (transduce (map (fn [x]
                                 (transduce (map (fn [y]
                                                   (agetxy arr x y)))
                                            +
                                            (range dim))))
                          +
                          (range dim)))]
  (prn result))

my solution runs in 3s and 6s, I am very curious to learn from the thread to find better data structures or approach https://github.com/nbardiuk/adventofcode/blob/master/2020/src/day11.clj

cache first-seen xys, and remove dots (floor) from the map. @nbardiuk

My runs in 0.6s and 1.2s with index of seen chairs. https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2020/day11.clj

My messy original solution (a cleaned up and faster version is coming later) For the part 2, it scans the whole data in 8 directions in O(n) before updating the data in O(n) https://github.com/green-coder/advent-of-code-2020/blob/1df1043c19017850257d403000d9b6f5568fddee/src/aoc/day_11.clj

Here is my solution. The key is “all decisions are based on the number of occupied seats…” https://github.com/zelark/AoC-2020/blob/master/src/zelark/aoc_2020/day_11.clj

My solution to Day 11. https://github.com/benfle/advent-of-code-2020/blob/main/day11.clj

TFW you think you'll speed it up by changing arrays in-place, and it's 100 times slower than updating vectors

Did you transient / persistent! a lot?

@vincent.cantin I tried, but it didn’t help much

I benched my solution with Criterium: part 1 — 882ms, and part 2 — 772ms.

Can you bench my part 1 and tell me how fast it takes on your computer? (I think my computer is way slower than everybody else) https://github.com/green-coder/advent-of-code-2020/blob/01fc1785a26872c165302c463e26caceb93e82ff/src/aoc/day_11.clj

Sure!

In this version, I tried to leverage the transducers.

Part 1 — 512.213845 ms Part 2 — 2.664164 sec

Thank you ! It seems that your computer is exactly twice faster than mine.

As concise as I could get it, but it does take ~20s to run both parts https://github.com/Solaxun/aoc2020_clj/blob/main/src/aoc2020_clj/day11.clj

(time (solve adjacent-count 4)) "Elapsed time: 1488.883654 msecs" (time (solve seen-count 5)) "Elapsed time: 2997.948211 msecs" I was pretty happy with the functional composition in this one! (And the completely unnecessary selections from math.combinatorics) https://github.com/Dexterminator/advent-of-code-2020/blob/main/src/day11/core.clj

@pez https://clojurians.slack.com/archives/C0GLTDB2T/p1607681391129000?thread_ts=1607671401.120300&cid=C0GLTDB2T

after incorporating examples and suggestions I've managed to reduce runtime from 2s,6s to 0.6s,0.9s. What helped is to precompute near seats for each seat and split map of seat states into 3 sets (occupied, floor, seats)

@misha:I remove floor cells from the map.

So if I memoize my neighbour-of function, I get 3 secs for step 2. But can only do it once then, because on the second round it never finishes.

(def neighbours-of-
  (fn
    [{:keys [floor size]} seat]
    (let [[rows cols] size]
      (->> [[-1 -1] [0 -1] [1 -1] [-1 0] [1 0] [-1 1] [0 1] [1 1]]
           (keep (fn look [direction]
                   (loop [delta direction]
                     (let [[new-r new-y] (map + seat delta)]
                       (when-not (or (neg? new-r)
                                     (neg? new-y)
                                     (> new-r rows)
                                     (> new-y cols))
                         (if (floor [new-r new-y])
                           (recur (map + delta direction))
                           [new-r new-y]))))))
           (into #{})))))

(def neighbours-of
  (memoize neighbours-of-))

(defn occupied-neighbours-of
  [ferry seat]
  (->> (neighbours-of (select-keys ferry [:floor :size]) seat)
       (filter #((:occupied-seats ferry) %))
       (into #{})))

I’m down to 2 secs now, with cached neighbours/first-seens. Can’t see where I have gains to make. I might have choosen the wrong data structure for the grid.

(defn parse-seats [rows chs]
  (->> rows
       (map-indexed (fn [y row]
                      (map-indexed (fn [x this-ch]
                                     (when (chs this-ch)
                                       [x y]))
                                   row)))
       (apply concat)
       (remove nil?)
       (into #{})))

(defn parse [input]
  (->> input
       (re-seq #"[.L#]+")
       ((fn parse-ferry
          [rows]
          (let [floor (parse-seats rows #{\.})]
            {:floor          floor
             :occupied-seats (parse-seats rows #{\#})
             :all-seats      (clojure.set/difference (parse-seats rows #{\# \. \L}) floor)
             :neighbours-of  {}
             :size           [(count (first rows)) (count rows)]
             :generations    0})))))

(defn neighbours-of-1
  [seat]
  (->> [[-1 -1] [0 -1] [1 -1] [-1 0] [1 0] [-1 1] [0 1] [1 1]]
       (map (fn [direction]
              (map + seat direction)))
       (into #{})))

(defn occupied-neighbours-of-1
  [ferry seat]
  (->> (neighbours-of-1 seat)
       (filter (fn [c]
                 ((:occupied-seats ferry) c)))
       (into #{})))

(defn neighbours-of
  [{:keys [floor size]} seat]
  (let [[rows cols] size]
    (->> [[-1 -1] [0 -1] [1 -1] [-1 0] [1 0] [-1 1] [0 1] [1 1]]
         (keep (fn look [direction]
                 (loop [delta direction]
                   (let [[new-r new-y] (map + seat delta)]
                     (when-not (or (neg? new-r)
                                   (neg? new-y)
                                   (> new-r rows)
                                   (> new-y cols))
                       (if (floor [new-r new-y])
                         (recur (map + delta direction))
                         [new-r new-y]))))))
         (into #{}))))

(defn occupied-neighbours-of
  [ferry seat]
  (->> (get-in ferry [:neighbours-of seat])
       (clojure.set/intersection (:occupied-seats ferry))))

(defn render [ferry] ; TODO: This is broken
  (let [[rows cols] (:size ferry)
        pixels (for [row (range rows)
                     col (range cols)]
                 (cond
                   ((:floor ferry) [row col]) "."
                   ((:occupied-seats ferry) [row col]) "#"
                   :else                            "L"))]
    (->> pixels
         (partition 10)
         (map #(apply str %)))))

(defn next-ferry
  [ferry]
  (-> ferry
      (update :occupied-seats
              (fn [_]
                (->> (:all-seats ferry)
                     (filter (fn [seat]
                               (let [num-occupied-neighbours (count (occupied-neighbours-of ferry seat))]
                                 (cond
                                   (and (not ((:occupied-seats ferry) seat))
                                        (zero? num-occupied-neighbours))
                                   true

                                   (and ((:occupied-seats ferry) seat)
                                        (>= num-occupied-neighbours 5))
                                   false

                                   :else
                                   ((:occupied-seats ferry) seat)))))
                     (into #{}))))
      (update :generations inc)))

(defn cache-neighbours [ferry]
  (update ferry
          :neighbours-of
          #(into
            %
            (->> (:all-seats ferry)
                 (map (fn [seat]
                        {seat (neighbours-of ferry seat)}))
                 (into #{})))))

(comment
  (def input (util/fetch-input 11))

  (time (->> input
             (parse)
             (cache-neighbours)
             ((fn stabilize [ferry]
                (loop [old-ferry ferry]
                  (let [new-ferry (next-ferry old-ferry)]
                    (if (= (:occupied-seats new-ferry)
                           (:occupied-seats old-ferry))
                      old-ferry
                      (recur new-ferry))))))
             (:occupied-seats)
             (count))))

Would anyone be able to give me some clues as to why my Day 11 Part 1 solution is so slow? I'm caching neighbours, but I'm still getting >2 seconds. I'm doing a fair amount of set operations, maybe that's it? https://github.com/RedPenguin101/aoc2020/blob/main/day11-2.clj

Part 2 final stage (probably filpped): https://raw.githubusercontent.com/genmeblog/advent-of-code/master/images/advent_of_code_2020/day11_far_222.jpg

definitely not my best work, but i never cared for game of life when I had to do it in college either https://github.com/listba/advent-of-code-2020/blob/master/clojure/src/aoc_2020/days/11.clj