Fork me on GitHub
#adventofcode
<
2017-12-06
>
minikomi05:12:44

TIL.. max-key Also, TIL: max-key gives the last instance for which (k x) is greatest

borkdude08:12:17

Solved it, but no real insights for today

borkdude08:12:40

And it’s fast enough, so no optimizing today 😉

val_waeselynck08:12:51

@borkdude same thing, a bit disappointed 🙂

borkdude08:12:55

I almost never use loop in Clojure, but for Advent of Code I used it a couple of times now

orestis08:12:22

I got to use transient for the first time today. I like it how you can do that inside a tight loop so you don’t have to do the whole functional way for something that you know is never leaving that function.

orestis08:12:27

I just love this:

(nth (iterate next-cycle [0 2 7 0]) 5)
;; => [2 4 1 2]

minikomi08:12:50

ah, that's nice

val_waeselynck08:12:52

I did use quot and rem for better performance, wondering if that's wasted

minikomi08:12:20

Also, I learned you can use :as when destructuring vectors

orestis08:12:23

It’s only ~13k steps for me…

borkdude08:12:31

yeah, that’s nice, but could you apply iterate to find the solution, as you had to compare the previous ones

orestis08:12:38

Nope. But it’s ok, because detect-loop is only 7 lines of code and uses next-cycle.

borkdude08:12:07

it’s what I thought too, iterate is nice, but I can’t use it. I also have a next-state fn

orestis08:12:46

I solved part 2 directly in the REPL; I love this.

orestis08:12:00

Of course, this only is possible because we have a small problem today — couldn’t do it with yesterday’s 20 million operations.

minikomi08:12:20

trying to think of a clever way to use take-while & iterate..

borkdude08:12:47

If you would only have to compare the last two solutions (as I initially thought) you could maybe do it like lazy fibonacci: https://en.wikibooks.org/wiki/Clojure_Programming/Examples/Lazy_Fibonacci

borkdude08:12:10

but now you have to be able to look back at all solutions and it breaks down

orestis08:12:53

I don’t think you can do it without a reduction over sequence…

minikomi09:12:17

(count
 (let [seen (volatile! #{})]
   (take-while #(and (not (@seen %))
                     (vswap! seen conj %))
               (iterate step [0 2 7 0]))))

minikomi09:12:17

wait, need to clip the head until the first repeat too

orestis09:12:52

Why volatile and not a transient?

orestis09:12:10

Hah! Now I got the and bit :)

minikomi09:12:57

transient also works.. not sure when to use which to be honest!

orestis09:12:37

A nice discussion there ^

minikomi09:12:35

yeah i did find that, but seems a bit unclear in the end. My takeaway was: if the value has IEditableCollection, go for transient unless you want to co-ordinate between multiple threads, in which case use volatile! for speed and atom if you need what atom brings.. sound accurate?

chrisblom09:12:53

i'd be careful with volatile! in a multithreaded context, as vswap! is not atomic, concurrent vswaps will give unreliable results

minikomi09:12:44

Ah, I misread: > Volatiles are faster than atoms but give up atomicity guarantees so should only be used with thread isolation.

chrisblom09:12:45

i think there was a check on volatiles to detect concurrent swaps, but they removed it to use it in transducers

minikomi09:12:37

ah, seems like: atoms - mutable, can be updated from multiple threads, guaranteed atomic volatiles - mutable, can be updated from multiple threads, but not atomic so be careful transients - mutable, require thread isolation

chrisblom09:12:22

yeah that sounds right, maybe the check was on transients, i don't remember

val_waeselynck09:12:04

I would rephrase this as: - atoms: slowest, no caution required - volatiles: faster, but avoid concurrent updates - transients (or any non-synchronized data structure such as java.util.HashMap): fastest, but don't update after sharing to other threads

minikomi09:12:35

if each thread is only, for example, updating a specific index on an array I think it's safe.. but you'd best know what you're doing

minikomi09:12:32

https://gist.github.com/minikomi/0bf7bedb64767a832be172c5b0767d1e Trying some things out, only the atom gives [1000 1000 1000 1000 1000] every time.

minikomi09:12:48

wow, atoms are cool.

chrisblom10:12:11

thats a good way to test it, but the transient example is incorrect

chrisblom10:12:11

you need to pass the result of transient operation around (for assoc!, dissoc! etc), like how you would use normal assoc

theeternalpulse10:12:12

I just sat down with pen and paper for day 3 and I think I have a breakthrough lol. Love the aha moments of an interesting problem.

