For this week's challenge, we have an interesting problem to ponder while we're Waiting at the Bus Stop.
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.
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 ]
Discourse
Let's flesh out some implied requirements.
The problem isn't asking us to identify the best choice; it only wants us to find the minutes where the next bus is not the best.
The routes appear to have hourly cycles, so we should only have to look at minutes 0 to 59, and then the situation resets for the following hour.
We'll need to figure out, at minute m, the next arrival of each of the routes. Then we'll take the earliest, unless one of the other routes arrives sooner. We don't need to look ahead any farther than that.
I'm tempted to build a class around a "route", if only to have a more readable way to access the triple of numbers, but let's hold that thought for a minute.
I'm also tempted to pre-compute all the possible bus arrival times and corresponding destination times, and then search for the condition. But it occurs to me that in creating such a table, I will have done most of the work to answer the question.
Into the breach
Let's tackle the problem of figuring out when the next bus of a given route arrives. We are standing at the bus stop at minute m. The route is identified by a tuple of [cycle, offset, duration]. Buses on the route will arrive first at minute offset, and then at times offset+n*cycle. Our problem is figure out which n our minute m is in.
0 offset 1*cycle 2*cycle 3*cycle
|------|--------|---------|--------|----...
m
To figure out the block, subtract out offset from m so that it has the same origin as the route cycle. Then divide by cycle and round up to the next integer: n = ceil( (m - offset) / cycle ).
Then the next arrival of the route at or after m will be offset+n*cycle. That bus will arrive at the destination duration minutes later.
So, here's a helpful little function that will determine, for a given route at minute m, when the bus arrives at the stop, and when it reaches its destination. We'll return those two bits of information as a pair in an array reference.
sub nextBusAt($route, $minute)
{
my ($cycle, $offset, $duration) = $route->@*;
my $stop = $offset + $cycle * ceil( ($minute - $offset) / $cycle );
return [ $stop, $stop + $duration ];
}
Next step: at minute $minute, we want to know this information for each of the routes. Let's make a list of [bus, finish] pairs, applying nextBusAt as a transformation to each route.
map { nextBusAt($_, $minute) } $timetable->@*;
We need to know which of those is going to be first to arrive, so let's sort the pairs by the first element of each pair. Recall that nextBusAt returns an array reference to a pair, so we're operating on a list of array references from map.
my @next = sort { $a->[0] <=> $b->[0] } map { ...
The @next array is a list of pairs; each pair is an array reference to a bus arrival time, and a destination finish time. The first element in the @next array is the earliest bus to arrive, because of the sort. Let's pull that one aside and use it to compare to the others.
my ( $firstStopTime, $firstFinishTime) = (shift @next)->@*;
Is this the bus we should take? For the current minute, we should skip taking it if any other bus would have an earlier finish time. This can be expressed, using the any function from List::Util, as
my @skipToLater;
push @skipToLater, $minute
if any { $_->[1] < $firstFinishTime } @next
Almost. What if two buses arrive at the stop at the same time? We're not asked to determine which bus to take, only to decide whether we should keep waiting. If two buses pull up at the same time, we're going to jump on the faster bus, so the answer to the "keep waiting?" question is "no." We have to modify our decision to take this into account.
my @skipToLater;
push @skipToLater, $minute
if any { $_->[1] < $firstFinishTime
&& $_->[0] != $firstStopTime } @next
Let's put the pieces together. We need to make this decision for every minute in the hour, and accumulate the minutes where a bus should be skipped.
sub busRoute($timetable)
{
use List::Util qw/any/;
my @skipToLater;
for my $minute ( 0 .. 59 )
{
my @next = sort { $a->[0] <=> $b->[0] }
map { nextBusAt($_, $minute) } $timetable->@*;
my ( $firstStopTime, $firstFinishTime) = (shift @next)->@*;
push @skipToLater, $minute
if any { $_->[1] < $firstFinishTime
&& $_->[0] != $firstStopTime } @next;
}
return \@skipToLater;
}
It's probably not optimally efficient -- there are blocks of times when the answer is the same; we could probably figure those out based on (hand-wavy rationalization) some math of the common factors of the route cycle times, and therefore skip some loop iterations, but with only 60 iterations, it's not worth the mental gymnastics.
I didn't need to create any classes, or simulate the bus arrivals, or precompute the possibilities after all, fun as that might have been.
Top comments (1)
Thanks Bob! You're a great teacher! Nice text!