Advent of Code 2020: Day 1

, 6 min read
advent of code 2020

Yes, finally Advent of Code 2020 has started! Our first puzzle is below:

After saving Christmas five years in a row, you’ve decided to take a vacation at a nice resort on a tropical island. Surely, Christmas will go on without you.

The tropical island has its own currency and is entirely cash-only. The gold coins used there have a little picture of a starfish; the locals just call them stars. You’ll need to find fifty of these coins by the time you arrive so you can pay the deposit on your room.

Before you leave, the Elves in accounting just need you to fix your expense report (your puzzle input); apparently, something isn’t quite adding up.

Specifically, they need you to find the two entries that sum to 2020 and then multiply those two numbers together. For example, suppose your expense report contained the following:

1721, 979, 366, 299, 675, 1456

In this list, the two entries that sum to 2020 are 1721 and 299. Multiplying them together produces 1721 * 299 = 514579, so the correct answer is 514579. Of course, your expense report is much larger. Find the two entries that sum to 2020; what do you get if you multiply them together?

You can read the full text here. In summary, we have a long list of numbers, and we have to find the first two pairs of numbers which sum to give 2020 when we obtain this pair we just need to return the product.

Part 1

I think that the most efficient way to implement this is going to be using an ordered_map / ordered_set, but I will use a vector because it’s more general and may lend itself to part 2 easier.

My process will go as follows: open the file, loop through the list of numbers (which I read in as strings) and convert them to integers. I can store the integers in a vector, and then I can use two nested for loops to iterate over each possible pair of numbers.

I’m using the boilerplate solution file that I introduced here. I open a file stream and then loop through the file asking for the next line until there are no more lines. I process each line using std::stoi which converts a string to an integer.

1
2
3
4
5
6
7
std::vector<int> numbers;
std::fstream myfile("input", std::ios_base::in);
std::string line;
while(std::getline(myfile, line)){
  numbers.push_back(std::stoi(line));
}
myfile.close();

Now, with our input loaded into a vector of integers, we can just loop over and trial every pair of numbers. When we find a pair that works, we store the product and quit the loop (as we only want the first pair that works).

1
2
3
4
5
6
for(int i=0; i<numbers.size(); i++)
  for(int j=i+1; j<numbers.size(); j++)
    if (numbers[i] + numbers[j] == 2020){
      ans1 = numbers[i] * numbers[j];
      break;
    }

Great: we have the first ⭐

The full code can be found on github

Part 2

Now for the second part:

The Elves in accounting are thankful for your help; one of them even offers you a starfish coin they had leftover from a past vacation. They offer you a second one if you can find three numbers in your expense report that meet the same criteria.

You can read the full text here.

I’m glad I didn’t implement anything too fancy for part 1, because part 2 simply requires me to add a third for loop to the current configuration. I also made sure to set my answer variables to long integers because I could see the values were getting large and didn’t want to suffer from overflow.

1
2
3
4
5
6
7
for(int i=0; i<numbers.size(); i++)
  for(int j=i+1; j<numbers.size(); j++)
    for(int k=j+1; k<numbers.size(); k++)
      if (numbers[i] + numbers[j] + numbers[k] == 2020){
        ans2 = numbers[i] * numbers[j] * numbers[k];
        break;
      }

Well, that makes it a full house: ⭐⭐

The full code can be found on github

Reflections

The solution I implemented is relatively readable and straightforward, in my opinion. I think, and hope, most people with a programming background, will be able to follow the code. However, this is not an optimal solution.

For part 1, the worst-case scenario is when the pair of matching numbers are the last two numbers in the input. That means we have to try N^2 combinations before we find the solution. Part 2 is even worse, we may have to try N^3 combinations. If this is confusing, the following may help.

I suspect the best way to optimise this is to use an ordered_set or an ordered_map. These containers use hash functions and in the best-case scenario, the time complexity of finding a value in an STL unordered_map is O(1). Thus for part 1, we could go from O(N^2) to O(N) by implementing the following:

1
2
3
4
5
6
7
for(auto val : numbers_v){
  if (val > 2020) continue;
  if (numbers[2020-val] > 0){
    ans1 = (2020-val) * val;
    break;
  }
}

In the above code snippet, I loop through each number in the input once, and I calculate which other number is required to sum to 2020. I then use my ordered_map to check if that number exists anywhere in my input. This lookup is speedy (thanks to the hash function); thus, this solution will scale much better.

We can apply the same technique to part 2 to reduce it from O(N^3) to O(N^2). In the spirit of every physics lecturer I’ve ever been taught by; I’ll leave this as an exercise for the interested reader.

> Why do we care about the time and space complexity?

We care about the complexity of the solution because it indicates how our time-to-solution is likely to scale with input size. Imagine if the number of values in my input was suddenly increased by 10, so instead of N numbers, I now have 10N numbers.

For a solution that scales like O(N^2) that means the time to the solution will go like (10 * N) * (10 * N) = 100 * N. Thus, my code takes 100 times longer to solve the problem. For an O(N^3) algorithm, such as part 2 today, the same increase would take 1000 times longer to solve.

As such, we endeavour to keep complexities as low as possible. The best case is O(1) which means the time-to-solution doesn’t depend on the size of the input. However, that was not possible today.

Thanks for reading, and see you all tomorrow, where I suspect the puzzle will be much harder to solve!

. . . .

I have no affiliation with AoC. I’m just a fan of the programming puzzles. If you enjoy them too, please feel free to join in and support the creators

Back to my advent calendar

Comments

Back to all posts