diff options
| -rw-r--r-- | challenge-151/athanasius/perl/ch-1.pl | 260 | ||||
| -rw-r--r-- | challenge-151/athanasius/perl/ch-2.pl | 240 | ||||
| -rw-r--r-- | challenge-151/athanasius/raku/ch-1.raku | 257 | ||||
| -rw-r--r-- | challenge-151/athanasius/raku/ch-2.raku | 221 |
4 files changed, 978 insertions, 0 deletions
diff --git a/challenge-151/athanasius/perl/ch-1.pl b/challenge-151/athanasius/perl/ch-1.pl new file mode 100644 index 0000000000..98610549e3 --- /dev/null +++ b/challenge-151/athanasius/perl/ch-1.pl @@ -0,0 +1,260 @@ +#!perl + +############################################################################### +=comment + +Perl Weekly Challenge 151 +========================= + +TASK #1 +------- +*Binary Tree Depth* + +Submitted by: Mohammad S Anwar + +You are given binary tree. + +Write a script to find the minimum depth. + + The minimum depth is the number of nodes from the root to the nearest leaf + node (node without any children). + +Example 1: + + Input: '1 | 2 3 | 4 5' + + 1 + / \ + 2 3 + / \ + 4 5 + + Output: 2 + +Example 2: + + Input: '1 | 2 3 | 4 * * 5 | * 6' + + 1 + / \ + 2 3 + / \ + 4 5 + \ + 6 + + Output: 3 + +=cut +############################################################################### + +#--------------------------------------# +# Copyright © 2022 PerlMonk Athanasius # +#--------------------------------------# + +#============================================================================== +=comment + +Output +------ +The output is the minimum depth of any leaf node (see "Note on Tree Depth" +below). In addition, if $VERBOSE is set to a true value (the default), the +value/name of that leaf node is also shown. + +Note on Tree Depth +------------------ +According to Wikipedia [1]: + + The root node has depth zero, ... and a tree with only a single node (hence + both a root and leaf) has depth and height zero. + +However, from the Examples above it appears that the depth of node N is here +defined as the total number of nodes (including the root) in the path from root +to N. By this definition, the root node has depth 1. This is the definition +adopted in the solution below. + +Tree Representation +------------------- +A binary tree is here represented by an array of arrays, with indices as fol- +lows: + level width --> + | 0 0 (root) + V 1 0 1 + 2 0 1 2 3 + 3 0 1 2 3 4 5 6 7 + +Note that level l has width 2^l. For any arbitrary node N = (l, w): + + - N has left child (if any) L = (l + 1, 2w ) + - N has right child (if any) R = (l + 1, 2w + 1) + +and if l > 0: + + - N has parent P = (l - 1, ⌊w / 2⌋) + - N is a left child if w is even + - N is a right child if w is odd. + +Algorithm +--------- +Tree traversal is performed via a level-order walk (breadth-first search) which +proceeds until the first leaf node is found. The depth of this leaf node is the +required solution. + +Reference +--------- +[1] Wikipedia, "Tree (data structore)", Section 2: "Terminology" + https://en.wikipedia.org/wiki/Tree_(data_structure)#Terminology + +=cut +#============================================================================== + +use strict; +use warnings; +use Const::Fast; + +const my $VERBOSE => 1; +const my $EMPTY => '*'; +const my $USAGE => +qq[Usage: + perl $0 <binary_tree> + + <binary_tree> String: "|" separates levels, "*" = an empty node\n]; + +#------------------------------------------------------------------------------ +BEGIN +#------------------------------------------------------------------------------ +{ + $| = 1; + print "\nChallenge 151, Task #1: Binary Tree Depth (Perl)\n\n"; +} + +#============================================================================== +MAIN: +#============================================================================== +{ + my $str_rep = parse_command_line(); + + printf qq[Input: "%s"\n], $str_rep; + + my $tree = build_tree( $str_rep ); + + # Perform a level-order walk (breadth-first search) of the tree until the + # first leaf node is found + + L_OUTER: + for my $level (0 .. $#$tree) + { + for my $index (0 .. $#{ $tree->[ $level ] }) + { + my $node = $tree->[ $level ][ $index ]; + + if (defined $node) + { + if ($level == $#$tree || + (!defined $tree->[ $level + 1 ][ 2 * $index ] && + !defined $tree->[ $level + 1 ][ 2 * $index + 1 ])) + { + printf qq[Output: %d\n], $level + 1; + print qq[\nThe first leaf node is "$node"\n] if $VERBOSE; + + last L_OUTER; + } + } + } + } +} + +#------------------------------------------------------------------------------ +sub build_tree +#------------------------------------------------------------------------------ +{ + my ($str_rep) = @_; + my @rows = split m{ \| }x, $str_rep; + my $first_row = shift @rows; + my @tree; + push @tree, [ undef ]; + + add_root( $first_row, \@tree ); + + my $level = 1; + + for my $row (@rows) + { + add_children( $row, $level, \@tree ); + + ++$level; + } + + return \@tree; +} + +#------------------------------------------------------------------------------ +sub add_root +#------------------------------------------------------------------------------ +{ + my ($row, $tree) = @_; + + !defined $row || $row eq '' + and die "ERROR: Empty tree\n"; + + my @nodes = split ' ', $row; + + scalar @nodes == 0 + and die "ERROR: Empty tree\n"; + + scalar @nodes > 1 + and die "ERROR: Too many nodes for root\n"; + + $nodes[ 0 ] eq $EMPTY + and die "ERROR: Empty tree\n"; + + $tree->[ 0 ][ 0 ] = $nodes[ 0 ]; +} + +#------------------------------------------------------------------------------ +sub add_children +#------------------------------------------------------------------------------ +{ + my ($row, $level, $tree) = @_; + + my $width = 2 ** $level; + push @$tree, [ (undef) x $width ]; + my @nodes = split ' ', $row; + my $count = scalar @nodes; + + $count <= $width + or die "ERROR: Too many nodes ($count) for level $level\n"; + + my $col = 0; + + for my $node (@nodes) + { + if ($node ne $EMPTY) + { + defined $tree->[ $level - 1 ][ int( $col / 2 ) ] + or die qq[ERROR: Parentless child "$node"\n]; + + $tree->[ $level ][ $col ] = $node; + } + + ++$col; + } +} + +#------------------------------------------------------------------------------ +sub parse_command_line +#------------------------------------------------------------------------------ +{ + my $args = scalar @ARGV; + $args == 1 + or die "ERROR: Expected 1 command line argument, found $args\n$USAGE"; + + my $str_rep = $ARGV[ 0 ]; + $str_rep =~ s/ ^ \s+ //x; # Trim initial whitespace + $str_rep =~ s/ \s+ $ //x; # Trim trailing whitespace + $str_rep =~ s/ \s+ / /gx; # Remove superfluous whitespace + + return $str_rep; +} + +############################################################################### diff --git a/challenge-151/athanasius/perl/ch-2.pl b/challenge-151/athanasius/perl/ch-2.pl new file mode 100644 index 0000000000..0d918c0c03 --- /dev/null +++ b/challenge-151/athanasius/perl/ch-2.pl @@ -0,0 +1,240 @@ +#!perl + +############################################################################### +=comment + +Perl Weekly Challenge 151 +========================= + +TASK #2 +------- +*Rob The House* + +Submitted by: Mohammad S Anwar + +You are planning to rob a row of houses, always starting with the first and +moving in the same direction. However, you can’t rob two adjacent houses. + +Write a script to find the highest possible gain that can be achieved. + +Example 1: + + Input: @valuables = (2, 4, 5); + Output: 7 + + If we rob house (index=0) we get 2 and then the only house we can rob is house + (index=2) where we have 5. + So the total valuables in this case is (2 + 5) = 7. + +Example 2: + + Input: @valuables = (4, 2, 3, 6, 5, 3); + Output: 13 + + The best choice would be to first rob house (index=0) then rob house (index=3) + then finally house (index=5). + This would give us 4 + 6 + 3 = 13. + +=cut +############################################################################### + +#--------------------------------------# +# Copyright © 2022 PerlMonk Athanasius # +#--------------------------------------# + +#============================================================================== +=comment + +Output +------ +If $VERBOSE is set to a true value (the default), the output is followed by an +explanation showing the indices of the houses robbed, together with the sum of +their values. + +Assumptions +----------- +1. All house values are numbers greater than zero (i.e., every house is worth + robbing). +2. All house values are integers. (But note: if real values were to be allowed, + this would not affect the algorithm.) + +Steps +----- +Let the distance between houses be the difference of their indices. Since ad- +jacent houses (where the distance is 1) cannot be robbed, the minimum distance +between successive houses to rob is 2. + +Now consider a distance of 4. If, e.g., houses are a, b, c, d, e, then the dis- +tance from a to e is 4; but c could be robbed between a and e, without affect- +ing the algorithm from e onwards; and by assumption 1, robbing c will increase +the total gain. So a step of 4 is always inferior to 2 consecutive steps of 2. + +A similar argument holds for steps of 5 and above. So, step distances are lim- +ited to just 2 and 3. + +Algorithm +--------- +Note that the first house is always the first to be robbed, from which it fol- +lows that the second house - which is adjacent to the first - is never robbed. + +1. Each house is assigned a zero sum. (This "sum" will eventually represent the + maximum cumulative gain from robbing houses up to and including this house.) +2. The 3rd & 4th houses (indices 2 & 3) are initialised by assigning sums equal + to their own value plus the value of house 1 (index 0). This is the gain + from robbing house 1 followed by a step of 2 (house 3), and a step of 3 + (house 4). +3. Beginning with house 3 (index 2), and continuing until the 3rd last house, + steps of 2 and 3 are computed and the resulting cumulative gains compared + with the maximum already stored at the destination house. If the newly-com- + puted step results in a larger gain than the sum stored at the destination, + that sum is updated with the new maximum. In this way, when each house is + reached in this (step 3) traversal, the maximum gain to be made by robbing + houses up to this house has already been recorded against that house. +4. When the 3rd-last house has been processed, the sums for the remaining 2 + houses - the 2nd-last and the last - are compared. The larger sum is the + solution. + +=cut +#============================================================================== + +use strict; +use warnings; +use Const::Fast; +use Regexp::Common qw( number ); + +const my $VERBOSE => 1; +const my $USAGE => +"Usage: + perl $0 [<valubles> ...] + + [<valubles> ...] Positive integers: values of valubles\n"; + +#------------------------------------------------------------------------------ +BEGIN +#------------------------------------------------------------------------------ +{ + $| = 1; + print "\nChallenge 151, Task #2: Rob The House (Perl)\n\n"; +} + +#============================================================================== +package House +#============================================================================== +{ + use Class::Tiny qw( value sum path ); +} + +#============================================================================== +MAIN: +#============================================================================== +{ + my $values = parse_command_line(); + my $num_houses = scalar @$values; + + printf "Input: \@valuables = (%s)\n", join ', ', @$values; + + my $best_sum = $values->[ 0 ]; # First value + my $best_path = [ 0 ]; # House indices + + ($best_sum, $best_path) = find_best_path( $values ) if $num_houses > 2; + + print "Output: $best_sum\n"; + + if ($VERBOSE) + { + if ($num_houses <= 2) + { + print "\nRobbing house 0 yields $best_sum\n"; + } + else + { + printf "\nRobbing houses (%s) yields (%s) = %d\n", + join( ', ', @$best_path ), + join( ' + ', @$values[ @$best_path ] ), $best_sum; + } + } +} + +#------------------------------------------------------------------------------ +sub find_best_path +#------------------------------------------------------------------------------ +{ + my ($values) = @_; + my @houses = init_houses( $values ); + + for my $i (2 .. $#$values - 2) + { + for my $j ($i + 2, $i + 3) + { + if ($j <= $#$values) + { + my $new_sum = $houses[ $i ]->sum + + $houses[ $j ]->value; + + if ($new_sum > $houses[ $j ]->sum) + { + $houses[ $j ]->sum( $new_sum ); + $houses[ $j ]->path( [ $houses[ $i ]->path->@*, $j ] ); + } + } + } + } + + my $best_i = $houses[ -2 ]->sum >= + $houses[ -1 ]->sum ? -2 : -1; + + return ($houses[ $best_i ]->sum, + $houses[ $best_i ]->path); +} + +#------------------------------------------------------------------------------ +sub init_houses +#------------------------------------------------------------------------------ +{ + my ($values) = @_; + my @houses; + push @houses, House->new( value => $_, sum => 0, path => [] ) for @$values; + + for my $i (2, 3) + { + if ($i <= $#$values) + { + $houses[ $i ]->sum( $houses[ 0 ]->value + + $houses[ $i ]->value ); + + $houses[ $i ]->path( [ 0, $i ] ); + } + } + + return @houses; +} + +#------------------------------------------------------------------------------ +sub parse_command_line +#------------------------------------------------------------------------------ +{ + scalar @ARGV > 0 or error( 'Expected at least one command ' . + 'line argument, found none' ); + + my @valubles = @ARGV; + + for (@valubles) + { + / ^ $RE{num}{int} $ /x or error( qq["$_" is not a valid integer] ); + + $_ > 0 or error( qq["$_" is not positive] ); + } + + return \@valubles; +} + +#------------------------------------------------------------------------------ +sub error +#------------------------------------------------------------------------------ +{ + my ($message) = @_; + + die "ERROR: $message\n$USAGE"; +} + +############################################################################### diff --git a/challenge-151/athanasius/raku/ch-1.raku b/challenge-151/athanasius/raku/ch-1.raku new file mode 100644 index 0000000000..95c7ee3c87 --- /dev/null +++ b/challenge-151/athanasius/raku/ch-1.raku @@ -0,0 +1,257 @@ +use v6d; + +############################################################################### +=begin comment + +Perl Weekly Challenge 151 +========================= + +TASK #1 +------- +*Binary Tree Depth* + +Submitted by: Mohammad S Anwar + +You are given binary tree. + +Write a script to find the minimum depth. + + The minimum depth is the number of nodes from the root to the nearest leaf + node (node without any children). + +Example 1: + + Input: '1 | 2 3 | 4 5' + + 1 + / \ + 2 3 + / \ + 4 5 + + Output: 2 + +Example 2: + + Input: '1 | 2 3 | 4 * * 5 | * 6' + + 1 + / \ + 2 3 + / \ + 4 5 + \ + 6 + + Output: 3 + +=end comment +############################################################################### + +#--------------------------------------# +# Copyright © 2022 PerlMonk Athanasius # +#--------------------------------------# + +#============================================================================== +=begin comment + +Output +------ +The output is the minimum depth of any leaf node (see "Note on Tree Depth" +below). In addition, if $VERBOSE is set to True (the default), the value/name +of that leaf node is also shown. + +Note on Tree Depth +------------------ +According to Wikipedia [1]: + + The root node has depth zero, ... and a tree with only a single node (hence + both a root and leaf) has depth and height zero. + +However, from the Examples above it appears that the depth of node N is here +defined as the total number of nodes (including the root) in the path from root +to N. By this definition, the root node has depth 1. This is the definition +adopted in the solution below. + +Tree Representation +------------------- +A binary tree is here represented by an array of arrays, with indices as fol- +lows: + level width --> + | 0 0 (root) + V 1 0 1 + 2 0 1 2 3 + 3 0 1 2 3 4 5 6 7 + +Note that level l has width 2^l. For any arbitrary node N = (l, w): + + - N has left child (if any) L = (l + 1, 2w ) + - N has right child (if any) R = (l + 1, 2w + 1) + +and if l > 0: + + - N has parent P = (l - 1, ⌊w / 2⌋) + - N is a left child if w is even + - N is a right child if w is odd. + +Algorithm +--------- +Tree traversal is performed via a level-order walk (breadth-first search) which +proceeds until the first leaf node is found. The depth of this leaf node is the +required solution. + +Reference +--------- +[1] Wikipedia, "Tree (data structore)", Section 2: "Terminology" + https://en.wikipedia.org/wiki/Tree_(data_structure)#Terminology + +=end comment +#============================================================================== + +my Bool constant $VERBOSE = True; +my Str constant $EMPTY = '*'; + +#------------------------------------------------------------------------------ +BEGIN +#------------------------------------------------------------------------------ +{ + "\nChallenge 151, Task #1: Binary Tree Depth (Raku)\n".put; +} + +#============================================================================== +sub MAIN +( + Str:D $binary-tree #= String: "|" separates levels, "*" = an empty node +) +#============================================================================== +{ + my Str $str-rep = $binary-tree; + $str-rep ~~ s/ ^ \s+ //; # Trim initial whitespace + $str-rep ~~ s/ \s+ $ //; # Trim trailing whitespace + $str-rep ~~ s:g/ \s+ / /; # Remove superfluous whitespace + + qq[Input: "$str-rep"].put; + + my Array[Str] @tree = build-tree( $str-rep ); + + # Perform a level-order walk (breadth-first search) of the tree until the + # first leaf node is found + + L-OUTER: + for 0 .. @tree.end -> UInt $level + { + for 0 .. @tree[ $level ].end -> UInt $index + { + my Str $node = @tree[ $level ][ $index ]; + + if $node.defined + { + if $level == @tree.end || + (!@tree[ $level + 1 ][ 2 * $index ].defined && + !@tree[ $level + 1 ][ 2 * $index + 1 ].defined) + { + qq[Output: %d\n].printf: $level + 1; + qq[\nThe first leaf node is "$node"].put if $VERBOSE; + + last L-OUTER; + } + } + } + } +} + +#------------------------------------------------------------------------------ +sub build-tree( Str:D $str-rep --> Array:D[Array:D[Str]] ) +#------------------------------------------------------------------------------ +{ + my Str @rows = $str-rep.split: '|', :skip-empty; + my Str $first-row = @rows.shift; + my Array[Str] @tree; + + @tree.push: Array[Str].new: Nil; + + add-root( $first-row, @tree ); + + my UInt $level = 1; + + for @rows -> Str $row + { + add-children( $row, $level, @tree ); + + ++$level; + } + + return @tree; +} + +#------------------------------------------------------------------------------ +sub add-root( Str:D $row, Array:D[Array:D[Str]] $tree ) +#------------------------------------------------------------------------------ +{ + !$row.defined || $row eq '' + and error( 'Empty tree' ); + + my Str @nodes = $row.split: / \s+ /, :skip-empty; + + +@nodes == 0 + and error( 'Empty tree' ); + + +@nodes > 1 + and error( 'Too many nodes for root' ); + + @nodes[ 0 ] eq $EMPTY + and error( 'Empty tree' ); + + $tree[ 0 ][ 0 ] = @nodes[ 0 ]; +} + +#------------------------------------------------------------------------------ +sub add-children( Str:D $row, UInt:D $level, Array:D[Array:D[Str]] $tree ) +#------------------------------------------------------------------------------ +{ + my UInt $width = 2 ** $level; + + $tree.push: Array[Str].new: Nil xx $width; + + my Str @nodes = $row.split: / \s+ /, :skip-empty; + + +@nodes <= $width + or error( "Too many nodes ({ +@nodes }) for level $level\n" ); + + my UInt $col = 0; + + for @nodes -> Str $node + { + if $node ne $EMPTY + { + $tree[ $level - 1 ][ ( $col / 2 ).floor ].defined + or error( qq[Parentless child "$node"\n] ); + + $tree[ $level ][ $col ] = $node; + } + + ++$col; + } +} + +#------------------------------------------------------------------------------ +sub error( Str:D $message ) +#------------------------------------------------------------------------------ +{ + "ERROR: $message".put; + + exit; +} + +#------------------------------------------------------------------------------ +sub USAGE() +#------------------------------------------------------------------------------ +{ + my Str $usage = $*USAGE; + + $usage ~~ s/ ($*PROGRAM-NAME) /raku $0/; + + $usage.put; +} + +############################################################################## diff --git a/challenge-151/athanasius/raku/ch-2.raku b/challenge-151/athanasius/raku/ch-2.raku new file mode 100644 index 0000000000..acc790552f --- /dev/null +++ b/challenge-151/athanasius/raku/ch-2.raku @@ -0,0 +1,221 @@ +use v6d; + +############################################################################### +=begin comment + +Perl Weekly Challenge 151 +========================= + +TASK #2 +------- +*Rob The House* + +Submitted by: Mohammad S Anwar + +You are planning to rob a row of houses, always starting with the first and +moving in the same direction. However, you can’t rob two adjacent houses. + +Write a script to find the highest possible gain that can be achieved. + +Example 1: + + Input: @valuables = (2, 4, 5); + Output: 7 + + If we rob house (index=0) we get 2 and then the only house we can rob is house + (index=2) where we have 5. + So the total valuables in this case is (2 + 5) = 7. + +Example 2: + + Input: @valuables = (4, 2, 3, 6, 5, 3); + Output: 13 + + The best choice would be to first rob house (index=0) then rob house (index=3) + then finally house (index=5). + This would give us 4 + 6 + 3 = 13. + +=end comment +############################################################################### + +#--------------------------------------# +# Copyright © 2022 PerlMonk Athanasius # +#--------------------------------------# + +#============================================================================== +=begin comment + +Output +------ +If $VERBOSE is set to True (the default), the output is followed by an explana- +tion showing the indices of the houses robbed, together with the sum of their +values. + +Assumptions +----------- +1. All house values are numbers greater than zero (i.e., every house is worth + robbing). +2. All house values are integers. (But note: if real values were to be allowed, + this would not affect the algorithm.) + +Steps +----- +Let the distance between houses be the difference of their indices. Since ad- +jacent houses (where the distance is 1) cannot be robbed, the minimum distance +between successive houses to rob is 2. + +Now consider a distance of 4. If, e.g., houses are a, b, c, d, e, then the dis- +tance from a to e is 4; but c could be robbed between a and e, without affect- +ing the algorithm from e onwards; and by assumption 1, robbing c will increase +the total gain. So a step of 4 is always inferior to 2 consecutive steps of 2. + +A similar argument holds for steps of 5 and above. So, step distances are lim- +ited to just 2 and 3. + +Algorithm +--------- +Note that the first house is always the first to be robbed, from which it fol- +lows that the second house - which is adjacent to the first - is never robbed. + +1. Each house is assigned a zero sum. (This "sum" will eventually represent the + maximum cumulative gain from robbing houses up to and including this house.) +2. The 3rd & 4th houses (indices 2 & 3) are initialised by assigning sums equal + to their own value plus the value of house 1 (index 0). This is the gain + from robbing house 1 followed by a step of 2 (house 3), and a step of 3 + (house 4). +3. Beginning with house 3 (index 2), and continuing until the 3rd last house, + steps of 2 and 3 are computed and the resulting cumulative gains compared + with the maximum already stored at the destination house. If the newly-com- + puted step results in a larger gain than the sum stored at the destination, + that sum is updated with the new maximum. In this way, when each house is + reached in this (step 3) traversal, the maximum gain to be made by robbing + houses up to this house has already been recorded against that house. +4. When the 3rd-last house has been processed, the sums for the remaining 2 + houses - the 2nd-last and the last - are compared. The larger sum is the + solution. + +=end comment +#============================================================================== + +my Bool constant $VERBOSE = True; + +subset Pos of Int where * > 0; + +#------------------------------------------------------------------------------ +BEGIN +#------------------------------------------------------------------------------ +{ + "\nChallenge 151, Task #2: Rob The House (Raku)\n".put; +} + +#============================================================================== +class House +#============================================================================== +{ + has Pos $.value; + has UInt $.sum is rw; + has Array[UInt] $.path is rw; +} + +#============================================================================== +sub MAIN +( + *@valubles where { .all ~~ Pos:D && .elems > 0 } #= Positive integers: + #= values of valubles +) +#============================================================================== +{ + my Pos $num-houses = +@valubles; + + "Input: @valuables = ({ @valubles.join: ', ' })".put; + + my Pos $best-sum = @valubles[ 0 ]; # First value + my Array[UInt] $best-path = Array[UInt].new: 0; # House indices + + ($best-sum, $best-path) = find-best-path( @valubles ) if $num-houses > 2; + + "Output: $best-sum".put; + + if $VERBOSE + { + if $num-houses <= 2 + { + "\nRobbing house 0 yields $best-sum".put; + } + else + { + "\nRobbing houses (%s) yields (%s) = %d\n".printf: + $best-path.join( ', ' ), + @valubles[ @$best-path ].join( ' + ' ), + $best-sum; + } + } +} + +#------------------------------------------------------------------------------ +sub find-best-path( Array:D[Pos:D] $values --> List:D[Pos:D, Array:D[UInt:D]] ) +#------------------------------------------------------------------------------ +{ + my House @houses = init-houses( $values ); + + for 2 .. $values.end - 2 -> UInt $i + { + for $i + 2, $i + 3 -> UInt $j + { + if $j <= $values.end + { + my Pos $new-sum = @houses[ $i ].sum + + @houses[ $j ].value; + + if $new-sum > @houses[ $j ].sum + { + @houses[ $j ].sum = $new-sum; + @houses[ $j ].path = @houses[ $i ].path; + @houses[ $j ].path.push: $j; + } + } + } + } + + my UInt $best-i = @houses[ *-2 ].sum >= + @houses[ *-1 ].sum ?? @houses.end - 1 !! @houses.end; + + return @houses[ $best-i ].sum, + @houses[ $best-i ].path; +} + +#------------------------------------------------------------------------------ +sub init-houses( Array:D[Pos:D] $values --> Array:D[House:D] ) +#------------------------------------------------------------------------------ +{ + my House @houses; + + @houses.push: House.new: value => $_, sum => 0, path => Array[UInt].new + for @$values; + + for 2, 3 -> UInt $i + { + if $i <= $values.end + { + @houses[ $i ].sum = @houses[ 0 ].value + + @houses[ $i ].value; + + @houses[ $i ].path.push: 0, $i; + } + } + + return @houses; +} + +#------------------------------------------------------------------------------ +sub USAGE() +#------------------------------------------------------------------------------ +{ + my Str $usage = $*USAGE; + + $usage ~~ s/ ($*PROGRAM-NAME) /raku $0/; + + $usage.put; +} + +############################################################################## |