Fork me on GitHub
#adventofcode
<
2020-12-23
>
Vincent Cantin03:12:49

Day 23 answers thread - Post your answers here

rjray08:12:28

I basically implemented a linked-list of numbers for part 2. Don't ask how many bugs I had to deal with. Tomorrow I'll consolidate parts 1 & 2 into smaller code. https://github.com/rjray/advent-2020-clojure/blob/master/src/advent_of_code/day23.clj

👍 15
nbardiuk12:12:37

I've implemented double linked list/circle using maps, it is very slow but gives the answer in several minutes 😂 https://github.com/nbardiuk/adventofcode/blob/master/2020/src/day23.clj

👍 6
euccastro12:12:20

plain arrays, slow but workable

peterc12:12:03

I implemented a linked-list using a dictionary, and recursed the list + pointer to the head and tail. part-2 took ~125s.

Vincent Cantin12:12:31

The solution I posted today is running part2 in 64 seconds, probably half on your computers. I am cleaning up the code and will see if I can improve its performance a little more.

Vincent Cantin13:12:20

I am counting on reducing the memory footprint to reduce as well the CPU cost, since the CPU cache becomes the bottleneck here.

Vincent Cantin13:12:06

down to 57 secs

Vincent Cantin14:12:38

@U076FM90B When the CPU cache does not contain the memory that the program needs, it loads the data from the central memory and place it in the cache. This is very slow compared to the CPU’s raw speed, it’s the same as if it went to take a coffee while waiting for the next bus to pass by.

Vincent Cantin14:12:09

down to 25 seconds

🚀 6
Vincent Cantin14:12:32

By using a transient linked-list and assoc!, it’s down to 16 secs.

Vincent Cantin14:12:42

I think I should stop now before I destroy my source code 🙂

9
benoit15:12:59

In the right thread this time. Solution with linked list in an int array (takes around 15s) https://github.com/benfle/advent-of-code-2020/blob/main/day23.clj

🎉 6
👍 3
Vincent Cantin15:12:36

