« Perl Weekly Challenge 116. Perl Weekly Challenge 118. »

Perl Weekly Challenge 117.

My solutions (task 1, and task 2) to the The Weekly Challenge - 117.

Task 1: Missing Row

Submitted by: Mohammad S Anwar
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.

I assume all rows begin as the example, with the row number and a comma, and that there are fifteen rows, including the missing one. Thus I can use a hash for all possible entries, delete the entries that are present and then print the remaining one, which corresponds to the missing row. This can be done with a one liner.

perl -E '@r{1..15}=(1)x15; while(<>){/^\s*(\d+),/; delete $r{$1}} say "Missing: ", keys %r;' <<EOF
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
EOF

Results:

Missing: 12

Here is a slightly longer version:

# Perl weekly challenge 117
# Task 1: Missing row
#
# See https://wlmb.github.io/2021/06/15/PWC117/#task-1-missing-row
use strict;
use warnings;
use v5.12;

my %rows;
@rows{1..15}=map {"Line $_"} qw(one two three four five six seven eight nine
				ten eleven twelve thirteen fourteen fifteen);
my $count=0;
while(<>){
    ++$count;
    die "Wrong format: $_" unless /^\s*(\d+),/;
    die "Wrong number: $_" unless defined $rows{$1};
    delete $rows{$1};
}
die "Not 14 lines" unless $count=14;
say "Missing row: $_, $rows{$_}" for keys %rows;

Example:

./ch-1.pl <<EOF
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

Results:

Missing row: 12, Line twelve

Task 2: Find Possible Paths

Submitted by: E. Choroba
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

I can count and generate all the paths recursively very easily starting from the lower right hand side corner by noting that I can reach any position travelling horizontally from its left neighbor, moving towards the right from its upper-left neighbor or traveling towards the left from its upper-right neighbor. I just have to deal with the boundaries. As the number of paths grows very fast, I wrap and truncate the printout.

# Perl weekly challenge 117
# Task 2: Find possible paths
#
# See https://wlmb.github.io/2021/06/15/PWC117/#task-2-find-possible-paths
use strict;
use warnings;
use v5.12;
use Text::Wrap;
use Memoize;
memoize qw(N P);
my $length=25; # keep this many paths
foreach(@ARGV){
    my @paths=P($_-1,$_-1);
    @paths=(@paths[0..$length], "...") if @paths>$length;
    say "\nHeight: $_\nNumber of paths: ", N($_-1,$_-1), "\nPaths:\n", wrap ("\t", "\t", @paths);
}
sub N { #Number of paths
    my ($row, $column)=@_;
    return 0 if $column>$row;
    return 0 if $column<0;
    return 0 if $row < 0;
    return 1 if $row==0 and $column==0;
    return N($row, $column-1)+N($row-1, $column-1)+N($row-1, $column);
}
sub P { #actual paths
    my ($r, $c)=@_; #row column
    return () if $c>$r;
    return () if $c<0;
    return () if $r < 0;
    return ("") if $r==0 and $c==0;
    return ((map {$_."H"} P($r, $c-1)), (map {$_."R"} P($r-1, $c-1)), (map {$_."L"} P($r-1, $c)));
}

Examples:

./ch-2.pl 2 3 4 5 6 7 8 9 10

Results:

Height: 2
Number of paths: 2
Paths:
	LH R

Height: 3
Number of paths: 6
Paths:
	LLHH LRH LHLH RLH LHR RR

Height: 4
Number of paths: 22
Paths:
	LLLHHH LLRHH LLHLHH LRLHH LHLLHH RLLHH LLHRH LRRH LHLRH RLRH LLHHLH
	LRHLH LHLHLH RLHLH LHRLH RRLH LLHHR LRHR LHLHR RLHR LHRR RRR

Height: 5
Number of paths: 90
Paths:
	LLLLHHHH LLLRHHH LLLHLHHH LLRLHHH LLHLLHHH LRLLHHH LHLLLHHH RLLLHHH
	LLLHRHH LLRRHH LLHLRHH LRLRHH LHLLRHH RLLRHH LLLHHLHH LLRHLHH
	LLHLHLHH LRLHLHH LHLLHLHH RLLHLHH LLHRLHH LRRLHH LHLRLHH RLRLHH
	LLHHLLHH LRHLLHH ...

