Clojurians Log v2

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

Solved it, but no real insights for today

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

@borkdude same thing, a bit disappointed 🙂

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

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.

I just love this:

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

ah, that's nice

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

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

It’s only ~13k steps for me…

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

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

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

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

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

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

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

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

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

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

lol

:shipit:

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

Why volatile and not a transient?

Hah! Now I got the and bit :)

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

https://stackoverflow.com/questions/31288608/what-is-clojure-volatile

A nice discussion there ^

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?

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

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

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

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

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

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

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

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

wow, atoms are cool.

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

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

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.

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

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

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

@minikomi this shows how it fails:

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

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

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

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

right

thanks, learned something tonight 🙂 and now i go home

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

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

yeah

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

looks like the redistribution has to be sequential

I just found out 😄

Part 1 finishes in 63 ms on my machine

(without using transients or mutable arrays)

completely instant on my machine in planck, so cljs

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

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

I find this a creative way of finding part 2: https://github.com/EsthervdS/AdventOfCode/blob/master/day6/Reallocation.java#L52

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

how do I profile in planck?

@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

hm

not too shabby

The a in advent stands for array

@nooga Cool! Without transients/mutable?

@borkdude no tricks, plain and simple

@nooga Can you try my input for comparison? https://github.com/borkdude/aoc2017/blob/master/resources/day6.txt

sure

definately in the ballpark

nice

My solutions committed https://github.com/mfikes/advent-of-code/blob/master/src/advent_2017/day_06.cljc

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

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

https://github.com/mfikes/advent-of-code/blob/master/resources/advent_2017/day_06/input

My perf is around half a second

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

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

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

@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

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

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

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

(defn max-ndx [banks] (.indexOf banks (apply max banks)))

(defn max-ndx [v]
  (- (dec (count v))
     (apply max-key (vec (rseq v)) (range (count v)))))

@minikomi me too: https://github.com/borkdude/aoc2017/blob/master/src/day6.clj#L14

nice. same concept, but neater than mine

https://github.com/minikomi/advent-of-code/blob/master/src/advent/2017/day6.clj#L9-L17

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

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

runs 4-5x faster for me

faster than mine too?

just commited mine https://github.com/bhauman/advent-of-clojure-2016/blob/master/src/advent_of_clojure_2017/day06.clj

sorry didn’t see yours, I’ll check

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

@minikomi yes

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

good one

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"

so reduce-kv is fastest

interesting

the indexOf solution has to go through the list twice

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

maybe if you get rid of the tuple allocations

@mikelis.vindavs TIL. I suppose it is meant to be a stable / public part of the API: https://github.com/clojure/clojurescript/blob/3b3db232711266f9f41c94c777084664d6d0b71b/src/test/cljs/cljs/seqs_test.cljs#L131-L147

max-idx, max-val?

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

without

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

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

😄

hm, one sec

thats cool, you could gist them out!

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

make of that what you will 😜

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

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

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

I don’t put much energy into this 😄

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

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

perfect!

much better than hackerrank problems IMO

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

Nice solutions @bhauman. Thanks for sharing!

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

oh cool! i didn't know this

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

very very cool and good to know

I wonder if these test imply that they are stable / public https://github.com/clojure/clojurescript/blob/3b3db232711266f9f41c94c777084664d6d0b71b/src/test/cljs/cljs/seqs_test.cljs#L131-L168

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

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

could be

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

Thanks for the tip @mikelis.vindavs, I've incorporated it https://github.com/mfikes/advent-of-code/blob/master/src/advent_2017/day_06.cljc

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.

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

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

the inputs are always positive

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

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

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

ah, so it’s incrementing one by one

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

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

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

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

that merge-with behavior is unexpected

@borkdude my redistribute version just duplicates the process specified

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

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

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

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

yeah thats likely

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

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

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

(merge-with (fn [_ x] x) [0 3] {0 7 1 2} {0 3 2 32})

(merge [0 3] {0 7 1 2} {0 3 2 32})

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

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

yeah thats probably why

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

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

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

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

when dynamic typing and implementation details meet

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.

that'll do it

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

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

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

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 ?

it’s rather elegant though

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

@grzm I agree

Hah, I recognize this approach 🙂

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

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

geez guys

thanks