Task — 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.

Examples

Example 1
Input: [ [12, 11, 41], [15, 5, 35] ]
Output: [36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47]

Route 1 leaves every 12 minutes, starting at 11 minutes 
past the hour (so 11, 23, ...) and takes 41 minutes. Route
2 leaves every 15 minutes, starting at 5 minutes past 
(5, 20, ...) and takes 35 minutes.

At 45 minutes past the hour I could take the route 1 bus 
at 47 past the hour, arriving at 28 minutes past the 
following hour, but if I wait for the route 2 bus at 50 
past I will get to town sooner, at 25 minutes past the 
next hour.

Example 2
Input: [ [12, 3, 41], [15, 9, 35], [30, 5, 25] ]
Output: [ 0, 1, 2, 3, 25, 26, 27, 40, 41, 42, 43, 44, 45, 
    46, 47, 48, 49, 50, 51, 55, 56, 57, 58, 59 ]

Analysis

I think the easiest way to do this is to

• run through 0 to 59 minutes past the hour,
• find the next bus on each route and see which gets to town soonest,
• check whether any of the other routes leave between now and that one,
• and if so list that (or them) as buses to be skipped.

Note that if there are 3+ routes it may be necessary to let 2+ buses pass by and take the third - as in my 3rd example.

Although many bus stops in the UK have displays showing when buses are due, I've never seen one that shows this calculation, maybe because alternative timings to the same place are not very common.

I have seen displays in train stations showing the fastest route, though not at my local station (Cambridge) where there are 3 routes to almost the same place in London with different durations.

I submitted this challenge based on the actual timings of two bus routes from my home to the centre of Cambridge - and those are example 1 above. Now I know when to wait!

Try it 

Script

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2024-06-17
use utf8;     # Week 274 - task 2 - Bus route
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

bus_route([12, 11, 41], [15, 5, 35]);
bus_route([12, 3, 41], [15, 9, 35], [30, 5, 25]);
bus_route([20, 0, 13], [15, 14, 15], [30, 15, 7]);

sub bus_route {
    
    my ($r, @interval, @offset, @duration, 
        @leave, @arrive, $take, $time, $best, $soonest, $routes);
    
    # import and show data
    $routes = @_;
    say qq[\nInput:\n    rt int off dur];
    for $r (0 .. $routes - 1) {
        ($interval[$r], $offset[$r], $duration[$r]) = @{$_[$r]};
        printf("    %2d  %2d  %2d %3d\n", $r + 1, $interval[$r], $offset[$r], $duration[$r]);
    }
    
    say qq[Output:];
    say qq[    at take lv  ar  not lv  ar];
    
    # first departure in the hour
    for $r (0 .. $routes - 1) {
        $leave[$r] = $offset[$r];
    }
    
    # loop over minutes
    for $time (0 .. 59) {
        
        # get soonest arrival for this $time departure
        $soonest = 999;
        for $r (0 .. $routes - 1) {
            $leave[$r] += $interval[$r] if $leave[$r] < $time;
            $arrive[$r] = $leave[$r] + $duration[$r];
            
            if ($arrive[$r] < $soonest) {
                $soonest = $arrive[$r];
                $best = $r;
            }
        }
        
        # see if we can get there sooner by leaving later on another route
        for $r (0 .. $routes - 1) {
            if ($leave[$r] < $leave[$best] and $arrive[$r] > $arrive[$best]) {
                printf("    %02d    %d %02d %3d    %d %02d %3d\n", 
                    $time, $best + 1, $leave[$best], $arrive[$best], $r + 1, $leave[$r], $arrive[$r]);
            }
        }
    }
}

Output

Input:
    rt int off dur
     1  12  11  41
     2  15   5  35
Output:
    at take lv  ar  not lv  ar
    36    2 50  85    1 47  88
    37    2 50  85    1 47  88
    38    2 50  85    1 47  88
    39    2 50  85    1 47  88
    40    2 50  85    1 47  88
    41    2 50  85    1 47  88
    42    2 50  85    1 47  88
    43    2 50  85    1 47  88
    44    2 50  85    1 47  88
    45    2 50  85    1 47  88
    46    2 50  85    1 47  88
    47    2 50  85    1 47  88

Input:
    rt int off dur
     1  12   3  41
     2  15   9  35
     3  30   5  25
Output:
    at take lv  ar  not lv  ar
    00    3 05  30    1 03  44
    01    3 05  30    1 03  44
    02    3 05  30    1 03  44
    03    3 05  30    1 03  44
    25    3 35  60    1 27  68
    26    3 35  60    1 27  68
    27    3 35  60    1 27  68
    40    2 54  89    1 51  92
    41    2 54  89    1 51  92
    42    2 54  89    1 51  92
    43    2 54  89    1 51  92
    44    2 54  89    1 51  92
    45    2 54  89    1 51  92
    46    2 54  89    1 51  92
    47    2 54  89    1 51  92
    48    2 54  89    1 51  92
    49    2 54  89    1 51  92
    50    2 54  89    1 51  92
    51    2 54  89    1 51  92
    55    3 65  90    1 63 104
    56    3 65  90    1 63 104
    57    3 65  90    1 63 104
    58    3 65  90    1 63 104
    59    3 65  90    1 63 104

Input:
    rt int off dur
     1  20   0  13
     2  15  14  15
     3  30  15   7
Output:
    at take lv  ar  not lv  ar
    01    3 15  22    2 14  29
    02    3 15  22    2 14  29
    03    3 15  22    2 14  29
    04    3 15  22    2 14  29
    05    3 15  22    2 14  29
    06    3 15  22    2 14  29
    07    3 15  22    2 14  29
    08    3 15  22    2 14  29
    09    3 15  22    2 14  29
    10    3 15  22    2 14  29
    11    3 15  22    2 14  29
    12    3 15  22    2 14  29
    13    3 15  22    2 14  29
    14    3 15  22    2 14  29
    30    3 45  52    1 40  53
    30    3 45  52    2 44  59
    31    3 45  52    1 40  53
    31    3 45  52    2 44  59
    32    3 45  52    1 40  53
    32    3 45  52    2 44  59
    33    3 45  52    1 40  53
    33    3 45  52    2 44  59
    34    3 45  52    1 40  53
    34    3 45  52    2 44  59
    35    3 45  52    1 40  53
    35    3 45  52    2 44  59
    36    3 45  52    1 40  53
    36    3 45  52    2 44  59
    37    3 45  52    1 40  53
    37    3 45  52    2 44  59
    38    3 45  52    1 40  53
    38    3 45  52    2 44  59
    39    3 45  52    1 40  53
    39    3 45  52    2 44  59
    40    3 45  52    1 40  53
    40    3 45  52    2 44  59
    41    3 45  52    2 44  59
    42    3 45  52    2 44  59
    43    3 45  52    2 44  59
    44    3 45  52    2 44  59
    46    1 60  73    2 59  74
    47    1 60  73    2 59  74
    48    1 60  73    2 59  74
    49    1 60  73    2 59  74
    50    1 60  73    2 59  74
    51    1 60  73    2 59  74
    52    1 60  73    2 59  74
    53    1 60  73    2 59  74
    54    1 60  73    2 59  74
    55    1 60  73    2 59  74
    56    1 60  73    2 59  74
    57    1 60  73    2 59  74
    58    1 60  73    2 59  74
    59    1 60  73    2 59  74