Height: 6
Number of paths: 394
Paths:
	LLLLLHHHHH LLLLRHHHH LLLLHLHHHH LLLRLHHHH LLLHLLHHHH LLRLLHHHH
	LLHLLLHHHH LRLLLHHHH LHLLLLHHHH RLLLLHHHH LLLLHRHHH LLLRRHHH
	LLLHLRHHH LLRLRHHH LLHLLRHHH LRLLRHHH LHLLLRHHH RLLLRHHH LLLLHHLHHH
	LLLRHLHHH LLLHLHLHHH LLRLHLHHH LLHLLHLHHH LRLLHLHHH LHLLLHLHHH
	RLLLHLHHH ...

Height: 7
Number of paths: 1806
Paths:
	LLLLLLHHHHHH LLLLLRHHHHH LLLLLHLHHHHH LLLLRLHHHHH LLLLHLLHHHHH
	LLLRLLHHHHH LLLHLLLHHHHH LLRLLLHHHHH LLHLLLLHHHHH LRLLLLHHHHH
	LHLLLLLHHHHH RLLLLLHHHHH LLLLLHRHHHH LLLLRRHHHH LLLLHLRHHHH
	LLLRLRHHHH LLLHLLRHHHH LLRLLRHHHH LLHLLLRHHHH LRLLLRHHHH
	LHLLLLRHHHH RLLLLRHHHH LLLLLHHLHHHH LLLLRHLHHHH LLLLHLHLHHHH
	LLLRLHLHHHH ...

Height: 8
Number of paths: 8558
Paths:
	LLLLLLLHHHHHHH LLLLLLRHHHHHH LLLLLLHLHHHHHH LLLLLRLHHHHHH
	LLLLLHLLHHHHHH LLLLRLLHHHHHH LLLLHLLLHHHHHH LLLRLLLHHHHHH
	LLLHLLLLHHHHHH LLRLLLLHHHHHH LLHLLLLLHHHHHH LRLLLLLHHHHHH
	LHLLLLLLHHHHHH RLLLLLLHHHHHH LLLLLLHRHHHHH LLLLLRRHHHHH
	LLLLLHLRHHHHH LLLLRLRHHHHH LLLLHLLRHHHHH LLLRLLRHHHHH LLLHLLLRHHHHH
	LLRLLLRHHHHH LLHLLLLRHHHHH LRLLLLRHHHHH LHLLLLLRHHHHH RLLLLLRHHHHH
	...

Height: 9
Number of paths: 41586
Paths:
	LLLLLLLLHHHHHHHH LLLLLLLRHHHHHHH LLLLLLLHLHHHHHHH LLLLLLRLHHHHHHH
	LLLLLLHLLHHHHHHH LLLLLRLLHHHHHHH LLLLLHLLLHHHHHHH LLLLRLLLHHHHHHH
	LLLLHLLLLHHHHHHH LLLRLLLLHHHHHHH LLLHLLLLLHHHHHHH LLRLLLLLHHHHHHH
	LLHLLLLLLHHHHHHH LRLLLLLLHHHHHHH LHLLLLLLLHHHHHHH RLLLLLLLHHHHHHH
	LLLLLLLHRHHHHHH LLLLLLRRHHHHHH LLLLLLHLRHHHHHH LLLLLRLRHHHHHH
	LLLLLHLLRHHHHHH LLLLRLLRHHHHHH LLLLHLLLRHHHHHH LLLRLLLRHHHHHH
	LLLHLLLLRHHHHHH LLRLLLLRHHHHHH ...

Height: 10
Number of paths: 206098
Paths:
	LLLLLLLLLHHHHHHHHH LLLLLLLLRHHHHHHHH LLLLLLLLHLHHHHHHHH
	LLLLLLLRLHHHHHHHH LLLLLLLHLLHHHHHHHH LLLLLLRLLHHHHHHHH
	LLLLLLHLLLHHHHHHHH LLLLLRLLLHHHHHHHH LLLLLHLLLLHHHHHHHH
	LLLLRLLLLHHHHHHHH LLLLHLLLLLHHHHHHHH LLLRLLLLLHHHHHHHH
	LLLHLLLLLLHHHHHHHH LLRLLLLLLHHHHHHHH LLHLLLLLLLHHHHHHHH
	LRLLLLLLLHHHHHHHH LHLLLLLLLLHHHHHHHH RLLLLLLLLHHHHHHHH
	LLLLLLLLHRHHHHHHH LLLLLLLRRHHHHHHH LLLLLLLHLRHHHHHHH
	LLLLLLRLRHHHHHHH LLLLLLHLLRHHHHHHH LLLLLRLLRHHHHHHH
	LLLLLHLLLRHHHHHHH LLLLRLLLRHHHHHHH ...

Written on June 15, 2021