Fork me on GitHub
#adventofcode
<
2018-12-09
>
baritonehands01:12:40

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

theeternalpulse02:12:03

02

0️⃣ 4
2️⃣ 4
mfikes02:12:39

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

taylor06:12:25

performance matters now

baritonehands07:12:49

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

taylor07:12:13

100x is ~5h for me

taylor07:12:11

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

taylor07:12:26

probably just gonna go to sleep and let it run haha

meikemertsch07:12:57

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 😮

norman07:12:58

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

taylor07:12:39

are you using persistent vectors?

norman07:12:53

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

norman07:12:34

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.

mfikes16:12:00

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

norman07:12:23

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

meikemertsch07:12:31

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

norman07:12:57

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

norman07:12:46

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

meikemertsch08:12:52

I think I know why. Funnily enough my solution still worked on the input data :shocked_face_with_exploding_head:

meikemertsch08:12:42

Yeah. I was wrong in calculating the new positions. I didn’t consider an important edge case

taylor07:12:16

I got the same answer in 1199ms

meikemertsch07:12:07

1.6 secs for running all five cases :thinking_face:

Average-user07:12:59

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

taylor07:12:18

part 1 is now 83s for me using vanilla vectors

Average-user07:12:54

i was mistaken:

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

Average-user07:12:33

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

Average-user07:12:15

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

Average-user07:12:28

minute and some for part-2

fellshard07:12:25

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.

fellshard08:12:43

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.

helios08:12:15

my solution to part 1 is so slow 😢

helios08:12:29

@taylor in the same boat as you i see 😄

baritonehands08:12:38

Transients and subvec reduced my part1 by 10x

helios08:12:24

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

helios08:12:38

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

baritonehands16:12:40

Originally 300+ seconds, 30+ after

meikemertsch08:12:23

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

meikemertsch08:12:52

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:

😭 4
gklijs09:12:49

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

namenu10:12:29

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

☝️ 4
namenu10:12:47

java.util.ArrayDeque 🙂

pesterhazy18:12:27

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?

ihabunek11:12:18

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

plexus12:12:13

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

plexus12:12:25

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

plexus12:12:46

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

borkdude12:12:12

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…

plexus12:12:01

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

plexus12:12:52

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

plexus12:12:33

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

borkdude12:12:13

that works. strange that I need this?

plexus12:12:50

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

borkdude12:12:01

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

plexus12:12:39

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

plexus12:12:40

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

plexus12:12:30

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

borkdude12:12:49

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

plexus12:12:20

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

plexus12:12:28

i.e. "array of string"

borkdude12:12:57

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 that

meikemertsch12:12:13

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

drowsy13:12:19

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?

fellshard18:12:10

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

borkdude13:12:51

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

genmeblog13:12:32

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)

athos13:12:15

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

benoit13:12:50

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

👍 16
borkdude13:12:21

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

plexus15:12:11

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

athos13:12:28

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

rmprescott14:12:13

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.

drowsy14:12:55

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.

taylor14:12:19

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

borkdude14:12:01

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

drowsy14:12:54

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

borkdude14:12:28

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

drowsy14:12:36

tools.deps

borkdude14:12:08

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

drowsy14:12:09

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

drowsy14:12:02

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

borkdude14:12:13

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

borkdude14:12:43

did you turn on unchecked math or anything?

drowsy14:12:59

yeah I did

borkdude14:12:12

maybe you didn’t turn it on in the tests

drowsy14:12:42

well, it's in top of the file

borkdude14:12:11

can you try with binding around the test body?

drowsy14:12:11

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

drowsy15:12:56

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.

taylor14:12:38

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

taylor14:12:27

Guess I could visualize a much smaller game of elf marbles

borkdude14:12:45

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

taylor14:12:37

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

ihabunek14:12:42

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?

ihabunek14:12:57

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

ihabunek14:12:05

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

drowsy14:12:55

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

ihabunek14:12:29

cool, that works

ihabunek14:12:36

weird solution though 🙂

ihabunek14:12:39

and i need to typehint the index

taylor14:12:27

I saw a really fast Clojure solution using linked list

ihabunek14:12:36

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

mattly15:12:31

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

ihabunek15:12:11

zippers! i forgot about those.

ihabunek15:12:30

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

ihabunek15:12:39

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

ihabunek15:12:43

