4
\$\begingroup\$

Part One:

The task involves organizing multiple toy boat races, each assigned a specific race time and a recorded distance. To surpass the existing record, participants must optimize the duration of holding the button, as the toy boat's speed increases by one millimeter per millisecond for every whole millisecond the button is pressed at the beginning of the race. The objective is to determine the various possible ways to achieve a performance surpassing the established record.

For example:

Time:      7  15   30
Distance:  9  40  200

This document describes three races:

  • The first race lasts 7 milliseconds. The record distance in this race is 9 millimeters.
  • The second race lasts 15 milliseconds. The record distance in this race is 40 millimeters.
  • The third race lasts 30 milliseconds. The record distance in this race is 200 millimeters.

Your toy boat has a starting speed of zero millimeters per millisecond. For each whole millisecond you spend at the beginning of the race holding down the button, the boat's speed increases by one millimeter per millisecond.

So, because the first race lasts 7 milliseconds, you only have a few options:

  • Don't hold the button at all (that is, hold it for 0 milliseconds) at the start of the race. The boat won't move; it will have traveled 0 millimeters by the end of the race.
  • Hold the button for 1 millisecond at the start of the race. Then, the boat will travel at a speed of 1 millimeter per millisecond for 6 milliseconds, reaching a total distance traveled of 6 millimeters.
  • Hold the button for 2 milliseconds, giving the boat a speed of 2 millimeters per millisecond. It will then get 5 milliseconds to move, reaching a total distance of 10 millimeters.
  • Hold the button for 3 milliseconds. After its remaining 4 milliseconds of travel time, the boat will have gone 12 millimeters.
  • Hold the button for 4 milliseconds. After its remaining 3 milliseconds of travel time, the boat will have gone 12 millimeters.
  • Hold the button for 5 milliseconds, causing the boat to travel a total of 10 millimeters.
  • Hold the button for 6 milliseconds, causing the boat to travel a total of 6 millimeters. Hold the button for 7 milliseconds. That's the entire duration of the race. You never let go of the button. The boat can't move until you let go of the button. Please make sure you let go of the button so the boat gets to move. 0 millimeters.

In the example provided, with a current record of 9 millimeters:

  • For the first race, holding the button for 2, 3, 4, or 5 milliseconds allows winning, totaling 4 different ways.
  • In the second race, winning strategies involve holding the button for at least 4 milliseconds and at most 11 milliseconds, providing a total of 8 different ways to win.
  • For the third race, winning requires holding the button for at least 11 milliseconds and no more than 19 milliseconds, offering a total of 9 ways to win.

The answer is determined by multiplying the respective counts of winning strategies in each race.

In this example, if you multiply all these values together, you get 288 (4 * 8 * 9).

#!/usr/bin/env python3

from pathlib import Path
from typing import Iterable

import typer


def race(speed: int, time_left: int, record: int) -> bool:
    # Check if we can cover a distance greater than the specified record.
    return speed * time_left > record


def parse_nums(line: str) -> list[int]:
    # Name:     A B C ...
    nums = line.split(": ")[1]
    return list(map(int, nums.split()))


def count_wins(time: int, distance: int) -> int:
    return sum(
        race(hold_time, time - hold_time, distance)
        for hold_time in range(1, time + 1)
    )


def total_possibilities(lines: Iterable[str]) -> int:
    times, distances = tuple(map(parse_nums, lines))
    total_margin = 1

    for idx, time in enumerate(times):
        count = count_wins(time, distances[idx])

        if count:
            total_margin *= count

    return total_margin


def main(race_document: Path) -> None:
    with open(race_document) as f:
        print(total_possibilities(f))


if __name__ == "__main__":
    typer.run(main)

Part 2:

This part involves a single, extended toy boat race with combined time and record distance.

So, the example from before:

Time:      7  15   30
Distance:  9  40  200

now instead means this:

Time:      71530
Distance:  940200

This time, the answer is 71503.

#!/usr/bin/env python3

import sys
from pathlib import Path
from typing import Iterable

import typer


def race(hold_time: int, time_left: int, record: int) -> bool:
    # Check if we can cover a distance greater than the specified record.
    return hold_time * time_left > record


