Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

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

by choroba (Archbishop)
on Feb 16, 2021 at 21:20 UTC ( #11128475=note: print w/replies, xml ) 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();

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);
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

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?