Clojurians Log v2

I ended up using loop, but had to use trampoline due to stack overflows: https://github.com/baritonehands/advent-of-code-2018/blob/master/src/aoc/dec8.clj

02

Just don't try 08; that will cause an issue.

performance matters now ⏩

Yeah, my solution took 5 min to run, so 100x would be 8h

100x is ~5h for me

must be missing some intuition, there are people that solved both parts in less than 10m :thinking_face:

probably just gonna go to sleep and let it run haha

Does the given test case “13 players; last marble is worth 7999 points: high score is 146373” run for you guys? That’s the only one that fails for me 😮

I often have the experience of writing a slow solution and while it is running I write a faster solution that finishes before the first one did. This time while the second solution was running, I wrote a third solution that finishes even faster. And it’s a good thing too, because I realized, 20 minutes into running the second solution, that I used the wrong number as an input

@meikemertsch advent2018.day9> (time (part2c 13 7999)) “Elapsed time: 30.633133 msecs” 146373

I got the same answer in 1199ms

fudge 🙈 now I have no clue why that one doesn’t work but all others do

1.6 secs for running all five cases :thinking_face:

are you using persistent vectors?

No - I wrote a double-linked circular list out of volatiles. I feel dirty

nice

I'm using clojure.data.finger-tree but still takes 3.4m for part1

part 1 is now 83s for me using vanilla vectors

i was mistaken:

(time (part-1))
"Elapsed time: 924.570809 msecs"
388024

forgot to change reduce conj by finget-trees/ft-concat

for part1 I used a naive vector approach. That was too slow , so then I used an ArrayList. That was much much faster, but still slow. So then I hacked together the circular list real fast. I can’t think of any way to do this efficienttly with a persistent data structure.

(time (part-2))
"Elapsed time: 82914.062071 msecs"
3180929875

minute and some for part-2

Do you have an easy way to print out the removed values for that case?

https://pastebin.com/CvYTZnD9 is mine if you get stuck and want to compare later

https://github.com/Average-user/adventofcode-clj-2018/blob/master/src/adventofcode_clj_2018/day09.clj

Hmm, I was wondering if a tree would be a better structure for arbitrary insertion / deletion. I'd heard good things about finger trees, it seems I should pay more attention to them.

My attempt to use a straight Java Linked List did not fare well. In the end, I hopped over to straight Java and got pretty much instantaneous results. So I need to figure out where on earth I'm going wrong to get such poor performance. I think I cut out a great deal of potential reflection slowdown, so not sure what's up.

my solution to part 1 is so slow 😢

@taylor in the same boat as you i see 😄

Transients and subvec reduced my part1 by 10x

@baritonehands yeah, good advice. I got to a speedup but my code still takes ~1 minute to run (70k marbles, 400 players)

@baritonehands what kind of execution time you had for part 1 ?

718902 msecs for part one 😂 I have plenty of ideas how to make it better though

OMG the start of the next part is “Amused by the speed of your answer” 😂 :rolling_on_the_floor_laughing:😂 :rolling_on_the_floor_laughing:😂 :rolling_on_the_floor_laughing:😂 :rolling_on_the_floor_laughing:😂 :rolling_on_the_floor_laughing:😂 :rolling_on_the_floor_laughing:😂 :rolling_on_the_floor_laughing:😂 :rolling_on_the_floor_laughing:😂 :rolling_on_the_floor_laughing:😂 :rolling_on_the_floor_laughing:😂 :rolling_on_the_floor_laughing:😂 :rolling_on_the_floor_laughing:😂 :rolling_on_the_floor_laughing:😂 :rolling_on_the_floor_laughing:😂 :rolling_on_the_floor_laughing:😂 :rolling_on_the_floor_laughing:

Even for java there was no collection in the standard I could found for solving the second one.

I used ArrayDeque both O(1) for head and tail manipulation.

java.util.ArrayDeque 🙂

