aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--challenge-100/athanasius/perl/ch-2.pl223
-rw-r--r--challenge-100/athanasius/raku/ch-2.raku226
2 files changed, 449 insertions, 0 deletions
diff --git a/challenge-100/athanasius/perl/ch-2.pl b/challenge-100/athanasius/perl/ch-2.pl
new file mode 100644
index 0000000000..5b42680d03
--- /dev/null
+++ b/challenge-100/athanasius/perl/ch-2.pl
@@ -0,0 +1,223 @@
+#!perl
+
+###############################################################################
+=comment
+
+Perl Weekly Challenge 100
+=========================
+
+Task #2
+-------
+*Triangle Sum*
+
+Submitted by: Mohammad S Anwar
+
+You are given triangle array.
+
+Write a script to find the minimum path sum from top to bottom.
+
+When you are on index i on the current row then you may move to either index i
+or index i + 1 on the next row.
+
+Example 1:
+
+ Input: Triangle = [ [1], [2,4], [6,4,9], [5,1,7,2] ]
+ Output: 8
+
+ Explanation: The given triangle
+
+ 1
+ 2 4
+ 6 4 9
+ 5 1 7 2
+
+ The minimum path sum from top to bottom: 1 + 2 + 4 + 1 = 8
+
+ [1]
+ [2] 4
+ 6 [4] 9
+ 5 [1] 7 2
+
+Example 2:
+
+ Input: Triangle = [ [3], [3,1], [5,2,3], [4,3,1,3] ]
+ Output: 7
+
+ Explanation: The given triangle
+
+ 3
+ 3 1
+ 5 2 3
+ 4 3 1 3
+
+ The minimum path sum from top to bottom: 3 + 1 + 2 + 1 = 7
+
+ [3]
+ 3 [1]
+ 5 [2] 3
+ 4 3 [1] 3
+
+=cut
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2021 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=comment
+
+Algorithm
+
+Although the path sum is from top to bottom, the algorithm for finding the min-
+imum path sum proceeds from bottom to top. For each row, starting at the second
+last and moving up, each element is summed with the smaller of the two elements
+immediately below it. When the top (i.e., first) row is reached, the final sum
+is guaranteed to be the minimum.
+
+Output
+
+If the constant $VERBOSE is given a true value, the output is supplemented with
+a summary of the elements in the minimum path sum, followed by a table of moves
+(left or right) from top to bottom of the triangle.
+
+=cut
+#==============================================================================
+
+use strict;
+use warnings;
+use enum qw( VALUE SUM INDEX );
+use Const::Fast;
+use Data::Dump qw( pp );
+use Regexp::Common qw( number );
+
+const my $VERBOSE => 1;
+const my $USAGE =>
+"Usage:
+ perl $0 <triangle>
+
+ <triangle> String representing a non-empty triangular array of real
+ numbers\n";
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+ $| = 1;
+ print "\nChallenge 100, Task #2: Triangle Sum (Perl)\n\n";
+}
+
+#==============================================================================
+MAIN:
+#==============================================================================
+{
+ my @triangle = parse_command_line();
+
+ printf "Input: %s\n", pp( \@triangle );
+
+ for my $col (0 .. scalar @{ $triangle[ $#triangle ] } - 1)
+ {
+ my $element = \$triangle[$#triangle][$col];
+ $$element = [ $$element, $$element, undef ];
+ }
+
+ for my $row (reverse 0 .. $#triangle - 1)
+ {
+ for my $col (0 .. scalar @{ $triangle[$row] } - 1)
+ {
+ my $lhs = $triangle[$row + 1][$col ];
+ my $rhs = $triangle[$row + 1][$col + 1];
+ my $element = \$triangle[$row ][$col ];
+
+ my $left = $lhs->[SUM] <= $rhs->[SUM];
+ my $addend = $left ? $lhs->[SUM] : $rhs->[SUM];
+ my $new_col = $left ? $col : $col + 1;
+
+ $$element = [ $$element, $$element + $addend, $new_col ];
+ }
+ }
+
+ printf "Output: %s\n", $triangle[0][0][SUM];
+
+ show_path( \@triangle ) if $VERBOSE;
+}
+
+#------------------------------------------------------------------------------
+sub show_path
+#------------------------------------------------------------------------------
+{
+ my ($triangle) = @_;
+ my $first = $triangle->[0][0][VALUE];
+ my @terms = ($first);
+ my $path = "\t $first\n";
+ my $col = 0;
+
+ for my $row (1 .. $#$triangle)
+ {
+ my $next_col = $triangle->[$row - 1][$col][INDEX];
+ my $direction = ($next_col == $col) ? 'Left' : (++$col, 'Right');
+
+ push @terms, $triangle->[$row][$col][VALUE];
+
+ $path .= sprintf "\t%-5s --> %s\n", $direction, $terms[-1];
+ }
+
+ my $sum = 0;
+ $sum += $_ for @terms;
+
+ printf "\nThe minimum path from top to bottom: %s = %s\n\n\tMove " .
+ "Element\n\t%s\n%s", join(' + ', @terms), $sum, '-' x 17, $path;
+
+ $sum == $triangle->[0][0][SUM] or die 'Logic error'; # Sanity check
+}
+
+#------------------------------------------------------------------------------
+sub parse_command_line
+#------------------------------------------------------------------------------
+{
+ my $args = scalar @ARGV;
+ $args == 1 or error( "Expected 1 command-line argument, found $args" );
+
+ my $str = $ARGV[0];
+ $str =~ / ^ \s* \[ .+ \] \s* $ /x or error( 'Invalid input array' );
+ $str =~ s/ ^ ( \s* \[ \s* \[ ) //x;
+ $str =~ s/ ( \] \s* \] \s* ) $ //x;
+
+ my @lines = split / \] \, \s+ \[ /x, $str;
+ my @triangle = map [ split /,/ ], @lines;
+
+ defined $triangle[0] && scalar @{ $triangle[0] } == 1
+ or error( 'Invalid first row' );
+
+ for my $row (0 .. $#triangle)
+ {
+ my $cols = scalar @{ $triangle[$row] };
+ my $row_ = $row + 1;
+
+ $cols == $row_
+ or error( sprintf 'Expected %d columns in row %d, found %d',
+ $row_, $row_, $cols );
+
+ for my $col (0 .. $cols - 1)
+ {
+ my $element = \$triangle[$row][$col];
+ $$element =~ s/ ^ \s+ //x;
+ $$element =~ s/ \s+ $ //x;
+ $$element =~ / ^ $RE{num}{real} $ /x
+ or error( qq[Element "$$element" is not a real number] );
+ }
+ }
+
+ return @triangle;
+}
+
+#------------------------------------------------------------------------------
+sub error
+#------------------------------------------------------------------------------
+{
+ my ($message) = @_;
+
+ die "ERROR: $message\n$USAGE";
+}
+
+###############################################################################
diff --git a/challenge-100/athanasius/raku/ch-2.raku b/challenge-100/athanasius/raku/ch-2.raku
new file mode 100644
index 0000000000..acfc9ec189
--- /dev/null
+++ b/challenge-100/athanasius/raku/ch-2.raku
@@ -0,0 +1,226 @@
+use v6d;
+
+###############################################################################
+=begin comment
+
+Perl Weekly Challenge 100
+=========================
+
+Task #2
+-------
+*Triangle Sum*
+
+Submitted by: Mohammad S Anwar
+
+You are given triangle array.
+
+Write a script to find the minimum path sum from top to bottom.
+
+When you are on index i on the current row then you may move to either index i
+or index i + 1 on the next row.
+
+Example 1:
+
+ Input: Triangle = [ [1], [2,4], [6,4,9], [5,1,7,2] ]
+ Output: 8
+
+ Explanation: The given triangle
+
+ 1
+ 2 4
+ 6 4 9
+ 5 1 7 2
+
+ The minimum path sum from top to bottom: 1 + 2 + 4 + 1 = 8
+
+ [1]
+ [2] 4
+ 6 [4] 9
+ 5 [1] 7 2
+
+Example 2:
+
+ Input: Triangle = [ [3], [3,1], [5,2,3], [4,3,1,3] ]
+ Output: 7
+
+ Explanation: The given triangle
+
+ 3
+ 3 1
+ 5 2 3
+ 4 3 1 3
+
+ The minimum path sum from top to bottom: 3 + 1 + 2 + 1 = 7
+
+ [3]
+ 3 [1]
+ 5 [2] 3
+ 4 3 [1] 3
+
+=end comment
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2021 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=begin comment
+
+Algorithm
+
+Although the path sum is from top to bottom, the algorithm for finding the min-
+imum path sum proceeds from bottom to top. For each row, starting at the second
+last and moving up, each element is summed with the smaller of the two elements
+immediately below it. When the top (i.e., first) row is reached, the final sum
+is guaranteed to be the minimum.
+
+Output
+
+If the constant $VERBOSE is True, the output is supplemented with a summary of
+the elements in the minimum path sum, followed by a table of moves (left or
+right) from top to bottom of the triangle.
+
+=end comment
+#==============================================================================
+
+my Bool constant $VERBOSE = True;
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+ "\nChallenge 100, Task #2: Triangle Sum (Raku)\n".put;
+}
+
+#==============================================================================
+sub MAIN
+(
+ Str:D $triangle #= String representing a non-empty triangular array
+ #= of numbers
+)
+#==============================================================================
+{
+ my Array[Real] @reals = get-array( $triangle );
+ my Array[Hash] @triangle = Array[Hash].new xx @reals.elems;
+
+ "Input: %s\n".printf: @reals.gist;
+
+ for 0 .. @reals[ @reals.end ].end -> UInt $col
+ {
+ @triangle[ @reals.end; $col ] =
+ {
+ VALUE => @reals[ @reals.end; $col ],
+ SUM => @reals[ @reals.end; $col ],
+ INDEX => Nil,
+ };
+ }
+
+ for (0 .. @reals.end - 1).reverse -> UInt $row
+ {
+ for 0 .. @reals[ $row ].end -> UInt $col
+ {
+ my Real $lhs = @triangle[ $row + 1; $col ]<SUM>;
+ my Real $rhs = @triangle[ $row + 1; $col + 1 ]<SUM>;
+ my Bool $left = $lhs <= $rhs;
+
+ @triangle[ $row; $col ] =
+ {
+ VALUE => @reals[ $row; $col ],
+ SUM => @reals[ $row; $col ] + ($left ?? $lhs !! $rhs),
+ INDEX => $left ?? $col !! $col + 1;
+ };
+ }
+ }
+
+ "Output: %s\n".printf: @triangle[ 0; 0 ]<SUM>;
+
+ show-path( @triangle ) if $VERBOSE;
+}
+
+#------------------------------------------------------------------------------
+sub show-path( Array:D[Array:D[Hash:D]] $triangle )
+#------------------------------------------------------------------------------
+{
+ my Real $first = $triangle[ 0; 0 ]<VALUE>;
+ my Real @terms = $first;
+ my Str $path = "\t $first\n";
+ my UInt $col = 0;
+
+ for 1 .. $triangle.end -> UInt $row
+ {
+ my UInt $next-col = $triangle[ $row - 1; $col ]<INDEX>;
+ my Str $direction = 'Left';
+
+ if $next-col != $col
+ {
+ $direction = 'Right';
+ ++$col;
+ }
+
+ @terms.push: $triangle[ $row; $col ]<VALUE>;
+
+ $path ~= "\t%-5s --> %s\n".sprintf: $direction, @terms[ *-1 ];
+ }
+
+ my Real $sum = @terms.sum;
+
+ ("\nThe minimum path from top to bottom: %s = %s\n\n\tMove Element" ~
+ "\n\t%s\n%s").printf: @terms.join(' + '), $sum, '-' x 17, $path;
+
+ $sum == $triangle[ 0; 0 ]<SUM> or die 'Logic error'; # Sanity check
+}
+
+#------------------------------------------------------------------------------
+sub get-array( Str:D $triangle --> Array:D[ Array:D[ Real:D ] ] )
+#------------------------------------------------------------------------------
+{
+ $triangle ~~ / ^ \s* \[ \s* \[ \s* (.*?) \s* \] \s* \] \s* $ /
+ or error( 'Invalid input array' );
+ my Str $string = $0.Str;
+ $string.chars > 0 or error( 'Empty array' );
+ my Str @rows = $string.split: / \] \, \s+ \[ /;
+ my Array[Real] @triangle;
+
+ try
+ {
+ @triangle = @rows.map:
+ { Array[Real].new( .split( ',', :skip-empty ).map: { .Real } ) };
+ }
+
+ $! and error( 'Found an element that is not a real number' );
+
+ for 0 .. @triangle.end -> UInt $row
+ {
+ my UInt $cols = @triangle[$row].elems;
+
+ $cols == $row + 1
+ or error( 'Expected %d column%s in row %d, found %d'.sprintf:
+ $row + 1, $row == 0 ?? '' !! 's', $row + 1, $cols );
+ }
+
+ return @triangle;
+}
+
+#------------------------------------------------------------------------------
+sub error( Str:D $message )
+#------------------------------------------------------------------------------
+{
+ "ERROR: $message".put;
+
+ USAGE();
+
+ exit;
+}
+
+#------------------------------------------------------------------------------
+sub USAGE()
+#------------------------------------------------------------------------------
+{
+ my Str $usage = $*USAGE;
+
+ $usage ~~ s/ ($*PROGRAM-NAME) /raku $0/;
+ $usage.put;
+}
+
+##############################################################################
generated by cgit (git 2.34.1) at 2026-07-03 12:56:24 +0000