( …continues from previous week. )
Welcome to the Perl review pages for Week 151 of The Weekly Challenge! Here we will take the time to discuss the submissions offered up by the team, factor out some common methodologies that came up in those solutions, and highlight some of the unique approaches and unusual code created.
●︎ Why do we do these challenges?
I suppose any reasonable answer to that question would be from a field as wide ranging and varied as the people who choose to join the team. One thing, though, is clear: it’s not a competition, and there are no judges, even if there is a “prize” of sorts. About that – I think of it more as an honorarium periodically awarded to acknowledge the efforts we make towards this strange goal. So there’s no determination to find the fastest, or the shortest, or even, in some abstract way, the best way to go about things, although I’m certain the participants have their own aspirations and personal drives. As Perl is such a wonderfully expressive language, this provides quite a bit of fodder to the core idea of TMTOWTDI, producing a gamut of varied techniques and solutions.
Even the tasks themselves are often open to a certain amount of discretionary interpretation. What we end up with is a situation where each participant is producing something in the manner they find the most interesting or satisfying. Some team members focus on carefully crafted complete applications, thoroughly vetting input data and handling every use case they can think up. Others choose to apply themselves to the logic of the underlying puzzle and making it work in the most elegant way they can. Some eschew modules they would ordinarily reach for, others embrace them, bringing to light wheels perhaps invented years ago that happen to exactly solve the problem in front of them today.
I’ve been considering this question for some time and have found one binding commonality between all of us out solving these challenges each week, in that however we normally live our lives, the task in front of us more than likely has nothing to do with any of that. And I think this has great value. We all do what we do, in the real world, and hopefully we do it well. The Weekly Challenge provides us with an opportunity to do something germane to that life yet distinctly different; if we only do the things we already know how to do then we will only do the same things over and over. This is where the “challenge” aspect comes into play.
So we can consider The Weekly Challenge as providing a problem space outside of our comfort zone, as far out from that comfort as we wish to take things. From those reaches we can gather and learn things, pick and choose and bring what we want back into our lives. Personally, I think that’s what this whole thing is about. YMMV.
And that, my friends, is why I’m here, to try and figure out ways to do just that.
So, here we are then. I’m ready — let’s get to it and see what we can find.
For Additional Context…
before we begin, you may wish to revisit either the pages for the original tasks or the summary recap of the challenge. But don’t worry about it, the challenge text will be repeated and presented as we progress from task to task.
Oh, and one more thing before we get started:
Getting in Touch with Us
Email › Please feel free to email me (Colin) with any feedback, notes, clarifications or whatnot about this review.
GitHub › Submit a pull request to us for any issues you may find with this page.
Twitter › Join the discussion on Twitter!
I’m always curious as to what the people think of these efforts. Everyone here at the PWC would like to hear any feedback you’d like to give.
• Task 1 • Task 2 • BLOGS •
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
about the solutions
Abigail, Alexander Pankoff, Athanasius, Colin Crain, Dave Jacoby, Duncan C. White, E. Choroba, Flavio Poletti, James Smith, Jorg Sommrey, Laurent Rosenfeld, Lubos Kolouch, Matthew Neleigh, Mohammad S Anwar, Peter Campbell Smith, Roger Bell_West, Simon Green, Ulrich Rieke, and W. Luis Mochan
In weeks past we’ve explored a great deal around the topic of binary trees. We’ve looked at maximum diameters, depths, and accessed various nodes, and processed them both breadth- and depth-first. At this point many long-term members of the team have developed complex libraries of tree objects and methods to draw on. And with the first task this week we return to this familiar territory with a seemingly innocent, not-too-difficult task, looking for the closest leaf node to the root.
Or, to put a darker, Grimms Fairy Tales spin on it, a pair of missing children.
One key difference to this particular task, generally left ambiguous in previous challenges, is that the input is specified. Or rather, that the input format is specified — in the examples we are given a particular stringified serial encoding.
The rules for the encoding are not specified, which could be regarded as part of the puzzle for anyone who did not immediately recognise it. The tree data is recorded as a breadth-first traversal, with individual levels delineated by vertical pipes. Within each level, a symbol for a null node is required to fix placements unambiguously, and this format chooses an asterisk. Other than that, items and delimiters are separated by whitespace, apparently with multiple spaces allowed for clarity. We don’t have enough examples to determine whether there are specific rules for multiple spaces, but it doesn’t seem to affect our parsing in any way anyways, so I’d say it doesn’t really matter.
Null nodes at the end of the tree can be inferred and are hence optional. What’s not clear, however is whether the same rule would apply to interior levels, although with the vertical pipe level delimiters these too could be inferred. We don’t have any examples of this, however.
There were an unusually large number of improperly working submissions this week, which was, not to put too fine a point on it, a little weird.
COUNTING the RINGS
Athanasius, Alexander Pankoff, Mohammad S Anwar, Jorg Sommrey, Dave Jacoby, Colin Crain, Roger Bell_West, Abigail, and Flavio Poletti
Here’s the start of a theory:
There turned out to be quite a bit of ambiguity remaining in the task definition, specifically as to what, exactly, a leaf node is in the context of a binary tree. A binary tree is nominally a tree structure where a node has at most two children, and a leaf as a node without children. However one Set Theory definition of a binary tree is a recursive structure of nodes as tuples, with each tuple containing a value and two child tuples, which may themselves be a null set. The precise meaning of the idea of a null in this definition varies, however.
The question arises between whether a node is null, or whether the value of a node is null. Ultimately this leads to the question of whether a null node can logically be itself a leaf node.
To which I say: “You have to be f’ing kidding me”. However if you define a binary tree as a fixed structure with each node containing exactly two children this follows. I am, shall we say, highly disinclined to agree with this interpretation, but it seems implicit to many of the results we saw. But if a null child node is still a node, then by definition all nodes will have children, and the leaf nodes will be simply the furthest extant of whatever full structure we’ve defined, or become meaningless altogether.
Or, you know, a group of otherwise very capable people has screwed up en masse.
To explain my point of view, consider the following tree:
Input: '1 | 2 3 | 4 * * 5 | * 6 * * * * 7 8'
┏━━━━━━┫1┣━━━━━━┓
┃ ┃
┏━━┫2┃ ┃3┣━━┓
┃ ┃
┃4┣┓ ┏┫5┣┓
┃ ┃ ┃
┃6┃ ┃7┃ ┃8┃
Many solutions return the answer 3, instead of 4. It does not appear to be an off-by-one error. I eventually had to run this test data on every single submission to see what was happening. I took this to be my shibboleth. You have draw the line somewhere.
additional languages: Raku
We’ll let the monk start things off today. Drawing a direct inference from the input format, they first slice the string into an array of arrays, one level each. In this form each level will have 2level nodes, 0-indexed. Traversing each level in turn, the childen for a node at a given index will always be located on the following level at postions 2 × index and 2 × index + 1. Thus we can easily look up the children and check for their existence. At the first double-miss, we have found a leaf node and we note the level we’re on.
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;
}
}
}
}
At the other end of the complexity spectrum, Alexander chooses multiple layers of abstraction to structure his parsed input. A tokenizer is defined, with a TokenType class and three subclasses for separators, values and placeholders. Parsed and labeled, the list of tokens is then handed to the main minimum_binary_tree_depth() routine.
The tokens are systematically processed, ratcheting a level counter as they go, counting by powers of 2 and filling in an array of arrays with the tree data. This tree is then used to find the first leaf.
As I said, lots of abstraction. Kind of like building a hovercraft because you needed to go to the corner store.
And hovercrafts, as everyone knows, are very cool.
while (@tokens) {
push @$tree, [];
my $num_elems = 2**$depth;
for ( my $i = 0 ; $i < $num_elems ; $i++ ) {
if ( !@tokens || $tokens[0]->isa('SeparatorToken') ) {
## fill row with dummy placeholder tokens.
unshift @tokens,
map { PlaceHolderToken->new(-1) }
0 .. ( $num_elems - 1 - $i ); # Dummy Token
}
my $cur = shift @tokens;
if ( $cur->isa('ValueToken') ) {
if ( $depth && !defined( $tree->[-2][ int( $i / 2 ) ] ) ) {
die join( " ",
"Missing parent for node with value",
$cur->{lexeme},
"at position",
$cur->pos_human_readable(),
"in input\n" );
}
push @{ $tree->[-1] }, $cur->{lexeme};
}
elsif ( $cur->isa('PlaceHolderToken') ) {
if ( $i % 2
&& !defined $tree->[-1][-1]
&& ( !$depth || defined $tree->[-2][ int( $i / 2 ) ] ) )
{
return $depth;
}
push @{ $tree->[-1] }, undef;
## do nothing
}
}
$depth += 1;
# handle optional separatortoken
if ( @tokens && $tokens[0]->isa("SeparatorToken") ) {
shift @tokens;
}
}
return $depth;
Mohammad has curiously chosen to buck his own input format suggestion, defining individual trees as nested Node objects, hashes with 3 keys for left and right children and a value. A recursive routine traverses the structure depth-first, returning the smallest result as the recursion collapses at whatever maximum depth is found.
sub min_depth {
my ($node) = @_;
return 0 unless defined $node;
my $min_left = min_depth($node->{left});
my $min_right = min_depth($node->{right});
return $min_right + 1 unless defined $node->{left};
return $min_left + 1 unless defined $node->{right};
return ($min_left > $min_right)
?
($min_right + 1)
:
($min_left + 1);
}
Jorg imports the Graph module to supply a framework for his tree. After all, a tree is a directed graph, linked from top to bottom. The thing about thinking of the tree as a graph is it allows the use of graph theory techniques to find our minimum depth. An intermediate structure is created of shortest paths from the root to each node, and from this the minimum value is taken for all of these paths that travel to a “sink vertex”, that is to say a vertex that does not connect forward to any other vertex.
A careful reading will show we’re talking about leaf nodes, just using slightly different language.
Here’s the core logic, after we’ve constructed our graph:
# Find the minimum depth in a tree-like graph from its root.
sub min_depth ($g) {
# Use zero as the depth of an empty tree.
return 0 unless $g->has_vertices;
# Find the (unique) root vertex.
my $root = ($g->source_vertices)[0];
# Use one as the depth of a root-only tree. (An isolated vertex
# does not count as a source vertex.)
return 1 unless defined $root;
# Create the tree of Single-Source Shortest Paths originating at the
# root vertex.
my $sptg = $g->SPT_Dijkstra($root);
# Find the shortest path from the root to all leafs (i.e. sink
# vertices) and take the minimum thereof. As the depth is defined
# here as the number of vertices in the path instead of the number
# of edges, we need to add one for the desired result.
1 + min map $sptg->get_vertex_attribute($_, 'weight'),
$sptg->sink_vertices;
}
blog writeup: Dr. Metropolis and His Amazing MANIAC Machine!: The Weekly Challenge #151 | Committed to Memory
As way of a preface, Dave in his blog writeup introduces us to one Dr. Nicholas Metropolis, mathematician and inventor of the Monte Carlo method. He sounds like a fascinating character, although bearing only a passing resemblance to Rotwang, the protagonist on the 1927 Fritz Lang film bearing the same name.
Incidentally, the robot Maria in Metropolis was referred to by Rotwang as a Maschinenmensch, which obviously inspired Die Mensch-Maschine, the 1978 classic recording by the Kraut-rock synthesizer band Kraftwerk.
The world, as you may have noticed, is a very interconnected place.
By way of his solution, Dave parses the input to construct Node objects into a proper tree structure. The nodes themselves contain an upwards parent link, allowing for a node_depth() method that can traverse upwards, counting until it finds the root. A similar method peeks at the children to see whether it is given node is a leaf.
The nodes are kept in a hash, and the keys to the hash are filtered to find leaf nodes, blocking the root should itself be a leaf. Then each of these are mapped to their depth and the depths sorted to find the minimum.
The core:
my @input = split m{\s*\|\s*}, $input; # basis for all the rows
my %nodes =
map { $_ => Node->new($_) }
grep { /\d+/ } split m{\D}, $input; # create all the nodes
# here's where the tree is made
for my $r (@input) {
my $w = -1 + 2**$e;
my @i = split /\s+/, $r;
my @row = map { $i[$_] || '*' } 0 .. $w;
push @rows, \@row;
for my $n ( 0 .. $w ) {
my $val = $row[$n];
my $node = $nodes{$val};
my $lr = $n % 2;
my $p = ' ';
my $u = ' ';
if ( $e > 0 ) { $u = int( $n / 2 ); $p = $rows[ $e - 1 ][$u]; }
my $parent = $nodes{$p};
if ( defined $node && defined $parent ) {
my $v = $node->value;
if ($lr) { $nodes{$p}->left( $nodes{$v} ); }
else { $nodes{$p}->right( $nodes{$v} ); }
}
}
$e++;
}
my @o = # REMEMBER, READ THIS BACK TO FRONT
sort { $a <=> $b } # sort low to high
map { 1 + node_depth($_) } # 1 + node_depth = number of nodes involved
grep { ! $_->is_root } # each node is not a root
grep { $_->is_leaf } # each node is a leaf
map { $nodes{$_} } # turn it into nodes
keys %nodes; # the keys to the nodes
return $o[0]; # and we pull the first one, which should be
additional languages: Raku
blog writeup: No Diving in the Shallow End - Programming Excursions in Perl and Raku
For my own solution I chose simplicity, constructing a list-processing chain to split the input on whitespace and remove the pipes, mapping the asterisks to undef and preserving the positional data as one long structured array.
Iterating through the indices of this array a second counter is maintained to ratchet through the level count, counting out 2 × level - 1 elements at a time. Done this way the children for a given index n will be found according to well-defined relationships that can be checked as we go. When we find the first element without children we return the current level count.
my $input = shift ;
say mindepth( parse( $input ) ) if defined $input;;
sub parse ( $input ) {
return map { $_ eq '*' ? undef : $_ }
grep { $_ ne '|' }
split ' ', $input;
}
sub mindepth ( @tree ) {
my $level = 1 ;
my $count = 0 ;
for my $idx ( 0 .. $#tree ) {
return $level if ( defined $tree[$idx]
and not defined $tree[$idx * 2 + 1]
and not defined $tree[$idx * 2 + 2] ) ;
$level++ and $count = 0 if ++$count == 2 ** ($level-1) ;
}
}
additional languages: Javascript, Kotlin, Lua, Postscript, Python, Raku, Ruby, Rust
blog writeup: RogerBW’s Blog: The Weekly Challenge 151: Robbing Depth
Roger brings us two routines: str2tree() to parse his input, and mindepth() to walk the structure produced and find the minimum depth. The tree itself is a flattened breadth-first traversal, with 0s substituted for the null nodes. This format will not allow a node value to be 0, but accepting that it does make the structure easy to visualize, and null still translates to false in comparisons. It’s a reasonable tradeoff as long as you remember it’s there.
To find the leaf nodes we walk the indices up from 0, and we look for children by bit-shifting the index left one place. A set of sorting criteria are established: if a node is 0 it cannot be a leaf, and if its first child is over the limit of the array bounds it must be leaf. Otherwise we calculate the child positions and examine them.
Proceeding this way from left-to-right we find the first leaf and count bit-shifts back rightward to get the level. I think the bit-shifting adds a pleasing elegance to the technique.
sub str2tree {
my $st=shift;
my @o;
my $d=0;
my $p=0;
foreach my $e (split ' ',$st) {
if ($e eq '|') {
$d++;
$p=0;
my $m=(1<<($d+1))-1;
if (scalar @o < $m) {
push @o,(0) x ($m - scalar @o);
}
} else {
my $y=0;
if ($e ne '*') {
$y=0+$e;
}
my $i=(1<<$d) -1 +$p;
$o[$i]=$y;
$p++;
}
}
return \@o;
}
sub mindepth {
my $tree = shift;
my $firstleaf=scalar @{$tree};
foreach my $i (0..$#{$tree}) {
if ($tree->[$i]==0) {
next;
} elsif (($i+1) << 1 >= scalar @{$tree}) {
$firstleaf=$i;
last;
} else {
my $ni=(($i+1) << 1)-1;
if ($tree->[$ni]==0 && $tree->[$ni+1]==0) {
$firstleaf=$i;
last;
}
}
}
my $t=$firstleaf+1;
my $d=0;
while ($t > 0) {
$t >>= 1;
$d++;
}
additional languages: Awk, Bash, C, Lua, Node, Python, Ruby
Abigail economically breaks the input into an array-of-arrays at the vertical pipes, and then walks each level looking ahead for the first instance of two missing children. With Hasel and Gretel locked in a hut in the woods, we have found the first leaf and the level index is adjusted and returned.
It’s a dark tale, but compact and to-the-point.
TREE: while (<>) {
chomp;
my @tree = map {[map {$_ ne '*'} /\S+/g]} split /\|/;
foreach my $d (keys @tree) {
foreach my $i (keys @{$tree [$d]}) {
if ($tree [$d] [$i] && !$tree [$d + 1] [2 * $i]
&& !$tree [$d + 1] [2 * $i + 1]) {
say $d + 1;
next TREE;
}
}
}
}
additional languages: Raku
blog writeup: PWC151 - Binary Tree Depth - ETOOBUSY
Flavio has arrived at a very similarly concise solution, solving the problem in two parts: as the manipulation of a string into a multidimensional array and then checking from place-to-place to find the first answer. In one way you can consider the talk of a tree to be a deceptive red-herring, but viewed another the serialized tree is a real tree just as good as any other, merely presented in an unusually flat manner. Like a number, the representation does not alter what it is. And it is a tree. When i run the script here it is a tree grown in Brooklyn.
my @levels = map { [ split m{\s+}mxs ] } split m{\s*\|\s*}mxs, $input;
for my $depth (1 .. $#levels) {
for my $i (0 .. $levels[$depth - 1]->$#*) {
next if $levels[$depth - 1][$i] eq '*'
|| ($levels[$depth][$i * 2] // '*') ne '*'
|| ($levels[$depth][$i * 2 + 1] // '*') ne '*';
say $depth;
exit 0;
}
}
say scalar @levels;
Blogs and Additional Submissions in Guest Languages for Task 1:
blog writeup: Perl Weekly Challenge #151
additional languages: Raku
blog writeup: Perl Weekly Challenge 151: Binary tree Depth
additional languages: Php, Python
blog writeup: Locate a leaf and rob a road
additional languages: Python
blog writeup: Weekly Challenge 151
additional languages: C++, Haskell, Raku
blog writeup: Perl Weekly Challenge 151 – W. Luis Mochán
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.
about the solutions
Abigail, Alexander Pankoff, Athanasius, Cheok-Yin Fung, Colin Crain, Dave Jacoby, Duncan C. White, E. Choroba, Flavio Poletti, James Smith, Jorg Sommrey, Lubos Kolouch, Matthew Neleigh, Peter Campbell Smith, Roger Bell_West, Simon Green, Ulrich Rieke, and W. Luis Mochan
So I’ve been hearing doomsayer talk for years about the decline of Perl, but have we truly sunk to the point where we’re burgling houses now? Oh dear.
Well it’s just another example of doing what we must to survive in this challenging world. We might as well be practical about it.
We are however burdened by some unusual conditions in our house-breaking: we must start at the first house, and we cannot hit two houses in a row. As Abigail correctly points out, this means we will never, under any circumstances, rob the second house. I suppose with our luck, that’s where all the money is, too. Such is life. Oh why, why did I stay in school?
I could have been someone. I could have been a contender. Now I’m reduced to robbing houses to buy sketchy black-market electricity to keep my screen lit. Day in, day out, got to keep those electrons flowing. The monkey on the keyboard needs his fix. Don’t listen to your parents, kids. Don’t end up like me.
(uncomfortable silence as your editor contemplates his life choices)
Where was I? Oh, right.
We were considering how to best select elements from an array according to a set of conditions, to optimize a sum.
From the conditions, some emergent rules become apparent. Besides never visiting the second house, it’s also true that it only makes sense to skip either one or two houses. This follows from the observation that for any longer jump than three, there exists at least one intermediate house that can also be visited before arriving at the same place. As the values are assumed to be positive or at least zero, there is no reason to ever not include the stopovers.
Although negative values are not explicitly excluded, it is rather hard to justify the idea of negative loot in our imaginary scenario. Time-to-rob would be a good negative variable to counter the loot gained and make things nice and complex, but we’re not compounding that in here today. Alternately including item weights could turn it into a variant of the Knapsack Problem.
There were 18 submissions for the second task this past week.
a selection from the RIFF-RAFF, PICKPOCKETS and GENTLEMAN THIEVES
Laurent Rosenfeld, Simon Green, Lubos Kolouch, Ulrich Rieke, Matthew Neleigh, Peter Campbell Smith, Duncan C. White, James Smith, and E. Choroba
The most common technique was recursion, exploring from each landing the two possibilites of skipping ahead two or three houses. The complexity expands quadratically, but as we are tasked with robbing real imaginary houses on a real imaginary block the number of houses under consideration should not be too large. After all, the whole purpose of blocks is to break collections of lots onto managable pieces. It’s not unreasonable to surmise that very dense blocks and apartment buildings would require a adjustments to both the conditions and the resultant strategy.
A variant on this is to produce the combinations of houses combinatorically up-front, and compute the sums and find the maximal value.
The recursion decisions center around the partial summing of a choice of two positions as we proceed, making the problem suitable to dynamic programming optimization, and we saw several examples of this as well. Ultimately we can remove the recursion from the algorithm completely, and produce a dynamic programming array in a single pass by deciding on partial sums based on previously computed values in same the dynamic array.
additional languages: Raku
blog writeup: Perl Weekly Challenge 151: Binary tree Depth
Laurent will start us off with an example of a recursive solution. At every stage a routine, get_best() is called with a growing partial sum and the remainder of the array, sliced off and packaged up. Internally both options of skipping ahead two or three houses are explored with another recursive call. A variable in the script scope, $best_so_far is kept updated with a running maximum.
sub get_best {
my $sum_so_far = $_[0];
my @in = @{$_[1]};
if (@in <= 2) {
$sum_so_far += $in[0] if @in == 1;
$sum_so_far += $in[1] if @in == 2;
$best_so_far = $sum_so_far if $sum_so_far > $best_so_far;
return;
}
for my $i (0, 1) {
get_best($sum_so_far + $in[$i], [@in[$i + 2 .. $#in]]);
}
}
additional languages: Python
blog writeup: Weekly Challenge 151
Simon presents another version. In it his rob() routine is passed two arguments, the previous loot plus the current house, and the remaining list of houses down the street.
The recursive solutions in general need to accommodate the edge-cases where there are few or no houses on the street.
Here each call returns the larger of the two calls returned to it; as the recursion collapses the maximum gets propagated backwards up the stack until the first call returns the result.
# Call the function recursively skipping either one or two houses
my @hauls = ();
push @hauls, rob( $haul + $valuables->[0], [ @{$valuables}[ 2 .. $#$valuables ] ] );
if ( @{$valuables} >= 4 ) {
push @hauls, rob( $haul + $valuables->[0], [ @{$valuables}[ 3 .. $#$valuables ] ] );
}
# Return the largest haul
return max(@hauls);
additional languages: Php, Python
Here’s another by Lubos to give a nice overview of different ways to implement the technique.
sub get_houses_max {
my @houses = @_;
return $cache{@houses} if $cache{@houses};
my $max_value = 0;
my $house_index = 0;
for my $house (@houses[2..@houses-1]) {
my $next_houses_values = get_houses_max(@houses[2+$house_index..@houses-1]);
$max_value = $next_houses_values if $next_houses_values > $max_value;
$house_index++;
}
$cache{@houses} = $houses[0] + $max_value;
return $houses[0] + $max_value;
}
additional languages: Haskell, Raku
Next we have Ulrich, who brings in the Algorithm::Combinatorics module to fit the combinations for him. Practically this visits all possibilities, the same as the recursive solution, offloading the work to a compiled library might improve performance.
my @robbedValues ;
my @combilengths ;
if ( $len % 2 == 1 ) {
push @combilengths , int( $len / 2 ) , int( $len / 2 ) + 1 ;
}
else {
push @combilengths, int( $len / 2 ) ;
}
my @positions = (0 .. $len - 1 ) ;
for my $combilen ( @combilengths ) {
my $iter = combinations( \@positions, $combilen ) ;
while ( my $c = $iter->next ) {
if ( checkCondition( $c ) ) {
push @robbedValues , sum (@valuables[ @$c ]) ;
}
}
}
say max( @robbedValues ) ;
Using dynamic programming, as we process the house array from left to right we can construct a parallel array of partial sums as we go. Each new position added is decided by choosing the maximum sum from the most recent previous partial solutions, themselves chosen from earlier paths. In this way only two partial solutions are used at each decision: “What if we jumped here from two steps back?” and “What if we jumped from three?". Every house after the start gets the same decision, and when we get to the end we have our maximum. Nice.
sub calculate_loot_yield_on_street{
use List::Util qw(max);
# Empty list, no houses to rob
return(0)
unless(@ARG);
my @loot;
my $loot_initial;
my $i;
# We always start with the first house, as
# specified (though this seems limiting...)
$loot_initial = $ARG[0];
# Strip off the first two houses- we've
# robbed the first and can't rob the second
splice(@ARG, 0, 2);
# Edge cases- zero or one houses left
return($loot_initial)
unless(@ARG);
if(scalar(@ARG) == 1){
return($loot_initial + $ARG[0]);
}
# Proceed as normal(?)
$loot[0] = $ARG[0];
$loot[1] = max($ARG[0], $ARG[1]);
for($i = 2; $i < scalar(@ARG); $i++){
$loot[$i] = max($ARG[$i] + $loot[$i - 2], $loot[$i - 1]);
}
return($loot_initial + $loot[$#loot]);
}
blog writeup: Locate a leaf and rob a road
Peter examines all paths forward at every cycle in his recursion, including those past the third position forward, considering all jumps to the end of the line. There’s no harm in this and the algorithm handles a 45-house street in a few seconds.
sub robberies {
# robberies($number, $swag) updates $best with the best result starting from house $number
# with $swag already in the bag
my ($number, $swag, $next, $new_swag);
($number, $swag) = @_;
# try all the next allowable houses starting from $number
for ($next = $number + 2; $next <= $last; $next ++) {
$new_swag = $swag + $houses[$next];
$best = $new_swag if $new_swag > $best; # looking good!
robberies($next, $new_swag);
}
}
Duncan has devised another recursive way to search all the paths, compounding a best total value as he goes:
fun maxrobbery( $starthouseno, @valuables )
{
my @besth;
my $besttotal = 0;
foreach my $hno ($starthouseno+2..$#valuables)
{
# find the best partial solution starting by robbing house $hno
my( $mv2, @rh2 ) = maxrobbery( $hno, @valuables );
# then find the best of all those partial solutions
if( $mv2 > $besttotal )
{
$besttotal = $mv2;
@besth = @rh2;
}
}
# then the overall best solution involves adding starthouseno
# to the best partial solution..
return ( $valuables[$starthouseno]+$besttotal, $starthouseno, @besth );
}
blog writeup: Perl Weekly Challenge #151
James delivers a very compact solution that will probably appear quite mysterious, but is a reworking of the dynamic programming solution, working backwards from the end. Fortunately he provides notes to the action, both in the comments and at his writeup.
sub rob {
## Line 1 - Trip finishing at the first house the value is the
## points for the first house
## Line 2 - If there is more than one house we set the value
## for the second house to be the points for the house
## itself, unless the first house has a better value
## Line 3 - We repeat this for the remaining houses.... It is the
## points for this house + the value for two houses before
## or the value for the previous house if it is greater
## Line 4 - When we get to the end the result is just the value
## for the last house!
##
## Comments this way so they don't hide the symmetry of the code
my @b = shift;
(push @b,shift ), $b[-1]<$b[-2] && ($b[-1]=$b[-2]) if @_;
(push @b,$_+$b[-2]), $b[-1]<$b[-2] && ($b[-1]=$b[-2]) for @_;
$b[-1];
}
All of this looking and working backwards to see which position to have traveled from produces the optimal sub-problem can be quite confusing. Choroba has reversed everything, so the algorithm is run forward. However note we’re not picking the best option available, skipping to it and proceeding from there however — rather we’re systematically looking at every house and figuring instead the best way to have gotten there. When we’re done the value at $sums[0] reveals the answer. Dynamic programming is such an intersting technique, currying the data processing.
sub rob_the_house {
my (@valuables) = @_;
my @sums;
for my $i (reverse 0 .. $#valuables) {
$sums[$i] = $valuables[$i];
if ($i + 2 <= $#valuables) {
my $add = $sums[$i + 2];
$add = $sums[$i + 3] if $i + 3 <= $#valuables
&& $sums[$i + 3] > $sums[$i + 2];
$sums[$i] += $add;
}
}
return $sums[0]
}
Blogs and Additional Submissions in Guest Languages for Task 2:
additional languages: Awk, Bash, Bc, C, Go, Java, Lua, Node, Pascal, Python, R, Ruby, Tcl
additional languages: Raku
additional languages: Raku
blog writeup: Burglary Tools
blog writeup: Dr. Metropolis and His Amazing MANIAC Machine!: The Weekly Challenge #151 | Committed to Memory
additional languages: Raku
blog writeup: PWC151 - Rob The House - ETOOBUSY
additional languages: Javascript, Kotlin, Lua, Postscript, Python, Raku, Ruby, Rust
blog writeup: RogerBW’s Blog: The Weekly Challenge 151: Robbing Depth
blog writeup: Perl Weekly Challenge 151 – W. Luis Mochán
_________ THE BLOG PAGES _________
That’s it for me this week, people! Warped by the rain, driven by the snow, resolute and unbroken by the torrential influx, by some miracle I somehow continue to maintain my bearings.
Looking forward to next wave, the perfect wave, I am: your humble servant.
But if Your Unquenchable THIRST for KNOWLEDGE is not SLAKED,
then RUN (dont walk!) to the WATERING HOLE
and FOLLOW these BLOG LINKS:
( …don’t think, trust your training, you’re in the zone, just do it … )
Arne Sommer
- The Tree House with Raku ( Raku )
Colin Crain
- No Diving in the Shallow End - Programming Excursions in Perl and Raku ( Perl & Raku )
- Burglary Tools ( Perl & Raku )
Dave Jacoby
- Dr. Metropolis and His Amazing MANIAC Machine!: The Weekly Challenge #151 | Committed to Memory ( Perl )
Flavio Poletti
- PWC151 - Binary Tree Depth - ETOOBUSY ( Perl & Raku )
- PWC151 - Rob The House - ETOOBUSY ( Perl & Raku )
James Smith
- Perl Weekly Challenge #151 ( Perl )
Laurent Rosenfeld
- Perl Weekly Challenge 151: Binary tree Depth ( Perl & Raku )
Peter Campbell Smith
- Locate a leaf and rob a road ( Perl )
Roger Bell_West
- RogerBW’s Blog: The Weekly Challenge 151: Robbing Depth ( Perl & Raku )
Simon Green
- Weekly Challenge 151 ( Perl )
W. Luis Mochan