Wherein we ride our chariots of the gods up into the heavens, navigating with the power of time to guide us on our voyage…
THE WEEKLY CHALLENGE – PERL & RAKU #100
episode one:
“The Doctor Will See You Now”
Task 1
TASK #1 › Fun Time
Submitted by: Mohammad S Anwar
You are given a time (12 hour / 24 hour).
Write a script to convert the given time from 12 hour format to 24 hour format and vice versa.
Ideally we expect a one-liner.
Example 1:
Input: 05:15 pm or 05:15pm
Output: 17:15
Example 2:
Input: 19:15
Output: 07:15 pm or 07:15pm
Method
So, we are being asked to write a single script, that, when given a time formatted in 12-hour intervals, will return the time as 24-hour, and given 24, translate the time into 12.
Ok.
Oh, and make it a command line one-liner. That makes sense. This certainly sounds like a useful little widget to have around. In reality, it probably isn’t very useful at all, but it certainly sounds like it should be.
In any case let’s figure it out.
Whatever is delivered on the command line will be a string representation of the time in one format or another, so it makes sense to write a regular expression to piece it apart into sections — hours, minutes and whatever else. Once we’ve done that, we can figure out what to do with them.
What we have is two translation processes that get called either way depending on what needs to happen. Thus the very first question to arise is to figure out which to perform. If we parse the input left to right into hours, minutes, and the cycle indicator am/pm, then should we find anything in the last position we’ve been given a 12-hour representation, and we can assume 24-hours if not. It doesn’t make any sense to give us 5:15 and expect us to figure out you want it in the evening, at 17:15, without giving a clue. By requiring am or pm we can avoid guessing and getting it wrong. As they say: “There’s a limit.”
So two algorithms, one to convert up to 24-hour time and one to convert down. They’ll be related, but won’t be exactly reversed. Converting up to 24-hour time is the easier one, but even it has some oddities.
Let’s break it down. We start with hours, minutes and an indicator, am or pm, of which cycle half we’re in. For both of these schemes the minutes always remain unchanged, so we’re going to ignore them. They aren’t even numbers to us. This sounds a bit harsh, but it’s true, and we can even leave the delimiter attached to whatever digits are found so we don’t have to reattach it later. It”s just a string of characters that follow our hours — nothing more, nothing less. Don’t cry for them; they know what they’ve done.
Where were we? Oh, right, converting up from 12-hour time. Well let’s see, if the indicator says “pm” then we add 12 hours, right? Well yes, but the problem is that in 24-hour time midnight, 12am is 00:00 and noon, 12pm is 12:00. What to do? Well our method of adding 12 works fine if we count hours from 0 to 11. We’re still counting in 12s, and the in-between hours stay the same, but we make 12 o’clock cycle around to 0 again.
What we’re describing is modulo math, where we divide by 12 and keep the remainder. If the number divided is less that the modulus, it remains unchanged. If it’s more, it gets divided down until it becomes less. And if it’s equal, the remainder becomes 0. Nice. This is indeed exactly what we want.
This simple algorithm will get us to 24-hour time, but one small detail remains. That is, in another effort to avoid ambiguity and potential confusion, all hours, no matter what they are, are declared with two digits. Thus 5am becomes 05:00: “Oh five-hundred”. As our converted hours are a number, and numbers don’t normally come with leading zeros, that won’t always be the case. We’ll have to explicitly stringify the value and add the leading 0 if that’s what’s required.
For the back-conversion, things are a little more complex. We’ll want to subtract 12 if our hours lie in the afternoon, but we never talk about “zero o’clock” — either am or pm — so we only want to subtract if our total is *greater* that 12. Modulo 12 gives us the numbers 0 through 11, but what we want is the numbers 1 through 12. On the other hand the modulo operation does give up the proper 12 number range.
There’s two ways to go about this: we can either mod 12 and add 12 again if the result is 0, or subtract 1, mod 12 and then add the 1 again. Six of one half-dozen of the other, really — it even works out to the same number of characters to write it. One thing though: before we start we need to assign our cycle indicator to “pm” for any time after 12:00. Once we have that we can mess with our hours however we wish.
In the interests of clarity, we’re going to adopt a GIGO attitude and forgo any input validation. We’ll assume what we get will be a string formatted hh:mm followed by maybe a space, and then maybe am or pm. The widget will take it from there. I’m not going to concern myself with failing gracefully.
PERL 5 SOLUTION
So now we have our logic figured, how do we do it? The best way would be to code it is to start with a subroutine version, to get the code down, before we refine it. We’ll begin with a regular expression on our input that looks for three parts: the hours, the minutes and a cycle indicator that may or may not be present. If it is, we’ll go one way, if it isn’t, the other.
Let’s implement the logic we have so far:
sub timef {
local $_= shift;
/^ (\d+)(:\d+)\s?(am|pm)* $/x; ## (hrs) (min) (am/pm)
my $hr = $1; ## first capture is hours
my $cyc = 'am'; ## defaults to 'am'
if ( $3 ) { ## finding am/pm means 12hr->24hr
$hr = sprintf "%02d", $1 % 12; ## mod 12 hours, add leading 0
$hr += 12 if $3 eq 'pm'; ## add 12 if after noon
return "$hr$2"; ## hh:mm
}
else { ## 24hr->12hr
$cyc = 'pm' if $hr > 11; ## set to 'pm' if after noon
$hr %= 12; ## now range 0-11
$hr ||= 12; ## if hrs == 0,
## OR fails and we add 12.
## now range is 1-12
return "$hr$2$cyc"; ## hh:mm am/pm
}
}
This works swimmingly. But remember we’ve been asked to produce a one-liner. To do this we’ll have to jigger the I/O to accept @ARGV[0] and print our output instead of returning. While we’re in there we’ll also strip out any whitespace and aggressively refactor everything in sight until we have it as lean as we can possibly make it. But before we complete our obfuscation, let’s have one final look after refactoring:
sub timefl {
no strict 'vars';
local $_ = shift;
/^(\d+)(:\d+)\s?(am|pm)*$/;
$c=$1>11?'pm':'am'; ## assign cycle no matter what
$h=$1%12; ## always mod 12 either way
if($3){
$h+=12if$3eq"pm";
sprintf"%02d%s",$h,$2; ## move sprintf to output
## remove explicit return
}
else{
$h||=12;
"$h$2$c"; ## remove explicit return
}
}
Yup. It’s shorter alright, albeit less clear, surely.
Ahh, line noise. Now we’re cooking with steam! To get it into a one-liner we will need to do the aforementioned input jiggering, and instead of returning we will change the sprintf to a simple printf, and say() the second option. Once we have that done, it looks like this:
perl -E '@ARGV[0]=~/^(\d+)(:\d+)\s?(am|pm)*$/i;$c=$1>11?'pm':'am';$h=$1%12;if($3){$3eq"pm"and$h+=12;printf"%02d%s\n",$h,$2;}else{$h||=12;say"$h$2$c"}' 5:15pmYes that’s all one line, soft-wrapped, coming in at 148 characters. Does the job, though. Wrapping it up in a shell function with a nice, short name would be bit less unwieldy.
function 24time() {
perl -E '@ARGV[0]=~/^(\d+)(:\d+)\s?(am|pm)*$/i;$c=$1>11?'pm':'am';$h=$1%12;if($3){$3eq"pm"and$h+=12;printf"%02d%s\n",$h,$2;}else{$h||=12;say"$h$2$c"}' $1
}
Now we can simply call
[colincrain@boris:~/PWC]$ 24time 5:15pm
17:15That’s the ticket!
raku solution
The Raku parser has a lot more trouble with removing certain whitespace. Oh well. We were able to use the smartwatch operator to shorten the construct $2 eq "pm" into $2~~"pm" which is pretty neat.
[colincrain@MacBook-Pro:~/Code/PWC]$ raku -e '$_=@*ARGS[0];m/^(\d+)(":"\d+)\s?(am|pm)*$/;my$c=$0>11??"pm"!!"am";my$h=$0%12;if $2 {$2~~"pm"and$h+=12;"%02d%s\n".printf($h,$1)}else{$h||=12;"$h$1$c".say}' 17:15
5:15pm
And the expanded version:
unit sub MAIN () ;
use Test;
plan 8;
is timef("5:15am"), "05:15", '12->24am';
is timef("5:15pm"), "17:15", '12->24pm';
is timef("12:15am"), "00:15", '12->24am-mid';
is timef("12:15pm"), "12:15", '12->24pm-noon';
is timef("5:15"), "5:15am", '24->12am';
is timef("17:15"), "5:15pm", '12->24am';
is timef("12:00"), "12:00pm", '24->12-noon';
is timef("00:00"), "12:00am", '24->12-mid';
sub timef ($_) {
m:i/^ (\d+) (":"\d+) \s? (am|pm)* $/;
my $c = $0 > 11 ?? 'pm'
!! 'am';
my $h = $0 % 12;
if ($2) {
$h += 12 if $2 eq "pm";
"%02d%s".sprintf($h,$1);
}
else{
$h ||= 12;
"$h$1$c";
}
}
episode two:
“Däniken? I Hardly Knew Him!”
task 2
Triangle Sum
Submitted by: Mohammad S Anwar
You are given triangle array.
Write a script to find the minimum path sum from top to bottom.
When you are on index i on the current row then you may move to either index i or index i + 1 on the next row.
Example 1:
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
Example 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] 3Method
“Given a triangular array” aren’t words you hear everyday. It’s actually not that weird a concept — Pascal’s triangle is a rather famous example. In any case considered as a data structure, as we have here, it resembles a binary tree that sort of folds back into itself. Or a lattice made of triangles with an enforced direction aspect. Or a pachinko, or bean machine.
As such, it’s a form of directed acyclic graph. Each node is has a total of six neighbors, but only four are connected — lateral movement on the same level is not allowed. Movement itself in only allowed to progress away from the root vertex, so considered this way there are only two edges available to move forward from each vertex, and either zero, one or two paths leading into it, depending on location within the triangle.
Traversing each possible path through the graph is reasonably straightforward, as all paths are the same length. We need only start at the root and add each of the two options, proceeding downward and bifurcating each path at every level. In the end there will be 2level-1 paths created.
We can keep track of the sums as we go and avoid recomputing any sums, which is nice. We will also keep a list of every value added to the chain so we can make the output a little more interesting.
PERL 5 SOLUTION
Two techniques immediately present themselves for the task — to either build a recursive routine to handle each node branching event, or to loop through the levels, adding complexity to partial solutions at each step. I feel as though I’ve been making a lot of recursive solutions lately so this time I’ll choose the latter.
In this method, we have essentially two lists: one with partial solutions so far, the other to receive newly modified versions of these paths. For each partial path so far constructed on the first list, two new versions are created and added to the second, one for each option available to descend the triangle.
Further, because we always know how many paths exist at any given level into the traversal, these two lists can be in fact the same queue. We can shift paths off one end and push new paths onto the other, iterating through exactly as many paths as we need to at each tier. Each path itself will be an array composed of three parts: the running sum total, a second internal array with the values of vertices visited, and then the index last visited within the current row.
The two options for the path to continue are always on the next row at the positions of the last index and the last plus one. As we’re calculating the next row in every depth, if we stop at the last level minus one we’ll compute the last level and not overrun.
~/Code/PWC/pyramid-power.pl
--------------------------------------------------------------------------
minimum path sum: 8
path:
1 -> 2 -> 4 -> 1
ok 1 - ex-1
minimum path sum: 7
path:
3 -> 1 -> 2 -> 1
ok 2 - ex-2
1..2
The code itself is direct. For each level of the triangle from 0 to the next-to-last, shift off each partial path created in the previous step (there will be 2depth of these). Then two new paths are created by visiting the next row at the current index and the one following. Each of these in turn are updated by adding the value found to the sum, appending the value to the internal list for that path, and changing the next-line index for that path to the index visited. The newly-extended paths are pushed on the the end of the data array and the process continues. When done we can sort the @data array on the summed values in the first element, selecting the lowest sorted path array. This will contain both the sum and those values visited to arrive there.
use warnings;
use strict;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';
sub findpath ($arr) {
## the data structure: [ sum, [arr of values along path], last index ]
my $root = $arr->[0][0];
my @data = [$root, [$root], 0];
for my $depth ( 0..$#$arr-1 ) { ## last - 1, 0-based
for my $pos ( 0..2**$depth-1 ) { ## 2^depth paths when 0-based
my $path = shift @data;
for (0,1) { ## new path each L,R
my ($sum, $trace, $last) = @$path;
my $value = $arr->[$depth+1][$last+$_];
my $newpath = [ $sum + $value,
[$trace->@*, $value],
$last + $_ ];
push @data, $newpath;
}
}
}
my $minpath = (sort {$a->[0] <=> $b->[0]} @data)[0];
say "minimum path sum: ", $minpath->[0];
say "path:";
say join ' -> ', $minpath->[1]->@*;
return $minpath->[0];
}
use Test::More;
is findpath( [[1], [2,4], [6,4,9], [5,1,7,2]] ), 8, 'ex-1';
is findpath( [[3], [3,1], [5,2,3], [4,3,1,3]] ), 7, 'ex-2';Raku Solution
The Raku solution closely follows the Perl. Keeping track of the complex nested arrays is simplified by using $ variables for the internal lists, which avoids some unwanted containerizing. Note the slip in the @newpath assignment. Also we can attach a &by function to the min to tell us what we want the minimum of for our result, which makes that whole step much simpler and clear.
unit sub MAIN () ;
use Test;
plan 3;
is findpath( [[1], [2,3], [4,5,6], [7,8,9,10]] ), 14, "BFO triangle test";
is findpath( [[1], [2,4], [6,4,9], [5,1,7,2]] ) , 8, "ex-1";
is findpath( [[3], [3,1], [5,2,3], [4,3,1,3]] ) , 7, 'ex-2';
sub findpath (@arr) {
## the data structure: [ sum, [arr of values along path], last index ]
my $root = @arr[0][0];
my @root = [$root, [$root], 0];
my @data.push: @root;
for 0..@arr.elems-2 -> $depth {
for 0..2**$depth-1 -> $pos {
my $path = @data.shift;
for 0,1 {
my ($sum, $trace, $last) = $path;
my $value = @arr[$depth+1][$last+$_];
my @newpath = $sum + $value,
[|$trace, $value],
$last + $_ ;
push @data, @newpath;
}
}
}
## a little verbose output
my $minpath = @data.min( { $^a[0] } );
say '';
say "minimum path sum: ", $minpath[0];
say "path:";
say $minpath[1].join: ' -> ';
## the requested value
return $minpath[0];
}
The Perl Weekly Challenge, that idyllic glade wherein we stumble upon the holes for these sweet descents, is now known as
The Weekly Challenge – Perl and Raku
It is the creation of the lovely Mohammad Sajid Anwar and a veritable swarm of contributors from all over the world, who gather, as might be expected, weekly online to solve puzzles. Everyone is encouraged to visit, learn and contribute at
Programming Excursions in Perl and Raku 