Reverse Polish Guest Book, Raku Edition

by Arne Sommer

Reverse Polish Guest Book, Raku Edition

Published 22. December 2019

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

Challenge #39.1: Guest House

A guest house had a policy that the light remain ON as long as the at least one guest is in the house. There is guest book which tracks all guest in/out time. Write a script to find out how long in minutes the light were ON.

Guest Book
1) Alex    IN: 09:10 OUT: 09:45
2) Arnold  IN: 09:15 OUT: 09:33
3) Bob     IN: 09:22 OUT: 09:55
4) Charlie IN: 09:25 OUT: 10:05
5) Steve   IN: 09:33 OUT: 10:01
6) Roger   IN: 09:44 OUT: 10:12
7) David   IN: 09:57 OUT: 10:23
8) Neil    IN: 10:01 OUT: 10:19
9) Chris   IN: 10:10 OUT: 11:00

I'll start with the Guest Book itself, which I have placed in a separate file (so that I can have several versions of it):

File: guest-book.txt
1) Alex    IN: 09:10 OUT: 09:45
2) Arnold  IN: 09:15 OUT: 09:33
3) Bob     IN: 09:22 OUT: 09:55
4) Charlie IN: 09:25 OUT: 10:05
5) Steve   IN: 09:33 OUT: 10:01
6) Roger   IN: 09:44 OUT: 10:12
7) David   IN: 09:57 OUT: 10:23
8) Neil    IN: 10:01 OUT: 10:19
9) Chris   IN: 10:10 OUT: 11:00

Looking at this file gives some clues as to how to handle this:

  • This is a single day (so the hours don't exceed 24:00)
  • There are no periods without guests (i.e. the light is on for the whole duration)
  • All entries are in cronological order (i.e. the guests add themselves to the book on entry).

Then the program

File: guest-book
use Time::Repeat::HHMM;             # [9]

unit sub MAIN (:$verbose,                                                # [1]
               :$guest-book where $guest-book.IO.r = "guest-book.txt");  # [2]

my $from;                           # [3]
my $to;                             # [3]

for $guest-book.IO.lines -> $line   # [4]
{
  die "Wrong file format" unless $line ~~                                # [5]
    /IN \: \s+ (\d\d) \: (\d\d) \s+ OUT \: \s+ (\d\d) \: (\d\d)/;
    ############ 5a ###### 5b ################## 5c ###### 5d ###

  my $current-from = "$0$1";       # [6]
  my $current-to   = "$2$3";       # [6]

  say "- Line (from: $current-from to: $current-to)" if $verbose;        # [1]

  if ! $from.defined               # [7]
  {
    $from = $current-from;         # [7a]
    $to   = $current-to;           # [7b]
  } 
  else
  {
    $to = $current-to if $current-to > $to;       # [8]
  }
}

say "From: $from to: $to" if $verbose;            # [1]

my $from-o = Time::Repeat::HHMM.new($from);       # [9]
my $to-o   = Time::Repeat::HHMM.new($to);         # [9]

my $diff = $to-o.Real - $from-o.Real;             # [10]

say "The light were ON for $diff minutes.";       # [11]

[1] I have added support for a verbose mode, to help during development (and also to help a user seeing what is going on).

[2] We can specify another guest book if we want. I'll get back to that later.

[3] We have a single continous timespan, and we keep the start and end in these variables.

[4] Read the guest book, line for line.

[5] Abort if the line doesn't match the regex, as we reghard that as an unrecoverable error. (The regex picks out the four double digit parts: in hour (5a), in minutes (5b), out hours (5c) and out minutes (5d). I have done it this way as the colons have to go.)

[6] Set the current from and to values.

[7] This kicks in the first time (as $from is undefined), sets the start (7a) and end values (7b) to the current values.

[8] After the first line, increase the $to value if the new value is higher.

[9] Calculating the number of minutes between to points in time can be done with the «Time::Repeat::HHMM» class (which is part of the «Time::Repeat» module (github | modules.raku.org) version 0.0.1). We set up two objects, for the start and the end,

[10] and calculate the difference in minutes by subtracting the values. As the author of the module didn't think about this use case, we have to coerce the objects to the «Num» type with .Real for this to work. Bummer...

[11] Print the result.

Note that we do not change the $from value after initialising it, as the first entry on the guest book has the earliest «in» value.

If you disapprove of my critical tone towards the module author, don't worry. I have written the module myself, and can cope with self-criticism.

Running it:

$ raku guest-book
The light was ON for 110 minutes.

Without the Module

The program can manage quite well without my «Time::Repeat::HHMM» module, but it makes the code harder to read:

File: guest-book-pure (changes only)
say "From: $from to: $to" if $verbose;

my $diff = ( $to.substr(0,2)   * 60 +  $to.substr(2,2) )
         - ( $from.substr(0,2) * 60 +  $from.substr(2,2) );

say "The light was ON for $diff minutes.";

And remove the «use Time::Repeat::HHMM» line.

Disjunct Data

If all the guests were to leave, before somebody turns up again, the program will disregard any periods without guests and just assume that the light is on for the duration.

File: guest-book-disjunct.txt
1) Alex    IN: 09:10 OUT: 09:45
2) Arnold  IN: 09:15 OUT: 09:33
3) Bob     IN: 09:22 OUT: 09:55
4) Charlie IN: 09:25 OUT: 10:05
5) Steve   IN: 09:33 OUT: 10:01
6) Roger   IN: 09:44 OUT: 10:12
7) David   IN: 09:57 OUT: 10:23
8) Neil    IN: 10:01 OUT: 10:19
9) Chris   IN: 10:10 OUT: 11:00
10) Donald IN: 14:55 OUT: 15:00

