forked from manwar/perlweeklychallenge-club
-
Notifications
You must be signed in to change notification settings - Fork 0
/
ch-2.pl
executable file
·83 lines (73 loc) · 2.17 KB
/
ch-2.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#!/usr/bin/env perl
use v5.40;
use List::Util qw( mesh uniq );
sub routeTimes($route) {
my ($interval, $start, $duration) = @$route;
my %times;
while ($start < 60 + $interval) {
$times{$start} = $start + $duration;
$start += $interval;
}
return %times;
}
sub faster(@routes) {
# find the arrival times for each route's departures
my %times;
foreach my $route ( @routes ) {
foreach my($start, $arrive) ( routeTimes($route) ) {
if (exists $times{$start} && $times{$start} > $arrive) {
# this departure for this route will arrive sooner than
# the departure for the earlier route, keep this one!
$times{$start} = $arrive;
}
elsif (! exists $times{$start}) {
# no route we've seen has a departure at this time
$times{$start} = $arrive;
}
}
}
# now look at all the departures and see if there are
# later departures with earlier arrivals
my @bad_starts;
my @starts = sort { $a <=> $b } keys %times;
foreach my($pos, $start) ( mesh [0 .. $#starts], \@starts ) {
foreach my $i (@starts[$pos+1 .. $#starts]) {
if ($times{$i} < $times{$start} ) {
# we found a later departure with an earlier arrival!
push @bad_starts, $start;
}
}
}
@bad_starts = uniq @bad_starts;
# now determine which minutes of the hour we should say
# "skip the next bus and take the later one"
my @skip;
foreach my $min ( 0 .. 59 ) {
if (@starts && @bad_starts && $starts[0] == $bad_starts[0]) {
# we're in a bad window!
push @skip, $min;
}
if (@starts && $starts[0] == $min) {
shift @starts; # remove the start time
}
if (@bad_starts && $bad_starts[0] == $min) {
shift @bad_starts; # remove the bad start time
}
}
return @skip;
}
sub routeJoin(@routes) {
my @out;
foreach my $route ( @routes ) {
push @out, '[' . join(', ', @$route) . ']';
}
return '[ ' . join(', ', @out) . ' ]'
}
sub solution(@routes) {
say 'Input: ' . routeJoin(@routes);
say 'Output: [' . join(', ', faster(@routes)) . ']';
}
say "Example 1:";
solution([12, 11, 41], [15, 5, 35]);
say "\nExample 2:";
solution([12, 3, 41], [15, 9, 35], [30, 5, 25]);