laurent_r

These are some answers to the Week 117 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a couple of days (June 20, 2021). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

Task 1: Missing Row

You are given text file with rows numbered 1-15 in random order but there is a catch one row in missing in the file.

11, Line Eleven
1, Line one
9, Line Nine
13, Line Thirteen
2, Line two
6, Line Six
8, Line Eight
10, Line Ten
7, Line Seven
4, Line Four
14, Line Fourteen
3, Line three
15, Line Fifteen
5, Line Five

Write a script to find the missing row number.

If the numbers are really 1 to 15 and if only one number is missing, then we could sum the numbers that we have and subtract the result from the sum of all integers between 1 and 15 (120), which would give us the missing number.

However, I’ll work on a task that is a bit more general: rather than only 1 to 15, I’ll use a range from 1 to any larger integer, and I’ll also suppose that there can be more than 1 number missing.

Missing Row in Raku

I will simulate the input file as a string variable. We read the input data and store in the %seen hash the row numbers. At the end, we go through the range and print out numbers that are not in the hash.

use v6;

my $file = "11, Line Eleven
1, Line one
9, Line Nine
13, Line Thirteen
2, Line two
6, Line Six
8, Line Eight
10, Line Ten
7, Line Seven
4, Line Four
14, Line Fourteen
3, Line three
15, Line Fifteen
5, Line Five";

my %seen;
my $max = 0;

for $file.lines -> $line {
    my $num = $line ~~ /^(\d+)/;
    %seen{$num} = 1;
    $max = $num if $num > $max;
}
for 1..$max -> $i {
    say "Missing number = ", $i unless %seen{$i}:exists;
}

This program displays the following output:

raku ./missing_row.raku
Missing number = 12

Missing Row in Perl

This is essentially a port to Perl of the Raku program above, except that we store the input in a __DATA__ section:

use strict;
use warnings;
use feature "say";

my %seen;
my $max = 0;

while (my $line = <DATA>) {
    my $num = $1 if $line =~ /^(\d+)/;
    $seen{$num} = 1;
    $max = $num if $num > $max;
}
for my $i (1..$max) {
    say "Missing number = ", $i unless exists $seen{$i};
}

__DATA__
11, Line Eleven
1, Line one
9, Line Nine
13, Line Thirteen
2, Line two
6, Line Six
8, Line Eight
10, Line Ten
7, Line Seven
4, Line Four
14, Line Fourteen
3, Line three
15, Line Fifteen
5, Line Five

This program displays the same output as the Raku program:

$ perl missing_row.pl
Missing number = 12

Task 2 - Find Possible Paths

You are given size of a triangle.

Write a script to find all possible paths from top to the bottom right corner.

In each step, we can either move horizontally to the right (H), or move downwards to the left (L) or right (R).

BONUS: Try if it can handle triangle of size 10 or 20.

Example 1:

Input: $N = 2

           S
          / \
         / _ \
        /\   /\
       /__\ /__\ E

Output: RR, LHR, LHLH, LLHH, RLH, LRH

Example 2:

Input: $N = 1

           S
          / \
         / _ \ E

Output: R, LH

First, I will not try the bonus, because the result would just be insanely large: a triangle of size 10 has more than one million possible paths and a triangle of size 20 has billions or possibly trillions of paths.

Possible Paths in Raku

We use the recursive visit subroutine to build all possible paths.

use v6;

sub visit ($row, $col, $path) {
    print "$path " and return if $row == $col == $*end;
    visit($row + 1, $col + 1, "{$path}R") if $row < $*end and $col < $*end;
    visit($row, $col + 1, "{$path}H") if $col < $row;
    visit($row + 1, $col, "{$path}L") if $row < $*end;
}   

sub MAIN(UInt $size = 3) {
    my $*end = $size;
    visit(0, 0, '');
}

This program displays the following output:

raku ./possible_path.raku 3
RRR RRLH RLRH RLHR RLHLH RLLHH LRRH LRHR LRHLH LRLHH LHRR LHRLH LHLRH LHLHR LHLHLH LHLLHH LLRHH LLHRH LLHHR LLHHLH LLHLHH LLLHHH

We can also find the number of paths with an input value of 10:

raku ./possible_path.raku 10 | wc
      0 1037718 18474633

Possible Paths in Perl

This a port to Perl of the above Raku program:

use strict;
use warnings;
use feature "say";

my $end = shift // 3;

sub visit  { 
    my ($row, $col, $path) = @_;
    print "$path " and return if $row == $end and $col == $end;
    visit($row + 1, $col + 1, "${path}R") if $row < $end and $col < $end;
    visit($row, $col + 1, "${path}H") if $col < $row;
    visit($row + 1, $col, "${path}L") if $row < $end;
}   

visit(0, 0, '');

This program displays the following output:

$ perl possible_path.pl 3
RRR RRLH RLRH RLHR RLHLH RLLHH LRRH LRHR LRHLH LRLHH LHRR LHRLH LHLRH LHLHR LHLHLH LHLLHH LLRHH LLHRH LLHHR LLHHLH LLHLHH LLLHHH

$ perl possible_path.pl 2
RR RLH LRH LHR LHLH LLHH

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, June 27, 2021. And, please, also spread the word about the Perl Weekly Challenge if you can.