Running it:

$ raku guest-book --guest-book=guest-book-disjunct.txt
The light was ON for 350 minutes.

That is certainly wrong. The challenge doesn't address this problem, but I'll have a go at it anyway.

Using existing code is a good way, but the «Time::Interval» module isn't quite up to the task. So I rewrote it...

The .Real calls are annoying, but we can get rid of them if we add a «Numeric» method:

File: Time/Repeat/HHMM.pm6 (changes only)
method Numeric
{
  return $.is-next-day * 24 * 60 + $.hour * 60 + $.minute;
}

This looks much nicer:

File: guest-book-disjunct (changes only)
my $diff = $to-o - $from-o;

Removing the «Real» method is not a good idea, as a numeric comparison (e.g. with >) depends on it. We don't need it now, but we will later on.

That was nice, but we still haven't addressed the problem of disjunct periods.

We can add to the module. A new «HHMM::Interval» class seems appropriate.

File: Time/Repeat/HHMM/Interval.pm6
use Time::Repeat::HHMM;

unit class Time::Repeat::HHMM::Interval:ver<0.0.2> is export;

our $VERSION = '0.02';

has HHMM $.start;
has HHMM $.stop;

multi method new(HHMM $start, HHMM $stop)
{
  return self.bless(start => $start, stop => $stop);
}

multi method new(Str $start, Str $stop)
{
  return self.bless(start => Time::Repeat::HHMM.new($start),
                    stop  => Time::Repeat::HHMM.new($stop) );
}

method Str
{
  return $.start ~ "-" ~ $.stop;
}

method Numeric
{
  return $.stop - $.start;
}

It doesn't do much yet. We can set up intervals, with the start and stop either specified as strings or «HHMM» objects. The «Str» method ensures that we can print the intervals (and also sort them). The «Numeric» method uses the »Numeric» method in the «HHMM» class to get the duration in minutes.

Now we can start rewriting the program:

File: guest-book-disjunct
use Time::Repeat::HHMM;
use Time::Repeat::HHMM::Interval;

unit sub MAIN (:$verbose,
               :$guest-book where $guest-book.IO.r = "guest-book.txt");

my @intervals;

