Speaking Goat Latin on the fastest bus to town
Tags: perl, python, theweeklychallenge
Published: 2024-06-23 13:16:53

## Weekly Challenge 274

Each week Mohammad S. Anwar sends out [The Weekly Challenge](https://theweeklychallenge.org/), 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](https://theweeklychallenge.org/blog/perl-weekly-challenge-274/), [My solutions](https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-274/sgreen)

## 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.
1. If a word begins with consonant i.e. not a vowel, remove first letter and append it to the end then add "ma".
1. 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.

![output from vscode with copilot](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/31s1nhftm22e049f971r.png)

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.

```python
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

```bash
$ ./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](https://docs.python.org/3/library/dataclasses.html) that has information about each route. This makes it easier to reference the attributes of each route.

```python
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.

```python
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).

```python
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.

```python
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.

```python
    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

```bash
$ ./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]
```