[Day 6] Wait For It // Advent of Code 2023 (Python)

Wait For It (via DALL-E 3)

Advent of Code
The ferry quickly brings you across Island Island. After asking around, you discover that there is indeed normally a…adventofcode.com

---

Part One

The ferry quickly brings you across Island Island. After asking around, you discover that there is indeed normally a large pile of sand somewhere near here, but you don’t see anything besides lots of water and the small island where the ferry has docked.

As you try to figure out what to do next, you notice a poster on a wall near the ferry dock. “Boat races! Open to the public! Grand prize is an all-expenses-paid trip to Desert Island!” That must be where the sand comes from! Best of all, the boat races are starting in just a few minutes.

You manage to sign up as a competitor in the boat races just in time. The organizer explains that it’s not really a traditional race — instead, you will get a fixed amount of time during which your boat has to travel as far as it can, and you win if your boat goes the farthest.

As part of signing up, you get a sheet of paper (your puzzle input) that lists the time allowed for each race and also the best distance ever recorded in that race. To guarantee you win the grand prize, you need to make sure you go farther in each race than the current record holder.

The organizer brings you over to the area where the boat races are held. The boats are much smaller than you expected — they’re actually toy boats, each with a big button on top. Holding down the button charges the boat, and releasing the button allows the boat to move. Boats move faster if their button was held longer, but time spent holding the button counts against the total race time. You can only hold the button at the start of the race, and boats don’t move until the button is released.

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 0millimeters 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 2millimeters 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.

Since the current record for this race is 9 millimeters, there are actually 4 different ways you could win: you could hold the button for 2, 3, 4, or 5 milliseconds at the start of the race.

In the second race, you could hold the button for at least 4 milliseconds and at most 11 milliseconds and beat the record, a total of 8 different ways to win.

In the third race, you could hold the button for at least 11 milliseconds and no more than 19 milliseconds and still beat the record, a total of 9ways you could win.

To see how much margin of error you have, determine the number of ways you can beat the record in each race; in this example, if you multiply these values together, you get 288 (4 * 8 * 9).

Determine the number of ways you could beat the record in each race. What do you get if you multiply these numbers together?

---

This is quite an interesting problem! It reminded me of the my highschool Physics questions with respect to velocity and acceleration!

Anyhow, the idea in question is fairly straight forward, we are given an input with record of each race with:

Time:      7  15   30  (milliseconds)
Distance:  9  40  200  (millimeters)

where, there’s a record of 9mm in 7ms, and 40mm in 15ms and so on…

The boat given to us allows us to charge (accelerate?) upto a speed based on the following rules:

• Initial speed: 0 mm/ms
• Charge: +1 mm/ms

The race starts at t0 and then you have a choice on how long you want to charge the boat, so that we can beat the given record, we can plot it to make it simpler!

The essence is we need to optimise b/w our charging time and speeding time to break the record!

where w1, w2, w3 are 3 ways to break a record in less than k time

And then we need to count the number of ways we can break the record for each race and return the product of all ways for each race!

Let’s see how we can code this, but first, let’s implement the give base test case first:

As expected, this will fail:

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_6/wait_for_it.py"
Traceback (most recent call last):
  File "/Users/jmalik/github/advent-of-code-2023/day_6/wait_for_it.py", line 24, in <module>
    test_find_number_of_ways_to_win()
  File "/Users/jmalik/github/advent-of-code-2023/day_6/wait_for_it.py", line 20, in test_find_number_of_ways_to_win
    assert ans == 288, f"Expected 288, got {ans}"
AssertionError: Expected 288, got 1

Perfect, let’s now look into the logic but first we need a parser for input. Like always, a quick ipython session and we can see how to get relevant info from the multiline str:

Translating to code:

This allows us to repesent the record in a python’s dict {time:distance} format, such as:

# race_records
{7: 9, 15: 40, 30: 200}

So, I also created a Boat class early on, to keep as an easy track of speed, charge and distance :

This allows us to keep our calculation logic simple, initially I am going for the brute force update where I will simple just check for all chargeTimes from (1 to record_time-1) as:

• 0 charging time will lead to 0 distance
• 1 unit of time is needed to move as well (post charging)

Here’s the code to just calculate number of ways_to_win per race record, where I am just lazyingly calculating boat.distance() post each unit time spend in boat.charge() :

And then we can extrapolate this to a function to check product of all ways_to_win for all the race_records :