for $guest-book.IO.lines -> $line
{
  die "Wrong file format" unless
     $line ~~ /IN \: \s+ (\d\d) \: (\d\d) \s+ OUT \: \s+ (\d\d) \: (\d\d)/;

  my $current-from = "$0$1";
  my $current-to   = "$2$3";

  say "- Line (from: $current-from to: $current-to)" if $verbose;

  @intervals.push(Time::Repeat::HHMM::Interval.new($current-from,
                                                   $current-to));
}

for @intervals -> $interval
{
  say $interval.Str;
}

The program doesn't do anything useful yet, besides printing the intervals (and showing that the new module does work).

But let us show off a little, with a modified guest book where the entries are shuffled around. The values are the same as before:

File: guest-book-disjunct2.txt
1) Alex    IN: 09:10 OUT: 09:45
8) Neil    IN: 10:01 OUT: 10:19
7) David   IN: 09:57 OUT: 10:23
3) Bob     IN: 09:22 OUT: 09:55
6) Roger   IN: 09:44 OUT: 10:12
4) Charlie IN: 09:25 OUT: 10:05
5) Steve   IN: 09:33 OUT: 10:01
9) Chris   IN: 10:10 OUT: 11:00
10) Donald IN: 14:55 OUT: 15:00
2) Arnold  IN: 09:15 OUT: 09:33

Running it:

$ raku guest-book-disjunct --guest-book=guest-book-disjunct2.txt
0910-0945
1001-1019
0957-1023
0922-0955
0944-1012
0925-1005
0933-1001
1010-1100
1455-1500
0915-0933

That was as expected. But we can get them ordered with a single method call:

File: guest-book-disjunct (changes only)
for @intervals.sort -> $interval

Running it with this change:

$ raku guest-book-disjunct --guest-book=guest-book-disjunct2.txt
0910-0945
0915-0933
0922-0955
0925-1005
0933-1001
0944-1012
0957-1023
1001-1019
1010-1100
1455-1500

So now we have a way of handling entries in wrong order. (Probably not very useful, but easy to do.)

Now the exciting part, merging intervals. That belongs to our module, as a function:

File: Time/Repeat/HHMM/Interval.pm6 (changes only)
our sub merge (Time::Repeat::HHMM::Interval @intervals is copy)  # [1]
{
  my Time::Repeat::HHMM::Interval @result;                       # [2]

  my $first = @intervals.shift;                                  # [3]
  my $start = $first.start;                                      # [3]
  my $stop  = $first.stop;                                       # [3]
  
  for @intervals.sort -> $interval
  {
    if $interval.start > $stop                                   # [4]
    {
      @result.push: Time::Repeat::HHMM::Interval.new($start, $stop);
      $start = $interval.start;
      $stop  = $interval.stop;
    }
    else                                                         # [5]
    {
      $stop = $interval.stop if $interval.stop > $stop;
    }
  }
  
  @result.push: Time::Repeat::HHMM::Interval.new($start, $stop); # [6]
  
  return @result;                                                # [2]
}

[1] It takes a list of Interval objects,

[2] and returns another list of Interval objects.

[3] This time I pick out the start values before the loop. (Compare it with «guest-book» where I did it in the loop.) Using «shift» on the input requires a writeable list, so we get that with «is copy» in [1].

[4] This comparison coerces the values with the «Real» method (in «HHMM»), so it has to say. If the new interval is disjunct with the current one, push the current to the result list and use the new interval as the current one.

[5] If not disjunct (they overlapp), use the highest stop value.

[6] We are left with an interval after the loop. Add that to the list.

Now we can rewrite the program. Replace the loop at the end with this:

File: guest-book-disjunct (changes only)
my Time::Repeat::HHMM::Interval @merged
     = Time::Repeat::HHMM::Interval::merge(@intervals);

for @merged -> $interval
{
  say "The light was ON for { +$interval } minutes (at { $interval.Str }).";
}

Running it:

$ raku guest-book-disjunct --guest-book=guest-book-disjunct2.txt
The light was ON for 110 minutes (at 0910-1100).
The light was ON for 5 minutes (at 1455-1500).

