Advent of Code 2020 notes

There is a yearly challenge named “Advent of Code” in which I took part this year . Here are some notes and analysis.

If you’re not familiar with it, Advent of Code is like a Christmas calendar for programmers. Starting from the 1st of December, there are daily tasks available. Each “day” consists of two parts, the first one is a “basic problem” and the second one is usually a slightly modified version of it, usually much harder. All you need to do is to submit a correct answer, you can solve your puzzles in any language, using Excel or just a piece of paper.

You don’t know what part 2 will be until you solve part 1. You often find yourself in a situation that you need to rewrite the entire program.

All my code is available here if you want to take a look, but beware, some of it is disgusting. Of course, I was writing in Rust, because why not.

🔗Why?

This is an important question. If I can’t find an answer to it, then eventually I’ll drop it, just as many people did. So my receipt of driving things to completion: ensure that you know why you’re doing something and don’t do it if there is no reason!

Here is my reasoning for participating:

🔗Refresh algorithms in memory

Working as an “enterprise” developer means that 90% of tasks are just about transforming data fetched from somewhere and serving it in a specific format. Not that exciting, right? What is worse is that there is almost no algorithm skill required. Any data structure that you may need is already written and all problems are solved . You just need to search a bit and apply a pre-made solution.

Modern programming is more like a building from blocks. You just need to know those blocks or know where to get some.

On the other side, this type of challenges usually require implementing a very custom logic or super-efficient solution, because the hot loop will be intentionally iterated literally 10000000000000 times.

🔗Relief of a daily programming routine

The Advent of Code gives me a rare opportunity to test my skills in “olympiad programming”. This is a completely different skill than “enterprise programming” because:

• You don’t need to write reliable code, just get an answer
• You won’t read this code ever again so “spaghetti”, “stinky”, or highly obscure code is pretty much okay
• You don’t need to collaborate with anybody, communication skill is not used
• Nobody will see it. No comments thus
• Copy-pasting instead of shared logic is also fine
• Specifications are clear (almost all the time)
• Output is well-documented, test cases are already written

So yeah, I would consider those two completely independent skills.

🔗Change my daily routine

With the pandemic going on (just search for 2020 on the internet), my day now lacks many small things like dressing, commute, and podcasts :) I can’t make myself do pointless things, like walking out before coming back home for work to maintain the routine. After many months of getting up, having breakfast, going to work, and then back to sleep, I began to feel that this is not so healthy.

I needed to break this loop and the best way to do this is to introduce something new, change the schedule, set alarm to a different time, or somehow else change the things or move them around a bit.

Each Advent of Code day unlocks at 7:00 in my timezone, so it was a perfect chance to do that! Now when the challenge is over, I’ll spend this additional morning time writing for this blog.

🔗Community

There is a huge reddit community around Advent of Code. 146 000 participants solved day 1, which is a HUGE number. Even my colleges organized a private leaderboard, though I was the only one who completed all the tasks. It’s amazing to see all this activity going on and share problems and solutions with others. In the morning you write Conway’s Game of Life for 3 and 4 dimensions, a few hours later you see a visualization of it!

🔗Days

I won’t go into every single one of them, just highlight the most remarkable ones. If you want a detailed walkthrough, take a look at this awesome article series by Amos.

🔗Day 1: Report Repair

TL;DR: Find two numbers in a list that sum in 2020

The start was super easy, few lines, and part 1 is done.

For part 2, find 3 such numbers

Copy-paste one line and part 2 is done as well.

I was a bit disappointed, so I decided to implement a general solution for any given N. This turned out to be somewhat tricky, since I didn’t want to use any side libraries at that moment, so I implemented an array of indexes:

const N: usize = 3;

// This is a const fn, so the value is computed during the compile-time!
// it just produces a fixed-length array like
// [0, 1, 2]
const fn get_indexes() -> [usize; N] {
    let mut result = [0; 3];
    let mut i: usize = 0;
    // for loops do not work in const fns :c
    loop {
        if i == N {
            break;
        }
        result[i] = i;
        i += 1;
    }
    result
}

