Speaking Goat Latin on the fastest bus to town

Weekly Challenge 274

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Goat Latin

Task

You are given a sentence, $sentence.

Write a script to convert the given sentence to Goat Latin, a made up language similar to Pig Latin.

Rules for Goat Latin:

1. If a word begins with a vowel ("a", "e", "i", "o", "u"), append "ma" to the end of the word.
2. If a word begins with consonant i.e. not a vowel, remove first letter and append it to the end then add "ma".
3. Add letter "a" to the end of first word in the sentence, "aa" to the second word, etc etc.

My solution

A few weeks ago I mentioned how my employer - now former employer :( - give us access to GitHub Copilot. It's pretty cool, and practically wrote the code for me.

I did modify it slightly to make the code a little easier to understand, but I'm super impressed that it came up with a perfectly working solution.

def goat_latin(sentence: str) -> str:
    words = sentence.split(' ')
    for i, word in enumerate(words):
        if word[0].lower() not in ['a', 'e', 'i', 'o', 'u']:
            word = word[1:] + word[0]

        words[i] = word + 'maa' + 'a' * i

    return ' '.join(words)

Examples

$ ./ch-1.py "I love Perl"
Imaa ovelmaaa erlPmaaaa

$ ./ch-1.py "Perl and Raku are friends"
erlPmaa andmaaa akuRmaaaa aremaaaaa riendsfmaaaaaa

$ ./ch-1.py "The Weekly Challenge"
heTmaa eeklyWmaaa hallengeCmaaaa

Task 2: Bus Route

Task

Several bus routes start from a bus stop near my home, and go to the same stop in town. They each run to a set timetable, but they take different times to get into town.

Write a script to find the times - if any - I should let one bus leave and catch a strictly later one in order to get into town strictly sooner.

An input timetable consists of the service interval, the offset within the hour, and the duration of the trip.

My solution

I'd love to see more challenges like this one. Yes, they take a longer time to come up with a solution, but they challenge me to turn the task into a working solution. And this is one where Copilot was less than helpful.

For the input from the command line, I take the integers in sets of three for the attribute of each route.

For this task I worked out a solution on my whiteboard before writing a single line of code. There are many different parts to my solution.

The first is a dataclass that has information about each route. This makes it easier to reference the attributes of each route.

from dataclasses import dataclass

@dataclass
class Route:
    freq: int
    offset: int
    length: int

The next part to my solution is a function that takes the route, and finds the fastest bus that leaves at each minute. This is stored as a dict where the key is the departure minute, and the value is the journey time of the quickest bus leaving at that minute.

def calculate_departures(routes):
    departures = {}
    for route in routes:
        start_minute = route.offset % route.freq
        while start_minute < 60:
            if start_minute in departures and departures[start_minute] < route.length:
                # This is a slower bus, so we can ignore it
                continue
            departures[start_minute] = route.length
            start_minute += route.freq

    return departures

The next function I have is called next_bus. Given the departures (from the above function) and a minute, it will determine the next bus to depart, which may possibly cross over an hour (eg. 11:59, 12:00, 12:01...). The function returns the start_minute minute and the end_minute minute (start minute + journey length).

def next_bus(departures, minute):
    start_minute = minute
    while True:
        if start_minute in departures:
            return start_minute, start_minute + departures[start_minute]

        start_minute += 1
        if start_minute == 60:
            start_minute = 0

The main function puts this all together. I start by defining departures from the calculate_departures function, and the skip_bus variable as an empty list.

def bus_route(routes: list[Route]) -> list[int]:
    # Get the start time of all bus routes
    departures = calculate_departures(routes)
    skip_bus = []

I then have a double loop. The outer loop uses the variable minute and is loops from zero to 59. I use the next_bus function to determine the start_minute and end_minute of the next bus to arrive.

The inner loop uses the variable second_bus_start and loops from one minute past the start_minute to one less than the end_minute. It checks if there is a bus departing at that minute. If there is and it gets us to the destination quicker, I exit the inner loop and add the start_minute value to the skip_bus list.

    for minute in range(60):
        start_minute, end_minute = next_bus(departures, minute)

        for second_bus_start in range(start_minute + 1, end_minute):
            if second_bus_start % 60 not in departures:
                continue
            if second_bus_start + departures[second_bus_start % 60] < end_minute:
                break
        else:
            continue

        skip_bus.append(minute)

Examples

$ ./ch-2.py 12 11 41 15 5 35
[36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47]

$ ./ch-2.py 12 3 41 15 9 35 30 5 25
[0, 1, 2, 3, 25, 26, 27, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 55, 56, 57, 58, 59]