Peter Campbell Smith
Latin buses
Weekly challenge 274 — 17 June 2024
Week 274: 17 Jun 2024
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
Any content of this website which has been created by Peter Campbell Smith is in the public domain