Advent of Code — Day 9 — Javascript

For day 9, you are given a list of numbers. Starting from 26th indexed number, every number indexed further down is the sum of two numbers in the previous 25 numbers. The problem asks for which number is not a sum of any combination of the previous 25 numbers.

For the sample data, we will be starting with the 6th indexed number and the previous 5 numbers.

[1] 35
[2] 20
[3] 15
[4] 25
[5] 47
40 = (Range 1-5) [3] 15 + [4] 25
62 = (Range 2-6) [3] 15 + [5] 47
55 = (Range 3-7) [3] 15 + [6] 40
65 = (Range 4-8) [4] 25 + [6] 40
95 = (Range 5-9) [6] 40 + [8] 55
102 = (Range 6-10) [6] 40 + [7] 62
117 = (Range 7-11) [7] 62 + [8] 55
150 = [Range 8-12) [8] 55 + [10] 95
182 = (Range 9-13) [9] 65 + [12] 117
127 = (Range 10-14) Not Found
219
299
277
309
576

We can start the function by splitting the data and setting the correct starting index.

function day9(input){
let arr = input.split('\n')
for(let i = 5; i < arr.length; i++){
//Iterate over each number starting at the 5th index
}
}

This question is a two sum problem which can be solved in a single pass. I will use an object or hash to maintain the count.

function day9(input){
let arr = input.split('\n')
for(let i = 5; i < arr.length; i++){
let obj = {}
for(let j = i - 5; j < i; j++){
//arr[i] is the 5th index
//arr[j] will start at i-5 and will iterate 5 times
}
}
}

Now we need to store the difference in the object and check if the current value and has a difference available.

function day9(input){
let arr = input.split('\n')
for(let i = 5; i < arr.length; i++){
let obj = {}
let aSum = false
for(let j = i - 5; j < i; j++){
let diff = arr[i] - arr[j]
if(obj[diff]){
aSum = true
}
obj[diff] = "Hello World"
}
}
}

In a basic two sum problem, we set the a variable to be the difference and place it into the object. As we continue through the loop, if a value is present in the set, then there is a complement.

function day9(input){
let arr = input.split('\n')
for(let i = 5; i < arr.length; i++){
let isASum = false
let obj = {}
for(let j = 0; j < 5; j++){
let diff = arr[i] - arr[i-j]
obj[diff] = "Hello World"
if(Object.keys(obj).length === 5){
for(let k = 0; k < 5; k++){
if(obj[nums[i-k]])
isASum = true
delete obj[nums[i-5]]
}
}
}
if(!isASum]
return arr[i]
}
}

In the program above, we are iterating over the entire array at the correct index. In the second for loop, we create a sliding window and placing all of the differences in the object. Once all of the differences are in, we loop again and check if there are two numbers that sum up to what we need. If a number ever returns false, we return the number.