E. Choroba

Guest Book

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.

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

If we visualise the input, we’ll see that it represents the easy case: the first guest turns the light on, and it stays on until the last guest leaves. But in the general case, the guest house might be empty several times a day, causing the lights being turned off and back on repeatedly.

Fortunately, CPAN has a tool to handle even the general case. It uses so called Inversion Lists: instead of storing each minute, we just store the times when the light changes its state. I first learned about the concept in the PerlMonks article RFC: The Lazy Manager’s Calendar with Inversion Lists.

As speed isn’t the main concern here, we’ll use the module Set::IntSpan. Although the article shows that many operations on the intervals are easy to implement, the module saves us even from this work. We just need to convert each time from hours and minutes to just minutes, then we’ll merge each “span” to a Set::IntSpan object. To get the number of minutes the light was on, we can just examine the object’s cardinality, i.e. the number of integers belonging to the union of all the spans.

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

use Set::IntSpan qw{ grep_set };

sub minutes {
    my ($time) = @_;
    my ($hours, $minutes) = split /:/, $time;
    return $hours * 60 + $minutes
}

my $span = 'Set::IntSpan'->new;
while (<>) {
    my ($in, $out) = (split)[3, 5];
    $_ = minutes($_) for $in, $out;
    $span += 'Set::IntSpan'->new([[$in, $out]]);
}

say $span->cardinality;

Try it yourself, it works even if the guest house stays empty several times a day.

By the way, the answer to the initial question is 111 minutes (or 110 if we don’t count the final minute).

Reverse Polish Notation

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

We’ll use the example from Wikipedia:

15 7 1 1 + − ÷ 3 × 2 1 1 + + −

It’s interesting because it uses the fancy symbols for mathematical operation (well, except for addition which uses the old boring +).

The Reverse Polish notation is easy to implement: we just need a single stack. We than scan the tokens left to right: if the current token is a number, we store it in the stack, otherwise it’s an operator, and we pop the two topmost numbers from the stack, perform the operation on them and store the result back to the stack.

First, we need to tokenise the input. All tokens are separated by whitespace, so we can reach for Perl’s split with its special string separator ' '.

If we ran out of stack in the middle of the expression, the input wasn’t valid: there weren’t enough numbers. If, on the other hand, we finish the computation and the stack contains more than one number, the input is again invalid, this time it didn’t contain enough operators.

To implement the operations, we’ll use a dispatch table (already demonstrated in Perl Weekly Challenge 034).

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };
use utf8;

my %op = ( '+' => sub { $_[0] + $_[1] },
           '−' => sub { $_[0] - $_[1] },
           '×' => sub { $_[0] * $_[1] },
           '÷' => sub { $_[0] / $_[1] });

sub rpn {
    my ($input) = @_;
    my @tokens = split ' ', $input;
    my @stack;
    for my $token (@tokens) {
        if ($token =~ /^[0-9]+$/) {
            push @stack, $token;
        } else {
            push @stack,
                 $op{$token}->(((pop @stack) // die 'Stack empty'),
                                (pop @stack) // die 'Stack empty');
        }
    }
    my $result = pop @stack;
    die "Left on stack: @stack" if @stack;

    return $result
}

my $input = '15 7 1 1 + − ÷ 3 × 2 1 1 + + −';
my $expected_result = 5;
my $result = rpn($input);
die unless $result == $expected_result;
say $result;