Task 1: Guest Book / Light Minutes
Write a script to compute the total number of minutes the light was on in a room. The light is turned on when the first person enters and off when the last person leaves. You are given a list of guest entry times in the format "HH:MM".
Example Output
Input: Guest book entries (Alex 09:10-09:45, Arnold 09:15-09:33, Bob 09:22-09:55, Charlie 09:25-10:05, Steve 09:33-10:01, Roger 09:44-10:12, David 09:57-10:23, Neil 10:01-10:19, Chris 10:10-11:00)
Output: 110 minutes
Logic
Convert all HH:MM times to absolute minutes from midnight. Sort the interval list by start times. Traverse the intervals, merging overlapping intervals by extending the end time of the current active interval. Finally, sum the durations of the merged intervals.
Perl Solution
ch-1.pl
sub minutes_light_on {
my @guest_book = @_;
my @time_ranges;
for my $entry (@guest_book) {
my ( $in_time, $out_time ) = @{$entry}[ 1, 2 ];
my $in_time_minutes = int( substr( $in_time, 0, 2 ) ) * 60 + int( substr( $in_time, 3, 2 ) );
my $out_time_minutes = int( substr( $out_time, 0, 2 ) ) * 60 + int( substr( $out_time, 3, 2 ) );
push @time_ranges, [ $in_time_minutes, $out_time_minutes ];
}
@time_ranges = sort { $a->[0] <=> $b->[0] } @time_ranges;
my @merged_ranges = ( $time_ranges[0] );
for my $i ( 1 .. $#time_ranges ) {
my ( $current_start, $current_end ) = @{ $time_ranges[$i] };
my ( $last_start, $last_end ) = @{ $merged_ranges[-1] };
if ( $current_start > $last_end ) {
push @merged_ranges, [ $current_start, $current_end ];
} else {
$merged_ranges[-1] = [ $last_start, max( $current_end, $last_end ) ];
}
}
my $total_minutes = 0;
$total_minutes += $_->[1] - $_->[0] for @merged_ranges;
return $total_minutes;
}
Python Solution
ch-1.py
def minutes_light_on(guest_book: List[Tuple[str, str, str]]) -> int:
time_ranges = []
for _, in_time, out_time in guest_book:
in_time_minutes = int(in_time.split(":")[0]) * 60 + int(in_time.split(":")[1])
out_time_minutes = int(out_time.split(":")[0]) * 60 + int(out_time.split(":")[1])
time_ranges.append((in_time_minutes, out_time_minutes))
time_ranges.sort()
merged_ranges = [time_ranges[0]]
for current_start, current_end in time_ranges[1:]:
last_start, last_end = merged_ranges[-1]
if current_start > last_end:
merged_ranges.append((current_start, current_end))
else:
merged_ranges[-1] = (last_start, max(current_end, last_end))
return sum(end - start for start, end in merged_ranges)
Task 2: Reverse Polish Notation
Write a script to evaluate a given Reverse Polish Notation (RPN) mathematical expression.
Example Output
Input: "3 4 + 2 * 1 +"
Output: 15
Logic
Traverse the tokens of the space-separated RPN expression. If a token is an operator (+, -, *, /), pop the top two numbers from the stack, apply the operator, and push the result back. Otherwise, push the token (parsed as a number) onto the stack. The final remaining element in the stack is the result.
Perl Solution
ch-2.pl
sub evaluate_rpn {
my ($expression) = @_;
my @stack;
for my $token ( split / /, $expression ) {
if ( $token =~ /^[+\-*\/]$/ ) {
my $b = pop @stack;
my $a = pop @stack;
if ( $token eq '+' ) {
push @stack, $a + $b;
}
elsif ( $token eq '-' ) {
push @stack, $a - $b;
}
elsif ( $token eq '*' ) {
push @stack, $a * $b;
}
else {
push @stack, $a / $b;
}
}
else {
push @stack, $token;
}
}
return $stack[0];
}
Python Solution
ch-2.py
def evaluate_rpn(expression: str) -> float:
stack = []
for token in expression.split():
if token in "+-*/":
b = stack.pop()
a = stack.pop()
if token == "+":
stack.append(a + b)
elif token == "-":
stack.append(a - b)
elif token == "*":
stack.append(a * b)
else:
stack.append(a / b)
else:
stack.append(float(token))
return stack[0]