Yep, at least 12 matching relative distances makes a match. I keep the corresponding points together, so then i can use one pair of matching points to get the distance between scanners. Warning: my solution is stupid slow. Takes 15 min on the full input. I have one idea for an optimization, but it is still pretty naïve in terms of size with all the Cartesian products involved

Managed to trim to 8 minutes from 15 by reducing some memory pressure and putting most-needed things at the front lists rather than towards the end. Remarkably, htop says the memory usage is nearly constant for the entire thing (2% usage), but the time-apply info says we spent 1.5 min in the gc! Neat! (This is a little obscure; I was careless with names: https://github.com/benknoble/advent2021/blob/main/day19/solution.rkt)

Day 20

Okay.. I admit, I’m stumped on this one. It’s dead freaking simple, I’ve “solved” it 3 different ways now and can process the test data perfectly every way.

However, I always get the same answer on my real data and the site says it’s incorrect (for part 1).

Would someone that’s completed this be willing to..

1. Run your code on my data (https://github.com/massung/advent2021/blob/main/day20/real.txt) and tell me what you get for comparison?
2. Give me your real data and part 1 answer as another test case I can use?

@massung Are you also on Discord? There seems to be more solvers there.

i have discord, and no, im not chatting there about the puzzles

The discord (in some spoilers between me, jimjorps, and eutro) contains a key observation that is true of the input but not of the sample (or rather, true of both, but they differ)

hmm, just knowing there is one may be enough

pretty frustrating for what’s obviously just game of life :wink:

okay, i think i have an idea. if that’s it, i think that’s pretty stupid, but whatever /shrug

Hint: endpoints, and the way they apply to the infinite grid.

yeah, i know im pretty sure i got it. what’s “dumb” (IMO) about it is that the puzzle only works with the the # of steps being even, otherwise the answer is “infinite”

yep… that was it… :face_palm:

and then part 2 of course just takes 0.5s to run :wink:

What annoys me what I looked at the real data and was noticing this exact thing, and thought “maybe…” and then just put it out of my mind b/c I thought that was a ridiculous thing to do for reasons stated above

Yeah, Eutro was pretty upset about it :)

I really came close to just tossing the rest of the year due to this. But, then I stop and remember that if it was me trying to come up with 25 puzzles every single year (and setup the infra for the site, maintain it, etc), I’d probably come up with a couple that a chunk of the world would find… perturbing as well.

I felt that way about yesterdays, frankly. It feels very underspecified. Had to work out all the rotations manually, think of a way to do the overlapping detection, etc. I usually feel like there’s enough instruction to get the answer slowly/naïvely if you follow the directions and never see the trick, but yesterday was just a big ol’ shrug

yeah, i felt similar about it. I actually did all 48 rotations as I didn’t have the time to remember/calculate the discriminates for which ones were mirrors

There have also been a few puzzles this year that definitely weren’t “optimizable” in that every puzzle should be able to run in < 1s or so.

“Nor do you need a fancy computer; every problem has a solution that completes in at most 15 seconds on ten-year-old hardware.” lol. My optimized version for yesterday took 8 minutes on a 6yo mac.

<https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2021/solutions/day20/day20.rkt|Day 20>

@massung how did you get .5s? Takes me 42s to get part2 on just the sample, am I missing some obvious trick?

Wow! I changed from: (for*/list ([ dy (inclusive-range -1 1) ] [ dx (inclusive-range -1 1) ]) (get-pixel img (+ x dx) (+ y dy))) to: (i.e. replaced inclusive-range with in-range ) (for*/list ([ dy (in-range -1 2) ] [ dx (in-range -1 2) ]) (get-pixel img (+ x dx) (+ y dy))) and it dropped my total runtime in half! inclusive-range simply returns a list, e.g. '(-1 0 1) and this for loop is what gets the 9 pixels.

This is the sample after 50 steps :slightly_smiling_face:

@badkins I used (in-list '(-1 0 1)) for both; does that go any faster?

I’d be surprised if it did since you’re creating a list.

A tiny 3-element list, but fair

The in-list is key for performance optimizations though; maybe adding it to inclusive-range there would help

in-list is 8% slower than in-range

both of those do optimizations in the for family.

The above change moved me from 1,299 ms down to 689 ms.

A disappointing blob for my input :disappointed: but I got the answer right after 2min.

Yeesh I must be doing something stupid then, if that’s the perf I’m getting

But good to know re: in-range

Here’s my enhance-pixel, and I bet the map and bool-list->decimal are slowing me down: (define (enhance-pixel x y) (~>> (for*/list ([ dy (in-range -1 2) ] [ dx (in-range -1 2) ]) (get-pixel img (+ x dx) (+ y dy))) (map (λ (c) (match c [ #\. 0 ][ #\# 1 ]))) (bool-list->decimal) (vector-ref iea)))

(lambda (c) (match c …)) is (match-lambda …) for the record, it’s a handy one. Not sure what your bool-list->decimal is but I found that string->number i the fastest way to go: ;; with qi (~> (amp ~a) string-append (string->number 2))

Ok, got to 568ms by removing map. Also @ben.knoble I’m only timing the solve, not the parse.

Hm. I’m timing both, but the parse is in the noise, ish.

Oops, my bad. For this one, solve does call parse (on past days I’ve parsed before calling solve), so the total run time for everything is 606 ms.

Wow - I had no idea string->nubmer had a radix arg !! Thanks @ben.knoble

Of course, now I think I’ll just do a performance deep dive, so that means building up the binary value directly :)

@ben.knoble my solution: https://github.com/massung/advent2021/blob/main/day20/day20.lisp

https://github.com/benknoble/advent2021/blob/main/day20/solution.rkt Hopefully getting faster soon

Ah, right, lisp

obviously sbcl is compiled, so that helps a bit. mostly just using hash tables. I usually solve game-of-life problems using just ints and bits, but a hash table is easier for this one because of the whole “infinite default value” part

some basic things I do, which might be helping:

• I don’t try and parse the “algorithm” line, rather just index into the string to get the char • I store 0 or 1 bits in the hash table, so i can just shift and or them together to get the index into the algorithm string

lol - just found out from sorawee that in-inclusive-range exists ! <sheesh>

I also just assume the size of the image increases by 2 in both dimensions each iteration. I don’t know that this is strictly true (could there be a pattern where one edge does something to where it shouldn’t grow in that direction?), but it works. I’ve seen a couple solutions where people iterate over all elements to find the largest x/y coordinate

Yeah I’m trying to optimizing my padding function atm. the string index is interesting; I’m not sure if that’s constant time in racket or not, but I think it is.

if not, just make a vector 512 in size of all 0/1’s

but i’m pretty sure it is. even if unicode, they are probably forcing 16-bit wide chars or something to ensure it’s O(1) indexed

Yeah. I’ve been using a hash for the decoder, but that’s probably more than I need.

Low hanging fruit got <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2021/solutions/day20/day20-performance.rkt|this version> down to 101 ms total :)

Oops - forgot to use unsafe in the macro - that got it down to 83 ms.

Well, I’ve implemented all the obvious things I could think of (string instead of hash, storing bits rather than chars, etc.) and it’s still not as fast as I want. But oh well.

Final timing is 53 ms for part 2 w/ parsing file.

It’s nice that Racket can be super high level, while still allowing some pretty nice performance optimizations. If we can get the math module to be fast for dynamically typed code, I’ll be a happy camper :)

Hmm… I’m not motivated to do this, but I’m pretty sure that instead of a get-pixel function that checks the x/y bounds and returns a default if out of bounds, it would be measurably faster to pad the image with the default value each time. Then, no need for bounds checking, and it’s just a vector-ref.

Lastly, “double buffering” by using just 2 big vectors should be a win :)

Double buffering likely isn’t much of a win unless you’re starting with a really small vector/hash and building it up. A single, large allocation once per iteration should be plenty fast.

My original version using integers (one per row) instead of a hash map and it was about 5x faster (finished in ~10 ms - with the close-but-wrong answer), but added complications when trying to handle the edge cases and the default value.

Instead of doing 9 pixel lookups you can get away with 3 (one per row) and OR them together.