@U963A21SL (doseq [_ (range n)] can also be (dotimes [_ n]

👍 6
Vincent Cantin15:12:16

@U963A21SL why (aset cups 0 ^int c4) ?

benoit15:12:05

I keep the value of the current pointer in the first element. And if you move the next 3 elements, the next current pointer will be c4.

👍 6
Vincent Cantin15:12:08

I see, no problem then

Average-user16:12:53

Takes about 1 minute, simulating a linked list with a map

Average-user16:12:39

$ clj -M day23.clj 
[68245739 219634632000]"Elapsed time: 53733.237706 msecs"

Average-user16:12:50

You are right, thanks. Always forget about that

rjray20:12:50

Going to re-do my code, using some of the tips from here 🙂. I completely forgot about transient last night, or my part 2 might have run faster. It currently runs ~32 sec on my machine. I believe I can significantly shrink my code by rewriting part 1 using part 2's structure. (It will also help the line-count when I remove the debugging fn that I left in last night...)

erwinrooijakkers21:12:03

@UCJNB809E can you elaborate a bit on “simulating a linked list with a map”?

Average-user21:12:21

@U2PGHFU5U The entry of the map at i si the value which i is pointing to in my imaginary linked list.

thanks2 3
erwinrooijakkers21:12:04

I see:

(build input)
;; => {7 1, 1 5, 4 3, 6 2, 3 9, 2 4, 9 7, 5 8, 8 6}
input
;; => [6 2 4 3 9 7 1 5 8]

erwinrooijakkers21:12:19

what are those f and g doing?

Average-user21:12:20

to not build the complete map of 1000000 entries, g just returns i+1 if the entry of the map at i is undefined

Average-user21:12:36

d stands for destination, as in the problem specification. And f I think should be clear by its definition

Average-user21:12:03

I also ended up changing the map for a vector. Now it takes half the time it did before. But as other people have done, is probably better to use other structures more suited

erwinrooijakkers21:12:12

thanks for elaboration i learned something 🙂

😀 3
Average-user21:12:47

I'm sorry if I name things to vaguely. I really should get better at naming

Max Deineko22:12:53

TIL about rrb-vector, which worked fine for me in part 1 and broke in part 2 for some reason..  Well, I'm quite content with ~20s running time using int vector for storage. https://github.com/next-mad-hatter/adventofcode/blob/master/src/aoc_2020/day_23.clj

euccastro00:12:57

so I got envious of all your sub-half-an-hour solutions using linked lists and I tried a solution myself. it seems very simple and runs in about 10 seconds (I did no profiling to see whether it can be further optimized yet): https://github.com/euccastro/advent-of-code-2020/blob/8d89563a8909dc1865c2108470b4a928a3394dd1/src/advent/day23.clj#L94

🎉 3
euccastro00:12:31

ha, I see I ended with essentially the same solution as @misha 🙂

bellissimo 3
Vincent Cantin15:12:53

You redefined the term "persistence". Congratz.

bananadance 3
holymackerels05:12:23

I'm about a week behind, trying to play catch up, but I managed to get my day 15 solution down to ~1.7s, my first solution took like 5 minutes

👍 3
holymackerels05:12:50

ah I found the thread 👀

Vincent Cantin06:12:23

That puzzle should have been named “Crab, unchained”

🦀 6
⛓️ 3
euccastro06:12:38

my naive solution for part 2 will take 7 seconds to iterate through 10 steps, so I'll give my dog a 7 million second walk

😅 3
Vincent Cantin06:12:34

I did not even try the naive solution.

Vincent Cantin06:12:50

I go for the fast way, but it’s complicated to implement.

3
Vincent Cantin06:12:02

Many off-by-one issues to deal with.

euccastro06:12:08

well, I had a step function from part 1, so might as well

euccastro06:12:25

it would take 81 days to finish 😄

Vincent Cantin07:12:34

I finished the impl, but I have a bug somewhere.

rjray08:12:30

I'm getting the wrong answer for the test input on part 2. Ugh.

Vincent Cantin08:12:42

My bug was that I was doing 1 million rounds instead of 10 millions.

Vincent Cantin08:12:08

I should repeat to myself: RTFM !

rjray08:12:47

That's OK. I just got a wrong answer because I submitted the answer from the test data instead of the real data.

🎉 3
euccastro09:12:41

OK, with a simplish array-based implementation I got it down to 5 days. I guess I need to reduce copying...

euccastro09:12:48

and figure out how to hint stuff for reflection and boxed math

euccastro09:12:52

might not happen today

erwinrooijakkers09:12:02

Mine runs in 925 days in time for Christmas 2023

erwinrooijakkers09:12:42

Will look for some help :)

erwinrooijakkers09:12:30

I see that the use of a LinkedList would help, but not sure what to store where. This evening

euccastro10:12:37

https://github.com/ptaoussanis/tufte helped me narrow the performance bottleneck down to how I'm searching for the index of the destination cup. a simple improvement to that got me down to one day

euccastro10:12:25

ok, got it down to 45 minutes, which is close to what I was expecting. I'll just let it run at this point...

alekszelark10:12:53

I’m done, but the part 2 was running a few minutes (~3). It was hard to implement and my code is dirty and full of side effects…

alekszelark10:12:01

I came up with this

(defprotocol ICircleNode
  (get-next [this])
  (get-val [this])
  (insert-after [this node])
  (remove-after [this]))

👍 6
euccastro10:12:16

I suppose you have them indexed by val?

Vincent Cantin11:12:23

In French, a linked list is called a "chained list"

Vincent Cantin11:12:53

I failed my pun about the crab, used the wrong word.

euccastro11:12:53

haha, after 45 minutes waiting I realized that I had fed it the demo input! at least I know it works now 😛

euccastro11:12:52

since I learned programming on my own from sources in English I don't know most technical terms in my own language 🙂

alekszelark11:12:56

@U65FN6WL9 yes, I also have a map for that

👍 3
alekszelark17:12:33

Here is my solution, I wrote it today morning, but polished only now. It runs under 2 minutes for the part 2. https://github.com/zelark/AoC-2020/blob/master/src/zelark/aoc_2020/day_23.clj

🎉 3
alekszelark18:12:24

Also built a fast implementation with deftype and the same protocol. It runs under 20 secs. https://github.com/zelark/AoC-2020/commit/4da8a0b8f6086a5cd552e753a5881edac6798e43

alekszelark06:12:36

Haha, just noticed it was a wrong thread.

😅 3
misha15:12:28

if someone still hopes to brute force part2, here is a hint:

misha15:12:34

(:import [java.util Deque ArrayDeque]))

alekszelark15:12:25

How fast is it?

misha15:12:06

no idea yet d but faster than vectors and lists ... I think

alekszelark16:12:03

How did you solve it then?

alekszelark16:12:38

I mean what approach did you choose?

misha16:12:33

I did not yet, just got to it. The Deque was handy in aoc 2018, so I quickly solved p1 with it, but then it turned out to be misfit for p2

namenu05:12:54

Here is an immutable version of it ;) https://github.com/namenu/data.deque

alekszelark17:12:07

About Day 20: “I might be able to improve this code, but I have no desire to look at it again any time soon.” Found it in one’s notes.

😂 12
rjray18:12:50

I resemble that remark 🙂.

💯 3
alekszelark19:12:46

Day 24 answers thread - Post your answers here

euccastro05:12:30

I lucked out on this one, since I'd worked with hex grids a while ago: https://wiki.call-cc.org/eggref/4/hexgrid [P.S.; NB I'm not using that coord system here, but a simpler one with y pointing northwest and x pointing east.]

