Thursday 30 December 2021

Advent of Learning 2021

I came across Advent of Code a few years ago and last year I introduced it to my team at Superdrug. For those who aren't familiar, it is a series of programming puzzles acros the 25 days of Advent; there are two puzzles each day, completing the first one unlocks the second one which is a variation or extension of the first. You can complete them in any language/environment.

This is what I've learned this year from doing AoC.

I had an aspiration this year to do at least some of the puzzles in JavaScript instead of C# so I could brush up on my JS a little bit/learn a JS unit test framework. But by the time 1st Dec rolled around I had nothing in place (or more accurately, I said I wanted to do some in JS but then did nothing else about it), so I've done everything in C# again this year, JS will have to wait another year.

I did a couple of the early days in bed first thing in the morning on my Surface Pro tablet, but I found the Type Cover keyboard a little too fiddly on an unstable surface so switched after that to doing them at my desk on a full-size keyboard.

Exponentials and Overflows

Day 6 featured exponential growth of lanternfish. If there's one thing we should have all learned in the past two years, it's how to model exponential growth... There was a trap in the puzzle in that you could complete Part 1 by modelling each individual fish, but the numbers of fish were so large in Part 2 that this approach wasn't viable (I briefly contemplated spinning up a high performance VM on Azure to run my solution...).

So I completely rewrote my solution to work on a Dictionary<int, int>, where for each day that passed the number of fish at each stage of their life dropped down a step. I ran this solution for Part 1 to confirm it gave me the same answer as my previous solution, then ran it for Part 2 and entered the result to the AoC site to get my confirmation. To my surprise the answer was still too low! Debugging into my solution I discovered some of the values in the dictionary were becoming negative numbers, and it took me a minutes thought to work out that this was probably integer overflow, the first time I can recall coming across it in 25 years of coding professionally (I very rarely deal with numbers large enough that the problem arises). I changed the dictionary to Dictionary<int, long> and the puzzle  was solved. 

Stacks

In Day 10's puzzle, you had to find a corrupt character in a string, which in another first for me marked the first time I can remember having to use a Stack. 

(I was watching my friend Dylan doing this one, and he figured out it was a Stack machine within a few seconds, but says that is the result of having had to write a LISP interpreter at college...)

A* and Djikstra

Day 15 required you to find the lowest risk path through a cave filled with chitons. Which in turn required me to learn about the Djikstra and A* algorithms, and then implement one of them. I found a C# version of A* that I could crib from, and wrote my solution. Which didn't (and at time of writing still doesn't) work.

However discussing it with my team, we were talking about practical uses for A* and think we could use it for planning routes through our stores when in-store staff are picking customer orders. 

LINQ

The puzzle for Day 7 involved crabs in tiny submarines moving from side to side and finding the most efficient point for them to align on (you get used to this sort of imagery when you do AoC...). For which based on the example I took to mean finding the point on which the most submarines were located. Which meant  I had to properly learn how to use the GroupBy method in Linq. And this was useful again on Day 14 where having constructed a long string of letters you had to find the most and least common occurring letters, I used GroupBy to project each letter and it's count, followed by OrderBy and OrderByDescending to get the two letters. 

On Day 4, we were playing bingo with a giant squid, and the task in Part 2 was to find the last winning bingo card from a set of cards. Which I was struggling with in using Enumerable.All, when I switched it to List.TrueForAll it worked first time. I've just looked up the docs for Enumerable.All and I have a feeling I may not have been calling it the correct way. (Incidentally our dev manager had a great hack for this day where after laying out the bingo cards, he transposed the columns into extra rows so that when checking for a winning card he only had to write a method for finding a winning row and not worry about columns as well.)

Also in the aforementioned C# implementation of the A* algorithm, it uses the List.FindIndex method which is not one I've come across before, and when discussing this with my colleagues they mentioned the List.IndexOf method. These two methods look pretty much identical, but it looks like their implementations are different - there's some discussion in the answers to this SO question which suggests that IndexOf is about 10 times faster than FindIndex.

Wrap Up

I've picked up quite a few things this year that I can take back to the day job, GroupBy being probably the one I'm most pleased about and potentially the most applicable. And I did set a new PB this year.


I also made some useful changes to my AoC project template. For next year I'd really like to make this a template in Visual Studio so I can have solutions named for the day they are for instead of multiple AdventTemplate solutions. And I still want to get a template together for JavaScript ahead of AoC 2022.

1 comment:

AOC Newbie said...

Thanks for the write-up. I liked that you took us through your stumbles and victories.

Very relatable!

This was my first year doing AOC and really enjoyed it.

As an aside -- I live in Pacific Standard Time Zone which means the daily AOC is released at 9:00 PM (a much more sane time than 6:00 AM). I give myself an hour or two to do the problem and then shelve it for the next day. Sometimes, it means completing part 1 and thinking about part 2, and in the second half of the month it more often than not meant going to bed with neither part completed.