This is my response to the Perl Weekly Challenge #100.
Input: 05:15 pm or 05:15pm
Output: 17:15
Input: 19:15
Output: 07:15 pm or 07:15pm
The program should support AM values as well, even if they are missing from the examples.
The conversion can be summarised like this:
| 24 Hour | 12 Hour |
|---|---|
| 00:xx | 12:xx am |
| 01:xx | 01:xx am |
| 11:xx | 11:xx am |
| 12:xx | 12:xx pm |
| 13:xx | 01:xx pm |
| 23:xx | 11:xx pm |
| 24:00 | 12:00 am (next day) |
See e.g. en.wikipedia.org/wiki/24-hour_clock for more information about conversion between the 12 and 24 hour formats.
Here it is, as a one liner (if you remove the crash bang line, and the newlines):
File: fun-time
#! /usr/bin/env raku
@*ARGS[0] ~~ /^(\d\d)\:(\d\d) \s? ([<[ap]>m]?)$/ && $2.chars # [1]
## 1a ####### 1b ########### # 1c # 1d ######### # 1e ######
?? ($2 eq "pm" # [2]
?? say "{ $0 eq '12' ?? '12' !! $0 + 12 }:{ $1 }" # [2a]
!! say "{ $0 eq '12' ?? '00' !! $0 }:{ $1 }" # [2b]
)
!! (12 <= $0 < 24 # [3]
?? say "{ $0 eq '12' ?? '12' !! ($0 - 12).fmt('%02d') }:{ $1 } pm" # [3a]
!! say "{ $0 eq '00'|'24' ?? '12' !! $0 }:{ $1 } am" # [3b]
);
[1] Start with the first argument on the command line [1a], and compare it with this
regex, matching the entire string (^…$). First we have two
digits (the hour, ends up in $0), a colon and two additional digits
(the minutes, ends up in $1) [1b]. (This assumes, as the examples do,
that we cannot specify a one digit hour value without a leading zero.) This can
optionally be followed by a single space [1c], and this again by an optional "am" or
"pm" [1d]. The "am" or "pm" match end up in $2, if found, and we check
if we got a match like this [1e].
[2] We got an am/pm value. If «am», print the hour if it is 12, if not add 12 to it [2a]. If not (it is «pm»), print 12 if the hour is 00, if not print the hour itself.
[3] We have a 24 hour value if we get here. If the hour is in the
interval 12 to 23 [3a], print the hour if it is 12 - or subtracted with 12 if not
(i.e. it is in the interval 13 to 23). Note the fmt call to ensure two
digits (i.e. a leading zero). If it is not in this interval (i.e. less than 12) [3b],
print 12 if the hour is 00 or 24 - and the hour value otherwise.
See
docs.raku.org/routine/fmt
for more information about fmt.
Running it:
$ ./fun-time "00:00" ## -> 12:00 am
$ ./fun-time "01:00" ## -> 01:00 am
$ ./fun-time "11:00" ## -> 11:00 am
$ ./fun-time "12:00" ## -> 12:00 pm
$ ./fun-time "13:00" ## -> 01:00 pm
$ ./fun-time "23:00" ## -> 11:00 pm
$ ./fun-time "24:00" ## -> 12:00 am
$ ./fun-time "12:00 am" ## -> 00:00
$ ./fun-time "01:00 am" ## -> 01:00
$ ./fun-time "11:00 am" ## -> 11:00
$ ./fun-time "12:00 pm" ## -> 12:00
$ ./fun-time "01:00 pm" ## -> 13:00
$ ./fun-time "11:00 pm" ## -> 23:00
Error checking is missing. Garbage in, garbage out:
$ ./fun-time "99:99 pm" ## -> 111:99
#! /usr/bin/env perl
use strict;
use warnings;
$ARGV[0] =~ /^(\d\d)\:(\d\d)\s?(am|pm)?$/ && length($3)
? ($3 eq "pm"
? print $1 eq '12' ? '12' : $1 + 12, ":$2\n"
: print $1 eq '12' ? '00' : $1, ":$2\n"
)
: ($1 >= 12 && $1 < 24
? print $1 eq '12' ? '12' : sprintf('%02d', $1 - 12), ":$2 pm\n"
: print $1 eq '00'|| $1 eq '24' ? '12' : $1, ":$2 am\n"
);
Running it gives the same result as the Raku version:
$ ./fun-time-perl "00:00" ## -> 12:00 am
$ ./fun-time-perl "01:00" ## -> 01:00 am
$ ./fun-time-perl "11:00" ## -> 11:00 am
$ ./fun-time-perl "12:00" ## -> 12:00 pm
$ ./fun-time-perl "13:00" ## -> 01:00 pm
$ ./fun-time-perl "23:00" ## -> 11:00 pm
$ ./fun-time-perl "24:00" ## -> 12:00 am
$ ./fun-time-perl "12:00 am" ## -> 00:00
$ ./fun-time-perl "01:00 am" ## -> 01:00
$ ./fun-time-perl "11:00 am" ## -> 11:00
$ ./fun-time-perl "12:00 pm" ## -> 12:00
$ ./fun-time-perl "01:00 pm" ## -> 13:00
$ ./fun-time-perl "11:00 pm" ## -> 23:00
Error checking is missing here as well:
$ ./fun-time-perl "99:99 pm" ## -> 111:99
i on the current row then you may move to either
index i or index i + 1 on the next row.
Input: Triangle = [ [1], [2,4], [6,4,9], [5,1,7,2] ]
Output: 8
Explanation: The given triangle
1
2 4
6 4 9
5 1 7 2
The minimum path sum from top to bottom: 1 + 2 + 4 + 1 = 8
[1]
[2] 4
6 [4] 9
5 [1] 7 2
Input: Triangle = [ [3], [3,1], [5,2,3], [4,3,1,3] ]
Output: 7
Explanation: The given triangle
3
3 1
5 2 3
4 3 1 3
The minimum path sum from top to bottom: 3 + 1 + 2 + 1 = 7
[3]
3 [1]
5 [2] 3
4 3 [1] 3
We have traversed triangles several times before. The following solution is inspired by my «sum-path» program from Pointy Path with Raku. (Scroll down to «Challenge #093.2: Sum Path»).
Note that the challenge only asks for the result, not the actual path. So we can get away with this simple program:
File: triangle-sum
#! /usr/bin/env raku
unit sub MAIN (Str $tree = "1 | 2 4 | 6 4 9 | 5 1 7 2"); # [1]
my @tree = $tree.split("|")>>.words; # [2]
my @solutions; # [3]
traverse(0, 0, 0); # [4]
sub traverse($row, $col, $sum is copy) # [4a]
{
$sum += @tree[$row][$col]; # [5]
if @tree[$row+1] # [6]
{
traverse($row+1, $col, $sum); # [7]
traverse($row+1, $col+1, $sum); # [7a]
}
else # [8]
{
@solutions.push: $sum; # [8a]
}
}
say @solutions.min; # [9]
[1] The default triangle. Note the | to separate the rows.
[2]
Split the string into a two dimentional array. The split
takes care of the first part (the rows), and .>>words splits the
rows into separate values. The .>> part tells Raku to apply the
function (on the right) on each item in the list (to the left).
[3] We are storing the solutions (the sum of each possible path) here.
[4] Start at row 0, column 0 and with the accumulated sum (not including the current position) 0. Off we go, recursively
[5] Add the value of the current position to the sum.
[6] Do we have another row (below the current one)?
[7] • follow the left [7] and right [7a] children.
[8] No children? Then we are done, and can add the sum to the list of solutions.
[9] Get the lowest value (in the list) with min,
and print it.
See
docs.raku.org/routine/split
for more information about split.
See
docs.raku.org/routine/words
for more information about words.
See
docs.raku.org/routine/min
for more information about min.
Running it:
$ ./triangle-sum "1 | 2 4 | 6 4 9 | 5 1 7 2"
8
$ ./triangle-sum "3 | 3 1 | 5 2 3 | 4 3 1 3"
7
We certainly got the correct result, but it would have been nice to see why.
That requires quite a lot of extra code:
File: triangle-sum-verbose
#! /usr/bin/env raku
unit sub MAIN (Str $tree = "1 | 2 4 | 6 4 9 | 5 1 7 2",
:v(:$verbose),
:c(:$colour),
:h(:$html-colour));
class TrianglePath # [1]
{
has Int $.sum; # [1a]
has @.path; # [1b]
}
constant ansi-blue = "\e[44m"; # [7]
constant ansi-green = "\e[42m";
constant ansi-red = "\e[101m";
constant ansi-stop = "\e[0m";
constant html-blue = '<span class="text-light bg-primary">';
constant html-green = '<span class="text-light bg-success">';
constant html-red = '<span class="text-light bg-danger">';
constant html-stop = '</span>';
my @tree = $tree.split("|")>>.words;
my $width = $tree.split("|")>>.words>>.chars>>.max.max; # [2]
my $height = @tree.elems; # [2a]
my @solutions;
traverse(0, 0, 0, ()); # [3]
sub traverse($row, $col, $sum is copy, @path is copy) # [3a]
{
@path.push: $col;
$sum += @tree[$row][$col];
if @tree[$row+1]
{
traverse($row+1, $col, $sum, @path);
traverse($row+1, $col+1, $sum, @path);
}
else
{
say ": Sum: $sum. Path (as indices on the rows): { @path.raku }"
if $verbose;
@solutions.push: TrianglePath.new(sum => $sum, path => @path); # [4]
}
}
my $first = @solutions.sort({$^a.sum <=> $^b.sum }).first; # [5]
if $colour | $html-colour
{
my $start = $html-colour ?? html-green !! ansi-green;
my $stop = $html-colour ?? html-stop !! ansi-stop;
for ^@tree.elems -> $row # [6]
{
say ": "
~ (" " x $width * ($height - $row -1)) ~ (^@tree[$row].elems)
.map({ $_ eq $first.path[$row]
?? $start ~ @tree[$row][$_].fmt("%{$width}d") ~ $stop
!! (@tree[$row][$_].fmt("%{$width}d")) }
).join(" " x $width);
}
}
say $first.sum;
[1] We are going to print out the best triangle, so we need a way of keeping track as we try them all. THis class does that, with the sum [1a] and path (as indices on each row, from top to bottom) [1b].
[2] We need these when we print the triangle. The width is the maximum number of characters used on the values [2], and the height is the number of rows [2a].
[3] We pass along the path as well, this time. Note the is copy, so that
we end up with a copy that we can add to locally (so that the left and right recursion
do not interfere with each other) [3a].
[4] Generate the object when we have reached the bottom row.
[5] We have a list of paths (TrianglePath objects). Sort it by the
sum field, and get the first one (with first. That is the one with the
lowest sum. (Note that we can have several paths with the same sum, but that does not
really matter.)
[6] Print the triangle, with the path highlighted. See if you can understand the code…
[7] I have included code for three colours here, even if we only use green.
Running it with verbose mode, to see the different paths and their values:
$ ./triangle-sum-verbose -v "1 | 2 4 | 6 4 9 | 5 1 7 2"
: Sum: 14. Path (as indices on the rows): [0, 0, 0, 0]
: Sum: 10. Path (as indices on the rows): [0, 0, 0, 1]
: Sum: 8. Path (as indices on the rows): [0, 0, 1, 1]
: Sum: 14. Path (as indices on the rows): [0, 0, 1, 2]
: Sum: 10. Path (as indices on the rows): [0, 1, 1, 1]
: Sum: 16. Path (as indices on the rows): [0, 1, 1, 2]
: Sum: 21. Path (as indices on the rows): [0, 1, 2, 2]
: Sum: 16. Path (as indices on the rows): [0, 1, 2, 3]
8
$ ./triangle-sum-verbose -v "3 | 3 1 | 5 2 3 | 4 3 1 3"
: Sum: 15. Path (as indices on the rows): [0, 0, 0, 0]
: Sum: 14. Path (as indices on the rows): [0, 0, 0, 1]
: Sum: 11. Path (as indices on the rows): [0, 0, 1, 1]
: Sum: 9. Path (as indices on the rows): [0, 0, 1, 2]
: Sum: 9. Path (as indices on the rows): [0, 1, 1, 1]
: Sum: 7. Path (as indices on the rows): [0, 1, 1, 2]
: Sum: 8. Path (as indices on the rows): [0, 1, 2, 2]
: Sum: 10. Path (as indices on the rows): [0, 1, 2, 3]
7
We can show the tree that gives us the lowest sum, with the path highlighted:
$ ./triangle-sum-verbose -c "1 | 2 4 | 6 4 9 | 5 1 7 2"
: 1
: 2 4
: 6 4 9
: 5 1 7 2
8
$ ./triangle-sum-verbose -c "3 | 3 1 | 5 2 3 | 4 3 1 3"
: 3
: 3 1
: 5 2 3
: 4 3 1 3
7
Use the «-h» command line option instead, if you want output suitable for inclusion in an html document (using Bootstrap colours).
Looking food.
#! /usr/bin/env perl
use strict;
use warnings;
use feature 'say';
use feature 'signatures';
use String::Util 'trim';
use List::Util 'min';
no warnings "experimental::signatures";
my $tree = shift(@ARGV) // "1 | 2 4 | 6 4 9 | 5 1 7 2";
my @tree;
for my $row (split('\|', $tree)) # [1]
{
my @row = split(/\s+/, trim($row)); # [1a]
push(@tree, \@row); # [1b]
}
my @solutions;
traverse(0, 0, 0);
sub traverse($row, $col, $sum)
{
$sum += $tree[$row][$col];
if ($tree[$row+1])
{
traverse($row+1, $col, $sum);
traverse($row+1, $col+1, $sum);
}
else
{
push(@solutions, $sum);
}
}
say min(@solutions);
[1] Generating a two dimentional array in Perl is harder than in Raku. We start by
splitting on the | to get the lines [1]. (Note that we have to quote
the bar character.) Then we get the values for each row [1a], and add those rows to
the array. Note the \ character telling Perl to use a pointer to the
variable. Skipping that would have given us a single one dimentional array.
Running it gives the same result as the Raku version:
$ ./triangle-sum-perl "1 | 2 4 | 6 4 9 | 5 1 7 2"
8
$ ./triangle-sum-perl "3 | 3 1 | 5 2 3 | 4 3 1 3"
7
And that's it.