i knew using lists for part 1 was silly but did not expect "Elapsed time: 527892.857699 msecs"

I ended up writing my own circular linked list implementation (after trying with regular lists and being waaaay too slow)

with that and after fixing some reflection call sites it's a comfortable 120ms for part 1 and 16sec for part 2

can't really do a doubly linked or circularly linked list that is functional though AFAIK so it's not a persistent data structure

https://github.com/plexus/advent-of-code/blob/master/src/advent2018/day9.clj

I get a boxed math warning on (- current-idx 7) where current-idx is a loop variable starting with 0. but when I place a type hint it says: can’t type hint primitive local. what does it want…

borkdude try [current-idx (long ...)] instead of [^long current-idx ...]

same thing: https://www.dropbox.com/s/i49vgj4n8aoazyx/Screenshot%202018-12-09%2013.25.41.png?dl=0

strange... from https://clojure.org/reference/java_interop#typehints

> (let [foo (int bar)] …​) is the correct way to get a primitive local. Do not use ^Integer etc.

Maybe put a (let [current-idx (long current-idx)] inside the loop?

that works. strange that I need this?

It kind of makes sense if you think of it, if you put it in the loop [] it knows it will be a long in the first iteration, but you can recur something else later

you can, but like with function arguments, the type hint is an invariant?

I guess you'll have to ask Rich... or dive into the compiler source 🙂

does that ^long (mod marble 23) make a difference? I thought type hints only worked on symbols...

this type hinting stuff remains a black art to me... adding tags left and right until the warnings go away 🙂

yes

same here. I usually only need this in advent of code..

I recently learned tags can also be strings, so you can do stuff like this ^"[Ljava.lang.String;"

i.e. "array of string"

now it starts to make sense:

(defn foo []
  (loop [current-idx (long 0)]
    (- current-idx 7)
    #_(recur nil)))

ok, down to 45 secs for part one and out of ideas :thinking_face:

I trying to switch to java.util.LinkedList but I'm not able to call the remove(int index) method. It keeps calling the remove(Object o) method. Any ideas?

My hunch is when it says: now do it x100 and it already takes long, that there might be some mathematical regularity you can take advantage of

just found out that using mapv instead of map on long lists give 6x speed gain 😕 (still optimizing day 6 and made 550ms instead of 3500ms)

I implemented a doubly circularly linked list, perhaps almost same as @plexus's and it takes ~5sec for part 2 https://github.com/athos/advent-of-code-2018/blob/master/src/advent_of_code_2018/day09.clj

My solution for Day 9: https://github.com/benfle/advent-of-code-2018/blob/master/day9.clj

Using zippers. Ended up at 17s for part 2.

interesting to see that zippers have similar performance to the custom data structure of plexus

My code got 1.7x faster by making it a little bit more branch prediction friendly 🙂

I really like @mfikes day 8 solution -- using the argument list as a stack in a shift reduce parser. A new trick to add to the bag-o-tricks.

strange, when running in the repl with time my part 2 now takes about 9 sec, running script/test-one it's about 23 sec.

Yeah I never would’ve thought to try zippers even though I try them in more unusual situations. Very cool

@drowsy maybe because your REPL has a warmed up JVM? wild guess. what if you run the code multiple times in the test wrapped in a time?

https://github.com/taylorwood/advent-of-code/blob/master/src/advent_of_code/2018/9.clj here’s my day 9

A little bummed the last few days problems don’t lend themselves to visualization

Guess I could visualize a much smaller game of elf marbles

I have the outcome for part 1 but didn’t look at the data. Why doesn’t it lend itself to visualization?

adding 4 (time (solve-2)) to the test brings the second run down a bit (about 20sec), but than it improves no further.

what are you using to run the REPL, tools.deps or lein?

tools.deps

what if you use clojure.test/deftest with your own time call around the code?

but actually cursive, so I'm not sure how the repl is started exaclty

I was just thinking there are so many players and marbles it’d just be tiny pixels to look at

(time (part-2)) is fast in the REPL as well

I mean use clojure.test/deftest instead of aoc.utils/deftest to exclude the possibility that it is my test macro

did you turn on unchecked math or anything?

yeah I did

maybe you didn’t turn it on in the tests

well, it's in top of the file

i'm playing with java.util.LinkedList which has remove(int) and remove(object) overloaded methods it's always invoking the second, but i want the first, what can i do?

trying (.remove lst 1) to remove element at index 1

but end up removing element with value 1 from the list, if it exists

can you try with binding around the test body?

docs are here https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

I asked this in #clojure and it seems you have to typehint the list itself in the call.

cool, that works

weird solution though 🙂

and i need to typehint the index

I saw a really fast Clojure solution using linked list

So it's not your macro and binding doesn't help. I will have a look at the flight-recorder

i wanted to make my own list but don't have much time now so doing this

oh wait.... it's not even the same jvm. The REPL is running on a oracle jdk 8 on windows while the test script is an open jdk 10 on the linux subsystem.

To be fair my solution is completely unoptimized outside of the custom data structure.

Wow, I feel happy that I reached for a vector zipper first. I figured it’d be slower than another solution but more convenient. Little did I know...

zippers! i forgot about those.

damn, now i have ideas for v4 and v5 of todays task 😄

I ended up just using two lists and no fancy mutable stuff. https://github.com/IamDrowsy/advent-of-cljc/blob/master/src/aoc/y2018/d09/iamdrowsy.cljc

😮

that's just like my deque idea, but with lists

how long does it run for?

this is somewhat strange 🙂 no an openjdk 10 it's around 18 secs, in my repl running a oracle jvm 8 it's about 8 secs. So maybe it's a bit stressfull for the GC?

oh wow. On @borkdude circleCI the clojurescript version evens kills the vm because it's out of heap... maybe I need to do some tweaks

Day 9: https://github.com/mfikes/advent-of-code/blob/master/src/advent_2018/day_09.cljc

sorted-map works quickly?

For part 1, it takes 566 ms, for part 2 maybe a minute or so

Part 2 is 90 seconds

Wow we got the exact same puzzle inputs

Fingertree(immutable) impl performs pretty good compared to java.util.ArrayDeque. Impressive! https://gist.github.com/namenu/402b46c61e385c801cdb4c150c3e4cd6

I got to 7s for part two with custom data structure: https://github.com/benfle/advent-of-code-2018/blob/master/day9_alt.clj

Originally 300+ seconds, 30+ after

I'm finding Day 9 very hard - not to get the right result but to get Part 2 to complete in time. My algorithm's time complexity is not good enough

what am I missing ?!

Oops, I had written mine in ClojureScript, and while it was working in Clojure, it was using rationals. Switching to doubles dropped part two to 30 seconds.

I have two impls, one based on PersistentVector and one based on sorted-map: https://github.com/pesterhazy/advent2018/blob/master/src/advent/puzzle09.clj#L7

sorted-map is slightly faster but still takes 100+ s for Part 1 - I can't even dream of trying Part 2

@pesterhazy Mine is sorted map as well; taking a look at yours

do you have a gentle hint for me @mfikes?

@pesterhazy I have to run out for a while, but quickly scanning through your solution, I don't see use of subseq. I was using that to find nearby indices (and rsubseq to find one 7 back)

lol, my second one now runs faster then the first one

@mfikes d'oh!

my naive pure clojure vector based solutions runs in 85 seconds for part 1. I tried https://github.com/clojure/core.rrb-vector but got an index out of bounds exception with it

The main idea of the sorted-map approach is: Use it as a poor man's mutable linked list. To insert and remove you assoc and dissoc, and to navigate forward and back, subseq and rsubseq. And Paulus and I have the same indexing strategy: Use doubles as your index and use midpoint to insert a marble between.

https://github.com/gklijs/advent_of_code_2018/blob/master/Gerard/src/main/java/com/gklijs/adventofcode/day9/MarbleGame.java

This was the first problem where I had to resort to transducers to bypass ClojureScript's head holding / lack of locals clearing.

(There were several of those last year.)

If you're curious, it is specifically this use of nth' here https://github.com/mfikes/advent-of-code/blob/master/src/advent_2018/day_09.cljc#L41 Otherwise regular nth holds head on the iterated sequence.

Ok here's my complete Day 09: https://github.com/pesterhazy/advent2018/blob/master/src/advent/puzzle09.clj#L38

solution-2 takes 37s

a far from the estimated 12h+ of my first PersistentVector approach

@mfikes thanks so much for getting me unstuck by mentioning subseq and especially rsubseq — these are functions I genuinely didn't know about (well I heard them mentioned here a few days ago but promptly forgot)

using doubles as indices works well but honestly we were lucky that we didn't reach the point where floating-point precision prevents squeezing in new positions

This fixed itself when I type-hinted the list as a ^java.util.LinkedList and the remove method argument as an int.

I'm very curious about what datastructures other JVm based solutions use

Got 58ms and 6864ms with my own transient map based linked list:

defn ll-init [n]
  (let [node (transient {:value n})]
    (assoc! node :next node)
    (assoc! node :prev node)
    node))

(defn ll-insert [{:keys [next] :as root} n]
  (let [node (transient {:value n})]
    (assoc! node :next next :prev root)
    (assoc! next :prev node)
    (assoc! root :next node)
    node))

(defn ll-remove [{:keys [next prev value] :as node}]
  (assoc! next :prev prev)
  (assoc! prev :next next)
  [next (:value node)])

(defn ll-nth [node idx]
  (nth (iterate (if (neg? idx) :prev :next) node) (Math/abs (int idx))))

Hm, aren't you supposed to close transients by calling persistent!?

Thanks for mentioning Deque, wasn't aware of that. Did you end up using a Deque? Isn't it necessary to insert marbles at arbitrary positions, not just at head or tail?

very cool

Is that always necessary? They won’t just get cleaned up when I forget the reference?

Only if you want a persistent I guess

The docs say, > Note in particular that transients are not designed to be bashed in-place. You must capture and use the return value in the next call.

I store the return value in a seq

https://github.com/baritonehands/advent-of-code-2018/blob/master/src/aoc/dec9.clj

I can't believe how simple day9 can be with a good Deque implementation: https://www.reddit.com/r/adventofcode/comments/a4i97s/2018_day_9_solutions/ebepyc7/

Transients still worked for me, maybe because they were all of size 3? I would assume they change reference when the implementation changes at a certain size boundary

Reading up on deque, you can write rotate easily by popping on one side and pushing on the other - that should work with Java's ArrayDeque as well

I wonder if a PersistentDeque would be feasible?

I promise I won't read spoilers

@pesterhazy I do something like that. The rotate is implemented with ft-split-at from clojure.data.finger-trees

https://github.com/Average-user/adventofcode-clj-2018/blob/master/src/adventofcode_clj_2018/day09.clj

pjstadig has a persistent Deque implementation: https://github.com/pjstadig/deque-clojure/blob/master/src/name/stadig/deque/protocol.clj#L16

@lucaspolymeris nice - how long does it take to answer part 2?

@pesterhazy Thanks for the link to dequeue. I forgot about this one. That seems like the right data structure for the problem, yes.

Not very fast 1m aprox

What would be the gain against finger-tree?

that's still pretty good for a pure solution!

my sorted-set approach takes ~30s

Do have the link? Is it pure?

No idea. I never took the time to look at finger trees. Maybe I should. But for this problem deque's complexity properties seem appropriate.

And more importantly it makes the solution pretty clear. I tried to something similar w/ my solution but zippers require a rewinding that is not very elegant. And then my custom data structure is pretty specific to the problem so not great either 🙂

R u going to implement the dequeue one? I'm interested to compare times with finger trees

So if u do, could you please share it?

Yeah it's pure https://github.com/pesterhazy/advent2018/blob/master/src/advent/puzzle09.clj#L78

Using the java.util.LinkedList which implements java.util.Deque I'm getting between 2 and 3 seconds.

Mine is essentially the same and is also ~30s

But those r not pure i suppose

I got 33ms, after a lot of iterations, with Java

@gklijs For part 2?

Yes, the first one runs almost 100 times faster.

33ms part 2? you guys are killing me :harold:

Which has been your favourite day so far?

Day 7! It left me singing and dancing

@gklijs The "history" trick is neat.

With Java data structures (Deque and long array to keep scores). I'm done with this problem 🙂 https://github.com/benfle/advent-of-code-2018/blob/master/day9_alt2.clj

m

Today’s. I built a data structure just for it I was proud of 😄

My conclusions after (a very long) day 09: https://github.com/pesterhazy/advent2018/blob/master/journal.md#day-09

@gklijs is your solution available online?

lots of solutions here

I made a mutable doubly-linked circular list

looks pretty much like the python solution

that @pesterhazy posted

Nice solution in Java: https://www.reddit.com/r/adventofcode/comments/a4i97s/2018_day_9_solutions/ebetdc5/

If I only knew the word “deque”

oh well, had fun making my own 🙂

I’m at 20ms for p1, 9s for p2

lots of obvious waste to trim

@potetm same here: zip -> own deque -> java deque 🙂

pure clojure using deftype w/ mutable fields

yeah I bet java deque is sig better 🙂

you see a sig timing dif @me1740?

16 s -> 7 s -> 1s roughly

😕 yeah I guess java deque is next for me

Interestingly the timing w/ Java data structure seem to vary much more than the Clojure data structures. I'm not familiar enough w/ the internals of either to explain why.

mine varies quite a bit actually

no idea why

as short as 2s, as long as 10

GC I presume

very odd

Yeah the difference seems big

"Elapsed time: 8461.775695 msecs"
=> [344 3038972494]
"Elapsed time: 11364.651846 msecs"
=> [344 3038972494]
"Elapsed time: 2761.024937 msecs"
=> [344 3038972494]
"Elapsed time: 9324.289621 msecs"
=> [344 3038972494]
"Elapsed time: 3111.038354 msecs"
=> [344 3038972494]

:man-shrugging:

This one takes 2.3s for p2: https://www.reddit.com/r/adventofcode/comments/a4i97s/2018_day_9_solutions/ebetdc5/

yeah but they cheated

perf enhancing drugs

:troll:

New talk idea: “Mutation is a performance enhancing drug.”

lol, i did that same thing in clojure https://git.sr.ht/%7Eihabunek/aoc2018/tree/master/clojure/src/aoc2018/day09.clj

my excuse: i was going for a functional solution but it was too slow and i wanted to have a solution today 😄

Has anyone built a rotate-based solution based on core.rrb-vector?

My slightly optimized persistent vector solution was going to run for about 4 or 5 hours. Then I switched to finger tree at recommendation in this channel

I figure you can easily build a rotate operation on top of core.rrb-vector, getting two subvec from the right place, and then doing a catvec on them. Maybe that would be O (log n) ...

Damn, core.rrb-vector is broken. You get ClassCastExceptions deep down in its implementation. This code works if you comment the core.rbb-vector and uncomment the regular Clojure persistent vector calls. https://github.com/mfikes/advent-of-code/blob/day-9-rotate/src/advent_2018/day_09.cljc

That's unfortunate... the core.rrb-vector implementation works for (play 9 25), but not for larger problems, where it starts to crap out.

So, the fastest pure solution, using non-custom data structures is still sorted-map? Dang! I was hoping this core.rrb-vector approach would be fast, pure, and fairly idiomatic (and non-custom).