diff options
| author | PerlMonk Athanasius <PerlMonk.Athanasius@gmail.com> | 2021-06-19 21:46:38 +1000 |
|---|---|---|
| committer | PerlMonk Athanasius <PerlMonk.Athanasius@gmail.com> | 2021-06-19 21:46:38 +1000 |
| commit | fada25a5241c7c70e00df3eb8ece1323a11bcc33 (patch) | |
| tree | 5b7a2c611b5cfa36fe5974d62d5a8af3f4fb63f7 /challenge-117 | |
| parent | eda544efa917e0b554c55cdcc155c19f836ebb4b (diff) | |
| download | perlweeklychallenge-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.txt | 14 | ||||
| -rw-r--r-- | challenge-117/athanasius/perl/ch-1.pl | 167 | ||||
| -rw-r--r-- | challenge-117/athanasius/perl/ch-2.pl | 264 | ||||
| -rw-r--r-- | challenge-117/athanasius/raku/Example.txt | 14 | ||||
| -rw-r--r-- | challenge-117/athanasius/raku/ch-1.raku | 133 | ||||
| -rw-r--r-- | challenge-117/athanasius/raku/ch-2.raku | 240 |
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; +} + +############################################################################## |