Let’s run for our test case….and 🤞

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_6/wait_for_it.py"
All tests passed succesfully!

Awesome, now let’s take the puzzle input and run our code against it? We got an answer, let’s check it?

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_6/wait_for_it.py"
Margin of error: xxxxx

And….

😬

Oops! Let’s debug to see under the hood? Seems like our answer is too low.

💡Edge case: Ah! After spending a couple of minutes dry running the code, I was able to pin point the problem, in our puzzle input, we can have multiple races that have same record_time and since we are using a dict to keep a track of {time:distance} that will return in data loss, as our parse will just override the existing key.

Input has 4 records but our `race_records` only has 3 enteries!

Fix is pretty simple. We can just use a list[(tuples)...] to keep (t1, d1) and then iterate over it. Let’s fix it:

Observe `race_records` is now a list of tuples.

Let’s run it again…and..

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_6/wait_for_it.py"
Margin of error: xxxxxxx

🖖

Here’s our pythonic code till now:

# --- Day 6: Wait For It ---

class Boat:
    def __init__(self, speed=0):
        self.speed = speed # initial speed: 0 mm/ms

    def charge(self):
        """Increase the speed of the boat by 1 unit."""
        self.speed += 1 # Charge: +1 mm/ms 

    def distance(self, time):
        """Calculate the distance covered by the boat in a given time."""
        return self.speed * time

    def reset(self):
        """Reset the speed of the boat to its initial state."""
        self.speed = 0

class RaceAnalyzer:
    def __init__(self):
        self.boat = Boat()

    @staticmethod
    def parse_race_records(raw_race_records):
        """Parse raw race records into a list of tuples containing time and distance."""
        time_list = [int(t) for t in raw_race_records.splitlines()[0].split(":")[1].strip().split()]
        distance_list = [int(t) for t in raw_race_records.splitlines()[1].split(":")[1].strip().split()]
        return list(zip(time_list, distance_list))

    def find_number_of_ways_to_win(self, record_time, record_distance):
        """Determine the number of ways the boat can win given the record time and distance."""
        self.boat.reset()
        ways_to_win = 0

        for charging_time in range(1, record_time):
            self.boat.charge()
            if self.boat.distance(record_time - charging_time) > record_distance:
                ways_to_win += 1

        return ways_to_win

    def product_of_ways_to_win(self, race_records):
        """Calculate the product of ways to win for multiple race records."""
        prod = 1
        for record_time, record_distance in race_records:
            prod *= self.find_number_of_ways_to_win(record_time, record_distance)
        return prod

def part_1():
    analyzer = RaceAnalyzer()
    with open("day_6/input.txt", "r") as f:
        raw_race_records = f.read()

    race_records = analyzer.parse_race_records(raw_race_records)
    margin_of_error = analyzer.product_of_ways_to_win(race_records)
    print(f"Margin of error: {margin_of_error}")

def test_find_number_of_ways_to_win():
    raw_race_records = """Time:      7  15   30
Distance:  9  40  200"""

    analyzer = RaceAnalyzer()
    race_records = analyzer.parse_race_records(raw_race_records)
    margin_of_error = analyzer.product_of_ways_to_win(race_records)
    assert margin_of_error == 288, f"Expected 288, got {margin_of_error}"
    print("All tests passed successfully!")

if __name__ == "__main__":
    test_find_number_of_ways_to_win()
    part_1()

---

Part Two

As the race is about to start, you realize the piece of paper with race times and record distances you got earlier actually just has very badkerning. There’s really only one race — ignore the spaces between the numbers on each line.

So, the example from before:

Time: 7 15 30
Distance: 9 40 200

…now instead means this:

Time: 71530
Distance: 940200

Now, you have to figure out how many ways there are to win this single race. In this example, the race lasts for 71530 milliseconds and the record distance you need to beat is 940200 millimeters. You could hold the button anywhere from 14 to 71516 milliseconds and beat the record, a total of 71503 ways!

How many ways can you beat the record in this one much longer race?

---

Haha! Bad Kerning instead! Well, this should be pretty straight forward? 🤞

All we need to do is update our `parse_race_records` method, and rest of code should be same? I am just worried about the loop taking time, but since our code time complexity is O(n) running might be okay??!

Keep both in list to avoid modifying code above! 😅

Let’s run this for modified testcase?

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_6/wait_for_it.py"
All tests passed successfully!

