Advent of code: 2020 Day 01
Tags: adventofcode, python
Published: 2020-12-01 07:08:46

**SPOILER ALERT**
This is a post with my solutions and learnings from the puzzle. Don't continue reading if you haven't tried the puzzle on your own yet.

If you want to do the puzzle, visit [adventofcode.com](https://adventofcode.com/).

## TOC
* [Key learning](#key-learning)
* [Part 1](#part-1)
  * [Solution N^2](#solution-n2)  
  * [Solution N](#solution-n)
* [Part 2](#part-2)
  * [Solution N^3](#solution-n3)  
  * [Solution N^2](#solution-n22)
* [Other tricks](#other-tricks)
* [Functional style](#functional-style)

## Key learnings <a name="key-learning"></a>

* For-loops
* If statements

You need to understand loops and if-statements to solve the puzzle. You can make it more advanced by optimizing the solution, then there are some more key learnings. Though the input is small enough that no optimization is needed.

## Puzzle part 1  <a name="part-1"></a>

You get a list of numbers and the puzzle is: `Find the two entries that sum to 2020; what do you get if you multiply them together?`.

### Input example

The input is a file with numbers. They are in the format of one number per line.

```
1721
979
366
299
675
1456
```

### Parse input

Start by preparing how to parse the data. My programming language of choice is `python`:
```python
# Open the input file
inputfile = open('01.input', 'r')

# Parse lines to array of numbers
lines = inputfile.readlines()
entries = [int(x.strip()) for x in lines]
```

### Solution - O(N^2)  <a name="solution-n2"></a>

A first assumption is made that `1010` isn't on the entry-list. Therefore it doesn't matter if we happen to compare a entry to itself. Otherwise it would give a false positive.

The naive solution is a double for-loop where we check all possible combinations of two entries. For those entries we check if they sum up to `2020`, if so it returns the multiplication of them.

In worst case it requires O(N^2). The input-file is 200 lines long, which means 200 * 200 = 40 000 comparisons. It executes within a few seconds on my computer.

```python
def part1(entries):
  for x in entries:
    for y in entries:
      if x + y == 2020:
        return x * y
result = part1(entries)
print("Result part 1: %d" % result)
```

### Solution advanced - O(N)  <a name="solution-n"></a>

If we use a `set` to store the `rests` we can optimize the solution to O(N) in time complexity. The rest is the difference between our current entry X and `2020`

`X + rest = 2020 ` ==> `rest = 2020 - X`

For each entry X we check if we have a value in the rests-set which fulfills `X + rest == 2020`. Otherwise we store X as a rest.

```python
def part1(entries):
    rests = set()

    for x in entries:
        rest = 2020 - x
        if rest in rests:
            return rest * x
        else:
            rests.add(x)
```

## Part 2  <a name="part-2"></a>

The second part of the puzzle is: `what is the product of the three entries that sum to 2020?`

### Solution - O(N^3)  <a name="solution-n3"></a>

A naive solution is just to add another for loop. This gives us 3 for-loops that in worst case gives time complexity of `O(N^3)`

```python
def part2(entries):
    for x in entries:
        for y in entries:
            for z in entries:
                if x + y + z == 2020:
                    return x * y * z
```

### Solution - O(N^2)  <a name="solution-n22"></a>

A more optimized solution is to calculate this in two steps. First using a dictionary to store each possible combination of two entries. This takes O(N^2) time. Then we iterate through the list once again to find the third entry required to meet 2020.

The dictionary has the sum of two entries as key, and multiplication of them as the value.

This solution has time complexity of O(N^2 + N) which is simplified to `O(N^2)`

```python
def part2(entries):
    rests = {}
    for x in entries:
        for y in entries:
            rests[x + y] = x * y

    for x in entries:
        rest = 2020 - x
        if rest in rests:
            return x * rests[rest]
```

Please share if you know a faster way of solving this problem!

## Other tricks  <a name="other-tricks"></a>

Another way to increase performance is to never look at a combination twice. Not sure which time complexity it gives. At least better than `O(N^2)` and `O(N^3)` for part 1 and part 2 respectively. Please comment below if you know!

```python
def part1(entries):
  size = len(entries)
  for i in range(size):
      for j in range(i + 1, size):
          if entries[i] + entries[j] == 2020:
            return entries[i] * entries[j]
```

```python
def part2(entries):
  size = len(entries)
  for i in range(size):
    for j in range(i + 1, size):
      for k in range(j + 1, size):
        if entries[i] + entries[j] + entries[k] == 2020:
          return entries[i] * entries[j] * entries[k]
```

## Functional style <a name="functional-style"></a>
 
Some entertainment for the ones that prefer a more functional style of coding. The solutions generates all pairs that sum up to `2020`, and then filters on which pair that is present in the list.

```python
def part1functional(arr):
    return [
        a * b
        for (a,b)
        in filter(
            lambda (a,b): a in arr and b in arr,
            zip(range(0, 1010, 1), range(2020, 1010, -1))
        )
    ][0]
```