Advent of Code 2020 Review

Posted Saturday, December 26, 2020 in Programming

Advent of Code

This is a set of 25 programming puzzles released over the course of the advent, one puzzle each day. The puzzles somewhat increase in difficulty from start to finish. The nice thing about the advent problems is that you're not limited to an online compiler and there technically isn't any emphasis on micro-optimizations. There are still some questions that require a different approach than bruteforcing the problem given that the bruteforce approach would take an inordinate amount of time and processor power.

The Process

I worked on each problem as they were released (12pm EST) and recorded myself working on each one. I used c# as my language of choice, using the new .NET 5 runtime. You can see my code here on github.

The overall goal here was to 1) have some fun programming and 2) see where I need to work on for self-improvement.

What went well and what didn't

The majority of problems I was able to solve and without too much issue and I averaged around a 1000-3000 placement for each day. For these I suppose the only thing that would get me into a lower completion time would be more practice on puzzle type programming, learning shortcuts, and practicing the different type of datastructure traversals (e.g. multidemensional arrays, circular arrays, b-trees, etc…).

Now, what I'm most concerned about is where things didn't work out so well. These appeared to be areas where my knowledge of number theory and certain datastructures appeared to be lacking. In particular, the questions that gave me issues where:

Besides the day13 need for knowledge of moduli theory, the core issue of these problems was knowing how to take the problem requirements and to reason out the key information that alluded to the solution. For example, in the day10 problem we're presented with a set of rules describing how you'd start at the beginning of a sequence and generate the rest. If we followed this sequence generation requirement we'd end up having an extremely inefficient solution due to how each sequence step required knowledge of previous sequence segments. Now, memoization was the solution here, but the key to memoization is the ability to work from the end of the sequence (step 1+n) and work our way back to the beginning of the sequence. The eureka moment here would need to be “hey, I can start at the end, work my way back, and use memoization to improve the running time.” This should have been obvious to me, as I learned memoization with the fibonacci sequence being the example, which is pretty close to the day10 problem. However, I believe where I was lacking on this particular problem was the ability to reason about the memoization method in a more abstract way such that it would be more easy to determine where it was applicable. Simply just running through a programming technique and saying, “neat you can use this to do exactly this” without thinking about its wider application would be insufficient to really own that piece of knowledge.

Beyond owning programming knowledge, I noticed I struggled with a few core concepts in discrete mathematics and number theory. Even if I didn't memorize every programming related math theory, I should at least be able to take some core concepts in a problem (e.g. coprimes are used, sequence of moduli, combinatronics, etc…) such that I could research math related problem efficiently.

A couple c# things I learned

You can hash tuples. This came in handle a couple times that allowed me to create dictionaries or hashsets based on coordinates. C# lets you create dynamic tuples as well so you could do something like so:

var coordinates = new Dictionary<(int,int), string>();
coordinates.Add((0,0), "starting position");

Console.WriteLine("At x=0, y=0 we have {0}", coordinates[(0,0)]);

Keep in mind that there are some things that cant be hashed this way. For example, integer arrays and generic collections aren't going to work well with this approach.

One other thing is the modulus on an exponent provided in the BigInteger class. This turned out to be way faster than the manual approach:

var result = Math.Pow(x, y) % z // SLOW!

var result = BigInteger.ModPow(x, y, z); // FAST!