This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2020-12-23
Channels
- # adventofcode (135)
- # announcements (9)
- # babashka (27)
- # beginners (97)
- # bristol-clojurians (8)
- # calva (7)
- # chlorine-clover (1)
- # cider (3)
- # clara (16)
- # clj-kondo (9)
- # cljdoc (137)
- # clojars (4)
- # clojure (110)
- # clojure-europe (118)
- # clojure-taiwan (8)
- # clojure-uk (19)
- # clojurescript (30)
- # conjure (6)
- # cryogen (32)
- # datomic (11)
- # depstar (1)
- # duct (4)
- # emacs (6)
- # fulcro (73)
- # graalvm (9)
- # keechma (7)
- # leiningen (16)
- # luminus (1)
- # malli (35)
- # meander (3)
- # off-topic (45)
- # pathom (1)
- # pedestal (2)
- # re-frame (3)
- # reagent (31)
- # reitit (2)
- # reveal (17)
- # shadow-cljs (34)
- # tools-deps (11)
- # xtdb (14)
Day 23 answers thread - Post your answers here
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
I implemented a linked-list using a dictionary, and recursed the list + pointer to the head and tail. part-2 took ~125s.
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
@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.
By using a transient linked-list and assoc!
, it’s down to 16 secs.
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
@U963A21SL 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
Takes about 1 minute, simulating a linked list with a map
$ clj -M day23.clj
[68245739 219634632000]"Elapsed time: 53733.237706 msecs"
@UCJNB809E 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...)
@UCJNB809E can you elaborate a bit on “simulating a linked list with a map”?
@U2PGHFU5U 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?
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
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
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
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
ah I found the thread 👀
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
I did not even try the naive solution.
Many off-by-one issues to deal with.
I finished the impl, but I have a bug somewhere.
DONE ^_^
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...
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]))
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 🙂
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
How fast is it?
How did you solve it then?
I mean what approach did you choose?
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
Here is an immutable version of it ;) https://github.com/namenu/data.deque
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.
Day 24 answers thread - Post your answers here
https://github.com/euccastro/advent-of-code-2020/blob/master/src/advent/day24.clj
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.]
https://github.com/green-coder/advent-of-code-2020/blob/master/src/aoc/day_24.clj
@U067R559Q I was thinking about you when I saw that it was once again about neighbors.
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
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
And here is mine 🙂 https://github.com/zelark/AoC-2020/blob/master/src/zelark/aoc_2020/day_24.clj
As expected, frequencies
was frequently used.
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})
description of the coordinate system @U8MJBRSR5 and me used: https://www.redblobgames.com/grids/hexagons/#coordinates-axial
@U8MJBRSR5 @U067R559Q nice touch on using re-seq
to parse the line. I'll borrow that to remove my silly str/replace
s 😄
> “There is a REPL for that”
somehow that makes my code a bit slower... but I'll keep it anyway since it reads much better
after revisiting the redblobgames article and choosing right coordinate system it was easy https://github.com/nbardiuk/adventofcode/blob/master/2020/src/day24.clj
@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 (?)
A bit revisited my solution after @U076FM90B posted his https://github.com/zelark/AoC-2020/commit/61d33f71a38d146f74661ee497f13ead4fb1c553
@U65FN6WL9 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
@U2PGHFU5U apparently I used the same coordinates
Using coordinate system as well https://github.com/benfle/advent-of-code-2020/blob/main/day24.clj
@UEF091BP0 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.
@U076FM90B - I love your step
function. I wouldn't have thought of for -> :when
to construct the next set of black tiles.
https://github.com/akovantsev/adventofcode/blob/master/src/adventofcode/y2020/day23.cljc#L189-L231
"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
https://github.com/akovantsev/adventofcode/blob/master/src/adventofcode/y2020/day23.cljc#L111-L146
I'm surprised by the lack of intcode
this year. Maybe tomorrow?