The Weekly Challenge 039

Light Minutes and Reverse Polish Notation

Solutions on GitHub

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]