minikomi10:12:43

So it's not really equivalent to atom/volatile, in that you have to reassign it or use it in, say, a reduction where it's explicitly the updated version which is being passed around?

(let [t (transient {})]
  (assoc! t :test 3)
  (assoc! t :banana 4)
  (persistent! t))
seems to work fine, but in some cases it might fail?

chrisblom10:12:55

yes, try this with like 1000 assoc! with different keys and see what happens

minikomi10:12:44

https://clojuredocs.org/clojure.core/assoc! ooh, the docs explain well. thanks for the tip!

chrisblom10:12:21

@minikomi this shows how it fails:

(let [t (transient {})]
  (dotimes [i 1000]
    (assoc! t i :test))
  (persistent! t))

minikomi10:12:08

nice! that's what i was looking for, yeah

chrisblom10:12:18

its because for small maps a (transient) array-map is used

chrisblom10:12:59

and for larger maps (> 10) it switches to a hash-map, so then assoc! returns a different object

minikomi10:12:44

thanks, learned something tonight 🙂 and now i go home

borkdude12:12:36

I thought I had a nicer solution with mapv for next-state but that doesn’t pan out

borkdude12:12:41

e.g. (next-state [0 1 2 3 6 4 5 0]) => [1 2 3 3 0 5 6 1] is hard to do with mapv, where you don’t have some state in the function

nooga12:12:02

mapv doesn’t cut the cases where your number is smaller than count-1

nooga12:12:29

looks like the redistribution has to be sequential

nooga12:12:44

I just found out 😄

borkdude12:12:55

Part 1 finishes in 63 ms on my machine

borkdude12:12:08

(without using transients or mutable arrays)

nooga13:12:29

completely instant on my machine in planck, so cljs

mfikes13:12:54

I'm at 260 ms (Planck, optimized code for elegance, readability over speed)

borkdude13:12:41

@mfikes I would if I could find a more elegant solution, but mapv didn’t work… curious about other solutions.

mfikes13:12:09

I'm cleaning up my code before committing, and then I'll dig into the backlog here 🙂

nooga13:12:47

how do I profile in planck?

mfikes13:12:05

@nooga I haven't hooked in any profiling tools, but ClojureScript has a simple-benchmark core fn. See, for example http://blog.fikesfarm.com/posts/2017-11-18-clojurescript-performance-measurement.html

nooga13:12:22

not too shabby

borkdude13:12:12

The a in advent stands for array

borkdude13:12:36

@nooga Cool! Without transients/mutable?

nooga13:12:01

@borkdude no tricks, plain and simple

nooga13:12:56

definately in the ballpark

nooga14:12:06

I’m running this in planck because I’m too lazy to lein new for this

nooga14:12:45

@mfikes could you share your input? for performance comparison?

mfikes14:12:42

My perf is around half a second

mfikes14:12:41

@borkdude I think I ended up with the same approach as Esther's

nooga14:12:14

now that’s peculiar: solve1: 157.606489msecs, solve2: 157.029896msecs

nooga14:12:35

So you’ve got harder input than me and @borkdude

mfikes14:12:28

@minikomi Yes, the behavior of max-key is crucial if you happen to use it in this problem. Documented in Clojure and pending for ClojureScript https://dev.clojure.org/jira/browse/CLJS-2403

mfikes14:12:09

I haven't use loop / recur yet in this year's solutions. (Probably to the detriment of ouright perf.)

minikomi14:12:23

Right, which is why I ended up rolling my own indexed-max

Miķelis Vindavs14:12:05

not sure if you’ve incorporated this into your optimized solutions, but

(defn max-ndx [banks] (.indexOf banks (apply max banks)))
seems to be quite a bit faster than
(defn max-ndx [v]
  (- (dec (count v))
     (apply max-key (vec (rseq v)) (range (count v)))))

minikomi14:12:04

nice. same concept, but neater than mine

Miķelis Vindavs14:12:09

first-max-pos can be optimized using reduce-kv

Miķelis Vindavs14:12:15

(defn first-max-pos'
  [nums]
  (reduce-kv (fn [[_ max-val :as m]
                  k cur-val]
               (if (> cur-val max-val)
                 [k cur-val] m))
             [0 0]
             nums))

Miķelis Vindavs14:12:26

runs 4-5x faster for me

minikomi14:12:56

faster than mine too?

Miķelis Vindavs14:12:10

sorry didn’t see yours, I’ll check

bhauman14:12:36

now to look at all the great stuff you guys have wrought

