Huh, went from ~4.5s to ~1.2s just by swapping the fifos for lists. Must be that the list library is better optimized, either at the language or lower level.

I’m looking at the problem; did you or anyone come up with a clever way to treat the whole list as a single number instead of as a list of numbers? I imagine that would be really fast if the operations aren’t too bad.

https://github.com/ionathanch/adventofcode-2020/blob/main/src/23.rkt\|https://github.com/ionathanch/adventofcode-2020/blob/main/src/23.rkt This one was a doozy I started doing part 2 in C bc I didn’t know how else to manipulate pointers lol But it was really slow trying to find the cup with a given label and I found myself wishing I had a map but guess what. Racket has hash And finally I went from hash to vector since it’s ints to ints

Just found out that my list-solution for part1 would take maybe ~2300+ days to run, gonna have to do something different :slightly_smiling_face:

I wrote a simple circular queue for Part 1, and I really just wanted to use it as-is for Part 2, but I think it would take 11 hours :) I’m guessing there’s a clever, non-brute force approach, since AoC mentions there are solutions that run in less than 15 seconds on 10 year old hardware.

I did a bit of tuning, and got it to 235 moves/second, but that’s not even close to being fast enough.

I tried to figure out the pattern manually and derived smth for up to ~250000 moves but the pattern started breaking bc it was looping back from 1000000 to the start so I gave up :man-shrugging: It looked a lot like a Project Euler problem and I was hoping there’d be some sort of closed-ish form you could compute

Hmm… from the comments above, it seems a brute force approach is doable w/ some more tuning. I didn’t get around to using a hash for the lookup, that might get me there.

Wow! Replaced my function to lookup the cup in the circular queue by label with (vector-ref vec label), and it dropped from 11 hours to 2.2 seconds :)

I knew a hash or vector reference would be much quicker on that, but I didn’t realize what percentage of the run time was taken up by that operation - apparently quite a bit! I usually have better intuition than that :)

@jonathanhwchan trying to decipher your solution; does your vector map cup -> next cup? If so, that’s kind of genius

Yeah What you don’t see is the half dozen other implementations to get to that conclusion lol

Interesting. I didn’t know that’s what you were doing, but as soon as I read vector instead of hash above, I created a cross reference vector to map label to queue node. I still can’t believe the 21,000x speedup ! Here’s <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day23.rkt|the resulting code>

So glad I was able to reuse the circular queue from part 1 :)

@jonathanhwchan if I’m understanding correctly that you bypassed a queue entirely and, in effect, implemented the queue and cross reference in the vector, that must be pretty fast.

Although setting a few next prev pointers probably doesn’t add much overhead. My GC time was only 185 ms.

Yeah, setting values in the vector probably isn’t all that much faster than moving a few pointers around

I was getting tired of writing throw away code, so I figured I’d at least get a rudimentary circular queue out of today. Once I add some robustness, it might be useable later :)

Sigh. I tried immutable vectors, and performance was unacceptable. With mutable arrays, I get about 100k moves per 2–3 seconds, so 10 million takes 3–5 minutes if my math is right. I’m a little jealous of racket rn

I thought @jonathanhwchan’s solution was ideal for Julia, so <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day23–2.jl|I ported it to Julia> , and it runs 12x faster than my Racket solution. It takes 0.18 seconds for Part 2.

@ben.knoble you using SML?

I’ve pretty much been coding only in Racket for the last couple years, and it fits me very well. However, occasionally, it does feel good to just have some loops and assignment statements :)

Especially when it’s amazingly fast.

@badkins yeah; here’s the link. See the history for lists; i didnt commit the vector version but it’s almost the same https://github.com/benknoble/advent2020/blob/main/day23/solution.sml\|https://github.com/benknoble/advent2020/blob/main/day23/solution.sml

What compiler are you using? I wonder if MLton would be faster.

I did a <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day23-vector.rkt|Racket port of my Julia port> of Jonathan’s code. I’m getting 0.28 seconds (vs. 2.2 seconds w/ my queue solution), so Racket is pretty speedy. Only 1.6x Julia is pretty darn fast.

I tried porting that solution to C but I think I’m having problems with not being able to malloc all of the memory at once lol

Using <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day23-vector-unsafe.rkt|all the unsafe-fx bells and whistles> got down to 0.24 seconds. I don’t think the ugliness & unsafety is worth the 17% speedup.

@jonathanhwchan I did a C version for Day 15, and it was a pain to get it working (mainly due to not having coded C in a long time), the Julia version on Day 15 was both faster than the C version, and much, much nicer to program! :) I think I’d only use C when forced to i.e. for a microcontroller, or similar need.

@jonathanhwchan you should be able to allocate the vector on the stack in C. I did that for <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day15.c|my Day15 C version> by using a command line of: gcc -O3 -Wl,-stack_size -Wl,32000000 day15.c to get enough stack space.

I’m not motivated to try because I think the Julia version would win :)

… and one based arrays are pretty handy for this.

day 24 spoilers,

https://git.lain.faith/haskal/aoc2020/src/branch/aoc2020/24.rkt

i ended up using complex numbers representing truncated cubical coordinates as keys to a hash of #t (black) or #f (white). part 2 is ~4.7 seconds notably, using complex numbers pretty significantly speeds up execution vs a position struct

I used complex numbers too, but just used a slightly different mapping that looks closer to regular hexagons

https://gitlab.com/pythondude325/advent-of-code-2020/-/blob/master/day_24.rkt

haskal’s coords look like axial coords from here https://www.redblobgames.com/grids/hexagons/

yeah it’s cubical coords except truncate one of them because you only need 2

looks like that page explains the scheme

I think i used the same coordinates but just rotated a bit

yeah mine are a bit obtuse and perhaps rotated 60 degrees away from what you’d expect from the cardinal directions but ignore that lol

You probably avoided one slight issue i had. At first i was using 0.5+i for my offsets and i was getting some rounding errors, so i just had to switch to rationals