$ raku guest-book-disjunct --guest-book=guest-book-disjunct.txt
The light was ON for 110 minutes (at 0910-1100).
The light was ON for 5 minutes (at 1455-1500).

$ raku guest-book-disjunct --guest-book=guest-book.txt
The light was ON for 110 minutes (at 0910-1100).

The three guest book files are handled correctly.

Module Update

The updated version of the «Time::Repeat» module (version 0.0.2) is available on:

The «modules.raku.org» Indexer hasn't recognised the new version yet. I do not know why.

Challenge #39.2 - Reverse Polish Notation

Write a script to demonstrate Reverse Polish notation(RPN). Checkout the wiki page for more information about RPN.

The wiki page explains this as a push/pop task on a stack, so I'll do just that.

My first idea was to write it as a loop that reads input from the user, and acts on that. The wikipedia article has an example (where I have replaced the mathematical operator symbols with the normal ascii versions):

RPN> 15 7 1 1 + - / 3 * 2 1 1 + + - =
5

So the program should support both command line arguments, and interactive mode.

Note that specifying an unquoted * on the command line is not a good idea, as your shell will expand it to a list of all the files in the current directory. Quoting one or more of these values is not practical, so the input should be specified as a single string, like this:

$ raku rpn "15 7 1 1 + - / 3 * 2 1 1 + + - ="
5

The program:

File: rpn (partial)
my @stack;                               # [1]

multi sub MAIN (:$verbose)               # [2]
{
  loop                                   # [2a]
  {
    my $input = prompt "> ";             # [2b]

    parse($input, $verbose);             # [2c]
  }
}

multi sub MAIN (Str $args, :$verbose)    # [3]
{
  for $args.words -> $word               # [3a]
  {
    $word.Numeric                        # [4]
      ?? parse($word.Numeric, $verbose)  # [4a]
      !! parse($word, $verbose);         # [4b]
  }
}

[1] We store the values in this variable, treated as a stack.

[2] The first «multi sub MAIN» candidate (which could have been written as «multi MAIN» instead, saving a few characters) is used when we run the program without arguments (on the command line). It goes in an eternel loop [2a], prompting for input [2b], and acting on it [2c].

[3] The other «multi sub MAIN» candidate is used when we specify a singles string on the command line. It splits the string (with «words», using spaces as delimiters) [3a].

[4] All the words are strings, and we must coerce any numeric value to a number as the «parse» procedure relies on the type [4a]. If not numeric, pass it on as is [4b].

Note the «verbose» support. The value is passed on to each procedure call, ensuring encapsulation for everything except the stack («@stack»).

The «parse» procedure does the heavy lifting:

File: rpn (partial)
sub parse ($input, $verbose)
{
  if $input ~~ Numeric                        # [5]
  {
    stack-push($input, $verbose); 
  }
  elsif $input eq any( <* / + - ^> )          # [6]
  {
    my $result = calculate($input, $verbose); # [6a] 
    say ": - Result: $result" if $verbose;    # [6b]
    stack-push($result, $verbose);            # [6c]
  }
  elsif $input eq "="                         # [7]
  {
    @stack.elems                              # [7a]
      ?? say @stack.pop                       # [7a]
      !! say "Error. Not enough values on the stack";  # [7b]
  }
  elsif $input eq "s"                         # [8]
  {
    say @stack.join(", ");
  }
  elsif $input eq "h"                         # [9]
  {
    say 'Enter a number, an operator (* / + - ** div %), '
     ~  '= (show the value), s (show the stack)';
  }
  else                                        # [10]
  {
    say "Illegal input ($input). Use 'h' for help";
  }
}

[5] • If the input is numeric, push it on the stack.

[6] If the input is one of these operators, calculate the new value [6a] and push it on the stack [6c].

[7] • If the input is "=", pop a value from the stack and display it [7a] (or give a warning if the stack is empty [7b]).