// Tries to increase the index array by one
// true => increase successful
// false => no, abort, abort!
// This probably could be implemented as iterator!
fn increase(indexes: &mut [usize; N], max: usize) -> bool {
    // Find the index's index that can be increased
    let increasable = (0..N).rev().find(|&i| {
        let local_maximum = if i == N - 1 { max } else { indexes[i + 1] };
        local_maximum - indexes[i] > 1
    });
    match increasable {
        Some(i) => {
            let start = indexes[i];
            // Starting from that index set values of all consequential ones
            for (j, index) in indexes.iter_mut().skip(i).enumerate() {
                *index = start + j + 1;
            }
            true
        }
        None => false,
    }
}

// Just iterating over these indexes
fn find(numbers: Vec<i32>) -> i32 {
    let mut indexes = get_indexes();

    loop {
        let elements = indexes.iter().map(|&i| numbers[i]).collect::<Vec<_>>();
        if elements.iter().sum::<i32>() == 2020 {
            return elements.iter().product();
        }

        if !increase(&mut indexes, numbers.len()) {
            panic!("Bad input!")
        }
    }
}

🔗Day 4: Passport Processing

TL;DR: Validate a lot of passports by field requirements

Just recently I step across the validator crate by awesome Vincent Prouillet a.k.a Keats.

I was really happy with the result:

// Main struct.
// Validate trait adds .validate() method, which tells is the struct is valid or not
// Validity of fields if determined by an annotation
// We can even use custom validation functions (validate_hgt, validate_pid)!
#[derive(Debug, Validate)]
struct Passport {
    #[validate(range(min = 1920, max = 2002))]
    byr: u16,
    #[validate(range(min = 2010, max = 2020))]
    iyr: u16,
    #[validate(range(min = 2020, max = 2030))]
    eyr: u16,
    #[validate(custom = "validate_hgt")]
    hgt: String,
    #[validate(regex = "HCL_REGEX")]
    hcl: String,
    #[validate(regex = "ECL_REGEX")]
    ecl: String,
    #[validate(length(equal = 9), custom = "validate_pid")]
    pid: String,
    cid: Option<String>,
}

// Few validation regexes
lazy_static! {
    static ref HCL_REGEX: Regex = Regex::new(r"#[0-9a-f]{6}").unwrap();
    static ref ECL_REGEX: Regex = Regex::new(r"(amb|blu|brn|gry|grn|hzl|oth)").unwrap();
}

// Validation function example, the other one is a bit trickier
fn validate_pid(pid: &str) -> Result<(), ValidationError> {
    let err: ValidationError = ValidationError::new("pid validate error");
    pid.parse::<u32>().map_err(|_| err)?;
    Ok(())
}

That’s it, problem solved.

🔗Day 10: Adapter Array

TL;DR: Count all the possible ways to traversal a graph in which edges can connect vertices with no more than 3 value deltas

I didn’t want to deal with the graph problem myself, so I tried to use petgraph. That didn’t work well.

This was the first one on which I stuck for quite a while. The issue is that the input graph has too many branches, so if you’ll try to actually “build” all the paths and then count them, it would take ages to complete.

But petgraph allowed me to get an image of a test graph:

Looking at it for quite a while, I realized that the number of ways you can get to node 7 equals the number of ways you can get into 6 + same for 5 + same for 4.

Problem solved!

🔗Day 12: Rain Risk

TL;DR: You need to navigate a boat in a storm first using absolute directions, and then relative

Nothing special or difficult here, but I enjoyed this one! Probably because I implemented it in a way that diff between parts one and two was tiny.

🔗Day 13: Shuttle Search

TL;DR: For a list of periods (bus schedules) for a given time point find which period will be next. For part 2 find a point in time what all periods align next to each other

