Angles week
Weekly challenge 152 — 14 February 2022
Week 152: 14 Feb 2022
You are given a triangular array. Write a script to find the minimum sum path from top to bottom.
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
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.
#!/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; }
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