[8] • If the input is "s", show the stack. This is primarily useful for debugging.

[9] • If the input is "h", show a short help message.

[10] • if something else, show a warning.

The rest of the åproghram:

File: rpn (partial)
sub stack-push ($value, $verbose)             # [11]
{
  @stack.push: $value;
  if $verbose
  {
    say ": Stack: { @stack.join(", ") }";
    say ": - Added: $value";
  }
}

sub calculate ($operator, $verbose)           # [12]
{
  if @stack.elems < 2                         # [13]
  {
    say "Error. Not enough values on the stack";
    return;
  }

  my $right = @stack.pop;                     # [14]
  my $left  = @stack.pop;                     # [14]
  
  if $verbose
  {
    say ": Operator: $operator";
    say ": - Stack: { @stack.join(", ") }";
    say ": - Values: $left $right";
  }
  
  return $left -  $right if $operator eq "-";  # [15]
  return $left +  $right if $operator eq "+";
  return $left /  $right if $operator eq "/";
  return $left *  $right if $operator eq "*";
  return $left ** $right if $operator eq "^";

  die "Unknown operator";                      # [16]
}

[11] This is a separate procedure because of the verbose output.

[12] This procedure does the calculations.

[13] We must have at least two values on the stack. If not, display a warning and do nothing.

[14] Get two values from the stack.

[15] Apply the operator on the values, and return the result.

[16] Die in case of error. Note that this cannot happen with this program, as the test in [6] ensures a legal operator.

Runing it in interactive mode:

./rpn 
> 12
> 8
> +
> s
20
> 11
> *
> =
220
> ^C

With verbose mode:

$ raku rpn --verbose
> 12
: - Add to stack: 12
: Stack: 12
> 8
: - Add to stack: 8
: Stack: 12, 8
> +
: Operator: +
: - Stack: 
: - Values: 12 8
: - Result: 20
: - Add to stack: 20
: Stack: 20
> 11
: - Add to stack: 11
: Stack: 20, 11
> *
: Operator: *
: - Stack: 
: - Values: 20 11
: - Result: 220
: - Add to stack: 220
: Stack: 220
> =
220
> ^C

The example shown initially does work:

$ raku rpn "15 7 1 1 + - / 3 * 2 1 1 + + - ="
5

And with verbose mode:

$ raku rpn --verbose "15 7 1 1 + - / 3 * 2 1 1 + + - ="
: - Add to stack: 15
: Stack: 15
: - Add to stack: 7
: Stack: 15, 7
: - Add to stack: 1
: Stack: 15, 7, 1
: - Add to stack: 1
: Stack: 15, 7, 1, 1
: Operator: +
: - Stack: 15, 7
: - Values: 1 1
: - Result: 2
: - Add to stack: 2
: Stack: 15, 7, 2
: Operator: -
: - Stack: 15
: - Values: 7 2
: - Result: 5
: - Add to stack: 5
: Stack: 15, 5
: Operator: /
: - Stack: 
: - Values: 15 5
: - Result: 3
: - Add to stack: 3
: Stack: 3
: - Add to stack: 3
: Stack: 3, 3
: Operator: *
: - Stack: 
: - Values: 3 3
: - Result: 9
: - Add to stack: 9
: Stack: 9
: - Add to stack: 2
: Stack: 9, 2
: - Add to stack: 1
: Stack: 9, 2, 1
: - Add to stack: 1
: Stack: 9, 2, 1, 1
: Operator: +
: - Stack: 9, 2
: - Values: 1 1
: - Result: 2
: - Add to stack: 2
: Stack: 9, 2, 2
: Operator: +
: - Stack: 9
: - Values: 2 2
: - Result: 4
: - Add to stack: 4
: Stack: 9, 4
: Operator: -
: - Stack: 
: - Values: 9 4
: - Result: 5
: - Add to stack: 5
: Stack: 5
5

And that's it.

Except for a Happy Christmas wish.

And pointing out that the banner image is from Wroclaw in Poland.

But that absolutely is it.