Fun Sum Time
with Raku and Perl

by Arne Sommer

Fun Sum Time with Raku and Perl

[116] Published 20. February 2021.

This is my response to the Perl Weekly Challenge #100.

Challenge #100.1: Fun Time

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

The program should support AM values as well, even if they are missing from the examples.

The conversion can be summarised like this:

24 Hour12 Hour
00:xx12:xx am
01:xx01:xx am
11:xx11:xx am
12:xx12:xx pm
13:xx01:xx pm
23:xx11:xx pm
24:0012: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

A Perl Version

This is a straight forward translation of the Raku version.

File: fun-time-perl
#! /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

Challenge #100.2: Triangle Sum

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] 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.

Perl

This is a straight forward translation of the first Raku version.

File: triangle-sum-perl
#! /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.