That’s very odd

Can you post the code somewhere?

You have: (check-equal? (solve-2) 939490236001473) but the solution to part 2 is 640856202464541

Thanks for the explanation. I was so close! Looking at some notes I scribbled - I solved for bus ids 7 & 13 w/ 77 and 78 timestamps, and I see a 91 I circled (7 * 13). I was trying to see the relation between 91 and the timestamps, but didn’t think to just add 91 :)

lol - that’s funny - I had no idea about that!

This has to be a ton of work for the organizer.

Hard enough to come up with good puzzles and ensure they’re bug-free, but to have individualized inputs also seems to add a lot of work depending on the puzzle.

IIRC there are some parsing techniques that can generate generators as well, so Eric may be able to leverage something like that.

Thanks for the nudge! I’ve been really enjoying my first time with AoC, so I badged up despite having “C++” in the name ;)

@me1890 how did you come to know about Van Eck’s sequence?

It was covered in a numberphile video in June 2019. https://youtu.be/etMJxB-igrc

I just so happend to still have the code i wrote while watching that video

@samth…for whatever reason, this showed up while I was testing but not when I tried to replicate this behavior explicitly

regardless, my friend and I engineered similar solutions, and they also noted a significant improvement with begin0 — I can ask them, I guess?

was it perhaps when debugging was on in DrRacket?

I am not using DrRacket

redid Day 15 using a vector in Typed Racket, solves Part 2 in around 1.1 seconds on my machine: https://git.knightsofthelambdacalcul.us/hazel/advent-of-code-2020/src/branch/canon/day15.rkt anyone have any faster solutions without using racket/unsafe/ops?

also the hash table solution is much slower here, for some reason.

For comparison, my naive, brute force, <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day15-mutable-hash.rkt|mutable hash table solution> takes 6.2 seconds on a 16" macbook pro.

Using a <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day15-vector.rkt|mutable vector> instead of the mutable hash table brings it down to 0.82 seconds using #lang racket on Racket v7.9 [cs]

There’s also tricks he has to consider, like making sure to generate inputs that satisfy some invariants that aren’t actually stated in the rules but which are necessary to avoid pathological behavior

Like the buses being prime in day 13 or there being no gaps of two in day 10

I’m guessing he just has a program that generates random values inside suitable distributions then replaces them in the input

Right, reminds me a bit of Haskell’s quickcheck framework

I’ve heard of that, but only used something similar in rust.

Lastly, a <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day15.jl|newbie Julia version> takes about 0.43 seconds. That makes me pretty pleased with the 0.82 second Racket version.

By the way, are you using Racket’s time to time your code, or are you timing it from the shell i.e. including load time?

time. I am using Racket BC and thus the VM startup time kinda sucketh

chez would probably help. only using BC because I’m too lazy to change the NixOS derivation.

i implemented a solution with fxvector and unsafe fx ops which brings like 10–20% improvement over plain vectors

This is interesting, I did <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day15.c|a C version> based on the <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day15.jl|Julia version> and it came in at 0.64 seconds - in between Julia and Racket ! It’s been decades since I coded C seriously, so I may have done something stupid.

Try a Chez Scheme version next!

I don’t even have Chez installed at the moment, and I’m pretty tapped out on this by now :) Bottom line - I’m pleased with Racket’s speed, and if I need more, I’ll use Julia :)

Although, now I am curious about fxvector given @haskal’s comments above!

Ok, last one :) <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day15-unsafe-vector.rkt|Unsafe vector/arithmetic version> comes in at 0.75 seconds. @soegaard2 I would think Chez would be similar, but I’m not really sure.

So, the immutable hash table version is about 24x slower than the unsafe vector version.

Sorry for the noise, but to have all the results in one table: <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day15.rkt|Racket w/ immutable hash table> => ~ 18 seconds <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day15-mutable-hash.rkt|Racket w/ mutable hash table> => ~ 6 seconds <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day15-vector.rkt|Racket w/ mutable vector> => 0.82 seconds <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day15-unsafe-vector.rkt|Racket w/ unsafe vector/arithmetic> => 0.68 seconds <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day15.c|C version> => 0.47 seconds <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day15.jl|Julia w/ mutable vector> => 0.41 seconds

Racket/ unsafe vector/arithmetic => 0.75 seconds C version => 0.64 seconds That’s pretty close!

Yes, and I’d be fine with the 0.82 seconds with regular vectors to avoid the clutter of fx...

@badkins racket/fixnum doesn’t provide unsafe operations. They check that their inputs are fixnums.

Ah!

I don’t think your vector ops are unsafe either.

You’ll need racket/unsafe/ops variants

on it …

0.68 seconds - I’ll update the table ^

Changing the vector initialization of the C version dropped it from 0.64 to 0.59s

while playing with racket/unsafe/ops to make my solution fast(tm) I have successfully caused DrRacket to segfault for the first time

please clap

more unsafe -> program go fast -> win

what’s notable (and odd) is that my Typed Racket solution, my unsafe solution, and @badkins’s unsafe solution all run in around the same time on my machine (around 1200 ms)

Typed Racket ought to be producing similar code to your use of unsafe

this confirms my theory that Typed Racket good

this happens with PLT_TR_NO_OPTIMIZE though (albeit I’m not familiar with Typed Racket enough to know if this makes a difference here)

day 16 spoilers

in the interest of minimizing amount of code i used maximum-bipartite-matching from graph for part 2 i think this is a pretty neat solution https://git.lain.faith/haskal/aoc2020/src/commit/dc4fb90f0808bc08a0048d59f8dd800cfdac44ea/16.rkt#L17

wow, that is so much nicer than what i made

I made some very ugly code for today

note i usually make revisions. if you wanna see the first version see the history. it’s pretty bad (aoc is a tradeoff between code quality and your submission time and i’m optimizing for both because reasons)

I honestly don’t know how to write this nicely in racket. Could you tell me how to write these loops better? https://gitlab.com/-/snippets/2050872

I can explain parts if it doesn’t make sense

my first recommendation would be to dump the let* and use internal defines

and define helper functions. a lot of them

i am going to see if i can solve this problem in rosette later

but for now i sleep

I will try to make some helper functions. Thanks for the tips