minikomi14:12:50

(.indexOf block max-val) is probably fastest! ahh

Miķelis Vindavs14:12:54

cljs.user=> (time (dotimes [_ 10000] (first-max-pos [1 2 3 4 6 1])))
"Elapsed time: 146.985052 msecs"

; with reduce-kv
cljs.user=> (time (dotimes [_ 10000] (first-max-pos' [1 2 3 4 6 1])))
"Elapsed time: 33.089442 msecs"

cljs.user=> (time (dotimes [_ 10000] (get-indexed-max [1 2 3 4 6 1])))
"Elapsed time: 68.978079 msecs"

; using .indexOf
cljs.user=> (time (dotimes [_ 10000] (max-i-and-val [1 2 3 4 6 1])))
"Elapsed time: 42.277618 msecs"

Miķelis Vindavs14:12:41

so reduce-kv is fastest

minikomi14:12:50

interesting

Miķelis Vindavs14:12:58

the indexOf solution has to go through the list twice

minikomi14:12:44

(defn get-indexed-max [memory-state]
  (loop [idx 0
         current-max [nil -1]] ;; no values below 0
    (if-let [v (get memory-state idx)]
      (recur (inc idx)
             (if (< (second current-max) v)
               [idx v]
               current-max))
      current-max)))
here was my first attempt

Miķelis Vindavs14:12:05

maybe if you get rid of the tuple allocations

minikomi14:12:25

max-idx, max-val?

bhauman14:12:26

my straightforward solutions run in the 100 - 200ms range without perf optimizations

bhauman14:12:27

@nooga which repo is yours?? or have you posted your answer?

nooga14:12:03

Nah, I type them into planck repl as I go so I have nothing to post on gh

nooga14:12:26

hm, one sec

bhauman14:12:35

thats cool, you could gist them out!

minikomi14:12:54

console.time()
var max_idx, max_val=-1;
for (i = 0; i < 10000; i++) {
arr.forEach(function(i,v) {
  if(v > max_val) {
    max_idx = i; max_val = v;
  }
})
}
console.timeEnd()
VM750:10 default: 22.593017578125ms

minikomi14:12:03

make of that what you will 😜

nooga14:12:25

https://repl.it/repls/AwareOutgoingWolverine but really, it’s nothing special imo

bhauman14:12:13

yeah but its still good to see 🙂 thanks for posting it

bhauman14:12:49

I think we could make an entire clojure workshop based around this type of stuff

nooga14:12:54

I don’t put much energy into this 😄

nooga14:12:27

Yeah, a friend of mine is learning clojure at the moment and I got him to solve AoC

bhauman14:12:28

I like it because I get to do something that is simply for enjoyment

nooga14:12:37

much better than hackerrank problems IMO

Miķelis Vindavs14:12:15

(defn loop-nth [xs]
  (let [size (count xs)]
    (loop [i 0
           maxi 0
           m 0]
      (if (< i size)
        (let [v (nth xs i)]
          (if (> v m)
            (recur (inc i) i v)
            (recur (inc i) maxi m)))
        [maxi m]))))
is some 10% faster than reduce-kv

mfikes14:12:29

Nice solutions @bhauman. Thanks for sharing!

mfikes14:12:06

AFAICT .indexOf and .lastIndexOf are so useful, that they were made to work in ClojureScript

bhauman14:12:36

oh cool! i didn't know this

mfikes14:12:46

Even crazy construct like (.indexOf (sequence (map inc) '(0 1 2 3 4)) 5) work in Clojure and ClojureScript

bhauman14:12:30

very very cool and good to know

mfikes14:12:46

If that's true, index-of and last-index-of could be things. :thinking_face:

bhauman14:12:27

well I can't wait for the next episode of AOC

nooga14:12:22

I was suprized when .indexOf worked both in clj and cljs

mfikes14:12:04

I was surprised that (merge-with + [0 1] {0 7 1 2}) produced a vector. I used it without thinking but then checked afterwards that this is true.

mfikes14:12:46

Perhaps I'm violating the expectations of merge-with, TBH, looking at its docstring.

borkdude15:12:53

@mikelis.vindavs I looked at reduce-kv but this won’t work: (first-max-pos' [-1 -2 -5]), so I stayed with the current

Miķelis Vindavs15:12:10

the inputs are always positive

borkdude15:12:46

@mikelis.vindavs oh. well, then it works, but only for this puzzle 😉

Miķelis Vindavs15:12:49

but it could be made to work with negative ones by providing a different initial value

borkdude15:12:50

@bhauman I didn’t think of perf optimizations when I wrote mine, but ended up at 63 ms (on JVM that is). Now let’s see if I understand yours.

borkdude15:12:31

ah, so it’s incrementing one by one

mfikes15:12:06

Hah, I could see another variation on this, where all solutions are submitted to a server which benchmarks and ranks them.

mfikes15:12:23

It seems you can optimize roughly for 3 things: 1. Get it done ASAP so you can get points 2. Write it elegantly so it is mantainable 3. Optimize the crap out of it

borkdude15:12:32

Added some printlns to @bhauman’s solution because I had trouble seeing what was going on, but now I get it:

start: [0 2 7 0]

acc i [0 2 0 0] 3
acc i [0 2 0 1] 0
acc i [1 2 0 1] 1
acc i [1 3 0 1] 2
acc i [1 3 1 1] 3
acc i [1 3 1 2] 0
acc i [2 3 1 2] 1
Clever, so it will loop 7 times updating each index by one, starting from the index after the max value

borkdude15:12:20

In my solution I maintained the invariant that the sum of elements should always remain constant, because I had a bug in it that increased the sum

bhauman15:12:38

that merge-with behavior is unexpected

bhauman15:12:33

@borkdude my redistribute version just duplicates the process specified

bhauman15:12:19

not much different than a loop, oh and I got it down to 93ms with transients but I don't see that as worth it

borkdude15:12:48

@bhauman Just for fun, I moved the (count …) to a let bound name, but it becomes slower, not faster … 🙂

bhauman15:12:39

yeah didn't expect much from that as count is a constant time look up

borkdude15:12:41

Probably it’s a neglectable thing and just co-incidence

bhauman15:12:20

yeah thats likely

bhauman15:12:43

although, moving the count to a let probably makes the alg more clear

borkdude15:12:49

cool, with find-max-pos the bhauman solution is even faster than mine: 56 ms

mfikes15:12:02

@bhauman Yeah, I've concluded it only accidentally works:

(merge-with (fn [_ x] x) [0 3] {0 7 1 2} {0 3 2 32})
and
(merge [0 3] {0 7 1 2} {0 3 2 32})
don't produce the same result.

Miķelis Vindavs15:12:23

can someone explain this to me? I don’t really get it

bhauman15:12:04

@mfikes is this because merge-with is exploiting a more general interface like get and assoc on the first collection?

bhauman15:12:59

yeah thats probably why

mfikes15:12:18

Yeah, but it is an abuse to rely on it.

mfikes15:12:26

I'm going to see if I can fix my solution.

Miķelis Vindavs15:12:50

ah it’s just treating it as an associative collection, just like (assoc [:a :b :c] 1 :x) works

Miķelis Vindavs15:12:10

interesting that (merge-with + [10 11 12 13] [100 101 102 103]) doesn’t work but (merge-with + [10 11 12 13] {0 100 1 101 2 102 3 103}) does

Miķelis Vindavs15:12:25

when dynamic typing and implementation details meet

mfikes15:12:24

Well, since I want to treat the memory banks as associative and have it work with merge-with, I'm going to use maps instead of vectors.

bhauman16:12:36

that'll do it

borkdude21:12:53

Found a slight variation on bhauman’s next-state:

(defn redistribute [block]
  (let [[position max-val] (first-max-pos block)
        length (count block)]
    (reduce (fn [block [p v]]
              (update block p
                      + v))
            (assoc block position 0)
            (->> (range (inc position)
                        (+ (inc position) max-val))
                 (map #(mod % length))
                 frequencies))))

mfikes22:12:58

Hah, I recognize this approach 🙂

mfikes22:12:19

This was where the desire to use (merge-with + on a vector came from. (To avoid an explicit reduce.)

borkdude21:12:12

The original bhauman version is twice as fast though! Provided that you use first-max-pos.. 40 ms now on my machine

borkdude21:12:07

Ah, I see mfikes’ solution now, also used frequencies.

Miķelis Vindavs21:12:14

It’s an interesting solution with frequencies, but if focusing on perf, isn’t generating a whole sequence just to squash it down kinda slow vs just adding (quot n-to-distribute num-banks) and then figuring out where to put the rest ?

Miķelis Vindavs21:12:48

it’s rather elegant though

grzm21:12:19

wow. @bhauman’s is really nice and terse, and a good example of using reduce to avoid a loop.

mfikes22:12:33

Yeah, his solution is close to what I would consider "art" 🙂