Peter
Peter Campbell Smith

Angles week

Weekly challenge 152 — 14 February 2022

Week 152: 14 Feb 2022

Task 1

Task — Triangle sum path

You are given a triangular array. Write a script to find the minimum sum path from top to bottom.

Examples


Example 1:
Input: $triangle = [ [1], [5,3], [2,3,4], [7,1,0,2], 
     [6,4,5,2,8] ]
                1
               5 3
              2 3 4
             7 1 0 2
            6 4 5 2 8
Output: 8
    Minimum Sum Path = 1 + 3 + 2 + 0 + 2 => 8

Example 2:
Input: $triangle = [ [5], [2,3], [4,1,5], [0,1,2,3], 
     [7,2,4,1,9] ]
                5
               2 3
              4 1 5
             0 1 2 3
            7 2 4 1 9
Output: 9
    Minimum Sum Path = 5 + 2 + 1 + 0 + 1 => 9

Analysis

At first I thought that this was like Chinese Checkers: the path could only descend to the nodes immediately to its left or right in the row below, but the examples imply that we are simply looking for the sum of the smallest values in each row.

Someone will surely come up with a 1-line answer to this, but I amused myself by finding a way to display the triangle in the output. What I came up with was to put it in a string:

$example = qq[
    [1], 
   [5,3], 
  [2,3,4], 
 [7,1,0,2], 
[6,4,5,2,8] ]; 

which displays nicely, and then use eval to put it into an array of arrays:

$test = eval("[$example]");

from which the solution is pretty simple.

Try it 

Try running the script with any input:



example: [1], [5,3], [2,3,4], [7,1,0,2], [6,4,5,2,8]

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2022-02-17
# PWC 152 task 1

use v5.28;
use strict;
use utf8;

my ($test, $answer, @row, $r, @examples, $ex);

$examples[0] = qq[
    [1], 
   [5,3], 
  [2,3,4], 
 [7,1,0,2], 
[6,4,5,2,8] ];   # answer is 8
            
$examples[1] = qq[
    [5],
   [2,3],
  [4,1,5],
 [0,1,2,3],
[7,2,4,1,9] ];   # answer is 9

$examples[2] = qq[
            [ 9],
           [ 7, 8],
         [11,22,33],
        [ 2, 3, 4, 5],
      [ 9, 8, 7, 6, 5],
     [23,34,45,56,67,78],
   [17, 0,66, 3, 6,42, 1],
  [ 3, 6,33,11,-5, 6,12, 4],
[12, 3, 4, 7, 0, 3,-1, 2,99] ];   # answer is 51
                         
# loop over examples
for $ex (0..$#examples) {
    
    # evaluate example string as array ref of array refs
    say qq[\nInput:$examples[$ex]];
    $test = eval("[$examples[$ex]]");
    
    # add the least members of each row
    $answer = 0;
    for $r (0..$#{$test}) {
        @row = @{$test->[$r]};
        $answer += smallest(@row);
    }
    
    say qq[\nOutput: $answer];
}

sub smallest {
    
    my ($answer);
    
    # returns the least member of the input array
    $answer = 999;
    $answer = $_ < $answer ? $_ : $answer for (@_);
    return $answer;
}
            

Output


Input:
    [1], 
   [5,3], 
  [2,3,4], 
 [7,1,0,2], 
[6,4,5,2,8] 

Output: 8

Input:
    [5],
   [2,3],
  [4,1,5],
 [0,1,2,3],
[7,2,4,1,9] 

Output: 9

Input:
            [ 9],
           [ 7, 8],
         [11,22,33],
        [ 2, 3, 4, 5],
      [ 9, 8, 7, 6, 5],
     [23,34,45,56,67,78],
   [17, 0,66, 3, 6,42, 1],
  [ 3, 6,33,11,-5, 6,12, 4],
[12, 3, 4, 7, 0, 3,-1, 2,99] 

Output: 51

 

Any content of this website which has been created by Peter Campbell Smith is in the public domain