DEV Community

Cover image for Report Repair
Robert Mion
Robert Mion

Posted on

Report Repair

#adventofcode #algorithms #computerscience #programming

Advent of Code 2020 Day 1

Task: Solve for X where... 

X = the product of N numbers that sum to 2020
Enter fullscreen mode Exit fullscreen mode
  1. N = 2
  2. N = 3

Example input 

1721 979 366 299 675 1456
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode
  • 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
Enter fullscreen mode Exit fullscreen mode

A visual depiction

NullDev's algorithm for Part 2

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

2020 progress map

Top comments (1)