3
Vincent Cantin06:12:20

I was a game programmer, so I know my bestagon :-)

🕸️ 6
3
❤️ 6
Vincent Cantin06:12:12

I wasted 20 minutes on >= 2 vs > 2 picard-facepalm

picard-facepalm 3
Vincent Cantin06:12:23

@U067R559Q I was thinking about you when I saw that it was once again about neighbors.

😁 3
euccastro06:12:05

I missed this first initially so my solution2 was running forever and I got really scared that there was some combinatorial madness going on again 😄 https://github.com/euccastro/advent-of-code-2020/blob/9e9cabf2fcd8ea8383ec193696ec9ebdb81be400/src/advent/day24.clj#L84

rjray06:12:37

Thanks to what I learned on day 17 from @U067R559Q's code (and for the fact that I have been taking notes each day), part 2 went faster than part 1. https://github.com/rjray/advent-2020-clojure/blob/master/src/advent_of_code/day24.clj

😁 3
👏 12
3
Vincent Cantin06:12:03

As expected, frequencies was frequently used.

alekszelark06:12:28

just leave it here ^_^

(defn stepper [neighbours birth? survive?]
  (fn [cells]
    (set (for [[loc n] (frequencies (mapcat neighbours cells))
               :when (if (cells loc) (survive? n) (birth? n))]
           loc))))

(stepper neighbours #{2} #{1 2})

😍 6
euccastro06:12:01

description of the coordinate system @U8MJBRSR5 and me used: https://www.redblobgames.com/grids/hexagons/#coordinates-axial

👍 12
😏 3
euccastro06:12:43

only our y points northwest

euccastro06:12:20

@U8MJBRSR5 @U067R559Q nice touch on using re-seq to parse the line. I'll borrow that to remove my silly str/replaces 😄

euccastro06:12:04

I guess I wasn't sure enough that re-seq would do the right (greedy) thing..

Vincent Cantin06:12:27

> “There is a REPL for that”

euccastro06:12:50

true true...

euccastro06:12:21

somehow that makes my code a bit slower... but I'll keep it anyway since it reads much better

nbardiuk07:12:49

after revisiting the redblobgames article and choosing right coordinate system it was easy https://github.com/nbardiuk/adventofcode/blob/master/2020/src/day24.clj

🎉 12
euccastro08:12:37

@U076FM90B now I feel silly for using drop and first to pick an element by index in a lazy sequence. somehow I though nth didn't work on those (?)

🙂 3
alekszelark09:12:48

@U65FN6WL9 I believe It’s a matter of taste here. I prefer drop and first

Vincent Cantin09:12:11

drop and first works well with ->>, while nth needs ->

erwinrooijakkers09:12:25

I used this one https://www.redblobgames.com/grids/hexagons/#coordinates-doubled and brute forced inefficiently by looping over all the points and their neighbours, and then finding their neighbours again. The answer does print after some minutes: https://github.com/transducer/adventofcode/blob/master/src/adventofcode/2020/day24.clj

🎉 12
alekszelark09:12:44

@U2PGHFU5U apparently I used the same coordinates

benoit12:12:28

A little differently.

rjray17:12:03

Once again, I learn much from zelark's solution 🙂.

bestagon-ok 3
alekszelark18:12:58

@UEF091BP0 Also look at nbardiuk’s solution I borrowed a couple things from it.

rjray21:12:56

When this is over, I plan to link to several of the other Clojure repos (in my README.md), for future reference.

nbardiuk21:12:40

We slowly converge to similar code by learning from each other, nothing original in my solution 😁

Andrew Byala03:12:37

@U076FM90B - I love your step function. I wouldn't have thought of for -> :when to construct the next set of black tiles.

3
❤️ 3
misha19:12:58

projected time: 22minutes harold

misha19:12:44

"Elapsed time: 912366.338705 msecs", 15 minutes, with array as a continer.

👏 3
misha19:12:15

"Elapsed time: 28510.814642 msecs", 28 seconds, with transient map lol

misha19:12:07

"Elapsed time: 13782.338101 msecs", 13 seconds with java.util.HashMap

misha20:12:37

"Elapsed time: 6754.597334 msecs", 7 seconds, with typehints for int-array. so that was 14 minutes and 47 seconds of java reflexion, and 13 seconds of actual work, lol

gotta_go_fast 15
😮 3
Average-user22:12:20

I'm surprised by the lack of intcode this year. Maybe tomorrow?

rjray23:12:05

How odd. I tried re-writing my algorithm to use int-array as @misha does in the 7-second version. It's taking several times longer to run than my vector-based original. I must have something subtle that's wrong in it.

rjray23:12:07

Well, that's an improvement. I went from 32 seconds to 26 minutes.