Advent of Code 2020 Day 1

This month I am going to do the Advent of Code, which is a yearly advent calendar of 25 small programming puzzles.

This article series will contain spoilers for the solutions of these challenges. For fairness I will release these articles no soonedr than a day after the puzzles have been released.

I will be using Rust for the solutions. I have chosen rust because it is the programming language I am the most comfortable with.

All days have 2 challenges with 1 building on the other and both the input files and the result are specific to each user. Therefore the results I'll mention in this document will not be the same as the ones you need for your account.

Today's challenge can be found here: https://adventofcode.com/2020/day/1

The first challenge

For the first challenge we will need to find two entries that add up to 2020 and multiply them together. The list contains 200 numbers between 0 and 2020 (excluding both).

The most immediate way of finding such a pair is to have 2 nested loops that look for such a pair

pub fn day1a(data: &[u32]) -> u32 {
  for i in 0..data.len() {
    for j in 0..data.len() {
      if i != j && (data[i] + data[j]) == 2020 {
        return data[i] * data[j];
      }
    }
  }
  unreachable!();
}

This code runs in 17.289μs over the input data on my machine

First optimization

This code will get the job done, but is it the best we can do? after all we have two nested for loops. The a + b == 2020 check is executed n(n-1) = n^2-n times, or a complexity of O(n^2).

To answer that question we first have to know what exact thing we are looking for. We are looking for two elements a and b of the data such that a+b=2020. Finding two unknowns is slow, so can we relate a and b with each other?. Well we can subtract a from both sides and find that b=2020-a. This works well together with the fact that rust collections have a method called "contains" to check whether it contains an item.

pub fn day1a(data: &[u32]) -> u32 {
  for i in 0..data.len() {
    let a = data[i];
    let b = 2020-a;
    if data.contains(&b) {
      return a * b;
    }
  }
  unreachable!();
}

This code runs in 8.301μs. That's an improvement of over 50%! However how exactly does contains work? Let's check the rust source code. The implementation of .contains() seems to be in cmp.rs, and effectively does

data.iter().any(|slice| *slice == *self)

which is effectively just a short for loop! Are there datatypes where contains is not a for loop?

Introducing Hashsets

Such types actually do exist! Hashsets store their contents based on a "hash" that is calculated in constant time. This has the benefit that you can easily know whether an item is inside of the hash. However a hashset can only contain each item at most once and stores them in an arbitrary order. This doesn't matter for this challenge however as we merely have to know whether a value exists or not.

Rust has a Hashset in its standard library, under std::collections::HashSet. Let's use it!

use std::collections::HashSet;
pub fn day1a(data: &[u32]) -> u32 {
  let mut hs = HashSet::new();
  for ent in data.iter() {
    hs.insert(*ent);
  }
  for i in 0..data.len() {
    let a = data[i];
    let b = 2020-a;
    if hs.contains(&b) {
      return a * b;
    }
  }
  unreachable!();
}

This still uses two loops, but as you can tell these aren't nested in each other. This means that it only has to make 2n operations, meaning it suddenly only have the time complexity of O(n)!

This code runs in 7.2392μs. That's an improvement of over 12%, but we can do better with this approach. Unlike previously, this code uses heap memory. However the HashSet can't know for sure how much memory it actually needs, so it allocates memory as it is needed. We however know how large the list is and can therefore tell the hashmap how big it needs to be:

  let mut hs = HashSet::with_capacity(data.len());

This now runs in 4.0146μs. Another 44.806% faster!

De-Introducing Hashsets

Hashsets are great, but they need to do a lot of things in order to make them work with a large range of keys, like for example hashing, creating "buckets", allocating memory, etc. However we do not need that. We have a keyspace of 2020 keys. That is small enough to fit an array of on the stack. Hashsets also have to work around hash collision attacks by randomly choosing an initial hash value.

So instead of a hashmap, we simply replace it with a 2020 element boolean array, that we index to find out whether the hashmap contains a specific item

pub fn day1a(data: &[u32]) -> u32 {
  let mut present = [false; 2020];
  for ent in data.iter() {
    present[*ent as usize] = true;
  }
  for i in 0..data.len() {
    let a = data[i];
    let b = 2020-a;
    if present[b as usize] {
      return a * b;
    }
  }
  unreachable!();
}

Woah, speed immediately jumped through the roof! This code ran in 202.40ns! That's an almost 95% improvement!

Calculating using the compiler

One feature that rust has is "constant functions", or functions that can be evaluated at compile time. These are much more flexible than their C++ counterpart and allows us to do almost everything what we are doing right now.

There are two aspects of the function that is not supported in const functions:

  • The for loops (that are easily replacable with a manual while loop)
  • The panic at the end

Replacing both, we get:

pub const fn day1a(data: &[u32]) -> u32 {
  let mut present = [false; 2020];
  let mut i = 0;
  while i < data.len() {
    present[data[i] as usize] = true;
    i += 1;
  }
  i = 0;
  while i < data.len() {
    let a = data[i];
    let b = 2020-a;
    if present[b as usize] {
      return a * b;
    }
    i += 1;
  }
  0
}

Running this code results in a running time of 225.89ns…slower than before. Why?

This is because const fns are only evaluated at compile time if it is necessary to do so (for example in a static initializer or a constant), we can however fix that by just renaming the function to day1a_const and defining our day1a function as such:

pub fn day1a() -> u32 {
  const RESULT: u32 = day1a_const(&DATA);
}

Now the code is running in 1.1625ns. Another 99.483% improvement. Marking the function as #[inline] improves the speed to 230.51ps, or by another 80.162%

Second Challenge

For the second part of the puzzle we need to extend that to 3 elements that sum to 2020 and our framework of the previous, optimized, puzzle in place does allow us to do that in almost the same amount of time.

pub const fn day1b(data: &[u32]) -> u32 {
  let mut present = [false; 2020];
  let mut i = 0;
  while i < data.len() {
    present[data[i] as usize] = true;
    i += 1;
  }
  i = 0;
  while i < data.len() {
    let a = data[i];
    let sum = 2020-a;
    let mut j = 0;
    for j < data.len() {
      if i != j && data[j] < sum && present[(sum - data[j]) as usize] {
        return a * data[j] * (sum - data[j]);
      }
      j += 1
    }
    i += 1;
  }
  0
}