Part 1 was quite easy, but I stuck with part 2. After lots of trials and errors, I figured out that you need to start by iterating over points in time one by one. Once you met one period, you can start iterating by its value. Once you’ve faced another — you can find the least common multiple for them and continue stepping by it.

All the magic is in this loop:

// tt stands for "time table" — Vector of (u64, u64). First is the index, second is "period"
// The vector is sorted so the bus with the biggest route (period) will be the first
tt.sort_by(|(_, t), (_, ot)| ot.cmp(t));

let mut iter = tt.iter();

// Extract the first element — it'll be our initial step.
let (mut t, mut step) = iter.next().unwrap();
t = step - t;

for (offset, bus) in iter {
    loop {
        if (t + offset) % bus == 0 {
            step = step.lcm(bus);
            break;
        }
        t += step;
    }
}

🔗Day 17: Conway Cubes

TL;DR: Game of life in 3D. And then in 4D

Pretty simple and fun, the video above was created for this day. Part 1, of course =)

I never happened to implement the Game of Life, was just copy-pasting the algorithm from Wikipedia once. By the end of this day, I already implemented 4 versions of it (2 in this and 2 in Day 11: Seating System), but it still was a lot of fun for me!

🔗Day 18: Operation Order

TL;DR: Solve equations where + and * have the same priority. For part 2, do the same, but + goes first

This can be solved by using a regular expression to insert brackets, but this is not the way .

Mentioning it here just because it was funny :)

🔗Day 19: Monster Messages

TL;DR: Validate messages against… some sort of validation tree? AST ? I don’t know how to call it XD For part 2, do the same, but the tree is now recursive (contains loops). Luckily, there are only two of those and both are on level 1.

Fist part was easily solved by generating a set of all possible solutions, and checking that the message is in this list.

Part 2 ruined this approach completely. Any attempts to optimize that algorithm (e.g. get the list of messages before the recursion) completely failed.

After losing some hair, I had to rewrite everything from scratch “bottom-up” this time. Check the message symbol by symbol. Was pretty tricky, but with a small help of the community I managed to do it

🔗Day 20: Jurassic Jigsaw

TL;DR: Assemble a puzzle from given tiles. Tiles can be rotated or flipped. For part 1 find the edges For part 2 count a specific pattern on the image

Part 1 was rather simple. I’ve put all the borders into a hashmap, and then found all that tiles that have two unique borders. Easy-peasy.

Then I realized that you do need to actually assemble it. Oh, this was hell for me. I struggled the whole day with it, and then the next one and then the next… I managed to solve it only on day 25 when I realized that I can’t complete the challenge without it.

The initial idea was simple enough: get all possible tile borders, put them into a hashmap, and then “pull” it from there one by one. Do you see any problems?

Actually, yes. Since the tile can be flipped, you can get the “unique” border even for the central tile. All of those, actually.

To realize this I even had to make these tiles!

Ok, but how to solve this? Normalization! Luckily, I read about BitVec recently and was using it, so this worked like a charm:

fn normalize_border(border: BitVec) -> BitVec {
    let mut b1 = border.clone();
    b1.reverse();
    min(border, b1)
}

Yeah, a “Normalized” border is just a minimal number between a border and its flipped version. After that, the code just started to work.

Counting monsters was just a meter of tests .

🔗Day 23: Crab Cups

TL;DR: You’re playing in cups with Crab. He has 8 cups and makes 100 moves using a specific set of rules. You need to predict the final arrangement of cups. Part 2 is basically the same. Except Crab now has a million cups and makes 10 million moves!

I spent a lot of time solving part 1 in a very “efficient” way, as I thought. Not using LinkedLists, just swapping elements in-place in a fixed-length array. Surely, it will be faster, right?

No.

No. Turned out, the performance of swapping is terrible. So I rewrote it using LinkedLists, but the performance was just the same. I either had to wait for 14 hours or find a better way. After 8 hours of smashing my head into the wall flamegraph, I went to reddit looking for guidance. One last time.

