Clojurians Log v2

https://github.com/green-coder/advent-of-code-2020/blob/master/src/aoc/day_23.clj

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

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

https://github.com/euccastro/advent-of-code-2020/blob/master/src/advent/day23.clj

plain arrays, slow but workable

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

https://github.com/peterhhchan/aoc2020/blob/main/src/aoc2020/day23.clj

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.

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

down to 57 secs

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

down to 25 seconds

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

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

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

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

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

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.

I see, no problem then

https://github.com/Average-user/aoc2020/blob/main/src/day23.clj

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

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

@lucaspolymeris this can become 1 assoc : https://github.com/Average-user/aoc2020/blob/main/src/day23.clj#L13-L16

You are right, thanks. Always forget about that

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

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

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

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]

what are those f and g doing?

and d

and r

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

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

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

ah i see

smart

thanks for elaboration i learned something 🙂

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

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

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

and this little optimization cut it to under 3sec: https://github.com/euccastro/advent-of-code-2020/commit/4b48551440405efa8de1eef8010aba64ad836d6b

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

I hate it, 2 days and 1s by mutating int-array https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2020/day23.clj

You redefined the term "persistence". Congratz.

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

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

I should repeat to myself: RTFM !

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

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

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

might not happen today

Mine runs in 925 days in time for Christmas 2023

Will look for some help :)

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

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

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

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…

I came up with this

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

I suppose you have them indexed by val?

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

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

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

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

@euccastro yes, I also have a map for that

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

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

Haha, just noticed it was a wrong thread.

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

Niiice

@nbardiuk 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 (?)

A bit revisited my solution after @nbardiuk posted his https://github.com/zelark/AoC-2020/commit/61d33f71a38d146f74661ee497f13ead4fb1c553

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

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

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

@erwinrooijakkers apparently I used the same coordinates

Using coordinate system as well https://github.com/benfle/advent-of-code-2020/blob/main/day24.clj

A little differently.

https://raw.githubusercontent.com/genmeblog/advent-of-code/master/images/advent_of_code_2020/day24_100.jpg

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

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

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

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

Thank you to everyone for sharing your solutions - I'm learning a ton! https://github.com/abyala/advent-2020-clojure/blob/master/src/advent_2020_clojure/day24.clj.

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