Perl Weekly Challenge 100 part 2
This is the second post in relation to Mohammad Anwar's awesome Perl Weekly Challenge, to celebrate the 100th challenge.
You can find the first post here: pErLM for the Perl Weekly Challenge 100.
Task 2 - Triangle Sum (Minimum Path Sum)
I you head over to the https://perlweeklychallenge.org/blog/perl-weekly-challenge-100/#TASK2 page, you'll see the idea here. Calculate the smallest sum of the nodes in a triangle/tree of integers. This is a pretty classic problem and is solved a bunch of ways; my approach is the "Dynamic Programming" approach in Perl.
So the pseudo-code for this is:
- Take the array of arrays and make it a table/matrix
- Start at bottom row and calculate the smallest sum option.
- Repeat moving up the rows
- Return cell 0,0 which "should" be the minimum path sum.
As ever, I start with a test and work my way out from there. Adding the simplest solution I can as I go along... literally return static values at first. So I call a class method, see the tests fail. Then create the .pm file, name it and add a sub foo { return 8; } which literally does nothing. Then I expand out from there.
Lets break with tradition and lets look at the completed module first:
package Triangle;
use Moo;
use Data::Dumper;
$Data::Dumper::Sortkeys = 1;
sub min_path_sum {
my ( $self, $triangle ) = @_;
my $table = $self->triangle_to_table($triangle);
my $sum = $self->parse_table($table);
return $sum;
}
sub triangle_to_table {
my ( $self, $triangle ) = @_;
my $max = @$triangle - 1;
for my $row_index ( 0 .. $max ) {
for my $column_index ( 0 .. $max ) {
$triangle->[$row_index][$column_index] //= 0;
}
}
return $triangle;
}
sub parse_table {
my ( $self, $table ) = @_;
my $max = @$table - 1;
for my $row_index ( reverse( 0 .. $max - 1 ) ) {
for my $column_index ( 0 .. $max - 1 ) {
if ( $table->[ $row_index + 1 ][$column_index]
< $table->[ $row_index + 1 ][ $column_index + 1 ] )
{
$table->[$row_index][$column_index]
+= $table->[ $row_index + 1 ][$column_index];
}
else {
$table->[$row_index][$column_index]
+= $table->[ $row_index + 1 ][ $column_index + 1 ];
}
}
}
return $table->[0][0];
}
1;
So you can see the I broke the problem up into two stages:
- triangle_to_table
- parse_table
Bad names I think, but it does mean that hopefully you can recognise the approach I described in pseudo-code. There are absolutely better ways of doing this, but this works and I know it works because of the tests I wrote as I explored the approach:
use Test2::V0 -target => 'Triangle';
subtest 'min_path_sum' => sub {
is $CLASS->min_path_sum( [ [1], [ 2, 4 ], [ 6, 4, 9 ], [ 5, 1, 7, 2 ] ] ),
8,
'Example 1 returns 8';
is $CLASS->min_path_sum( [ [3], [ 3, 1 ], [ 5, 2, 3 ], [ 4, 3, 1, 3 ] ] ),
7,
'Example 2 returns 7';
};
subtest 'triangle_to_table' => sub {
my $in = [ [1], [ 2, 4 ], [ 6, 4, 9 ], [ 5, 1, 7, 2 ] ];
my $expected
= [ [ 1, 0, 0, 0 ], [ 2, 4, 0, 0 ], [ 6, 4, 9, 0 ], [ 5, 1, 7, 2 ] ];
is $CLASS->triangle_to_table($in), $expected, 'Example 1';
$in = [ [3], [ 3, 1 ], [ 5, 2, 3 ], [ 4, 3, 1, 3 ] ];
$expected
= [ [ 3, 0, 0, 0 ], [ 3, 1, 0, 0 ], [ 5, 2, 3, 0 ], [ 4, 3, 1, 3 ] ];
is $CLASS->triangle_to_table($in), $expected, 'Example 2';
};
ok 1;
done_testing;
When I started I only had the first test:
is $CLASS->min_path_sum( [ [1], [ 2, 4 ], [ 6, 4, 9 ], [ 5, 1, 7, 2 ] ] ),
8,
'Example 1 returns 8';
And the first iteration of Triangle.pm looked like this:
package Triangle;
sub min_path_sum {
return 8;
}
1;
As I've said elsewhere, this is my style of doing things. Write a test, hard-code a return value. Then I know that I have the simplest solution. If Mohammad literally only had the one example, I'd stop there as I have met the "user requirement".
But there is more than one example, so a simple return does not suffice (of course) so I did implement the next stage. In my case, I actually moved forward by hard coding the triangle_to_table sub, and worked on the actual logic to solve for first example properly. THEN, I added the second example as a test and it failed as the triangle_to_table sub was stubbed out. So then I wrote tests for that sub and implemented the logic.
The nice thing here was that once I did that, the tests worked and adding the second example to the min_path_sum test just plain worked. :)
A good example of how TDD helps you design and then maintain integrity when you get it right. It took me a little longer (arguably) to get to a working solution... but it got faster as I went along and when I was "done" I had confidence I was finished as the tests confirmed it. At least in so much that the assumptions I tested were true. I have not coded for edge cases, etc.
I actually find TDD gives me a smoother ramp up, I start coding with super simple building blocks, the scaffolding which I need to build my solution. And line physical scaffolding, it's pretty easy to put together and when done shows the shape of things to come. I find it gets my head into the right space to do the "hard stuff". I have got the dopamine hits of tests passing, I've also very lightly started thinking through interfaces and the problem space.
I should also focus some attention on the pseudo-code stage of the process.
This you could call the High Level Design (HLD) as it's been called in places I have worked. This is the whiteboard scribbles, the napkin design that serves as the first feedback cycle in the design. As you can see from the example at the top of this page, my initial plan had four steps. By the time I finished you can see that was altered to be 2 methods. So my design changed even between the time I wrote the pseudo-code and when I started coding. That is super cheap, this is the essence of pragmatic software development for me. Do the smallest thing that gets me feedback that I know what I am doing will work. Then do the next step.
The final step (and I admit I often skip this) was to wire this into a Perl script someone could call from the command line. This was actually one that took me a little longer than it should, and I'd not want to ship my solution to a real user as it's definitely a kludge.
use strict;
use warnings;
use lib './lib';
use Triangle;
my $tri = Triangle->new;
# usage:
# perl ch-2.pl [[1], [2,4], [6,4,9], [5,1,7,2]]
# perl ch-2.pl [[3], [3,1], [5,2,3], [4,3,1,3]]
my @triangle = parse(@ARGV);
print "The minimum path sum: ";
print $tri->min_path_sum( \@triangle );
print "\n";
sub parse {
my @rows = @_;
my @triangle;
for my $row (@rows) {
$row =~ s/\[//g;
$row =~ s/\]//g;
my @values = split ',', $row;
push @triangle, \@values;
}
return @triangle;
}
My script basically allowed me to cut and paste the Perl style arrayrefs that the challenge used directly. It meant some ugly regexing away the square brackets and using Perl's flexibility to auto-magically know that I wanted the strings that contained numbers should be integers to do the minimum_path_sum calculations to.
By this I mean that the way I wrote this the Perl script just sees an array of strings. So the square brackets are removing the character from the string. The split makes an array of strings from the row strings. Then pushes a reference to that array of strings into @triangle and returns that.
The min_path_sum method just starts treating the elements as integers later (in the comparisons and addition). It's one of Perl's strengths compared to typed languages for example where I'd have to explicitly do a conversion (if you look at my Elm solution to task 1 (previous post) you'll see I need to use String.toInt to make that happen. In Perl I don't have to do that dance. Yes, there are downsides and weird bugs that "could" occur; but for the purposes of this code, I don't need to worry about it and can just benefit from this feature of the language.
Summary
This was another fun one, nice to work on. The pattern is one we have seen in other challenges, and every time you get to exercise an approach intentionally it helps to cement it into your mind/toolkit. Making it easier to identify and take advantage of in a different context.
I hope if you have read this far that it was of interest and that you'll drop me a message with your thoughts.