The solution… hardly fits into my mind. It’s basically a linked list, but since the elements don’t need to store anything except the link to the next element, we can store it as an array, so the access will be O(1), we won’t need to go the whole linked list. This is so beautiful!

🔗Day 24: Lobby Layout

TL;DR: Another Game of Life, this time of a hex grid!

While reading the task, I realized that I had no idea how to store a hex grid in memory and navigate on it, so I just searched a bit. My finding was precious: this site with this article. I definitely advise you to check it out, even if you’re not interested in hex grids. It is very interactive and has a lot of stuff about the algorithm used in games. It helped a lot.

The idea is that you can treat a grid as a 3D cube on which you’re looking from the angle:

Simple and beautiful, just as I like it :)

🔗Stats

I found these survey results about this year’s challenge.

Interesting facts:

1. Rust is the second popular language with 10.17% usage! Fantastic!
   Python is of course the leader.
2. GNU\Linux is almost as popular as Microsoft Windows ™
3. The AoC author’s answers are quite remarkable, check them out :)

Global stats of participants look like this:

25    9173   3107  ****
24   12310    913  *****
23   11994   2486  *****
22   14469   2921  *****
21   14981    207  *****
20   11810   4670  ******
19   16525   3132  ******
18   23048   1703  *******
17   23949    684  ********
16   27362   3746  ********
15   31912   1763  **********
14   31278   3755  **********
13   32393   9711  ************
12   40511   3273  ************
11   41507   4458  *************
10   45585  10374  ***************
 9   57769   1375  ****************
 8   59329   4641  ******************
 7   58965   5786  ******************
 6   77145   2430  *********************
 5   82055   1749  **********************
 4   86370  10684  **************************
 3  104362   3381  ****************************
 2  124164   3820  *********************************
 1  146026  10309  *****************************************

check them out here

Another interesting graph is a conversion rate:

You can clearly see the hardest days I mentioned above: 4, 10, 13, 20.

🔗Results

My results aren’t exactly impressive:

      -------Part 1--------   --------Part 2--------
Day       Time  Rank  Score       Time   Rank  Score
 25   00:28:15  2140      0   01:55:06   3188      0
 24   00:37:24  2221      0   01:15:03   2148      0
 23   04:19:55  5735      0   10:56:10   5919      0
 22   00:36:59  3554      0   01:30:54   2612      0
 21   00:37:52  1491      0   00:45:10   1298      0
 20   01:41:02  2280      0       >24h  10961      0
 19   03:00:51  3987      0   11:23:30   6776      0
 18   00:37:29  1966      0   01:05:34   2077      0
 17   02:00:34  4498      0   02:06:09   4080      0
 16   00:42:28  4674      0   03:35:23   6316      0
 15   00:49:02  5064      0   00:50:05   3476      0
 14   00:40:12  3774      0   02:18:15   5185      0
 13   00:15:35  3400      0   03:54:02   5303      0
 12   01:11:54  6784      0   01:40:15   5748      0
 11   01:30:01  6845      0   04:18:42   9623      0
 10   00:23:31  6346      0   03:55:36   9770      0
  9   00:23:35  5808      0   00:41:18   5736      0
  8   00:27:07  6565      0   01:58:50   9691      0
  7   00:58:18  5244      0   01:04:09   3546      0
  6   00:09:23  3398      0   00:29:42   5495      0
  5   00:27:23  4995      0   00:35:38   4628      0
  4   00:30:34  5956      0   01:08:03   4940      0
  3   00:22:15  5223      0   00:37:14   5674      0
  2   00:29:59  5702      0   00:36:03   5144      0
  1   01:16:49  6714      0   01:17:52   6101      0

But I’m still pleased that I managed to accomplish this. It was a great experience and I feel that I became a better programmer 😎

Huge thanks to the author!