This page is not created by, affiliated with, or supported by Slack Technologies, Inc.

## 2020-12-11

## Channels

- # adventofcode (108)
- # announcements (4)
- # aws (11)
- # babashka (39)
- # beginners (199)
- # calva (12)
- # clj-kondo (17)
- # cljs-dev (1)
- # clojure (115)
- # clojure-dev (9)
- # clojure-europe (98)
- # clojure-italy (17)
- # clojure-nl (4)
- # clojure-norway (3)
- # clojure-seattle (7)
- # clojure-sweden (6)
- # clojure-switzerland (5)
- # clojure-uk (15)
- # clojurescript (41)
- # code-reviews (36)
- # conjure (7)
- # datomic (1)
- # emacs (1)
- # events (1)
- # fulcro (26)
- # graalvm (2)
- # helix (35)
- # jackdaw (2)
- # jobs (9)
- # jobs-discuss (5)
- # lambdaisland (2)
- # meander (24)
- # off-topic (80)
- # pathom (22)
- # pedestal (1)
- # portal (20)
- # re-frame (3)
- # releases (1)
- # reveal (13)
- # rewrite-clj (1)
- # shadow-cljs (8)
- # specter (5)
- # sql (4)

```
(frequencies (map #(* -1 (apply - %)) (partition 2 1 [0 1 4 5 6 7 10 11 12 15 16 19 22])))
;; => {1 7, 3 5}
(defn jolt-distribution [jolts]
(frequencies (map #(* -1 (apply - %)) (partition 2 1 jolts))))
(jolt-distribution [0 1 4 5 6 7 10 11 12 15 15 19 22])
;; => {1 6, 3 4, 0 1, 4 1} ???
```

I am pretty tired, so maybe I just don’t see it - but why do I get a different result .. the function is exactly what the expression above it does

How long take your programs for day 11?

Part 2 of day 11 on the real input runs in just under a second for me. Probably could be a lot faster but good enough for me 🙂

Good morning !

If you find it difficult today, just remember: “C’est la vie !” (that’s life)

Pleasantly surprised that my initial attempt at part 2 actually finished in under a second, I was expecting a similar scenario as yesterday... "back to the drawing board"

Impressive

I did not believe that the simple approach would be fast enough, so I spent a lot of time optimizing the algorithm and writing it down.

One more optimized approach I can think of is doing a single pass over the layout for each of the 8 directions, so you end up with 8 data structures with precomputed values for what the next chair in that direction is. I hope that makes sense 🙂

a couple of seconds ... but my computer is a mac book air from 2011

Note to self: learn the mutating operators ... assoc! and friends.

I used an atom as acc inside a double for loop

Doing the optimised algorithm only with immutable datastructure in limited time is very hard.

I only thought about atom because I usually don't do mutable things. It's time to change that.

Other note for myself: add a `reverse-range`

function to my tool ns

(range (dec n) -1 -1) .. with the adrenaline of the rush, a reverse-range function is wiser.

I might have a stab at doing the precomputing later, I feel like it should be possible to make it very fast without funky stuff like transitiens

The key is not to have to write 8 functions.

the transient stuff is a good idea for opening your next stream

but people in AoC may need it soon.

.. and that would be a good demonstration of the versatility of Clojure.

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

@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:

@U07FP7QJ0 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.

@U07FP7QJ0 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))
```

Not gonna win at code golf but at least it works 🙂 https://github.com/lambdaisland/aoc_2020/blob/main/src/lambdaisland/aoc_2020/puzzle11.clj

Second part (just executing how it is stated) takes 2 minutes but well, https://github.com/transducer/adventofcode/blob/master/src/adventofcode/2020/day11.clj. Not sure how to improve the speed.

Part 1, kinda crufty.

```
;; get neighbor coords
(defn addpairs [[x1 y1] [x2 y2]] [(+ x1 x2) (+ y1 y2)])
(def surround [[1 0] [1 1] [0 1] [-1 1] [-1 0] [-1 -1] [0 -1] [1 -1]])
(defn neighbors [posn] (map addpairs (repeat posn) surround))
;; get / set seat value
(defn getxy [brd [x y]] (get (get brd y) x))
(defn setxy [brd [x y] v]
(let [row (get brd y)
newrow (apply str (assoc (vec row) x v))]
(assoc brd y newrow)))
(defn countneighbors? [brd seat]
(count (filter #{\#} (map (partial getxy brd) (neighbors seat)))))
(defn update1seat [brd seat]
(let [seatstatus (getxy brd seat)
adjseats (countneighbors? brd seat)]
(case seatstatus
\L (if (= 0 adjseats) \# \L)
\# (if (>= adjseats 4) \L \#)
\. \.)))
(defn step1 [brd]
(let [dimx (count (first brd))
dimy (count brd)
allseats (for [y (range dimy) x (range dimx)] [x y])
updatedseats (map (partial update1seat brd) allseats)]
(vec (map (partial apply str) (partition dimx updatedseats)))))
(->> input
(iterate step1)
(partition 2 1)
(drop-while #(apply not= %))
ffirst
(apply str)
(filter #{\#})
count)
;; => 2412
```

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

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

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

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

@U0ETXRFEW 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)

@U051HUZLD: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

My bed book this weekend will be http://clojure-goes-fast.com/blog/

From slower to faster:

```
(swap! acc update row assoc col c)
(swap! acc assoc-in [row col] c)
(swap! acc (fn [grid]
(update grid row (fn [row]
(assoc row col c))))))))
```

My solution for Day 11, step 2 takes 6 seconds to run… But at least I have the stars.

I've been getting some good mileage out of `iterate`

in some of the problems. Haven't gotten the opportunity to use it that much before, it's so nice when the problen fits! I started writing the body for a loop/recur and then realised that I could just feed it to iterate and it turned out much nicer

Ah nice yeah I forgot about iterate

I feel like I should use a proper matrix library instead of the usual vector of vectors

What's the best library for this kind of stuff atm?

@andrea.crotti The ones I've seen (like `core.matrix`

) are a bit more math focused I'd say. One of the main matrix processing tools in core is https://clojuredocs.org/clojure.walk/prewalk

I don't really think either is very useful for today's problem though since you need to keep track of indices and stuff

If you find a way to use one of the walk functions in a nice way in the problem I'd love to hear it! That was the ugliest part of my solution

@vincent.cantin may the lisp gods forgive this abomination inspired by your comment:

```
(defmacro update-in-faster [m [k & ks] f & args]
(if ks
`((fn [m#]
(assoc m# ~k (update-in-faster (m# ~k) ~ks ~f [email protected])))
~m)
`(update ~m ~k ~f [email protected])))
```