Report Repair
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-04-16 17:37:24

## [Advent of Code 2020 Day 1](https://adventofcode.com/2020/day/1)

## Task: Solve for X where...
```
X = the product of N numbers that sum to 2020
```
1. N = 2
2. N = 3

### Example input
```
1721
979
366
299
675
1456
```
It represents:
- A list of numbers

## Part 1 - Find the matching half

### A written description:
```
For each item in the list
  Check the list for a value that is the difference of 2020 and the current value
  Once a match is found
    Return the product of both values
```

### A visual depiction:
```
 for i as 0 thru 5
 1721 979 366 299 675 1456

 i=0

 ****
 1721 979 366 299 675 1456

 2020
-1721
-----
  299

 **** ??? ??? !!! ??? ????
 1721 979 366 299 675 1456

 1721
* 299
-----
BINGO
```

### Performance
- Best-case: The array includes a value that is the difference of 2020 and the first value
- Worst-case: The array includes a value that is the difference of 2020 and the value in the middle of the array

## Part 1 - Another solver's code

JavaScript solver NullDev used an interesting data structure to solve this puzzle.

```
Input as array of numbers:
[1721,979,366,299,675,1456]

Object mapping array values to their index in the array:
{
  1721: 0
   979: 1
   366: 2
   299: 3
   675: 4
  1456: 5
}

 ****
 1721 979 366 299 675 1456

Does the object have a property equivalent to 2020 - 1721: 299?
[Y]/N

{
  1721: 0
   979: 1
   366: 2
   299: 3 <---- !!!
   675: 4
  1456: 5
}

Does that property's value equal the index of 1721?
Y/[N]

{
  1721: 0
   979: 1
   366: 2
   299: 3 <---- !== 0
   675: 4
  1456: 5
}

Store an array containing two elements:
  1. the current index (0) 
  2. the value associated with the key of the difference (3)

Return the product of the values in the input array at locations 0 and 3: 1721 * 299
```

## Part 2 - Brute-force

A written description
```
For i as each number in the input array
  For j as each number in the input array
    For k as each number in the input array
      If the sum of i, j and k is 2020
        Return the product of i, j and k
```
- Feels icky
- Terrible performance
- But...works!

## Part 2 - Another solver's code

JavaScript solver NullDev used an eloquent algorithm to solve this puzzle; one much more performant...but more complicated...than mine.

### A written description
```
First, sort the array of numbers in ascending order
Create an empty array that will eventually be filled with 3 numbers

For i from 0 to two less than the length of the input array
  As long as the value at i is not equal to the value one less than i
    Set left as i + 1
    Set right as the last location in the array
    Do as long as left is less than right
      Store the sum of the vales at the three locations: i, left and right
      If the sum is 2020
        Push all three values into the array created earlier
        As long as the value at left is equal to the next right-most value, increment left
        As long as the value at right is equal to the next left-most value, decrement right
        Increment left
        Decrement right
      Else, the sum is not 2020
        If the sum is less than 2020
          Increment left
        Else, the sum is greater than 2020
          Decrement right

Return the product of each of the three values now stored in the created array
```

### A visual depiction
![NullDev's algorithm for Part 2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1klclkhphoyzpc6c8cvw.gif)

## 2020 summary
- 40 stars attained - 6 more than 2021!
- [15 simulators created](https://aocsimulators.rmion.repl.co/)
- 23 Part 1's solved - 5 more than 2021!
- 17 Part 2's solved - 1 more than 2021!
- Countless animations crafted

![2020 progress map](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/syni1xr6qdilfyftm3vd.png)