Porject Euler # 18

This challenge asks that you find the greatest route possible in a triangle, decending each time one row. (Essentially, picking the route from top to bottom that gives the largest sum, without ever going back up in the rows).

My initial assumption was: go through each row from top to bottom, and pick the highest element of the adjoining indexes. This however, is wrong, as having two large numbers together at the top, might stop the route from finding three way larger elements on the opposite side of the triangle. However, calculating each route would not only be a tedious algorithm to implement, it’s running time increased with O(2n), n being the number of lines in the triangle.

This was however a good starting point, even though I was seeing things the wrong way around. Rather than assume you can pick the largest in a row as you descend the triangle’s rows, why not assume you know the largest possible route at any row.

Thats means, that if I know all the best numbers for the 5th  row, I can remove the worst possible candidate on row 6. Doing this recursively from (n-1) through to 1, I can replace each row by the sum of its elements with the highest possibility in the next row.

i.e.  if rows 4 and 5 are as follows:
01 03 04 06
10 20 44 55 60

I can replace row 4 by the following
21 47 59 66 (and eliminate the “10″ in row 5).

Given perl doesn’t seem to like 2 dimensional arrays (ok, that’s just me) I’m writing this with Inline::C. of course, writing the triangle as the 2 dimensional array is easy the first time.  It would appear that I need to figure a way to redo the same thing but for 100 rows laer on. Not going to enjoy retyping that one.

EDIT – turns out it’s not that bad in Perl by using anonymous arrays:

#! /usr/bin/perl

use strict;
use warnings;

print "What is the filename for the triangle? \n";

my $FILE = <>;
my $count = 0;
my @triangle = ();

open my $fh, '<', $FILE or die "$!\n";

while (defined (my $line = <$fh>))
{
chomp $line;
my @row = split ' ', $line;
push @triangle , [@row];
$count++;
}

## now you can go through the triangle as you would in C.

my $i = $count -1; # start at the n-1th line
for ($i; $i >=0; $i--)
{
my @tmp = @triangle[$count];
my $length = @tmp;
for (my $j = 0; $j < $length; $j ++)
{
if ($triangle[$i+1][$j] > $triangle[$i+1][$j+1]) 
{
$triangle[$i][$j] +=$triangle[$i+1][$j]
}
else
{
$triangle[$i][$j] +=$triangle[$i+1][$j+1]
}
}
} 

print $triangle[0][0];

Leave a Reply

Your email address will not be published. Required fields are marked *


+ six = 13

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>