На 9-й день вам дается список чисел. Начиная с 26-го проиндексированного числа, каждое последующее индексируемое число представляет собой сумму двух чисел из предыдущих 25 чисел. Задача спрашивает, какое число не является суммой какой-либо комбинации предыдущих 25 чисел.
Для выборки данных мы начнем с 6-го индексированного числа и предыдущих 5 чисел.
[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
Мы можем запустить функцию, разделив данные и установив правильный начальный индекс.
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 } }
Этот вопрос представляет собой задачу с двумя суммами, которую можно решить за один проход. Я буду использовать объект или хеш, чтобы вести счет.
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 } } }
Теперь нам нужно сохранить разницу в объекте и проверить, доступно ли текущее значение и разница.
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" } } }
В основной задаче двух сумм мы устанавливаем переменную как разность и помещаем ее в объект. По мере продолжения цикла, если значение присутствует в наборе, значит, есть дополнение.
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] } }
В приведенной выше программе мы перебираем весь массив с правильным индексом. Во втором цикле for мы создаем скользящее окно и размещаем все различия в объекте. Как только все различия обнаружены, мы снова зацикливаемся и проверяем, есть ли два числа, которые суммируют то, что нам нужно. Если число когда-либо возвращает false, мы возвращаем число.