def parse_nums(line: str) -> list[int]:
    # Name:     A B C ...
    nums = line.split(": ")[1].strip().split()
    return int("".join(nums))


def count_wins(time: int, distance: int) -> int:
    return sum(
        race(hold_time, time - hold_time, distance)
        for hold_time in range(1, time + 1)
    )


def total_possibilities(lines: Iterable[str]) -> int:
    return count_wins(*tuple(map(parse_nums, lines)))

def main(race_document: Path) -> None:
    sys.set_int_max_str_digits(0)

    with open(race_document) as f:
        print(total_possibilities(f))


if __name__ == "__main__":
    typer.run(main)

Review Request:

General coding comments, style, etc.

What are some possible simplications? What would you do differently?

\$\endgroup\$
3
  • \$\begingroup\$ Your solution is linear in terms of race duration. There is a constant time solution. \$\endgroup\$
    – vnp
    Commented Dec 19, 2023 at 18:43
  • \$\begingroup\$ @vnp Pray, elucidate. I was unable to figure out the constant time solution. \$\endgroup\$
    – Harith
    Commented Dec 20, 2023 at 17:55
  • 2
    \$\begingroup\$ Solve the quadratic equation hold * (time - hold) = record. Everything between the roots wins, so there are sqrt(time ** 2 - 4 * record) scenarios. Pay attention to the corner case when the discriminant is a perfect square. \$\endgroup\$
    – vnp
    Commented Dec 20, 2023 at 18:02

1 Answer 1

3
\$\begingroup\$

Part 1

You ask what might be done differently. In function total_possibilities I would probably replace the use of the enumerate function used in your loop with the buit-in zip function:

def total_possibilities(lines: Iterable[str]) -> int:
    # No need to use the tuple function:
    times, distances = map(parse_nums, lines)
    total_margin = 1

    for time, distance in zip(times, distances):
        count = count_wins(time, distance)

        if count:
            total_margin *= count

    return total_margin

We can now modify function parse_nums to return a map instead of a list since there is no longer any need to do any explicit indexing:


def parse_nums(line: str) -> list[int]:
    # Name:     A B C ...
    nums = line.split(": ")[1]
    return map(int, nums.split()) # No need to create a list

If you wished you could also incorporate the functools.reduce function into function total_possibilities and use a comprehension:

def total_possibilities(lines: Iterable[str]) -> int:
    times, distances = map(parse_nums, lines)

    return reduce(
        lambda x, y: x * y,
        (count_wins(time, distance) for time, distance in zip(times, distances)) 
    )

Finally, in count_wins you are letting hold_range take on the values in the range [1, time]. But you should use instead the range [1, time-1] since if you hold the button for the maximum allowed time there is no time left for the boat to move:

def count_wins(time: int, distance: int) -> int:
    return sum(
        race(hold_time, time - hold_time, distance)
        for hold_time in range(1, time)
    )

Part 2

In function parse_nums you are doing an extra split followed by a join. These two calls can be replaced with a call to replace:

def parse_nums(line: str) -> list[int]:
    # Name:     A B C ...
    return int(line.split(": ")[1].replace(' ', ''))

Note that there is no need to perform a call to strip.

But clearly, as indicated in the comment made by user vnp, the biggest improvement can be achieved with a change in algorithm. As I understand it you really want to solve the quadratic equation for distance + 1. This yields two roots and we wish to count all the integer values between these roots. So we have:

...

from math import sqrt, ceil, floor


def parse_nums(line: str) -> list[int]:
    # Name:     A B C ...
    return int(line.split(": ")[1].replace(' ', ''))


def count_wins(time: int, distance: int) -> int:
    distance += 1
    discriminant = time ** 2 - 4 * distance
    sqrt_discriminant = sqrt(discriminant)
    upper_root = (time + sqrt_discriminant) / 2
    lower_root = (time - sqrt_discriminant) / 2

    # Get number of integers in the range [lower_root, upper_root]:
    return floor(upper_root) - ceil(lower_root) + 1


def total_possibilities(lines: Iterable[str]) -> int:
    # No need for the tuple function:
    return count_wins(*map(parse_nums, lines))

...
```
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.