The weekly challenge 274 - Task 2: Bus Route

  1 #!/usr/bin/env perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-274/#TASK2
  3 #
  4 # Task 2: Bus Route
  5 # =================
  6 #
  7 # Several bus routes start from a bus stop near my home, and go to the same
  8 # stop in town. They each run to a set timetable, but they take different times
  9 # to get into town.
 10 #
 11 # Write a script to find the times - if any - I should let one bus leave and
 12 # catch a strictly later one in order to get into town strictly sooner.
 13 #
 14 # An input timetable consists of the service interval, the offset within the
 15 # hour, and the duration of the trip.
 16 #
 17 # Example 1
 18 #
 19 # Input: [ [12, 11, 41], [15, 5, 35] ]
 20 # Output: [36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47]
 21 #
 22 # Route 1 leaves every 12 minutes, starting at 11 minutes past the hour (so 11,
 23 # 23, ...) and takes 41 minutes. Route 2 leaves every 15 minutes, starting at 5
 24 # minutes past (5, 20, ...) and takes 35 minutes.
 25 #
 26 # At 45 minutes past the hour I could take the route 1 bus at 47 past the hour,
 27 # arriving at 28 minutes past the following hour, but if I wait for the route 2
 28 # bus at 50 past I will get to town sooner, at 25 minutes past the next hour.
 29 #
 30 # Example 2
 31 #
 32 # Input: [ [12, 3, 41], [15, 9, 35], [30, 5, 25] ]
 33 # 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 ]
 34 #
 35 ############################################################
 36 ##
 37 ## discussion
 38 ##
 39 ############################################################
 40 #
 41 # This one is a bit more complicated. First, we collect the data for
 42 # each bus line from the command line. While at it, we also initialize
 43 # two arrays for each line: The times of departure and the corresponding
 44 # arrivals. We fill those next by calculating each departure in the hour
 45 # together with the corresponding arrival time (in minutes relative to
 46 # the beginning of the current hour, so it's perfectly fine to have a number
 47 # > 60 for the arrival).
 48 # Now for each minute (0 through 59), we sort the bus lines by the next
 49 # departure time - if no more departure happens during this hour, take the
 50 # first one in the next hour (by adding 60 minutes to the first one in this
 51 # hour). We look at the arrival times of all bus lines sorted by departure
 52 # time. This way, if any arrival time is before the soonest arrival time
 53 # of the soonest departure time, we are better off waiting (yes, we have to
 54 # handle the case that two buses start at the same time).
 55 
 56 use strict;
 57 use warnings;
 58 use Data::Dumper;
 59 
 60 bus_route( [ [12, 11, 41], [15, 5, 35] ] );
 61 bus_route( [ [12, 3, 41], [15, 9, 35], [30, 5, 25] ] );
 62 
 63 sub bus_route {
 64    my $buses = shift;
 65    my $line = 0;
 66    my $data;
 67    foreach my $bus (@$buses) {
 68       $line++;
 69       $data->{$line} = {
 70          interval => $bus->[0],
 71          first => $bus->[1],
 72          duration => $bus->[2],
 73          times => [ $bus->[1] ],
 74          arrivals => [ $bus->[1] + $bus->[2] ],
 75       };
 76       my $f = $data->{$line}->{first};
 77 
 78       while($f < 60) {
 79          $f += $data->{$line}->{interval};
 80          my $arrival = $f + $data->{$line}->{duration};
 81          if($f < 60) {
 82             push @{ $data->{$line}->{times} }, $f;
 83             push @{ $data->{$line}->{arrivals} }, $arrival;
 84          }
 85       }
 86    }
 87 
 88    my @result = ();
 89    MINUTE: foreach my $minute (0..59) {
 90       my $this_schedule = {};
 91       foreach my $line (sort {$a <=> $b } keys %$data) {
 92          my $index = 0;
 93          foreach my $time (@{ $data->{$line}->{times} }) {
 94             if($time >= $minute) {
 95                $this_schedule->{$line}->{time} = $time;
 96                $this_schedule->{$line}->{arrival} = $data->{$line}->{arrivals}->[$index];
 97                last;
 98             }
 99             $index++;
100          }
101          unless($this_schedule->{$line}) {
102             $this_schedule->{$line}->{time} = $data->{$line}->{times}->[0] + 60;
103             $this_schedule->{$line}->{arrival} = $data->{$line}->{arrivals}->[0] + 60;
104          }
105       }
106       my @lines_by_time = sort { $this_schedule->{$a}->{time} <=> $this_schedule->{$b}->{time} } keys %$this_schedule;
107       my ($start, $arrival) = ( $this_schedule->{ $lines_by_time[0] }->{time}, $this_schedule->{ $lines_by_time[0] }->{arrival} );
108       foreach my $line (@lines_by_time) {
109          my $s = $this_schedule->{$line}->{time};
110          my $a = $this_schedule->{$line}->{arrival};
111          if($a < $arrival) {
112             $arrival = $a;
113             if($s > $start) {
114                push @result, $minute;
115                next MINUTE;
116             }
117          }
118       }
119    }
120    print "Output: [", join(", ", @result), "]\n";
121 }