Advent of Code 2020 Day 1 Solution

Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. People use them as a speed contest, interview prep, company training, university coursework, practice problems, or to challenge each other. — AdventOfCode.com

For this puzzle, they've given us a list of numbers as input (one number on each line).

Part I

Problem: Find the first two numbers that sum to 2020. The answer is the multplication of these two numbers.

Solution: We're going to iterate through the array and each time, caculate the difference between the current number and 2020. Then add the difference to a set that we have previously initialized if the current number doesn't exist in the set. However, if it does exist, it means that we have found our pair. Let's dive into the code:

Copied!
1const input = `
21721
3979
4366
5299
6675
71456
8`;
9
10const numbers = input
11	.trim()
12	.split('\n') // split on new line character
13	.map((str) => +str); // turn each string to a number so it'll be easier to work with
14
15const part1 = () => {
16	const seenDiffs: new Set<number>();
17
18	for (const number of numbers) {
19		if (seenDiffs.has(number)) {
20			return (2020 - number) * number;
21		}
22		seenDiffs.add(2020 - number);
23	}
24
25	// answer not found
26	return null;
27};

Complexity: Our time complexity is linear since we are only iterating the numbers array once and look-up and insert operations are done in constant time for sets. Worst case space complexity is also linear because we are storing a whole copy of the array in the set.

Part II

Problem: Find the first three numbers that sum to 2020. The answer is produced by multiplying these numbers together.

Solution: A good place to start is to make a function that returns a pair of numbers or null for a given array and a target sum. Then we can iterate through the array and use this function to see if there's a pair that sums to our current difference. That was a handful but hopefully it will make more sense after looking at the code:

Copied!
1const getPairForSum = (
2	numbers: number[],
3	sum: number,
4	skipIndex?: number
5) => {
6	const seenDiffs: new Set<number>();
7
8	for (const [index, number] of numbers.entries()) {
9		if (skipIndex === index) continue;
10		if (seenDiffs.has(number)) {
11			return [sum - number, number];
12		}
13
14		seenDiffs.add(sum - number);
15	}
16
17	// answer not found
18	return null;
19};
20
21const part2 = () => {
22	for (const [index, number] of numbers.entries()) {
23		const pair = getPairForSum(numbers, 2020 - number, index);
24
25		if (pair) {
26			return number * pair[0] * pair[1];
27		}
28	}
29
30	return null;
31};

Complexity: Time complexity is O(n^2) because we are doing a O(n) operation in each iteration (calling getPairForSum()). Space complexity is O(n) (linear) because we are doing a linear operation in each iteration and the space taken by each iteration frees up when we move on to the next iteration.