Paired Time with Raku
[226] Published 5. March 2023.This is my response to The Weekly Challenge #206.
Challenge #206.1: Shortest Time
HH:MM.
Write a script to find out the shortest time in minutes between any two time points.
Example 1:
Input: @time = ("00:00", "23:55", "20:00")
Output: 5
Since the difference between "00:00" and "23:55" is the shortest
(5 minutes).
Input: @array = ("01:01", "00:50", "00:57")
Output: 4
Input: @array = ("10:10", "09:30", "09:00", "09:55")
Output: 15
The shortest distance between two time points, will always be the period between two neighbouring time points - when we sort them.
This should illustrate why:
The shortest time can never be between a and c, but is either between a and b or between b and c. (If we assume that the values are distinct, that is. See # [3] for the case that they are not.)
File: shortest-time (partial)
#! /usr/bin/env raku
unit sub MAIN (*@time where @time.elems >= 2 # [1]
&& all(@time) ~~ /^<[012]><[0..9]>\:<[0..5]><[0..9]>$/,
:v($verbose));
my @sorted = @time.sort; # [2]
say ": Sorted: { @sorted.join(", ") }" if $verbose;
if (@sorted.elems > @sorted.unique.elems) # [3]
{
say "0";
exit;
}
@sorted.push: @sorted.head if @sorted.elems > 2; # [4]
say ": Sorted roundtrip: { @sorted.join(", ") }" if $verbose;
my $shortest = Inf; # [5]
my $first = @sorted.shift; # [6]
my $second; # [7]
while (@sorted) # [8]
{
my $second = @sorted.shift; # [9]
my $diff = time-diff($first, $second); # [10]
$shortest = min($shortest, $diff); # [11]
say ": first:$first second: $second -> diff:$diff" if $verbose;
$first = $second; # [12]
}
say $shortest; # [13]
[1] At least two elements, and all of them must satisfy the regex. Note that the regex will allow for hour values up to «29». I will look into that problem later.
[2] Sort the time values, as we are going to campare neighbouring values (in the array).
[3]
Do we have duplicate time points? Computed by removing duplicates
(unique) and comparing the number of elements (elems) with the
original number of elements). The shortest time between a time point and itself is zero
minutes.
See
docs.raku.org/routine/unique
for more information about unique.
See
https://docs.raku.org/routine/elems
for more information about elems.
[4] The very first example shows that we have to take the day divide into account. I'll tackle the difference between e.g. 23:59 and 00:01 later on, but as we are going to compare neighbouring values only, we need to add the first one at the end - so that we actually compare them all. This is only an issue when we have more than two elements, as the first and last value in the array are not neighbours in this case. (Think of the day not as line, but as a circle, where «23:59» lines up with «00:00».)
[5] We are looking for the shortest. So start off with a very large value.
[6] The first value (of each comparison pair).
[7] The second value (of the current pair) will end up here.
[8] As long as we have unfinished business,
[9] Get the second value.
[10] Compute the difference (in minutes).
[11] Save the new value (with min) if it is slower than
the old one.
See
docs.raku.org/routine/min
for more information about min.
[12] Get ready for the next iteration. The second value of this comparison becomes the first one in the next.
[13] Print the result.
File: shortest-time (the rest)
sub time-diff ($first, $second) # [14]
{
my ($first-h, $first-m) = $first.split(":"); # [15]
my ($second-h, $second-m) = $second.split(":"); # [15]
my $first-min = $first-h * 60 + $first-m; # [16]
my $second-min = $second-h * 60 + $second-m; # [16]
my $diff = ($second-min - $first-min); # [17]
return 24 * 60 + $diff if $diff < 0; # [18]
return $diff; # [19]
}
[14] The procedure doing the computation.
[15] Split the time point values into hours and minutes.
See
docs.raku.org/routine/split
for more information about split.
[16] Calculate the time points as minutes past midnight.
[17] Get the difference (in minutes).
[18] If the difference is negative, add one day's worth of minutes. This happens when we have copied the very first value to the end of the array, in [4].
[19] Return the (positive) difference.
Running it:
$ ./shortest-time 00:00 23:55 20:00
5
$ ./shortest-time 01:01 00:50 00:57
4
$ ./shortest-time 10:10 09:30 09:00 09:55
15
Looking good.
With verbose mode:
$ ./shortest-time -v 00:00 23:55 20:00
: Sorted: 00:00, 20:00, 23:55
: Sorted roundtrip: 00:00, 20:00, 23:55, 00:00
: first:00:00 second: 20:00 -> diff:1200
: first:20:00 second: 23:55 -> diff:235
: first:23:55 second: 00:00 -> diff:5
5
$ ./shortest-time -v 01:01 00:50 00:57
: Sorted: 00:50, 00:57, 01:01
: Sorted roundtrip: 00:50, 00:57, 01:01, 00:50
: first:00:50 second: 00:57 -> diff:7
: first:00:57 second: 01:01 -> diff:4
: first:01:01 second: 00:50 -> diff:1429
4
$ ./shortest-time -v 10:10 09:30 09:00 09:55
: Sorted: 09:00, 09:30, 09:55, 10:10
: Sorted roundtrip: 09:00, 09:30, 09:55, 10:10, 09:00
: first:09:00 second: 09:30 -> diff:30
: first:09:30 second: 09:55 -> diff:25
: first:09:55 second: 10:10 -> diff:15
: first:10:10 second: 09:00 -> diff:1370
15
Ok.
We could wrap the time points into a Class, together with most of the calculations. So let us do just that.
File: shortest-time-class
#! /usr/bin/env raku
unit sub MAIN (*@time where @time.elems >= 2 # [0]
&& all(@time) ~~ /^<[012]><[0..9]>\:<[0..5]><[0..9]>$/,
:v($verbose));
class HHMM # [1]
{
has UInt $.hh is rw where 0 <= $_ <= 23; # [2]
has UInt $.mm is rw where 0 <= $_ <= 59; # [2a]
method minutes # [3]
{
return $.hh * 60 + $.mm;
}
method diff (HHMM $second) # [4]
{
my $diff = $second.minutes - $.minutes;
return 24 * 60 + $diff if $diff < 0;
return $diff;
}
method Str # [5]
{
return $.hh.fmt('%02d') ~ ":" ~ $.mm.fmt('%02d');
}
}
my @sorted = @time.sort.map({ HHMM.new(hh => $_.substr(0,2).UInt,
mm => $_.substr(3,2).UInt) }); # [6]
say ": Sorted: { @sorted.join(", ") }" if $verbose;
if (@sorted.elems > @sorted.unique.elems)
{
say "0";
exit;
}
@sorted.push: @sorted.head if @sorted.elems > 2;
say ": Sorted roundtrip: { @sorted.join(", ") }" if $verbose;
my $shortest = Inf;
my $first = @sorted.shift;
my $second;
while (@sorted)
{
my $second = @sorted.shift;
my $diff = $first.diff($second); # [7]
$shortest = min($shortest, $diff);
say ": first:$first second: $second -> diff:$diff" if $verbose;
$first = $second;
}
say $shortest;
[1] The class, called «HHMM» because - why not.
[2] It has two values: «hh» the hour part, and «mm» the minute part. The where
clause ensures that we do not try to pass along illegal values, as e.g «25:20» (which
is not catched by the regex in [0]). Note the use of the UInt (Unsigned Int)
type, and is rw so that we can change the values after creating the object -
if we want to. We do not want to in this program, by the way...
[3] Method giving the time as minutes past midnight.
[4] Method giving the difference in minutes between two time points.
[5] This is used when Raku stringifies the objects, which it does with say
in verbose mode.
[6] Set up an array of HHMM objects. Note the use of the .UInt coercer, as
the substr method returns a string (which should not really be a great
surprise, given the last part of the method name), and passing the wrong type will
cause an exception.
[7] We envoke the «diff» method on the first object, and specify the second one as the argument.
Running it gives the expected result, even with verbose mode:
./shortest-time-class -v 00:00 23:55 20:00
: Sorted: 00:00, 20:00, 23:55
: Sorted roundtrip: 00:00, 20:00, 23:55, 00:00
: first:00:00 second: 20:00 -> diff:1200
: first:20:00 second: 23:55 -> diff:235
: first:23:55 second: 00:00 -> diff:5
5
The «25:00» problem in the initial program has been resolved:
$ ./shortest-time 22:00 25:00
180
$ ./shortest-time-class 22:00 25:00
Type check failed in assignment to $!hh; expected <anon> but got Int (25)
...
Challenge #206.2: Array Pairings
Write a script to find the maximum sum of the minimum of each pairs.
Example 1:
Input: @array = (1,2,3,4)
Output: 4
Possible Pairings are as below:
a) (1,2) and (3,4). So min(1,2) + min(3,4) => 1 + 3 => 4
b) (1,3) and (2,4). So min(1,3) + min(2,4) => 1 + 2 => 3
c) (1,4) and (2,3). So min(1,4) + min(2,3) => 2 + 1 => 3
So the maxium sum is 4.
Example 2
Input: @array = (0,2,1,3)
Output: 2
Possible Pairings are as below:
a) (0,2) and (1,3). So min(0,2) + min(1,3) => 0 + 1 => 1
b) (0,1) and (2,3). So min(0,1) + min(2,3) => 0 + 2 => 2
c) (0,3) and (2,1). So min(0,3) + min(2,1) => 0 + 1 => 1
So the maximum sum is 2.
#! /usr/bin/env raku
unit sub MAIN (*@array where @array.elems >= 2 && @array.elems %% 2 # [1]
&& all(@array) ~~ /^<[0..9]>*$/, :v($verbose));
my @permutations = @array.permutations; # [2]
say ": Permutations: { @permutations.join("|") }" if $verbose;
my $max = -Inf; # [3]
for @permutations -> @candidate # [4]
{
my $sum = max-sum-min-pair(@candidate); # [5]
$max = max($max, $sum); # [6]
}
say $max; # [7]
[1] At least two elements (>= 2), an even number of elements
(@array.elems %% 2, using the divisibility operator %%)
and a regex to ensure non-negative integers.
[2] We are shuffling the order, and permutations
does this for us.
See
docs.raku.org/routine/permutations for more information about permutations.
[3] We are aiming for the highest value, so start with the lowest possible.
[4] Iterate over the candidate arrays (permutations).
[5] Get the sum for the candidate.
[6] Save the highest value (with max).
See
docs.raku.org/routine/max
for more information about max.
[7] print the result.
File: array-pairings (the rest)
sub max-sum-min-pair (@array is copy) # [8]
{
my $sum = 0; # [9]
my $echo = $verbose ?? ":Candidate: { @array.join(",") } Pairs:" !! "";
while @array.elems # [10]
{
my $first = @array.shift; # [11]
my $second = @array.shift; # [12]
my $minimum = min($first, $second); # [13]
$echo ~= "[$first,$second -> $minimum]" if $verbose;
$sum += $minimum; # [14]
}
say "$echo -> Sum: $sum" if $verbose;
return $sum; # [15]
}
[8] The procedure doing the actual job. Note is copy, as we
are going to change the array (with shift in [11] and [12]).
[9] The sum is all the differences added together, so we add them to this variable in the loop below.
[10] As long as we have more values,
[11] Get the first value (of the pair).
[12] Get the second value (of the pair).
[13] Get the lowest value from the pair (with min).
[14] Add that value to the sum.
[15] Return the result.
Running it:
$ ./array-pairings 1 2 3 4
4
$ ./array-pairings 0 2 1 3
2
Looking good.
With verbose mode:
$ ./array-pairings -v 1 2 3 4
: Permutations: 1 2 3 4|1 2 4 3|1 3 2 4|1 3 4 2|1 4 2 3|1 4 3 2|2 1 3 4|\
2 1 4 3|2 3 1 4|2 3 4 1|2 4 1 3|2 4 3 1|3 1 2 4|3 1 4 2|\
3 2 1 4|3 2 4 1|3 4 1 2|3 4 2 1|4 1 2 3|4 1 3 2|4 2 1 3|\
4 2 3 1|4 3 1 2|4 3 2 1
:Candidate: 1,2,3,4 Pairs:[1,2 -> 1][3,4 -> 3] -> Sum: 4
:Candidate: 1,2,4,3 Pairs:[1,2 -> 1][4,3 -> 3] -> Sum: 4
:Candidate: 1,3,2,4 Pairs:[1,3 -> 1][2,4 -> 2] -> Sum: 3
:Candidate: 1,3,4,2 Pairs:[1,3 -> 1][4,2 -> 2] -> Sum: 3
:Candidate: 1,4,2,3 Pairs:[1,4 -> 1][2,3 -> 2] -> Sum: 3
:Candidate: 1,4,3,2 Pairs:[1,4 -> 1][3,2 -> 2] -> Sum: 3
:Candidate: 2,1,3,4 Pairs:[2,1 -> 1][3,4 -> 3] -> Sum: 4
:Candidate: 2,1,4,3 Pairs:[2,1 -> 1][4,3 -> 3] -> Sum: 4
:Candidate: 2,3,1,4 Pairs:[2,3 -> 2][1,4 -> 1] -> Sum: 3
:Candidate: 2,3,4,1 Pairs:[2,3 -> 2][4,1 -> 1] -> Sum: 3
:Candidate: 2,4,1,3 Pairs:[2,4 -> 2][1,3 -> 1] -> Sum: 3
:Candidate: 2,4,3,1 Pairs:[2,4 -> 2][3,1 -> 1] -> Sum: 3
:Candidate: 3,1,2,4 Pairs:[3,1 -> 1][2,4 -> 2] -> Sum: 3
:Candidate: 3,1,4,2 Pairs:[3,1 -> 1][4,2 -> 2] -> Sum: 3
:Candidate: 3,2,1,4 Pairs:[3,2 -> 2][1,4 -> 1] -> Sum: 3
:Candidate: 3,2,4,1 Pairs:[3,2 -> 2][4,1 -> 1] -> Sum: 3
:Candidate: 3,4,1,2 Pairs:[3,4 -> 3][1,2 -> 1] -> Sum: 4
:Candidate: 3,4,2,1 Pairs:[3,4 -> 3][2,1 -> 1] -> Sum: 4
:Candidate: 4,1,2,3 Pairs:[4,1 -> 1][2,3 -> 2] -> Sum: 3
:Candidate: 4,1,3,2 Pairs:[4,1 -> 1][3,2 -> 2] -> Sum: 3
:Candidate: 4,2,1,3 Pairs:[4,2 -> 2][1,3 -> 1] -> Sum: 3
:Candidate: 4,2,3,1 Pairs:[4,2 -> 2][3,1 -> 1] -> Sum: 3
:Candidate: 4,3,1,2 Pairs:[4,3 -> 3][1,2 -> 1] -> Sum: 4
:Candidate: 4,3,2,1 Pairs:[4,3 -> 3][2,1 -> 1] -> Sum: 4
4
$ ./array-pairings -v 0 2 1 3
: Permutations: 0 2 1 3|0 2 3 1|0 1 2 3|0 1 3 2|0 3 2 1|0 3 1 2|2 0 1 3|\
2 0 3 1|2 1 0 3|2 1 3 0|2 3 0 1|2 3 1 0|1 0 2 3|1 0 3 2|1 2 0 3|\
1 2 3 0|1 3 0 2|1 3 2 0|3 0 2 1|3 0 1 2|3 2 0 1|3 2 1 0|3 1 0 2|\
3 1 2 0
:Candidate: 0,2,1,3 Pairs:[0,2 -> 0][1,3 -> 1] -> Sum: 1
:Candidate: 0,2,3,1 Pairs:[0,2 -> 0][3,1 -> 1] -> Sum: 1
:Candidate: 0,1,2,3 Pairs:[0,1 -> 0][2,3 -> 2] -> Sum: 2
:Candidate: 0,1,3,2 Pairs:[0,1 -> 0][3,2 -> 2] -> Sum: 2
:Candidate: 0,3,2,1 Pairs:[0,3 -> 0][2,1 -> 1] -> Sum: 1
:Candidate: 0,3,1,2 Pairs:[0,3 -> 0][1,2 -> 1] -> Sum: 1
:Candidate: 2,0,1,3 Pairs:[2,0 -> 0][1,3 -> 1] -> Sum: 1
:Candidate: 2,0,3,1 Pairs:[2,0 -> 0][3,1 -> 1] -> Sum: 1
:Candidate: 2,1,0,3 Pairs:[2,1 -> 1][0,3 -> 0] -> Sum: 1
:Candidate: 2,1,3,0 Pairs:[2,1 -> 1][3,0 -> 0] -> Sum: 1
:Candidate: 2,3,0,1 Pairs:[2,3 -> 2][0,1 -> 0] -> Sum: 2
:Candidate: 2,3,1,0 Pairs:[2,3 -> 2][1,0 -> 0] -> Sum: 2
:Candidate: 1,0,2,3 Pairs:[1,0 -> 0][2,3 -> 2] -> Sum: 2
:Candidate: 1,0,3,2 Pairs:[1,0 -> 0][3,2 -> 2] -> Sum: 2
:Candidate: 1,2,0,3 Pairs:[1,2 -> 1][0,3 -> 0] -> Sum: 1
:Candidate: 1,2,3,0 Pairs:[1,2 -> 1][3,0 -> 0] -> Sum: 1
:Candidate: 1,3,0,2 Pairs:[1,3 -> 1][0,2 -> 0] -> Sum: 1
:Candidate: 1,3,2,0 Pairs:[1,3 -> 1][2,0 -> 0] -> Sum: 1
:Candidate: 3,0,2,1 Pairs:[3,0 -> 0][2,1 -> 1] -> Sum: 1
:Candidate: 3,0,1,2 Pairs:[3,0 -> 0][1,2 -> 1] -> Sum: 1
:Candidate: 3,2,0,1 Pairs:[3,2 -> 2][0,1 -> 0] -> Sum: 2
:Candidate: 3,2,1,0 Pairs:[3,2 -> 2][1,0 -> 0] -> Sum: 2
:Candidate: 3,1,0,2 Pairs:[3,1 -> 1][0,2 -> 0] -> Sum: 1
:Candidate: 3,1,2,0 Pairs:[3,1 -> 1][2,0 -> 0] -> Sum: 1
2
Note that half the canidates are duplicates, with a swapped left and right value of a single pair. The duplicates come nicely as every second candidate, so it easy to skip them.
File: array-pairings-half
#! /usr/bin/env raku
unit sub MAIN (*@array where @array.elems >= 2 && @array.elems %% 2
&& all(@array) ~~ /^<[0..9]>*$/, :v($verbose));
my @permutations = @array.permutations;
say ": Permutations: { @permutations.join("|") }" if $verbose;
my $max = -Inf;
for @permutations -> @candidate
{
state $index = 0; # [1]
$index++; # [2]
next if $index %% 2; # [3]
my $sum = max-sum-min-pair(@candidate);
$max = max($max, $sum);
}
say $max;
sub max-sum-min-pair (@array is copy)
{
my $sum = 0;
my $echo = $verbose ?? ":Candidate: { @array.join(",") } Pairs:" !! "";
while @array.elems
{
my $first = @array.shift;
my $second = @array.shift;
my $minimum = min($first, $second);
$echo ~= "[$first,$second -> $minimum]" if $verbose;
$sum += $minimum;
}
say "$echo -> Sum: $sum" if $verbose;
return $sum;
}
[1] Using a state variable (declared inside of the loop block) ensures that it is not visible to the outside. The assignment is only done once.
See
docs.raku.org/syntax/state for
more information about the variable declarator state.
[2] Count the number of iterations.
[3] Skip every second iteration (with an even value for $index).
Running it (with verbose mode):
$ ./array-pairings-half -v 1 2 3 4
: Permutations: 1 2 3 4|1 2 4 3|1 3 2 4|1 3 4 2|1 4 2 3|1 4 3 2|2 1 3 4|\
2 1 4 3|2 3 1 4|2 3 4 1|2 4 1 3|2 4 3 1|3 1 2 4|3 1 4 2|\
3 2 1 4|3 2 4 1|3 4 1 2|3 4 2 1|4 1 2 3|4 1 3 2|4 2 1 3|\
4 2 3 1|4 3 1 2|4 3 2 1
:Candidate: 1,2,3,4 Pairs:[1,2 -> 1][3,4 -> 3] -> Sum: 4
:Candidate: 1,3,2,4 Pairs:[1,3 -> 1][2,4 -> 2] -> Sum: 3
:Candidate: 1,4,2,3 Pairs:[1,4 -> 1][2,3 -> 2] -> Sum: 3
:Candidate: 2,1,3,4 Pairs:[2,1 -> 1][3,4 -> 3] -> Sum: 4
:Candidate: 2,3,1,4 Pairs:[2,3 -> 2][1,4 -> 1] -> Sum: 3
:Candidate: 2,4,1,3 Pairs:[2,4 -> 2][1,3 -> 1] -> Sum: 3
:Candidate: 3,1,2,4 Pairs:[3,1 -> 1][2,4 -> 2] -> Sum: 3
:Candidate: 3,2,1,4 Pairs:[3,2 -> 2][1,4 -> 1] -> Sum: 3
:Candidate: 3,4,1,2 Pairs:[3,4 -> 3][1,2 -> 1] -> Sum: 4
:Candidate: 4,1,2,3 Pairs:[4,1 -> 1][2,3 -> 2] -> Sum: 3
:Candidate: 4,2,1,3 Pairs:[4,2 -> 2][1,3 -> 1] -> Sum: 3
:Candidate: 4,3,1,2 Pairs:[4,3 -> 3][1,2 -> 1] -> Sum: 4
4
$ ./array-pairings-half -v 0 2 1 3
: Permutations: 0 2 1 3|0 2 3 1|0 1 2 3|0 1 3 2|0 3 2 1|0 3 1 2|2 0 1 3|\
2 0 3 1|2 1 0 3|2 1 3 0|2 3 0 1|2 3 1 0|1 0 2 3|1 0 3 2|\
1 2 0 3|1 2 3 0|1 3 0 2|1 3 2 0|3 0 2 1|3 0 1 2|3 2 0 1|\
3 2 1 0|3 1 0 2|3 1 2 0
:Candidate: 0,2,1,3 Pairs:[0,2 -> 0][1,3 -> 1] -> Sum: 1
:Candidate: 0,1,2,3 Pairs:[0,1 -> 0][2,3 -> 2] -> Sum: 2
:Candidate: 0,3,2,1 Pairs:[0,3 -> 0][2,1 -> 1] -> Sum: 1
:Candidate: 2,0,1,3 Pairs:[2,0 -> 0][1,3 -> 1] -> Sum: 1
:Candidate: 2,1,0,3 Pairs:[2,1 -> 1][0,3 -> 0] -> Sum: 1
:Candidate: 2,3,0,1 Pairs:[2,3 -> 2][0,1 -> 0] -> Sum: 2
:Candidate: 1,0,2,3 Pairs:[1,0 -> 0][2,3 -> 2] -> Sum: 2
:Candidate: 1,2,0,3 Pairs:[1,2 -> 1][0,3 -> 0] -> Sum: 1
:Candidate: 1,3,0,2 Pairs:[1,3 -> 1][0,2 -> 0] -> Sum: 1
:Candidate: 3,0,2,1 Pairs:[3,0 -> 0][2,1 -> 1] -> Sum: 1
:Candidate: 3,2,0,1 Pairs:[3,2 -> 2][0,1 -> 0] -> Sum: 2
:Candidate: 3,1,0,2 Pairs:[3,1 -> 1][0,2 -> 0] -> Sum: 1
2
Looking good.
And that's it.