RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved string tweaking and bus route analysis. (Note that this ends today.)

Task 1: Goat Latin

You are given a sentence, $sentance.

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

There are ways of optimising this, but I decided to do it in a straightforward way, step by step.

sub goatlatin($a) {
    my @out;

Look at each word, taking an index too.

    my @w = $a.split(' ');
    for @w.kv -> $ix, $word {

Split the word into characters, and build a default new word.

        my @c = $word.comb;
        my $nw = $word;

(Rule 1) If the first character is not a vowel,

        if (@c[0] !~~ m:i/<[aeiou]>/) {

Move the first letter to the end, and rebuild the new word.

            @c.push(@c.shift);
            $nw = @c.join('');
        }

(Rule 2) add "ma"

        $nw ~= 'ma';

(Rule 3) add one or more "a".

        $nw ~= 'a' x ($ix + 1);

Store the word, and return the concatenation of all words.

        @out.push($nw);
    }
    return @out.join(' ');
}

Task 2: Bus Route

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.

I built this by testing overlapping sets. (Which is why I've recently written set algebra functions for my PostScript libraries.) But here's the Rust:

fn busroute(a: Vec<Vec<u32>>) -> Vec<u32> {

Process each route into a hash of (departure time, arrival time), with times measured in minutes from the start of the first hour. Include the first bus of the next hour.

    let mut routes = Vec::new();
    for rt in a {
        let mut ri = HashMap::new();
        let interval = rt[0];
        let offset = rt[1];
        let duration = rt[2];
        let mut start = offset;
        while start <= 60 + offset {
            ri.insert(start, start + duration);
            start += interval;
        }
        routes.push(ri);
    }
    let mut out = Vec::new();

For each possible departure minute,

    for t in 0..60 {

we will be building sets of the "best" bus (the one that gets to the destination first) and the "next" bus (the next one to depart).

        let mut best = HashSet::new();
        let mut at: Option<u32> = None;
        let mut nxt = HashSet::new();
        let mut ndt: Option<u32> = None;

For each route,

        for (i, r) in routes.iter().enumerate() {

get the next departure time,

            let nb = r.keys().filter(|n| **n >= t).min().unwrap();

and the corresponding arrival time.

            let nt = r.get(nb).unwrap();

If we don't already have a best bus, or this one is better than the previous best, clear the set of best buses and record the arrival time.

            if at.is_none() || *nt < at.unwrap() {
                best.clear();
                at = Some(*nt);
            }

If this bus arrives no later than the previous best, add its route to the set.

            if *nt <= at.unwrap() {
                best.insert(i);
            }

Similarly with the next bus.

            if ndt.is_none() || *nb < ndt.unwrap() {
                nxt.clear();
                ndt = Some(*nb);
            }
            if *nb <= ndt.unwrap() {
                nxt.insert(i);
            }
        }

If the set of best buses intersects with the set of next buses, then that's the bus to take; but if there is no intersection, I'll do better to wait for a later bus, and that's what I'm counting.

        if best.intersection(&nxt).count() == 0 {
            out.push(t);
        }
    }
    out
}

(Some languages don't have sets, or don't have set intersection functions, but it's easy enough to write out longhand.)

Full code on github.