We’re really happy to say that our very own Michael is participating in this year’s Advent of Code!
Advent of Code runs from the 1st to the 25th of December every year, and poses a series of increasingly difficult coding challenges that Michael has described as “starting off as fun but ending up as pain, misery and sadness”. He’s jazzed.
We’ve taken some time to explain what this is, but if you’re interested in how Michael is getting on with this, check the diary.
What is Advent of Code?
Advent of Code is an advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language desired. Participants use the solutions for a variety of purposes, including interview prep, company training, university coursework, practice problems, a speed contest, or simply to challenge each other.
Created by Eric Wastl, the event consists of problems that can be approached by anyone, regardless of their level of programming knowledge. Having said that, the problems become increasingly complex the further you make it through the list of challenges.
We strongly encourage anyone interested in programming to get involved with Advent of Code – after all, it’s your practical skills, not your on-paper qualifications that enable you to solve real-world problems.
How does it work?
Each day in December, a new puzzle is made available, including instructions and a handful of test cases with which to try out your solution.
Most importantly, everyone gets their own puzzle input, which means you can’t copy anyone else’s work. It’s a great way to challenge your capabilities and learn new skills.
There are few rules: you can use literally any language (or platform) you’d like. Run some test cases, debug, and fix. Once you think your solution is ready, use the real input and finally submit your answer. Got the wrong solution? You can always try again.
Michael's Advent of Code Diary
December 1st
It begins! The first day can be seen as a warm-up day, the problem given to you is nice and simple and can be solved typically in 10-15 minutes. This is a far cry from the last few days, which can take hours to solve.
The problem is given in two parts, with the second being a continuation and requiring you to add to or modify your solution from the first. Each part gives you one gold star, with 50 up for grab in total.
Whilst writing my solution for today’s problem, I realised just how out of practice I was with writing code in this style. Writing code for Advent of Code (AoC) is all about speed. The code doesn’t have to be elegant or organised, it just has to run and get you the right answer. It also doesn’t matter how you get to the answer as long as you get it. This has lead to some people solving problems with crazy tools. My go-to example is Detrang1301 on Github who wrote solutions for 2021 using Excel. For this year I am writing my solutions using C++, and will be sharing code snippets if I think they are interesting.
My favourite part of AoC is seeing how the problems given fit into the story for the year. Each year’s story follows a Christmas themed narrative and sometimes even has connections between the years. I am very excited to see where this years story goes!
Today’s Problem
In today’s problem we were given a list of numbers, representing how many calories worth of food each of Santa’s elves were carrying. In Part 1 we had to figure out which elf was carrying the most calories. Each number was on a new line, with an extra blank line in-between each elf.
For example:
1000
2000
2000
4000
7000
The solution to this problem was fairly simple. After reading in the input, I wrote a loop that split the input into a list of total for each elf. So for the example above I would have a list of two values, 3000 (1000 + 2000) and 13000 (2000 + 4000 + 7000).
To find the elf that has the most calories, I sorted the list in descending order from largest to smallest. Then I just grabbed the amount in the first slot. This turned out to be the best solution, as Part 2 wanted to know the total calories carried by the 3 elves carrying the most. This means I simply had to add the values in slot 1, slot 2 and slot 3.
Overall, the first day was a nice warmup and I’m looking forward to sinking my teeth into the harder problems.
December 2nd
Back for Day 2! Today was another relatively easy problem. So I am going to take the time to talk about another cool thing on AoC that I love.
If you go to the AoC site now, you will see the problems in a big list as a bunch of hashes and @ symbols.
As you complete each day, you unlock these lines, which upon completion form an awesome ASCII Art image. Here is what we have so far:
If you want to discover the rest of the image as the days go on, why not have a go at the puzzles yourself? It’s a great way to develop your problem solving skills!
Today’s Problem
Today we are playing games, good ole rock paper scissors specifically. The data input day forms a strategy guide.
In part 1 the first letter in the line tells us what the opponent plays: A for Rock, B for Paper and C for Scissors. The second letter is what we should play in response: X for Rock, Y for Paper and Z for Scissors. Score is a combination of the move we play (1 for Rock, 2 for Paper, 3 for Scissors) plus the outcome (0 for Loss, 3 for Draw, 6 for a Win).
Its time for a code snippet! C++ has a keyword called enum, short for Enumeration. It acts as a way to assign a human readable value to a number. For example:
enum MoveScores {
Rock = 1,
Paper = 2,
Scissors = 3
}
Many languages have enumerations, but the fun thing about C++’s is they can be converted directly to number values. This means my score calculation that would read:
score = 2 + 6;can read:
score = (int)Paper + (int)Win;This makes the code easier to understand. For AoC this might be a little bit overkill, as like I said on Day 1, speed is the most important thing. But it can be helpful to make your code easy to read, so when you have to make changes for part 2, it’s easier to work out.
To calculate part 1’s score, I simply wrote a loop to go line by line, figure out the score for that round using the logic explained above, and then added it to a running total.
For part 2 this time, the meaning of the second letter was changed, instead of being the move we play in response, it now represents our target outcome: X for a Loss, Y for a Draw and Z for a Win. This was pretty simple to do. I simply adjusted the inside part of the loop to reflect the new meaning. Instead of assuming X means Rock and comparing to the first letter, X now means Loss, so I look at the first letter and choose the correct response to lose the round. Score is calculated in the same way, so nothing needed to be changed there.
I hope this was interesting to read, and I look forward to updating again tomorrow! See you then.
December 3rd - December 5th
As you can tell by my last entry, I forgot it was the weekend! So I’m going to crunch down the weekend problems and today’s problem into one entry for brevity.
But first, I’d like to raise an interesting development in AoC this year, which is the advent (pun intended) of AI powered code solutions. Whilst I’m sure this has been a thing in previous years, I’ve noticed a serious rise in people using AI to solve the problems far faster than a human could.
For example using GPT 3 max-sixty on GitHub managed to place 1st on the global leaderboard for Day 4 of this years leaderboard. Whilst the cool factor cannot be denied of this from a technical perspective, it feels somewhat sad for the people who put a lot of effort into placing high on the global leaderboard.
However, I wouldn’t worry about the integrity of the competition being affected quite yet. As can be seen in this fantastic article by Nils Eriksson, GPT does not always instantly give the correct answer, and can require careful guidance to get to the correct result.
December 3rd
This was the first day I actually struggled slightly, but this was more because of limitations on my knowledge of C++ rather than understanding of the problem itself.
Each line in the input represents items in a backpack, with the first half being one compartment’s items, and the second half being another. Items are representing by a single character (a, p, e etc). We had to take a look at each compartment and find the only item that was present in both.
Each character was given a numeric value, a-z is 1-26 whilst A-Z is 27-52. The answer is the sum of the value of each item present in both compartments.
To solve this I sorted each backpack from smallest to largest, and then used the find first of function to get the first value that was the same in each string. This is the overlapping value.
For part 2 we had to treat each full line as a separate backpack, and find the item that is common between groups of 3 backpacks. I solved this using a data structure called a Hash Map.
In a hash map, values are stored according to a given “key” value.
In this context, the numeric value was the “key” and then the value stored is how many times we had seen it. I looped through each line, and for each item, I added one to the hash map under that key. At the end, I looked at the hash map and found the item that had a value of 3, meaning it was present in all 3 backpacks.
December 4th
This day I was super happy with my solution for. Each line of the input represents a range of numbers, for example 2-4 means 2,3,4 and 6-8 means 6,7,8.
Each line has two ranges, and we have to figure out if one of the ranges fully overlaps the other one. If so we keep a count of it, and the expected answer is how many pairs of ranges fully overlap.
This at first seems like quite a lengthy process as you have to make sure that the first one is not overlapped by the second, and then that the second is not overlapped by the first. However, using a data structure called a bitset, we can simplify this.
A bitset is a structure that stores a group of bits (0 or 1). So for example in C++
std::bitset<10> my_bits;
For example, 2-4 would be presented in 10 bits as 0111000000 and 6-8 would be 0000011100. We can do a bitwise OR operation on these, which means we compare each bit and if either of the bits is 1 the output has a 1 for that bit. So doing a bitwise OR on ranges 2-4 and 6-8 would give an output of 0111011100. This doesnt appear like it is useful, however lets take an example that DOES have an overlap.
Take the ranges 3-5 and 2-6.
3-5 is 0011100000
2-6 is 0111110000
OR. is 0111110000
As you can see in the above example, the output result from the bitwise OR is the same as the bit value of 2-6. We can use this to make the assumption “If the output from our bitwise OR is the same as either of the inputs, one of the ranges overlaps the other”.
Thanks to this solution, part 2 is simplified. In part 2 we need to get the amount of ranges that have any overlap at all, not just a complete overlap. This can be done easily by performing a bitwise AND, which is performed the same as an OR, but the output is only 1 when BOTH inputs are 1. We can then check the output, and if it has a 1 in it, then we can assume there is some overlap.
December 5th
For this puzzle, we are given a list of stacks of named boxes (each box has a letter), and a set of instructions on how to move the boxes between the stacks. The answer is a list of the boxes that are on the tops of each stack after finishing the instructions.
There is a data structure that perfectly maps this problem, which is aptly called a stack. The way that I remember having stacks explained to me the first time is imagine it like a pile of dirty plates. You can add a new plate to the top (called pushing) or take a plate of the top (called popping), but you cannot take out a plate from the middle without breaking the whole structure.
There isn’t much interesting to say about this problem, as we simply had to loop the instructions and move boxes between the stacks, and then at the end look at the item on the top of each stack.
For part 2, we had to assume that the order is retained when moving items between stacks. Imagine taking the top 3 plates all at once and placing them on top of another stack of plates.
I had expected this, which is why I used a deque instead of a stack. A deque can be thought of as a magical stack of plates, that can have plates removed from the top OR from the bottom. However, you still cannot remove from the middle. Using a deque allows me to pop the items from the top of the stack, and push them to the bottom of a temporary stack. I can then place this entire temporary stack on top of the target stack, which retains the order.
Summary
Hopefully this wasn’t too mind boggling to take in all at once! Back to daily posts tomorrow, see you then!
December 6th
Today was one of those anomaly days that was REALLY easy, I’d almost say it was easier than the first day. I’ve seen a theory that Eric makes the weekday puzzles easier than the weekend puzzles, because many people have to work their job during the week.
Today’s Problem
No fancy parsing today, we were simply given a long string of characters. The problem asks to find how many characters we need to go through the string to get to a point where the last 4 characters are all unique. For example the string “bvwbjplbgvbhsrlpgdmjqwftvncz” requires reading 5 characters in, then the last 4 characters from before that point are “vwbj”. This is easy to solve, by reusing a data structure used on Day 3, the hash map.
I took 4 consecutive characters and used them as a keys in a hash map (the value stored is irrelevant). Thanks to each key in a hash map needing to be unique, if the length of hash map is less than 4, I knew that one of the characters was a repeat. That means I increase the starting point by 1 and check another 4 characters. Eventually when 4 characters are checked and generate a hash map of length 4, the loop can be broken and using the current starting point + 4 gives the required answer.
For part 2 we simply had to considered a longer sequence of characters, so I just had to change the loop to check more characters and then change the required size for the hash map.
I’m scared for what is going to come tomorrow, as normally something easy is followed by something with fangs!
December 7th
As I feared, today did indeed have fangs! From now the puzzles will start to ramp up quite a lot in the time required to complete them. Therefore my entries to this post may become further spaced. AoC problems release for us in England at 4am, so I’m not always going to have enough time in the mornings to fully solve each puzzle.
Regardless, this was a fun problem to solve. It was the first place this year I decided to write some more extensible code, which lead me into doing some Object Oriented Programming, or OOP. Let’s explore!
Today’s Problem
The input today was a crazy one, representing a list of terminal commands and outputs. These commands map out a filesystem, and the size of each directory and file within it. The problem prompts us to find the sum size of all directories that are over 100,000 bytes in size.
An important thing to mention is this is a recursive problem. Take the directory paths C:/123/abc/456 and C:/123/abc/789 . The size of folder abc includes the size of everyone within 456 and 789. The size of folder 123 contains everything within 456, 789 and abc. Each directories size is equal to the total sum of EVERYTHING below it.
To solve this problem effectively, I decided to use a tree structure and write some classes to help structure the code. Let’s break each of those down.
The Tree
A tree is a data structure which starts with one item at the top. This item can then have multiple children, who can all have multiple of their own children etc. It is easy to understand when you see it drawn out.
Paddy3118, CC BY-SA 4.0, via Wikimedia Commons
As you can see in the diagram, it looks like the roots of a tree flipped upside down, hence the name.
Classes
Classes are an organisational structure, that allows us to write code that mirrors our real world understanding. For example I could define a class as:
class car {
int wheels = 4;
void drive();
}
The real power of this comes from being able to define children classes. For example I could have a new class called “Polo” that expands on the “Car” class, and adds new functions and data. This helps keep the code organised and closer to being human readable.
How it applies
Using the two ideas explained briefly above, I created a “File” class. It looks something like this (not complete)
class file {
FileType type;
int size;
file* parent;
list<file*> children;
}
FileType is an enumeration (explained in Day 2) that is either Directory or File. The parent and children variables are pointers, however I will not be explained those now as it will make this post to long. Alls that matter is that we use them to move from file to file.
After creating this class, I can create a single directory to represent the root of the file system. I can then loop the given instructions and create new directories and files as needed, with each new being added as a child to the correct entry. By the end of the problem input, I have a tree built of the entire filesystem, which can be accessed using the root directory object we first created.
For part 1, I walked through this tree and summed to a running total all directories that had a size of over 100,000 bytes.
For part 2 we had to find the smallest directory we could delete, to reach 30,000,000 bytes free. This simply required us to first find how much space is left (70,000,000 – size of root), find the difference between this and 30 million and then walk the tree again to find the smallest folder that is more than that amount.
Hopefully this wasn’t too mind boggling. See you again soon!
December Xth - The transition
It’s reached the time of AoC where the problems take enough time to solve, that I simply cannot get them done the same day of release (unless I’m willing to wake up at 4am everyday!). I will still be completing each day, but my posts will be saved for interesting parts of the problems that arise. I’m currently preparing my post on what is possibly my favourite AoC problem ever, so look forward to that one!
