aboutsummaryrefslogtreecommitdiff
path: root/challenge-117
diff options
context:
space:
mode:
authorPerlMonk Athanasius <PerlMonk.Athanasius@gmail.com>2021-06-19 21:46:38 +1000
committerPerlMonk Athanasius <PerlMonk.Athanasius@gmail.com>2021-06-19 21:46:38 +1000
commitfada25a5241c7c70e00df3eb8ece1323a11bcc33 (patch)
tree5b7a2c611b5cfa36fe5974d62d5a8af3f4fb63f7 /challenge-117
parenteda544efa917e0b554c55cdcc155c19f836ebb4b (diff)
downloadperlweeklychallenge-club-fada25a5241c7c70e00df3eb8ece1323a11bcc33.tar.gz
perlweeklychallenge-club-fada25a5241c7c70e00df3eb8ece1323a11bcc33.tar.bz2
perlweeklychallenge-club-fada25a5241c7c70e00df3eb8ece1323a11bcc33.zip
Perl & Raku solutions to Tasks 1 & 2 of the Perl Weekly Challenge #117
On branch branch-for-challenge-117 Changes to be committed: new file: challenge-117/athanasius/perl/Example.txt new file: challenge-117/athanasius/perl/ch-1.pl new file: challenge-117/athanasius/perl/ch-2.pl new file: challenge-117/athanasius/raku/Example.txt new file: challenge-117/athanasius/raku/ch-1.raku new file: challenge-117/athanasius/raku/ch-2.raku
Diffstat (limited to 'challenge-117')
-rw-r--r--challenge-117/athanasius/perl/Example.txt14
-rw-r--r--challenge-117/athanasius/perl/ch-1.pl167
-rw-r--r--challenge-117/athanasius/perl/ch-2.pl264
-rw-r--r--challenge-117/athanasius/raku/Example.txt14
-rw-r--r--challenge-117/athanasius/raku/ch-1.raku133
-rw-r--r--challenge-117/athanasius/raku/ch-2.raku240
6 files changed, 832 insertions, 0 deletions
diff --git a/challenge-117/athanasius/perl/Example.txt b/challenge-117/athanasius/perl/Example.txt
new file mode 100644
index 0000000000..5b9d9ab1ce
--- /dev/null
+++ b/challenge-117/athanasius/perl/Example.txt
@@ -0,0 +1,14 @@
+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
diff --git a/challenge-117/athanasius/perl/ch-1.pl b/challenge-117/athanasius/perl/ch-1.pl
new file mode 100644
index 0000000000..b13672a702
--- /dev/null
+++ b/challenge-117/athanasius/perl/ch-1.pl
@@ -0,0 +1,167 @@
+#!perl
+
+###############################################################################
+=comment
+
+Perl 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.
+
+=cut
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2021 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=comment
+
+Algorithm
+---------
+1. Create a hash %rows which maps each row number in the range 1 to 15 to a
+ count of 0.
+2. Read the input file line-by-line, extracting the row number from the begin-
+ ning of the line, and increment the %rows count for that row number.
+3. 14 of the 15 rows should now have a count of 1. Output the only remaining
+ row number with a count of 0.
+
+=cut
+#==============================================================================
+
+use strict;
+use warnings;
+use Const::Fast;
+
+const my $FILE => 'Example.txt';
+const my $MAX_ROW => 15;
+const my $ROWS => $MAX_ROW - 1;
+const my $USAGE =>
+"Usage:
+ perl $0 [<file>]
+
+ [<file>] Text file of $ROWS lines, each uniquely numbered in the " .
+ "range 1-$MAX_ROW\n";
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+ $| = 1;
+ print "\nChallenge 117, Task #1: Missing Row (Perl)\n\n";
+}
+
+#=============================================================================
+MAIN:
+#==============================================================================
+{
+ my $file = parse_command_line();
+
+ print "Input: $file\n";
+
+ my $lines = get_lines( $file );
+
+ scalar @$lines == $ROWS
+ or error( qq[File "$file" does not contain $ROWS lines] );
+
+ my %rows = map { $_ => 0 } 1 .. $MAX_ROW;
+
+ for my $line (1 .. $ROWS)
+ {
+ $lines->[ $line - 1 ] =~ / ^ \s* ( \d+ ) /x
+ or error( "Line $line of the input file is invalid" );
+
+ my $num = $1;
+
+ 1 <= $num <= $MAX_ROW
+ or error( qq[Invalid number "$num" in line $line] );
+
+ ++$rows{ $num } == 1
+ or error( "Found 2 lines numbered $num" );
+ }
+
+ my $missing;
+
+ for my $row (1 .. $MAX_ROW)
+ {
+ $missing = $row, last if $rows{ $row } == 0;
+ }
+
+ print "Output: $missing\n";
+}
+
+#------------------------------------------------------------------------------
+sub get_lines
+#------------------------------------------------------------------------------
+{
+ my ($file) = @_;
+
+ open( my $fh, '<', $file )
+ or die qq[Cannot open file "$file" for reading, stopped];
+
+ my @lines = <$fh>;
+
+ close $fh
+ or die qq[Cannot close file "$file", stopped];
+
+ return \@lines;
+}
+
+#------------------------------------------------------------------------------
+sub parse_command_line
+#------------------------------------------------------------------------------
+{
+ my $args = scalar @ARGV;
+ $args <= 1
+ or error( "Expected 0 or 1 command line arguments, found $args" );
+
+ my $file = ($args == 0) ? $FILE : $ARGV[ 0 ];
+
+ open( my $fh, '<', $file )
+ or error( qq[Cannot open file "$file" for reading] );
+
+ -s $fh or error( qq[File "$file" is empty] );
+ -f $fh or error( qq[File "$file" is not a plain file] );
+ -T $fh or error( qq[File "$file" is not a text file] );
+
+ close $fh
+ or die qq[Cannot close file "$file", stopped];
+
+ return $file;
+}
+
+#------------------------------------------------------------------------------
+sub error
+#------------------------------------------------------------------------------
+{
+ my ($message) = @_;
+
+ die "ERROR: $message\n$USAGE";
+}
+
+###############################################################################
diff --git a/challenge-117/athanasius/perl/ch-2.pl b/challenge-117/athanasius/perl/ch-2.pl
new file mode 100644
index 0000000000..3fce017a3b
--- /dev/null
+++ b/challenge-117/athanasius/perl/ch-2.pl
@@ -0,0 +1,264 @@
+#!perl
+
+###############################################################################
+=comment
+
+Perl Weekly Challenge 117
+=========================
+
+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
+
+=cut
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2021 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=comment
+
+Output
+------
+Both the Task description and the associated Examples show that the required
+output is an enumeration of all the possible paths from the top of the equi-
+lateral triangle to its bottom right corner. However, for values of $N greater
+than 6 this becomes impractical. In particular, for the bonus size of 10, the
+number of paths is over a million, and for the bonus size of 20, the number of
+paths is over 17 trillion!
+
+An alternative output is simply the total number of distinct paths. In the
+script below, this number is given first, followed optionally by a full enumer-
+ation of the paths. This enumeration is output by default, but may be turned
+off by setting the $SHOW_PATHS constant to a false value. IT IS STRONGLY
+ADVISED THAT $SHOW_PATHS BE SET TO FALSE WHEN ENTERING ANY VALUE OF $N GREATER
+THAN 10, AS OTHERWISE MEMORY MAY BECOME EXHAUSTED.
+
+It is assumed that the full list of paths may be presented in any order. This
+script prioritizes R over both L and H, and L over H. For example, when $N = 4
+the paths are output in this order:
+
+ (beginning) RRRR ... LLLLHHHH ... LHLHLHLH (end).
+
+Algorithms
+----------
+The total number of distinct paths for each value of $N is given by the series
+of Schröder numbers (see the references below). Schröder numbers may be calcu-
+lated via a recurrence relation as detailed in the header to sub S(). Memoiza-
+tion is used to reduce the computation time.
+
+Enumeration of the paths is performed as follows:
+
+1. A ragged array is constructed to hold a path list for each node of the
+ triangle. For example, if $N = 2 then the array has this structure:
+
+ nodes[0] contains node[0][0]
+ nodes[1] contains node[1][0] and node[1][1]
+ nodes[2] contains node[2][0] and node[2][1] and node[2][2]
+
+2. The end point of the path -- in this case node[2][2] -- contains only the
+ empty string.
+
+3. FOR each row of the triangle, from last to first
+ FOR each column in this row, from last to first
+ All possible paths from the node at this row and column to the end
+ node are constructed by
+ - prepending 'R' to each path already stored in the node (if any)
+ immediately below and to the right
+ - prepending 'L' to each path already stored in the node (if any)
+ immediately below and to the left
+ - prepending 'H' to each path already stored in the node (if any)
+ immediately to the right
+ ENDFOR
+ ENDFOR
+
+4. All paths are now stored in node[0][0]
+
+References
+----------
+(1) "A006318 Large Schröder numbers ...", The On-Line Encyclopedia of Integer
+ Sequences (OEIS), https://oeis.org/A006318
+
+(2) "Schröder number", Wikipedia,
+ https://en.wikipedia.org/wiki/Schr%C3%B6der_number
+
+=cut
+#==============================================================================
+
+use strict;
+use warnings;
+use Const::Fast;
+use Memoize;
+use Regexp::Common qw( number );
+
+const my $SHOW_PATHS => 1;
+const my $USAGE =>
+"Usage:
+ perl $0 <N>
+
+ <N> Positive int: size (side length) of an equilateral triangle\n";
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+ $| = 1;
+ print "\nChallenge 117, Task #2: Find Possible Paths (Perl)\n\n";
+}
+
+#==============================================================================
+MAIN:
+#==============================================================================
+{
+ my $N = parse_command_line();
+
+ print "Input: \$N = $N\n";
+
+ memoize( 'S' );
+
+ my $s = S( $N );
+
+ print "Output:\n Total paths: $s\n";
+
+ if ($SHOW_PATHS)
+ {
+ my $paths = find_paths( $N );
+
+ printf " List of paths: %s\n", join ', ', @$paths;
+
+ $s == scalar @$paths
+ or warn "\nERROR: The number of paths found does not equal the " .
+ "Schroeder number of \$N\n";
+ }
+}
+
+#------------------------------------------------------------------------------
+# Schröder number
+# ---------------
+# Formula:
+# S[0] = 1
+# S[1] = 2
+# for n >= 2: S[n] = 3.S[n - 1] + SUM( k = 1 .. (n - 2) ){ S[k].S[n - k - 1] }
+#
+# -- https://en.wikipedia.org/wiki/Schr%C3%B6der_number#Recurrence_relation
+#
+sub S
+#------------------------------------------------------------------------------
+{
+ my ($N) = @_;
+
+ return 1 if $N == 0;
+ return 2 if $N == 1;
+
+ my $S = 3 * S( $N - 1 );
+
+ for my $k (1 .. $N - 2)
+ {
+ $S += S( $k ) * S( $N - $k - 1 );
+ }
+
+ return $S;
+}
+
+#------------------------------------------------------------------------------
+sub find_paths
+#------------------------------------------------------------------------------
+{
+ my ($N) = @_;
+ my @nodes;
+
+ for my $row (0 .. $N)
+ {
+ $nodes[$row][$_] = [] for 0 .. $row;
+ }
+
+ push $nodes[$N][$N]->@*, '';
+
+ for my $r (reverse 0 .. $N)
+ {
+ for my $c (reverse 0 .. $r)
+ {
+ if ($r < $N)
+ {
+ # (R) Move downwards to the right
+
+ push $nodes[$r][$c]->@*, "R$_" for $nodes[$r + 1][$c + 1]->@*;
+
+ # (L) Move downwards to the left
+
+ push $nodes[$r][$c]->@*, "L$_" for $nodes[$r + 1][$c ]->@*;
+ }
+
+ if ($c < $r)
+ {
+ # (H) Move horizontally to the right
+
+ push $nodes[$r][$c]->@*, "H$_" for $nodes[$r ][$c + 1]->@*;
+ }
+ }
+ }
+
+ return $nodes[0][0];
+}
+
+#------------------------------------------------------------------------------
+sub parse_command_line
+#------------------------------------------------------------------------------
+{
+ my $args = scalar @ARGV;
+ $args == 1 or error( "Expected 1 command line argument, found $args" );
+
+ my $N = $ARGV[0];
+ $N =~ / ^ $RE{num}{int} $ /x
+ or error( qq["$N" is not a valid integer] );
+ $N += 0; # Normalize: e.g., 010 --> 10
+ $N >= 0 or error( "$N is less than 0" );
+
+ return $N;
+}
+
+#------------------------------------------------------------------------------
+sub error
+#------------------------------------------------------------------------------
+{
+ my ($message) = @_;
+
+ die "ERROR: $message\n$USAGE";
+}
+
+###############################################################################
diff --git a/challenge-117/athanasius/raku/Example.txt b/challenge-117/athanasius/raku/Example.txt
new file mode 100644
index 0000000000..5b9d9ab1ce
--- /dev/null
+++ b/challenge-117/athanasius/raku/Example.txt
@@ -0,0 +1,14 @@
+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
diff --git a/challenge-117/athanasius/raku/ch-1.raku b/challenge-117/athanasius/raku/ch-1.raku
new file mode 100644
index 0000000000..fbf75b44c9
--- /dev/null
+++ b/challenge-117/athanasius/raku/ch-1.raku
@@ -0,0 +1,133 @@
+use v6d;
+
+###############################################################################
+=begin comment
+
+Perl 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.
+
+=end comment
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2021 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=begin comment
+
+Algorithm
+---------
+1. Create a hash %rows which maps each row number in the range 1 to 15 to a
+ count of 0.
+2. Read the input file line-by-line, extracting the row number from the begin-
+ ning of the line, and increment the %rows count for that row number.
+3. 14 of the 15 rows should now have a count of 1. Output the only remaining
+ row number with a count of 0.
+
+=end comment
+#==============================================================================
+
+my Int constant $MAX-ROW = 15;
+my Int constant $ROWS = $MAX-ROW - 1;
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+ "\nChallenge 117, Task #1: Missing Row (Raku)\n".put;
+}
+
+#==============================================================================
+sub MAIN
+(
+ #| Text file of ROWS lines, each uniquely numbered in the range 1-MAX-ROW
+
+ Str:D $file where { .IO.f && .IO.s > 0 } = 'Example.txt'
+)
+#==============================================================================
+{
+ "Input: $file".put;
+
+ my Str @lines = $file.IO.lines;
+
+ @lines.elems == $ROWS
+ or error( qq[File "$file" does not contain $ROWS lines] );
+
+ my UInt %rows = (1 .. $MAX-ROW).map: { $_ => 0 };
+
+ for 1 .. $ROWS -> UInt $line
+ {
+ @lines[ $line - 1 ] ~~ / ^ \s* ( \d+ ) /
+ or error( "Line $line of the input file is invalid" );
+
+ my UInt $num = $0.Int;
+
+ 1 <= $num <= $MAX-ROW
+ or error( qq[Invalid number "$num" in line $line] );
+
+ ++%rows{ $num } == 1
+ or error( "Found 2 lines numbered $num" );
+ }
+
+ my UInt $missing;
+
+ for 1 .. $MAX-ROW -> UInt $row
+ {
+ $missing = $row, last if %rows{ $row } == 0;
+ }
+
+ "Output: $missing".put;
+}
+
+#------------------------------------------------------------------------------
+sub error( Str:D $message )
+#------------------------------------------------------------------------------
+{
+ "ERROR: $message".put;
+
+ USAGE();
+
+ exit;
+}
+
+#------------------------------------------------------------------------------
+sub USAGE()
+#------------------------------------------------------------------------------
+{
+ my Str $usage = $*USAGE;
+
+ $usage ~~ s/ ($*PROGRAM-NAME) /raku $0/;
+ $usage ~~ s/ ROWS /$ROWS/;
+ $usage ~~ s/ MAX\-ROW /$MAX-ROW/;
+
+ $usage.put;
+}
+
+##############################################################################
diff --git a/challenge-117/athanasius/raku/ch-2.raku b/challenge-117/athanasius/raku/ch-2.raku
new file mode 100644
index 0000000000..5df24bd02e
--- /dev/null
+++ b/challenge-117/athanasius/raku/ch-2.raku
@@ -0,0 +1,240 @@
+use v6d;
+
+###############################################################################
+=begin comment
+
+Perl Weekly Challenge 117
+=========================
+
+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
+
+=end comment
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2021 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=begin comment
+
+Output
+------
+Both the Task description and the associated Examples show that the required
+output is an enumeration of all the possible paths from the top of the equi-
+lateral triangle to its bottom right corner. However, for values of $N greater
+than 6 this becomes impractical. In particular, for the bonus size of 10, the
+number of paths is over a million, and for the bonus size of 20, the number of
+paths is over 17 trillion!
+
+An alternative output is simply the total number of distinct paths. In the
+script below, this number is given first, followed optionally by a full enumer-
+ation of the paths. This enumeration is output by default, but may be turned
+off by setting the $SHOW_PATHS constant to a false value. IT IS STRONGLY
+ADVISED THAT $SHOW_PATHS BE SET TO FALSE WHEN ENTERING ANY VALUE OF $N GREATER
+THAN 10, AS OTHERWISE MEMORY MAY BECOME EXHAUSTED.
+
+It is assumed that the full list of paths may be presented in any order. This
+script prioritizes R over both L and H, and L over H. For example, when $N = 4
+the paths are output in this order:
+
+ (beginning) RRRR ... LLLLHHHH ... LHLHLHLH (end).
+
+Algorithms
+----------
+The total number of distinct paths for each value of $N is given by the series
+of Schröder numbers (see the references below). Schröder numbers may be calcu-
+lated via a recurrence relation as detailed in the header to sub S(). Memoiza-
+tion is used to reduce the computation time.
+
+Enumeration of the paths is performed as follows:
+
+1. A ragged array is constructed to hold a path list for each node of the
+ triangle. For example, if $N = 2 then the array has this structure:
+
+ nodes[0] contains node[0][0]
+ nodes[1] contains node[1][0] and node[1][1]
+ nodes[2] contains node[2][0] and node[2][1] and node[2][2]
+
+2. The end point of the path -- in this case node[2][2] -- contains only the
+ empty string.
+
+3. FOR each row of the triangle, from last to first
+ FOR each column in this row, from last to first
+ All possible paths from the node at this row and column to the end
+ node are constructed by
+ - prepending 'R' to each path already stored in the node (if any)
+ immediately below and to the right
+ - prepending 'L' to each path already stored in the node (if any)
+ immediately below and to the left
+ - prepending 'H' to each path already stored in the node (if any)
+ immediately to the right
+ ENDFOR
+ ENDFOR
+
+4. All paths are now stored in node[0][0]
+
+References
+----------
+(1) "A006318 Large Schröder numbers ...", The On-Line Encyclopedia of Integer
+ Sequences (OEIS), https://oeis.org/A006318
+
+(2) "Schröder number", Wikipedia,
+ https://en.wikipedia.org/wiki/Schr%C3%B6der_number
+
+=end comment
+#==============================================================================
+
+use Memoize;
+
+my Bool constant $SHOW-PATHS = True;
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+ "\nChallenge 117, Task #2: Find Possible Paths (Raku)\n".put;
+}
+
+#==============================================================================
+sub MAIN
+(
+ UInt:D $N #= Positive int: size (side length) of an equilateral triangle
+)
+#==============================================================================
+{
+ my UInt $n = $N + 0; # Normalize: e.g., 010 --> 10, 0x10 --> 16
+
+ "Input: \$N = $n".put;
+
+ memoize( 'S' );
+
+ my UInt $s = S( $n );
+
+ print "Output:\n Total paths: $s\n";
+
+ if $SHOW-PATHS
+ {
+ my Array[Str] $paths = find-paths( $n );
+
+ " List of paths: %s\n".printf: $paths.join: ', ';
+
+ $s == $paths.elems
+ or note "\nERROR: The number of paths found does not equal the " ~
+ "Schroeder number of \$N";
+ }
+}
+
+#------------------------------------------------------------------------------
+# Schröder number
+# ---------------
+# Formula:
+# S[0] = 1
+# S[1] = 2
+# for n >= 2: S[n] = 3.S[n - 1] + SUM( k = 1 .. (n - 2) ){ S[k].S[n - k - 1] }
+#
+# -- https://en.wikipedia.org/wiki/Schr%C3%B6der_number#Recurrence_relation
+#
+sub S( UInt:D $N --> UInt:D )
+#------------------------------------------------------------------------------
+{
+ return 1 if $N == 0;
+ return 2 if $N == 1;
+
+ my UInt $S = 3 * S( $N - 1 );
+
+ for 1 .. $N - 2 -> UInt $k
+ {
+ $S += S( $k ) * S( $N - $k - 1 );
+ }
+
+ return $S;
+}
+
+#------------------------------------------------------------------------------
+sub find-paths( UInt:D $N --> Array:D[Str:D] )
+#------------------------------------------------------------------------------
+{
+ my Array[Array[Str]] @nodes;
+
+ for 0 .. $N -> UInt $row
+ {
+ @nodes[$row] = Array[Array[Str]].new;
+ @nodes[$row][$_] = Array[Str].new for 0 .. $row;
+ }
+
+ @nodes[$N][$N].push: '';
+
+ for (0 .. $N).reverse -> UInt $r
+ {
+ for (0 .. $r).reverse -> UInt $c
+ {
+ if $r < $N
+ {
+ # (R) Move downwards to the right
+
+ @nodes[$r][$c].push: "R$_" for @nodes[$r + 1][$c + 1][];
+
+ # (L) Move downwards to the left
+
+ @nodes[$r][$c].push: "L$_" for @nodes[$r + 1][$c ][];
+ }
+
+ if $c < $r
+ {
+ # (H) Move horizontally to the right
+
+ @nodes[$r][$c].push: "H$_" for @nodes[$r ][$c + 1][];
+ }
+ }
+ }
+
+ return @nodes[0][0];
+}
+
+#------------------------------------------------------------------------------
+sub USAGE()
+#------------------------------------------------------------------------------
+{
+ my Str $usage = $*USAGE;
+
+ $usage ~~ s:g/ ($*PROGRAM-NAME) /raku $0/;
+ $usage.put;
+}
+
+##############################################################################