💡We may need to introduct some efficiency in code to not run once our boat.distance() goes below record_time after beating the record as those enteries will always be less. Going back to our diagram:

So, final code looks like:

# --- Day 6: Wait For It ---

class Boat:
    def __init__(self, speed=0):
        self.speed = speed # initial speed: 0 mm/ms

    def charge(self):
        """Increase the speed of the boat by 1 unit."""
        self.speed += 1 # Charge: +1 mm/ms 

    def distance(self, time):
        """Calculate the distance covered by the boat in a given time."""
        return self.speed * time

    def reset(self):
        """Reset the speed of the boat to its initial state."""
        self.speed = 0

class RaceAnalyzer:
    def __init__(self):
        self.boat = Boat()

    # --- For Part One ---
    @staticmethod
    def parse_race_records_part_1(raw_race_records):
        """Parse raw race records into a list of tuples containing time and distance."""
        time_list = [int(t) for t in raw_race_records.splitlines()[0].split(":")[1].strip().split()]
        distance_list = [int(t) for t in raw_race_records.splitlines()[1].split(":")[1].strip().split()]
        return list(zip(time_list, distance_list))
    
    # --- For Part Two ---
    @staticmethod
    def parse_race_records_part_2(raw_race_records):
        """Parse raw race records into a list of tuples containing time and distance."""
        record_time = int(raw_race_records.splitlines()[0].split(":")[1].replace(" ", "").strip())
        record_distance = int(raw_race_records.splitlines()[1].split(":")[1].replace(" ", "").strip())
        return [(record_time, record_distance)]

    def find_number_of_ways_to_win(self, record_time, record_distance):
        """Determine the number of ways the boat can win given the record time and distance."""
        self.boat.reset()
        ways_to_win = 0

        for charging_time in range(1, record_time):
            self.boat.charge()
            boat_distance = self.boat.distance(record_time - charging_time)

            # improve performance by breaking early if the boat can't win
            if ways_to_win > 0 and boat_distance <= record_distance:
                break
            
            if  boat_distance > record_distance:
                ways_to_win += 1

        return ways_to_win

    def product_of_ways_to_win(self, race_records):
        """Calculate the product of ways to win for multiple race records."""
        prod = 1
        for record_time, record_distance in race_records:
            prod *= self.find_number_of_ways_to_win(record_time, record_distance)
        return prod

def part_1():
    analyzer = RaceAnalyzer()
    with open("day_6/input.txt", "r") as f:
        raw_race_records = f.read()

    race_records = analyzer.parse_race_records_part_1(raw_race_records)
    margin_of_error = analyzer.product_of_ways_to_win(race_records)
    print(f"Margin of error: {margin_of_error}")

def part_2():
    analyzer = RaceAnalyzer()
    with open("day_6/input.txt", "r") as f:
        raw_race_records = f.read()

    race_records = analyzer.parse_race_records_part_2(raw_race_records)
    margin_of_error = analyzer.product_of_ways_to_win(race_records)
    print(f"Margin of error: {margin_of_error}")

def test_find_number_of_ways_to_win_part_1():
    raw_race_records = """Time:      7  15   30
Distance:  9  40  200"""

    analyzer = RaceAnalyzer()
    race_records = analyzer.parse_race_records_part_1(raw_race_records)
    margin_of_error = analyzer.product_of_ways_to_win(race_records)
    assert margin_of_error == 288, f"Expected 288, got {margin_of_error}"
    print("All tests passed successfully!")

def test_find_number_of_ways_to_win_part_2():
    raw_race_records = """Time:      7  15   30
Distance:  9  40  200"""

    analyzer = RaceAnalyzer()
    race_records = analyzer.parse_race_records_part_2(raw_race_records)
    margin_of_error = analyzer.product_of_ways_to_win(race_records)
    assert margin_of_error == 71503, f"Expected 288, got {margin_of_error}"
    print("All tests passed successfully!")

if __name__ == "__main__":
    # part 1
    test_find_number_of_ways_to_win_part_1()
    part_1()

    # part 2
    test_find_number_of_ways_to_win_part_2()
    part_2()

Running this, we do get an answers, let’s input this to our answer box…and….. 🎊

🥳

---

p.s: I am deliberating not adding answers here so you can actually spend some time trying to understand how we solved the problem!

Feel free to checkout code on my Github repo and try to set it up and run on your machine 👇

GitHub - jatinkrmalik/advent-of-code-2023: Advent of Code is an Advent calendar of small…
Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can…github.com