This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2018-12-09
Channels
- # adventofcode (229)
- # announcements (1)
- # beginners (9)
- # boot (1)
- # calva (11)
- # cider (14)
- # clojure (26)
- # clojure-kc (1)
- # clojurescript (46)
- # core-async (10)
- # cursive (6)
- # datomic (53)
- # figwheel-main (2)
- # fulcro (3)
- # hoplon (2)
- # hyperfiddle (1)
- # kaocha (2)
- # off-topic (11)
- # om (5)
- # quil (11)
- # re-frame (7)
- # reagent (6)
- # reitit (9)
- # shadow-cljs (9)
- # spacemacs (5)
- # vim (5)
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
Yeah, my solution took 5 min to run, so 100x would be 8h
must be missing some intuition, there are people that solved both parts in less than 10m :thinking_face:
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
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.
This is what actually happened with one of the Voyager spacecraft, right? (They launched it and years later developed better data compression algorithms, which let the images be sent back in reasonable time even though there was a comms channel slowdown due to a defective antenna or such.)
@meikemertsch advent2018.day9> (time (part2c 13 7999)) “Elapsed time: 30.633133 msecs” 146373
fudge 🙈 now I have no clue why that one doesn’t work but all others do
https://pastebin.com/CvYTZnD9 is mine if you get stuck and want to compare later
I think I know why. Funnily enough my solution still worked on the input data :shocked_face_with_exploding_head:
Yeah. I was wrong in calculating the new positions. I didn’t consider an important edge case
1.6 secs for running all five cases :thinking_face:
I'm using clojure.data.finger-tree but still takes 3.4m for part1
i was mistaken:
(time (part-1))
"Elapsed time: 924.570809 msecs"
388024
forgot to change reduce conj by finget-trees/ft-concat
(time (part-2))
"Elapsed time: 82914.062071 msecs"
3180929875
minute and some for part-2
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.
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 ?
Originally 300+ seconds, 30+ after
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.
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?
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
very cool
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…
same thing: https://www.dropbox.com/s/i49vgj4n8aoazyx/Screenshot%202018-12-09%2013.25.41.png?dl=0
> (let [foo (int bar)] …) is the correct way to get a primitive local. Do not use ^Integer etc.
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
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 🙂
I recently learned tags can also be strings, so you can do stuff like this ^"[Ljava.lang.String;"
now it starts to make sense:
(defn foo []
(loop [current-idx (long 0)]
(- current-idx 7)
#_(recur nil)))
you don’t get the boxed math warning if you remove the recur, so it has to do with thatok, 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?
This fixed itself when I type-hinted the list as a ^java.util.LinkedList
and the remove method argument as an int
.
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
interesting to see that zippers have similar performance to the custom data structure of plexus
To be fair my solution is completely unoptimized outside of the custom data structure.
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?
adding 4 (time (solve-2))
to the test brings the second run down a bit (about 20sec), but than it improves no further.
I mean use clojure.test/deftest
instead of aoc.utils/deftest
to exclude the possibility that it is my test macro
So it's not your macro and binding doesn't help. I will have a look at the flight-recorder
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.
https://github.com/taylorwood/advent-of-code/blob/master/src/advent_of_code/2018/9.clj here’s my day 9
I have the outcome for part 1 but didn’t look at the data. Why doesn’t it lend itself to visualization?
I was just thinking there are so many players and marbles it’d just be tiny pixels to look at
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?
I asked this in #clojure and it seems you have to typehint the list itself in the call.
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...
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
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
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
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)
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.
This was the first problem where I had to resort to transducers to bypass ClojureScript's head holding / lack of locals clearing.
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
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!
?
Is that always necessary? They won’t just get cleaned up when I forget the reference?
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?
@pesterhazy I do something like that. The rotate is implemented with ft-split-at from clojure.data.finger-trees
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?
Not very fast 1m aprox
that's still pretty good for a pure solution!
my sorted-set approach takes ~30s
Do have the link? Is it pure?
Yeah it's pure https://github.com/pesterhazy/advent2018/blob/master/src/advent/puzzle09.clj#L78
@pesterhazy Thanks for the link to dequeue. I forgot about this one. That seems like the right data structure for the problem, yes.
What would be the gain against finger-tree?
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?
Using the java.util.LinkedList
which implements java.util.Deque
I'm getting between 2 and 3 seconds.
But those r not pure i suppose
Which has been your favourite day so far?
Day 7! It left me singing and dancing
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
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?
that @pesterhazy posted
Nice solution in Java: https://www.reddit.com/r/adventofcode/comments/a4i97s/2018_day_9_solutions/ebetdc5/
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.
"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]
This one takes 2.3s for p2: https://www.reddit.com/r/adventofcode/comments/a4i97s/2018_day_9_solutions/ebetdc5/
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 😄
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 ClassCastException
s 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.