Robert Mion

Posted on

# Report Repair

## 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
``````

## 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