aoc2021 VS AoC

Can confirm, I implemented Djkstra badly (I made it visit every single cell, instead of stopping once it reached the end, since that's what wikipedia did), switched to A* w/o visiting every single cell, got the answer for part 2, and returned to the non-stupid Djkstra and measured -- A* with manhattan distance is about 5ms faster than A* with euclidean distance (since it avoids the square root, and the euclidean distance is actually less appropriate in this situation), and Djkstra beats the Manhattan distance by another 5ms. You can look through all my implementations in the commit history for this file: https://github.com/ritobanrc/aoc2021/blob/main/src/day15.rs

Rust, not my proudest code, honestly quite messy, I couldn't decide whether to represent points as Vector2 or usizes into a vector, using both a HashSet for flashed but a Vec for to_flash feels silly, especially since it calls contains on both in the same condition, nor am I proud of the rightward drift resulting in five layers of braces, and the messy conditions on neighbor. But nonetheless, it works, and part 2 was easy enough to hack in on top of part 1, with a couple extra lines (albeit, still a bit messy, with a range 0..usize::MAX since bounded and unbounded ranges are different types, and an unreachable!() in the match statement at the end).

Rust. I found today surprisingly easy, much better than the last couple -- part 1 was quite simple, just keep a list of the open ones and close them as necessary. Part 2 should have been trivial to implement on top of that, but I wasn't correctly discarding the corrupted lines, and apparently sorting a list and finding the median without off-by-one errors is hard, so that took a while to debug.

Rust -- part 1 was fairly easy, but I had absolutely no clue how to do part 2 for a long time. I ended up just brute forcing it, trying every single possible wire re-arrangement (thanks itertools::permutations). I used a bitmask to represent which lights were on (no idea if its necessary), but it was a fun exercise trying to get the bit fiddling right -- I was pleasantly surprised when it just worked (ig that's the benefit of writing small, fairly self-contained routines). My initial answer for part 2 was also reversed (3535 instead of 5353), which is why there's a rev in there near the end. Overall, very fun challenge -- I enjoyed not knowing how to approach it initially, and I'm sure lots of people will have far more clever solutions.

Rust, basic bruteforce solution. Played around with trying to find an analytic solution for a couple mins, but ended up just brute forcing it, and surprisingly, its not absurdly slow.

Rust. Unsurprisingly, I did the naive thing for part 1 and then had to re-write for part 2. I'm happy with how clean part 2 is, I just used a Rust array for the counts -- though I'm sure there's a more clean solution for shifting an iterator.

From u/ritobanrc (full solution): use nalgebra::Matrix5 and you can use column_iter() and row_iterator() on your board.

Rust -- Happy with how my code turned out for today. I used nalgebra's Matrix5 for storing the boards, which made checking for wins pretty easy.

Rust, nothing special here, not particularly fast (I initially thought aim should be a vector and lost some time because of it). The error handling could be a bit cleaner, I might fiddle with that for a bit so I don't have to put .unwraps and .expect and panic! everywhere.

Here's my solution without any collects: https://github.com/ritobanrc/aoc2021/blob/main/src/day01.rs -- but I don't think you could do it without itertools, since windows is only implemented for slices, and array_windows for iterators is still unstable (pending const-generics).

Part 1 took a bit of fiddling around debugging. I parsed the input into a list of coordinate pairs. I then found the largest X and Y value I could possibly be interested in, and then, for each X value, I checked if the column was clear, and if so, expanded it by adding one to the coordinates of all galaxies with a greater X-value (I spent quite a while trying to find a bug here - turns out that I'd messed up my conditional jump and was instead adding one to the coordinates of all galaxies with a smaller X-value - oops), and then adjusted my loop index and bounds to account for the extra column. I did the same with the Y-value. Finding the pairwise distances was a matter of, for each pair, calculating the taxicab distance. I did some fancy footwork with x86_64's SIMD instructions, doing a packed subtraction of quadwords. Alas, a packed absolute value of quadwords was something that required AVX-512, which my CPU does not support (and, in fact, most CPUs don't support - it's probably a server-tier CPU thing).

For both part 1 and part 2, I parsed the file into a set of flags - does the current space connect north, south, east, west? Is it, in fact, an actual space in the map? And is it marked as the starting space? I then converted the starting space into a regular space, but remembered its coordinates.

Part 1 involved a direct solution - for each line, I read it into a dynamically allocated array, then allocated a new array and calculated the differences between the previous array's elements, and so on until I got an array that's all zeroes. I then proceeded to extrapolate - I found the end of the list, and added the end of the previous list to this list to get the new element to add to the end of the list - I actually didn't need to save this value in new space, I could have just overwritten the old end of the list.

Part 1 was implemented pretty much following the problem statement - I chose to represent the map using a dense data structure (since, after all, RAM is cheap enough that I can ask for 26^3 * 4 bytes (~70kib) just because). I parsed the instructions and the map, but I found I couldn't zero-terminate my instructions, since I was representing left as zero and right as two (since these were actually memory offsets). I thus used 0xff - something the fullptr folks might appreciate. The map was parsed as follows - I treated each node as a base26 integer, where the first is an index into an array of pairs of words, and each word is the index that the left and right nodes lead to.

Part 1 and part 2 were surprisingly similar - for both, I parsed the cards, mapping letter cards to their rank ordering (so for part 1, t = 10, j = 11, and so on, and for part 2, t = 10, j = 1, q = 11, and so on (although I could have just modified j = 1, I guess...), and recording the bid, as a word - I decided that I would pack the input data into a qword per hand so that I could apply my qsort function that I'd already written with minimal modifications.

Part 1 and part 2 were very similar. The parsing was very standard, but then I had to do math with floating point numbers. And that involved new instructions - cvtsi2sd, for example (convert scalar integer to scalar double), and the rest of the modern SSE floating point operations. (While you could still pretend you had an 8087 and use such instructions as fmul, in practice, it's a lot nicer to use the SSE equivalents.) I then had to round everything back into integers, but I also had to fake the rounding modes "ceil-but-always-move-up-one" and "floor-but-always-move-down-one" - which lead me to the comisd (probably stands for compare like integers scalar doubles) instruction. Apparently there's a cmpsd instruction, but it returns results as a mask, which I guess might be useful for branchless operations on floating points. I didn't want to bother, and performance was not a major concern. You do get the default floor and ceil rounding modes, though - as well as truncation and rounding to even. I also had to deal with floating point constants. Floating point constants can't be inline, they must be loaded from memory, so I had to use the .rodata section for the first time.

Here's the cross-assembler with the part 1 runtime hardcoded, and here's the cross assembler with the part 2 runtime hardcoded. Both parts follow the same methodology: copy the prepared ELF header data, then copy in runtime setup code into the file. Next, output generated x86_64 for each Elvish instruction (which includes an inlined call into the runtime), finally, copy in the runtime exit code. and output the entire file.

Part 1 and part 2 were both implemented as interpreters directly interpreting the assembly code. This was the first time where we absolutely had to deal with negative numbers, so I had to write a parser that was cool with negative numbers, and an output formatter that was also okay with negative numbers (mainly for debugging). (I should add ascii-to-signed-long to the common library.) Unfortunately, I'm not willing to do OCR using assembly, so I printed out the result as pixels and manually translated that into ASCII characters. The core evaluator between the two parts was quite similar - the only difference was what happens during the cycle. With part 1, I had to sum up certain cycles. With part 2, I had to add characters to an array.

Part 1 starts by parsing the input. I first count how many steps there are (e.g. "R 4" is 4 steps). Then, after allocating an array to hold those steps, I read in the steps and expanded repeats.

In part 1, I parsed the input, first getting the size of the input (bear in mind I'm challenging myself to assume nothing about the size of the input), then reading it in. I could probably have used loop, lodsb, and stosb to write more concise parsing code. Then, for each cardinal direction, I marked the trees that were visible from that direction, and finally counted the trees that were not visible from any cardinal direction.