Ive had an idea but not had time (may not have time) to implement it. Instead of a shortest path on the massive grid, do all pairs on each tile (only 9, and theyre smallish). Then build a new graph as follows: include the source. It has edges pointing to each outer-rim node of its tile, with cost the shortest path cost from before. Connect each outer-rim node of that tile to the corresponding outer-rims of the next tile and to the adjacent nodes. For each tile connected this way, you only have to create edges based on the outer-rims (cost is either (a) moving between two adjacent nodes or (b) moving across the outer rim of a tile, as given by the all pairs). Finally the last tile has the destination. Do dijkstra on this smaller, dense but not super dense graph. As an optimization, the first and last tiles can do dijkstra (from source or dest, respectively, since it’s really undirected). Building that graph seems complicated algorithmically, but I suspect the smaller memory pressure and smaller number of things to do will be a win.
A picture makes the idea clearer but i had the idea in bed and have just woken up
On another note, I was curious about the performance of a heap vs sorting a list each time something is added vs. inserting something in order in a list, so I did <https://gist.github.com/lojic/78cc5c89e0080331f487e2db9c44dc47|some benchmarking> of how many elements for roughly 100 ms: sort each time = 1,650
insert into list = 6,500
heap = 115,000 The 1st and 3rd results weren’t surprising, but I thought the insertion might be faster than it was.
Once I had the parser going (not too hard), the rest was just mini interpreters. https://github.com/benknoble/advent2021/blob/main/day16/solution.rkt the hardest part was not finding a good stdlib way of decoding the hex into a correct bitstring (my initial idea of composing (~> (string->number 16) (number->string 2)) doesn’t work because you lose left-padded 0s and you cant add them back because you don’t know how many should be there). I actually really enjoyed this, but maybe I just find interpreters fun
Glancing at the comments, Bogdan and I noticed the same problem (you lose the left-padding)
> and you cant add them back because you don’t know how many should be there You do. Every hex char is a nibble. So you need (* 4 (length string)) binary characters total. If you need 12 and have 10, just prefix 2 #\0s to the string.
That won’t work if the first 6 bits are 0s. Then you need to add 6, but you can only detect the missing 2.
And AFAICT, that’s valid
Sure, but again - that’s known: just count the # of leading #\0 hex chars? Obviously now it’s getting more complex than what you have currently, but it is doable. :slightly_smiling_face:
The thing is you don’t get the leading #\0s, at least the way I was doing it, because (string->number 2) throws them away. It was faster to dump the hex-table in (paste the table from the input and a single :s does most of the work, thanks vim). Maybe I’m missing part of what you’re saying, though
Ah, I think I missed the part about string-length; I think I got to the point where I considered that and said “writing the table myself is faster”, but maybe there was a reason it was broken and I can’t remember it now.
Let’s say the input hex string is 0123. That’s binary (split on the nibbles for readability) 0000 0001 0010 0011. So, the input string is 4 chars long = 16 binary chars required output. When you do (format "~b" n) you only get 100100011 output (9 characters), so you need to prefix it with 7 more #\0s.
Yeah, I think you’re right. sigh. I threw away the padding code I had originally, but oh well. At least it works (and it’s pretty fast)
<https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2021/solutions/day16/day16.rkt|Day 16>
I briefly thought about trying to use a “real” parser e.g. parser-tools, but I was pretty sure it would’ve taken me much longer. Might be worth pursuing later though.
Oh, neat idea using a list of 0s and 1s.
There was enough complexity in the puzzle description, so I went with the simplest thing I could think of to keep me on track :)
Day 17
I just brute forced it :man-shrugging: