Link to Advent of Code day 6

Today, we'll do boat racing to win a trip to the Desert Island, were the sand is coming from.

Part 1

Rules

The race bots are actually toy boats ! To move a toy boat, you need to push the button to charge up speed, and release it to allow the boat to move. Each millisecond spent pushing the button increase the boat speed of one millimeter per millisecond.

The input is the representation of multiples races. The first line describe how long the race last, and the second describes the record distance for this race.

Time:      7  15   30
Distance:  9  40  200

In this example, the first race last 7 milliseconds, and the record is a distance of 9 millimeters.

To beat this record, we have a few possibilities: we can hold the button for 2, 3, 4, or 5 milliseconds at the start of the race, for a total of 4 possible ways to beat this record.

We need to determine for each races the number of ways we can beat the record, and multiply these values together.

Parsing

To represent each race, I chose to get a list of (time, distance).

The parsing is straightforward :

def get_races(input_file: str) -> list[tuple[int, int]]:
    with open(input_file) as f:
        lines = f.readlines()
        times = [int(x) for x in lines[0].split() if x.isdigit()]
        distances = [int(x) for x in lines[1].split() if x.isdigit()]
        return list(zip(times, distances))

Code

We can do a few observations already:

• we have only one variable we can change : holding_time
• the distance the boat will travel can be summarized by holding_time * (race_time - holding_time)

So a naive approach would be to try the holding_time from 1 to race_time, and count all of the occurrences where holding_time * (race_time - holding_time) is greater than race_distance:

def part_one(input_file: str) -> int:
    races = get_races(input_file)
    total = 1
    for (race_time, race_distance) in races:
        winning_possibilities_count = 0
        for holding_time in range(1, race_time):
            if holding_time * (race_time - holding_time) > race_distance:
                winning_possibilities_count += 1
        total *= winning_possibilities_count
    return total

Not optimum, but enough for part 1.

Part 2

Rules

The twist is that there is no multiple races: there is only one !

When parsing the input, we need to ignore the spaces for the numbers.

So the previous example

Time:      7  15   30
Distance:  9  40  200

Should be read

Time:      71530
Distance:  940200

And we now needs to find how many ways there is to win this single race ?

Code

We can have a result by updating the parsing function, and applying the same logic that for part 1:

def part_two(input_file: str):
    race_time, race_distance = get_race(input_file)
    winning_possibilities_count = get_race_win_possibilities_count(race_time, race_distance)
    return winning_possibilities_count


def get_race_win_possibilities_count(race_time: int, race_distance: int) -> int:
    winning_possibilities_count = 0
    for holding_time in range(1, race_time):
        if holding_time * (race_time - holding_time) > race_distance:
            winning_possibilities_count += 1
    return winning_possibilities_count


def get_race(input_file: str) -> tuple[int, int]:
    with open(input_file) as f:
        lines = f.readlines()
        time = int(lines[0].replace(" ", "").split(":")[1])
        distance = int(lines[1].replace(" ", "").split(":")[1])
        return time, distance

And this works !

Optimization

But this is very slow: almost 3 seconds on my laptop.

Even if the problem is solved, we can probably do way better. We already got the formula for the distance, so let's see if we can do more observations.

After playing a bit with IPython, I found that there is a pattern:

In [1]: race_time = 10

In [2]: for n in range(1, race_time):
   ...:     print(n, n * (race_time - n))
   ...:
1 9
2 16
3 21
4 24
5 25
6 24
7 21
8 16
9 9

For each race, the distance peak is always at race_time / 2, and the distances are then symmetric from this point (if the race time is odd, the max points are race_time // 2 and race_time // 2 + 1)

This means we have only one part of the curve to compute. We can start from half, and continue until we stop breaking the record.

Let's try again:

def get_race_win_possibilities_count(race_time: int, race_distance: int) -> int:
    winning_possibilities_count = 0
    for holding_time in range(math.ceil(race_time/2), race_time):
        if holding_time * (race_time - holding_time) > race_distance:
            winning_possibilities_count += 1
        else:
            break
    winning_possibilities_count *= 2
    if race_time % 2 == 0:
        winning_possibilities_count -= 1
    return winning_possibilities_count

As expected, we divided the computational time by 2. But it still takes 1.2sec, so I'm sure there is a better solution.

I feel like I could do something by computing the distance between the highest value and the record to break, but no luck here. And I don't have any more time for Advent Of Code today, so I'll stop here. I'll update this post if I find something in the future !

---

All the code is available on github