Fork me on GitHub
#adventofcode
<
2020-12-11
>
st3fan02:12:24

Can someone help me with the following (may contain a spoiler)

st3fan02:12:32

(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} ???

st3fan02:12:58

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

st3fan02:12:57

Maybe I should restart the REPL

st3fan02:12:42

I don’t get it 😕

Stuart02:12:56

look at line 4

Stuart02:12:59

12 15 15 19

st3fan02:12:24

Hope I can solve part 1 before I pass out 🙂

Stuart02:12:36

today was tough

st3fan02:12:13

Uhoh now I am afdraid of what to get for part 2 🙂

st3fan02:12:52

I need to get better at thinking in recursion

🐢 6
Stuart02:12:58

are you onto part 2?

Average-user06:12:04

How long take your programs for day 11?

plexus07:12:19

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 🙂

Vincent Cantin06:12:15

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

🎮 6
plexus07:12:15

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"

😆 9
🎉 6
3
👍 3
Vincent Cantin07:12:29

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.

plexus07:12:54

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 🙂

Vincent Cantin07:12:08

that's what I did.

👍 3
plexus07:12:25

And, how fast is it?

Vincent Cantin07:12:57

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

plexus07:12:31

hmmm that still feels like it should be faster

Vincent Cantin07:12:37

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

Vincent Cantin07:12:01

I used an atom as acc inside a double for loop

plexus07:12:12

yeah transients can help... not sure how much

Vincent Cantin07:12:05

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

Vincent Cantin07:12:43

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

Vincent Cantin07:12:31

Other note for myself: add a reverse-range function to my tool ns

plexus07:12:29

or just use a step of -1?

Vincent Cantin07:12:07

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

plexus07:12:23

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

Vincent Cantin07:12:44

The key is not to have to write 8 functions.

plexus07:12:23

yeah, makes sense. I might write two, one for diagonal one for straight

Vincent Cantin07:12:32

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

plexus07:12:06

I've never come across a real life need for transients

Vincent Cantin07:12:33

but people in AoC may need it soon.

Vincent Cantin07:12:24

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

Average-user13:12:24

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

plexus16:12:24

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.

Vincent Cantin16:12:27

Can we see how you did?

plexus16:12:44

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

3
plexus16:12:07

(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

plexus16:12:53

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

plexus17:12:44

@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

🎉 3
Vincent Cantin17:12:09

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

Vincent Cantin17:12:07

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.

Vincent Cantin17:12:20

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.

Vincent Cantin17:12:44

Thank you for spending the time to look into it.

Vincent Cantin17:12:14

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:

Vincent Cantin04:12:27

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

Vincent Cantin04:12:34

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.

Vincent Cantin04:12:37

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.

Vincent Cantin04:12:45

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

plexus07:12:21

Day 11 answers thread - Post your answers here

erwinrooijakkers07:12:56

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.

mchampine07:12:35

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

3
👏 3
nbardiuk09:12:37

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

👍 9
misha10:12:51

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

👍 6
Vincent Cantin13:12:13

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

alekszelark13:12:20

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

erwinrooijakkers14:12:49

🎨 9
❤️ 6
😍 6
parrot 12
🤯 6
plexus15:12:04

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

😅 9
Vincent Cantin15:12:01

Did you transient / persistent! a lot?

alekszelark16:12:37

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

alekszelark16:12:54

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

🚀 6
Vincent Cantin16:12:55

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

Vincent Cantin16:12:31

In this version, I tried to leverage the transducers.

alekszelark16:12:28

Part 1 — 512.213845 ms Part 2 — 2.664164 sec

Vincent Cantin16:12:10

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

markw17:12:19

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

curlyfry18:12:20

(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

👍 6
nbardiuk21:12:25

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)

bellissimo 3
pez21:12:48

@U051HUZLD:I remove floor cells from the map.

pez22:12:22

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 #{})))

pez00:12:34

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.

pez00:12:34

(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))))

Joe17:12:59

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

Ben List19:12:13

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

Vincent Cantin12:12:50

😱 I replaced get-in by 2 consecutive get and I cut my runtime by half !!!

😮 3
Vincent Cantin16:12:20

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

pez21:12:31

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

😁 12
Stuart00:12:45

just finished part 1 and it took 24 seconds. This does not bode well.

curlyfry21:12:11

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

metal 9
andrea.crotti21:12:46

Ah nice yeah I forgot about iterate

andrea.crotti21:12:12

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

andrea.crotti21:12:29

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

curlyfry22:12:13

@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

curlyfry22:12:37

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

curlyfry22:12:02

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

3
markw22:12:52

@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 ~@args)))
      ~m)
    `(update ~m ~k ~f ~@args)))

parrot 3
👍 3