Notes

Problem 1 part 1.

Originally I wrote a pure functional implementation with a fold() in calc_manhattan_length. But state needed to be kept in 2 places, the current position and the current direction. I decided that was harder to read than just mutating the direction as we go, so I changed it.

Problem 3 part 2.

I really wanted to create something functional and elegant for part 2 like I did for part 1. While it's pretty compact and it makes perfect sense to me, I wonder if it would be clearer if I had written it out with for loops and kept a counter variable. It would be more code and look messier to me, but might be easier to follow for someone not inside my functional head.

After looking over others' solutions, it hit me that I gave a more complicated solution to part 2 because I reused my is_triangle_possible implementation from part 1. I should have rewritten it to create a simpler solution overall.

Also, that code I stuck in main for part 2 really deserves its own function and a unit test.

Problem 4.

I solved the first part without using regexes, but after looking at the second part it was clear that using a regex would give a clearer and simpler solution. It would be cleaner overall to rewrite part 1 and make the whole thing use a regex.

Problem 5.

To avoid reallocating a string for every index that's tested, I create a string in get_password, truncate it on each iteration and append the new number at the end. Truncation should not change the string's capacity.

Problem 7.

Solution was very straightforward. The windows() iterator on slices comes in handy for many Advent of Code problems. I first considered parsing the string carefully to find things inside brackets, then realized that if the brackets are balanced we can simply split the string everywhere we find [ or ] and the resulting list will alternate between outside brackets and inside brackets. This solution would fail if the problem input contained tricks like including a [ inside a hypernet sequence.

Problem 8.

Because the light grid is so small (50 x 6 = 300 bytes) I went with a 2D array of bools for the data storage. If the display had been huge I would have been tempted to pull in the bit_vec crate. Bit twiddling is rarely worth the trouble when storing relatively small amounts of data.

To rotate a column or row I just make a copy. There are more efficient ways to rotate an array than that (look up "juggling algorithm" for example) but again, for the small amount of data here it doesn't seem worth it.

Problem 9.

For part 2, originally I tried making the recursive function take an Iterator argument, with the idea that I could call take(...) to make it iterate over a subset of the string slice iterator. This failed to compile because it woud recursively expand the type argument, so that it was Take<Chars> the first time, and Take<Take<Chars>> the second time, etc. I think I could have made it work using a boxed iterator but I really would have been disappointed if I had to resort to dynamic dispatch, so I changed it to the current method using string slices. I think the solution is quite readable anyway, so I am not disappointed in where it ended up.

Problem 12.

It wasn't clear to me from the instructions that the jnz instruction has an immediate form as well as a register form. I only found out when I ran my problem input. Unknown whether the immediate forms of cpy and jnz could take negative numbers as input, but I handle them anyway. The only negative numbers that appeared in my problem input were jump offsets.

My initial implementation turned out to be quite slow, taking about 20 seconds to complete both parts on my PC. It parsed each instruction every time using a regex.

Later this was optimized by preparsing everything. It has the benefit of separating the code that parses assembly input from the code that executes instructions. The end result is more readable, in my opinion.

Problem 13.

Simple breadth-first search to solve this problem. BFS means the first time we find the goal, it's already the shortest possible path so no need to keep exploring.

Problem 14.

Personal note, I really dig problems like this. It has a straightforward solution that is easy to implement but slow. With careful optimization you can make it much more efficient. In this case, the straightforward solution is to search for triples and then when you find a triple, search forward 1000 indices for matching quints. But that forces you to search for the same quints again and again. The optimized form I implemented creates queues of triples and quints. I read ahead by 1000 indices and then check the oldest triples for any matching quints. I throw away the triples as I go, but because quints are extremely rare I don't bother throwing the oldest away. Would have just added a bit more code for no measurable performance benefit.

For the second part, again there was a straightforward implementation (formatted write of the MD5 sum) that turned out to be quite slow when performed 2016 times for each index. Profiling with valgrind/callgrind showed most of the time spent in formatted write operations. I replaced it with a simple table lookup for a big performance boost.

After that, profiling of part 2 showed most of the remaining time for part 2 spent in the md5 library. I farmed the md5-related work out to worker threads using futures-cpupool for another big speedup.

Problem 16.

There are tricks to calculate whether a given step is a right or left turn in a standard dragon curve without reading the previous elements, but since this is a modified form I'm not sure that I could use those tricks. So I just keep the whole list in memory and generate new values on the end from the existing ones.

To calculate the checksum, I just calculate each element of the final checksum directly rather than iteratively reducing the original data in half until the length is odd. I observe that data_len = checksum_len * 2^N where checksum_len is odd. So I just count the zeros at the end of data_len, which gives me N. From there I can reduce data in chunks of 2^N bits at a time. Being able to use the chunks iterator that Vec<bool> provides is the primary reason I used Vec<bool> instead of the bit_vec crate. You'll see the type alias BV used because I wanted to be able to switch easily between bit_vec and Vec<bool> if I changed my mind later.

Problem 17.

Straightforward breadth-first search, similar to problem 13. One thing that may be interesting in this solution is theiter() method I implemented for the enum Dir. This lets you iterate over all four variants of Dir.

Problem 18.

The problem as written makes trap detection more complicated than it really is. If you think about it carefully, the center tile makes no difference. In fact, the new tile is a trap only if the left tile is different from the right tile. One way to make this even faster would be to encode each row as a bit vector, make 2 copies of the previous row, shift one 1 bit left, the other 1 bit right, and xor them together to get the new row. However, it ran plenty fast with my initial Vec<bool> implementation so I left it alone.

Problem 19.

My initial implementation for part 2, which I've left in the source, removed the victims from the elf Vec every time. Remove from a Vec causes all elements to the right of the removal to be copied, so it's really slow with the huge elf Vec we had in this problem. Replacing the Vec with a VecDeque can make some removals slightly faster but it's still terrible performance. I studied the pattern when choosing the next victim and found that it alternates between incrementing by 1 and incrementing by 2. So then I changed it to pass over half the elf Vec at a time. Worked much better.

Problem 22.

It turns out, the problem set I got (and most like the one that everyone got) has exactly 1 empty node and all others are either nodes that can never move or nodes that can only move to the empty node. Just like the sample data set. We can use the list of viable pairs from part 1's solution to find which is which. After that it's not so hard to find the solution.

I use the same algorithm given in the example, first sliding the empty node to the position just to the left of the goal data, then just a repeated number of shimmies to get it moved left to node (0, 0). I have to make a number of assumptions to get this to work, which I check for in code. If any of these assumptions are broken, my solution will not work, but it would also take longer and be more complicated so I'm sticking with my lame solution.

The find_steps function is recycled from day 13. I might come back to this and refactor it into a common lib. Originally I wanted these all to be standalone examples but I think it's worthwhile to show how a lib would work.

Problem 23.

This solution was not difficult to build on top of Day 12's solution. The only thing that felt a little ugly to me was I had to clone the instruction in a couple places so I could match on the instruction and then modify it within the match. It seems to me there should be a way to express this in safe Rust code without a copy or temporary variable but I couldn't think of a way.

The second part took about 25 s to run on my PC. It's worth coming back to this later to optimize further.

Problem 24.

Plan to reuse problem 13 solution to find shortest path between every pair of nodes. Once I have distances between every node it's essentially the traveling salesman problem, except I need to brute force the absolute answer. There is definitely opportunity for parallism here.