Advent of Code 2020 Day 1
Task: Solve for X where...
X = the product of N numbers that sum to 2020
- N = 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
2020 summary
- 40 stars attained - 6 more than 2021!
- 15 simulators created
- 23 Part 1's solved - 5 more than 2021!
- 17 Part 2's solved - 1 more than 2021!
- Countless animations crafted
Top comments (0)