Day 6 - Discoded/adventofcode GitHub Wiki

Day 6

Given a race's time and distance Where the time is the race's time in milliseconds distance is the record distance in millimeters

Holding a button increases the rate of speed your boat goes. The goal is to beat the record time.

Solution

Example:
    time = 7
    distance = 9

record_time = 7
record_distance = 9

Let Hold equal the milliseconds the button is pressed

If Hold(1):
    Boat goes 1 mm/s -> (7-1)*(1mm/s) = 6 millimeters
If Hold(2):
    Boat goes 2 mm/s -> (7-2)(2mm/s) = 10 millimeters

Therefore the distance the boat travels, boat_distance:
    boat_distance = (record_time - hold_time)*(boat_speed) 
    boat_speed = hold_time
    boat_distance = record_time*hold_time - hold_time^2

boat_distance must be greater than record_distance

time*hold_time - hold_time^2 > record_distance
hold_time(record_time - hold_time) - record_distance > 0
-hold_time^2 + record_time*hold_time - record_distance > 0

Quadratic equation: $$ -\text{hold_time}^2 + \text{record_time}\times\text{hold_time} - \text{record_distance} > 0 $$

Using the quadratic formula where: $$a = -1$$ $$b = \text{record_time}$$ $$c = -\text{record_distance}$$

$$ \begin{align*} \x&=\frac{-b\pm\sqrt[]{b^2-4ac}}{2a} \end{align*} $$

root_0 = ((-1*b)+math.sqrt(math.pow(b, 2) - 4*a*c ))/(2*a)
root_1 = ((-1*b)- math.sqrt(math.pow(b, 2) - 4*a*c ))/(2*a)

Once we get the roots, they will not be integers so we must convert them. The smallest root must be floored then added by 1 while the largest root must be ceiled then subtracted by 1. This ensures that they're in the range of the equation

floor_root_0 = math.floor(root_0) + 1
ceil_root_1 = math.ceil(root_1) - 1

Quadratic equation

Finally to check the number of ways to win, we simply subtract the largest root from the smallest and add 1

ways_to_win = hold_time[1] - hold_time[0] + 1

Example Output

times:  ['7', '15', '30']
distances:  ['9', '40', '200']

record_time: 7
record_distance: 9
h^2 + 7*h - 9
a:-1, b:7, c:-9
1.6972243622680054 5.302775637731995
2 5
ways_to_win:  4

record_time: 15
record_distance: 40
h^2 + 15*h - 40
a:-1, b:15, c:-40
3.4688711258507254 11.531128874149275
4 11
ways_to_win:  8

record_time: 30
record_distance: 200
h^2 + 30*h - 200
a:-1, b:30, c:-200
10.0 20.0
11 19
ways_to_win:  9
ways_to_win_list:  [4, 8, 9]
ways_to_win_list product: 288