how long does it run for?

drowsy15:12:46

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?

drowsy15:12:39

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

taylor16:12:21

Wow we got the exact same puzzle inputs

ihabunek15:12:45

sorted-map works quickly?

mfikes15:12:09

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

mfikes15:12:29

Part 2 is 90 seconds

namenu16:12:24

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

pesterhazy16:12:55

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

pesterhazy16:12:11

what am I missing ?!

mfikes16:12:51

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.

pesterhazy16:12:16

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

pesterhazy16:12:57

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

mfikes16:12:26

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

pesterhazy16:12:30

do you have a gentle hint for me @mfikes?

mfikes16:12:40

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

gklijs16:12:50

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

borkdude16:12:48

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

mfikes17:12:51

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.

mfikes17:12:15

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

mfikes17:12:40

(There were several of those last year.)

mfikes17:12:43

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.

pesterhazy18:12:20

solution-2 takes 37s

pesterhazy18:12:21

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

pesterhazy18:12:38

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

pesterhazy18:12:54

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

pesterhazy18:12:28

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

baritonehands18:12:40

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

pesterhazy18:12:46

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

baritonehands18:12:03

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

borkdude18:12:21

Only if you want a persistent I guess

pesterhazy18:12:31

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.

baritonehands18:12:10

I store the return value in a seq

pesterhazy18:12:49

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/

☝️ 8
baritonehands19:12:30

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

pesterhazy19:12:50

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

pesterhazy19:12:23

I wonder if a PersistentDeque would be feasible?

misha19:12:02

I promise I won't read spoilers

Average-user19:12:05

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

pesterhazy19:12:57

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

Average-user19:12:41

Not very fast 1m aprox

pesterhazy19:12:26

that's still pretty good for a pure solution!

pesterhazy19:12:38

my sorted-set approach takes ~30s

Average-user19:12:22

Do have the link? Is it pure?

mfikes20:12:21

Mine is essentially the same and is also ~30s

benoit19:12:20

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

Average-user19:12:22

What would be the gain against finger-tree?

benoit19:12:32

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.

benoit19:12:17

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 🙂

Average-user19:12:18

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

Average-user19:12:34

So if u do, could you please share it?

benoit20:12:40

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

Average-user20:12:45

But those r not pure i suppose

gklijs20:12:04

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

🤯 4
👍 4
gklijs20:12:22

Yes, the first one runs almost 100 times faster.

misha20:12:28

33ms part 2? you guys are killing me harold

Average-user20:12:29

Which has been your favourite day so far?

meikemertsch20:12:04

Day 7! It left me singing and dancing

potetm21:12:43

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

4
party-corgi 8
benoit20:12:50

@gklijs The "history" trick is neat.

benoit20:12:32

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

pesterhazy21:12:16

@gklijs is your solution available online?

potetm21:12:31

lots of solutions here

potetm21:12:43

I made a mutable doubly-linked circular list

potetm22:12:31

looks pretty much like the python solution

potetm22:12:07

If I only knew the word “deque”

potetm22:12:24

oh well, had fun making my own 🙂

potetm22:12:11

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

potetm22:12:27

lots of obvious waste to trim

benoit22:12:32

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

potetm22:12:47

pure clojure using deftype w/ mutable fields

potetm22:12:59

yeah I bet java deque is sig better 🙂

potetm22:12:10

you see a sig timing dif @me1740?

benoit22:12:48

16 s -> 7 s -> 1s roughly

potetm22:12:00

😕 yeah I guess java deque is next for me

benoit22:12:36

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.

potetm22:12:24

mine varies quite a bit actually

potetm22:12:26

no idea why

potetm22:12:33

as short as 2s, as long as 10

potetm22:12:38

GC I presume

benoit22:12:05

Yeah the difference seems big

potetm22:12:05

"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]

potetm22:12:13

:man-shrugging:

potetm22:12:44

yeah but they cheated

potetm22:12:47

perf enhancing drugs

potetm22:12:23

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

ihabunek22:12:28

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

mfikes22:12:12

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

taylor22:12:45

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

mfikes22:12:09

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

mfikes23:12:44

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

😱 4
mfikes23:12:27

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

mfikes23:12:54

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

gklijs04:12:19

A transient vector wouldn't do it? I might give it a try with transient vectors. I don't think it should be a lot slower then Java.