Advent of Code 2023 - Day 6

The Problem

Day 6 problem was relatively simply, the input was small and looked like below for the example

Time: 7 15 30
Distance: 9 40 200

The problem involved a user with a toy boat that starts with a speed of 0. The boat is equipped with a charging button that can be held for as long as the user desires. Each millisecond the button is held, the boat's speed increases by 1 mm per millisecond. However, a timer starts counting down as soon as the button is pressed. Therefore, holding the button for an extended period could increase the distance traveled, but holding it for too long could leave the boat without enough time to cover the required distance. The task was to determine how many different times exist at which holding the button down for that duration would result in the boat traveling a greater distance than the associated target distance.

Part 1

For Part 1 of the solution, our goal is to determine how frequently the boat can travel a greater distance for each given time-distance pair input, and then multiply all the results together.

To achieve this, we initially parsed the input into an array of objects structured as follows:

{ time: number; distance: number }[]

So for the example

[{ time: 7, distance: 9 }, { time: 15, distance: 40 }, { time: 30, distance: 200 }]

The initial approach for Solution 1 involved a straightforward process. We looped through the array of time-distance pairs, and for each object, a nested loop incremented from 0 to the specified 'time' value, increasing by 1 with each iteration. During this iteration, we calculated whether the distance traveled would exceed the given distance in the input. If it did, we incremented a counter associated with the corresponding object in the array. This basic solution effectively determined how many times the boat could travel a greater distance for each time-distance pair in the input.

1export function solution1(input: string) {
2    const parsedInput = parseInput1(input)
3
4    console.time('solution 1')
5    const waysToWinPerRound: number[] = []
6
7    for (const { time, distance } of parsedInput) {
8        let timesWon = 0
9        for (let timeHeld = 0; timeHeld <= time; timeHeld++) {
10            const speed = timeHeld
11            const timeLeft = time - timeHeld
12            const distanceTraveled = speed * timeLeft
13            if (distanceTraveled > distance) timesWon++
14        }
15        waysToWinPerRound.push(timesWon)
16    }
17
18    console.timeEnd('solution 1')
19    return waysToWinPerRound.reduce((acc, curr) => curr * acc, 1)
20}

Part 2

Part 2 wasn't significantly more challenging than Part 1; the primary change was in how the input was processed. Unlike Part 1, the input for Part 2 should not be read removing the spaces between the numbers.

Time: 7 15 30
Distance: 9 40 200

becomes a single race like so

{ time: 71530, distance: 940200 }

I initially approached the problem by simply looping through the times from 0 to, in this case, 71530. The method involved calculating the distance that could be traveled and tallying how many instances surpassed the predefined distance. The code ran efficiently on my machine, taking approximately 60ms for my real input. However, I recognized the potential for significant optimization.

1// 60ms
2export function solution2FullLoop(input: string): number {
3    const parsedInput = parseInput2(input)
4    const { time, distance } = parsedInput
5
6    console.time('solution 2 full loop')
7    let timesWon = 0
8
9    for (let timeHeld = 0; timeHeld <= time; timeHeld++) {
10        const speed = timeHeld
11        const timeLeft = time - timeHeld
12        const distanceTraveled = speed * timeLeft
13        if (distanceTraveled > distance) timesWon++
14    }
15
16    console.timeEnd('solution 2 full loop')
17    return timesWon
18}

An optimization strategy involves two loops: the first starts at 0, incrementing by 1 until a valid distance is found for the minimum time. The second loop starts at the input time, decrementing by 1 until a valid distance is found for the maximum time. The difference between the maximum and minimum values, plus one, represents the total number of valid solutions for the duration the boat's button could be held. This approach leverages the certainty that all values between the minimum and maximum are valid, while those outside the range are not.

This did solve about 4x faster for my real input but in the worst case the time complexity would not be any better.

1// 16 ms
2function solution2BreakLoopEarly(input: string): number {
3  const parsedInput = parseInput2(input)
4  const { time, distance } = parsedInput
5
6  console.time('solution 2 break early')
7  let minTimeNeededForWin = 0
8  let maxTimeNeededForWin = 0
9
10  for (let timeHeld = 0; timeHeld <= time; timeHeld++) {
11    const speed = timeHeld
12    const timeLeft = time - timeHeld
13    const distanceTraveled = speed * timeLeft
14    if (distanceTraveled > distance) {
15      minTimeNeededForWin = timeHeld
16      break
17    }
18  }
19
20  for (let timeHeld = time; timeHeld >= 0; timeHeld--) {
21    const speed = timeHeld
22    const timeLeft = time - timeHeld
23    const distanceTraveled = speed * timeLeft
24    if (distanceTraveled > distance) {
25      maxTimeNeededForWin = timeHeld
26      break
27    }
28  }
29
30  console.timeEnd('solution 2 break early')
31  return maxTimeNeededForWin - minTimeNeededForWin + 1
32}

However doing this it became clear the pattern between distance traveled and time held on the boat button follows a quadratic relationship. (wikipedia article on quadratic formula)

time = 71_530
distance = 940_200
speed = time held (TH)
distance = speed * time
distance = TH * (time - TH)
940_200 = TH * (71530 - TH)
940_200 = 71_530TH - TH^2
0 = -TH^2 + 71_530TH - 940_200

1function quadraticFormula(
2    a: number,
3    b: number,
4    c: number,
5  ): { lowerBound: number; upperBound: number } {
6    const root1 = ((-b + Math.sqrt(b * b - 4 * a * c)) / 2) * a
7    const root2 = ((-b - Math.sqrt(b * b - 4 * a * c)) / 2) * a
8  
9    return {
10      lowerBound: Math.min(root1, root2),
11      upperBound: Math.max(root1, root2),
12    }
13  }
14  
15  // 0.061ms
16  function solution2QuadraticEquation(input: string): number {
17    const parsedInput = parseInput2(input)
18    const { time, distance } = parsedInput
19  
20    console.time('solution 2 quadratic')
21  
22    const { lowerBound, upperBound } = quadraticFormula(-1, time, -distance)
23  
24    console.timeEnd('solution 2 quadratic')
25    return Math.floor(upperBound) - Math.ceil(lowerBound) + 1
26  }

A nice 1000x performance improvement on our basic for loop solution.