Thanks for pointing this out. TIL there are quite a few of these file shortcuts!

Enjoyed the game-of-life; added animations to mine for fun, but had to shrink my terminals font size way down to actually watch them on my full input :slightly_smiling_face:

I missed a key insight again :)

After I wrote my solutions. I took a look at this <https://github.com/tckmn/polyaoc–2020/blob/master/11/rb/11.rb|Ruby version> (this person has been doing great work), and realized you can compute the first seats ahead of time, so I <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day11-rb.rkt|ported it to Racket> , and naturally, it was considerably faster. I didn’t take any time to Racketize it, just did a port as close to the Ruby as I could in a hurry.

In my versions, I didn’t want to allocate much, so I just used two vectors (previous & current). My hunch is that if I did that in the port above, I’d gain some speed, compared to allocating a new vector of vectors each time.

I think I’m having trouble following; what is sight ? If it’s just the visible seats in the first generation, the ruby code never updates it, so that seems odd—makes me thing it has to be the possibly visible seats (like list of points to check or something)

I actually recalculate the visible seats each time; red-black trees and tail-recursion were “fast enough” (though not blindingly fast)

For any given seat, the first visible seat in all 8 directions never changes.

ah. I missed that. oh well :slightly_smiling_face:

Yeah, it took me a while to see what they were doing!

I just checked, and there are only 90 iterations until it stabilizes, so allocating 90 new vectors is no big deal for Racket; hence, I’m not going to bother experimenting with not allocating :)

I got about a 7x speedup using the precomputed sight table.

That makes sense; I’m tempted to try it on my sml solution and see what happens

It’s humbling when <https://adventofcode.com/2020/leaderboard/day/11|people are producing> concise, elegant & efficient solutions in about 5 minutes !!

you could make it faster by using a 1D vector instead of a 2D one

@samth yes, my original solution was pretty efficient except for lacking the key insight of precomputing the first seat :) I used two 1D vectors and vector-copy! to reset each iteration.

I may modify my original to use the precomputed table (instead of porting the Ruby), and see what the speedup is.

I keep learning little tidbits about Racket though, so it’s been profitable in addition to humbling :)

https://github.com/lojic/LearningRacket/blob/master/advent-of-code-2020/day11-1.rkt

I continue to find let loop to be noticeably faster than the for family.

Wow, using macros instead of functions for the following got me a 7x speedup ! (define-syntax-rule (is-empty? seat) (char=? empty-loc seat)) (define-syntax-rule (is-floor? seat) (char=? floor-loc seat)) (define-syntax-rule (is-occupied? seat) (char=? occupied-loc seat))

That is surprising

I agree, so I changed them back, measured again to confirm the results.

1,157ms w/ functions & 172ms w/ macros.

I’m on Racket BC 7.5

Oh wow, @samth it wasn’t function vs. macro!

Instead of: (define (is-empty? seat) (char=? empty-loc seat)) I was using: (define is-empty? (curry char=? empty-loc)) because point-free seemed cool - why the heck does that impose a performance penalty?

7x is a pretty stiff penalty

curry is creating a function that does runtime dispatch

In SML it sure doesn’t :slightly_smiling_face: if curry/compose/etc. are slower in racket, it would turn me off of that style of writing (which I happen to enjoy).

Looks like precomputing the seats doesn’t make much of a difference on the inputs that the site generates:

~/s/aoc2020 (master)> racket day11.rkt cpu time: 70 real time: 72 gc time: 4 2406 cpu time: 69 real time: 71 gc time: 1 2149 ~/s/aoc2020 (master)> racket day11-rb.rkt cpu time: 116 real time: 118 gc time: 36 2406 cpu time: 101 real time: 103 gc time: 0 2149 Though pre-computing would probably be faster if the inputs were larger and more sparse.

day11.rkt is https://github.com/Bogdanp/aoc2020/blob/e3ff6e1718b7d08fc585b33aa50477f4cb32c3e6/day11.rkt\|here and day11-rb.rkt is the one from your repo.

@popa.bogdanp did you try with a 1d vector and doing multiplication in ref?

I’m getting 170ms now with my original (non-precomputed) on a Macbook Pro 16", and about 175ms with day11-rb.rktnow that I got rid of curry !!

I’ll report back with the precomputed version, but I expect it typically only has to check 2 or 3 positions before finding a seat, so maybe not a big help.

@samth looks like no difference:

~/s/aoc2020 (master)> racket day11.rkt cpu time: 73 real time: 74 gc time: 3 2406 cpu time: 69 real time: 71 gc time: 1 2149 ~/s/aoc2020 (master)> racket day11-wide.rkt cpu time: 65 real time: 67 gc time: 3 2406 cpu time: 74 real time: 76 gc time: 5 2149

Well, 10% isn’t no difference :)

Fair, but I think that difference might just be noise (I’m on battery power). Here’s what it looks like when I bump the iteration count to 20:

~/s/aoc2020 (master)> racket day11.rkt cpu time: 1310 real time: 1339 gc time: 0 cpu time: 1438 real time: 1473 gc time: 11 ~/s/aoc2020 (master)> racket day11-wide.rkt cpu time: 1273 real time: 1301 gc time: 0 cpu time: 1434 real time: 1469 gc time: 10

So maybe real but not 10%

Had a power outage here, but I finally got some results. <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day11–2.rkt|Old Part 2> which requires <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day11–1.rkt|Part 1> is about 222 ms. The <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day11–2b.rkt|New Part 2> w/ precomputed seats is about 112 ms.

Installed Racket CS 7.9 out of curiosity. Timings are similar.

But at least I’m on a cool, recent version now!

@mbutterick I like your use of complex numbers for Day 11 - nice job!

Complex numbers made today really easy too