more useful options PerlMonks

Re: Brute force vs algorithm (PWC # 100) (updated: visualisation)

by choroba (Archbishop)
 on Feb 16, 2021 at 21:20 UTC Need Help??

in reply to Brute force vs algorithm (PWC # 100)

Here is my solution. It only finds the sum, I might add the highlighting later.
```#!/usr/bin/perl
use warnings;
use strict;

sub triangle_sum {
my (\$triangle) = @_;
my @sums = @{ \$triangle->[-1] };
@sums = map {
\$sums[\$sums[ \$_ - 1 ] < \$sums[\$_] ? \$_ - 1 : \$_]
+ \$triangle->[@sums - 2][ \$_ - 1 ]
} 1 .. \$#sums
while @sums > 1;
return \$sums[0]
}

use Test::More;

is triangle_sum ([ [1], [2,4], [6,4,9], [5,1,7,2] ]), 8, 'Example 1';
is triangle_sum ([ [3], [3,1], [5,2,3], [4,3,1,3] ]), 7, 'Example 2';

is triangle_sum([[2], [1, 5], [9, 10, 1]]), 8, 'Tricky';

done_testing();
[download]```

Update: Fixed an error (@sums - 1 instead of @sums - 2).

Update 2: Here's the visualisation part:

```sub triangle_sum_show {
my (\$triangle) = @_;
my @sums = @{ \$triangle->[-1] };
my @way;
while (@sums > 1) {
unshift @way, [];
@sums = map {
my \$i = \$sums[ \$_ - 1 ] < \$sums[\$_] ? \$_ - 1 : \$_;
push @{ \$way[0] }, \$i;
\$sums[\$i] + \$triangle->[@sums - 2][ \$_ - 1 ];
} 1 .. \$#sums;
}
unshift @way, [];
my \$previous;
for my \$row (@\$triangle) {
my @selected = @{ \$way[\$#\$row] };
\$previous = @selected ? \$selected[\$previous] : 0;
print ' ' x (@\$triangle - @\$row);
for my \$i (0 .. \$#\$row) {
print ' ', \$i == \$previous ? "[\$row->[\$i]]" : \$row->[\$i];
}
print "\n";
}
}
my \$triangle = [ map [map int rand 10, 1 .. \$_], 1 .. 20 ];
triangle_sum_show(\$triangle);
[download]```
Possible output:
```                    [9]
[1] 4
3 [2] 9
9 [6] 8 2
6 [2] 7 3 4
0 [0] 0 5 9 5
2 [2] 0 1 8 3 2
7 [1] 1 8 4 6 8 6
1 [0] 6 2 9 2 2 6 4
3 [2] 0 1 6 9 5 6 2 2
0 [1] 8 8 1 4 9 8 6 9 6
8 9 [7] 1 9 7 1 5 8 8 1 4
0 4 [4] 6 8 9 5 5 6 1 9 8 5
9 4 [3] 0 4 8 6 3 7 1 8 0 7 8
1 6 [1] 6 4 4 3 3 0 2 6 6 2 6 6
0 6 1 [3] 9 6 9 9 1 5 9 7 1 5 9 9
8 9 7 6 [1] 5 5 2 8 7 8 7 4 6 4 7 4
3 4 8 8 9 [3] 4 0 5 7 6 8 2 8 4 1 1 2
4 9 0 8 6 [0] 2 8 2 7 0 1 3 2 5 8 0 7 7
3 3 2 0 5 9 [1] 3 5 2 5 9 3 0 4 6 3 6 4 3
[download]```

map{substr\$_->[0],\$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]

Replies are listed 'Best First'.
Re^2: Brute force vs algorithm (PWC # 100)
by LanX (Cardinal) on Feb 16, 2021 at 22:37 UTC
Yes, it is. I wasn't able to come up with a top down algorithm.

map{substr\$_->[0],\$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]
Top-down is much harder.

And when one doesn't do it right, one will just end-up visiting each cell anyway.

That would have no benefit over this bottom-up approach.

Cheers Rolf
(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery

Log In?
 Username: Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://11128475]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (9)
As of 2021-04-22 17:46 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?