diff options
| -rw-r--r-- | challenge-152/duncan-c-white/README | 85 | ||||
| -rwxr-xr-x | challenge-152/duncan-c-white/perl/ch-1.pl | 75 | ||||
| -rwxr-xr-x | challenge-152/duncan-c-white/perl/ch-2.pl | 62 |
3 files changed, 173 insertions, 49 deletions
diff --git a/challenge-152/duncan-c-white/README b/challenge-152/duncan-c-white/README index b4889e4611..2bc85c8535 100644 --- a/challenge-152/duncan-c-white/README +++ b/challenge-152/duncan-c-white/README @@ -1,74 +1,61 @@ -TASK #1 - Binary Tree Depth +TASK #1 - Triangle Sum Path -You are given binary tree. +You are given a triangle array. -Write a script to find the minimum depth. - -The minimum depth is the number of nodes from the root to the nearest -leaf node (node without any children). +Write a script to find the minimum sum path from top to bottom. Example 1: - Input: '1 | 2 3 | 4 5' + 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 - 1 - / \ - 2 3 - / \ - 4 5 + Output: 8 - Output: 2 + Minimum Sum Path = 1 + 3 + 2 + 0 + 2 => 8 Example 2: - Input: '1 | 2 3 | 4 * * 5 | * 6' + Input: $triangle = [ [5], [2,3], [4,1,5], [0,1,2,3], [7,2,4,1,9] ] - 1 - / \ - 2 3 - / \ - 4 5 - \ - 6 - Output: 3 + 5 + 2 3 + 4 1 5 + 0 1 2 3 + 7 2 4 1 9 -MY NOTES: well, if I built a binary tree from the input, it would be quite -simple to find the minimum depth. But there must be a way to solve the -problem using only the input syntax. Something like: split into rows on '|'. -Each row has 2 * (rowno-1) elements (starting at row 1). If a row hasn't -got that many elements, pad it with '*'s. Now, find the first non-full row, -ie. with one or more '*'s. Take the row a pair of elements at a time. If -any pair are both '*'s, then the min depth is rowno-1. Otherwise proceed -to the next row, and keep going down the rows. + Output: 9 + Minimum Sum Path = 5 + 2 + 1 + 0 + 1 => 9 -TASK #2 - Rob The House +MY NOTES: So it appears at each row, we simply pick the minimum value. +It doesn't have to be adjacent, or even close to, the one we picked +on the row above. Ok, so that's easy! Actually, parsing the input +may be the hardest part. -You are planning to rob a row of houses, always starting with the first -and moving in the same direction. However, you can't rob two adjacent -houses. -Write a script to find the highest possible gain that can be achieved. +TASK #2 - Rectangle Area -Example 1: +You are given coordinates bottom-left and top-right corner of two rectangles in a 2D plane. - Input: @valuables = (2, 4, 5); - Output: 7 +Write a script to find the total area covered by the two rectangles. -If we rob house 0 we get 2 and then the only house we can rob is house -2 where we have 5. So the total valuables in this case is (2 + 5) = 7. +Example 1: + Input: Rectangle 1 => (-1,0), (2,2) + Rectangle 2 => (0,-1), (4,4) -Example 2: + Output: 22 - Input: @valuables = (4, 2, 3, 6, 5, 3); - Output: 13 +Example 2: -The best choice would be to first rob house 0 then rob house 3 then finally -house 5. This would give us 4 + 6 + 3 =13. + Input: Rectangle 1 => (-3,-1), (1,3) + Rectangle 2 => (-1,-3), (2,2) + Output: 25 -MY NOTES: Hmm.. some sort of recursive "find all paths" method. -It always helps to pick the right function purpose and name. -I think the recursive function we need is: -my $maxvaluables = maxrobbery( startpos ), invoked as my $max=maxrobbery(0)? +MY NOTES: Of course the tricky bit here is when the rectangles overlap. diff --git a/challenge-152/duncan-c-white/perl/ch-1.pl b/challenge-152/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..41cd93daf3 --- /dev/null +++ b/challenge-152/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,75 @@ +#!/usr/bin/perl +# +# TASK #1 - Triangle Sum Path +# +# You are given a triangle 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 +# +# MY NOTES: So it appears at each row, we simply pick the minimum value. +# It doesn't have to be adjacent, or even close to, the one we picked +# on the row above. Ok, so that's easy! Actually, parsing the input +# may be the hardest part. Let's choose a simplified input format: +# each argument is a separate row, and a row looks like '7,2,4,1,9' +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use List::Util qw(min); +#use Data::Dumper; + +my $debug=0; +die "Usage: triangle-sum-path [--debug] 'triangle row 1' ['triangle row 2...'\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV>0; + +# +# my $sum = sum_minimum( @rowstr ); +# Given an array of row strings, with elements in one row being +# comma separated numbers, pick the minimum of each row and sum +# them, returning the total. +# +sub sum_minimum +{ + my( @rowstr ) = @_; + my $result = 0; + foreach my $row (@rowstr) + { + my @row = split(/,/, $row); + $result += min( @row ); + } + return $result; +} + + +my $sum = sum_minimum( @ARGV ); +say $sum; diff --git a/challenge-152/duncan-c-white/perl/ch-2.pl b/challenge-152/duncan-c-white/perl/ch-2.pl new file mode 100755 index 0000000000..d8003ba3e1 --- /dev/null +++ b/challenge-152/duncan-c-white/perl/ch-2.pl @@ -0,0 +1,62 @@ +#!/usr/bin/perl +# +# TASK #2 - Rectangle Area +# +# You are given coordinates bottom-left and top-right corner of two rectangles in a 2D plane. +# +# Write a script to find the total area covered by the two rectangles. +# +# Example 1: +# +# Input: Rectangle 1 => (-1,0), (2,2) +# Rectangle 2 => (0,-1), (4,4) +# +# Output: 22 +# +# Example 2: +# +# Input: Rectangle 1 => (-3,-1), (1,3) +# Rectangle 2 => (-1,-3), (2,2) +# +# Output: 25 +# +# MY NOTES: Of course the tricky bit here is when the rectangles overlap. +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Function::Parameters; +use List::Util qw(min max); +#use Data::Dumper; + +my $debug=0; + +die "Usage: rectangle-area x1,y1 x2,y2 x3,y3 x4,y4\n" unless @ARGV==4; +my( $x1, $y1 ) = split( /,/, shift ); + +my( $x2, $y2 ) = split( /,/, shift ); +my( $x3, $y3 ) = split( /,/, shift ); +my( $x4, $y4 ) = split( /,/, shift ); + +# make sure that x1 <= x2. y1 <= y2, x3 <= x4, y3 <= y4 +($x1,$x2) = ($x2,$x1) if $x1 > $x2; +($y1,$y2) = ($y2,$y1) if $y1 > $y2; +($x3,$x4) = ($x4,$x3) if $x3 > $x4; +($y3,$y4) = ($y4,$y3) if $y3 > $y4; + +my $r1area = ($x2-$x1)*($y2-$y1); +my $r2area = ($x4-$x3)*($y4-$y3); +say "r1 area: $r1area, r2 area: $r2area" if $debug; + +# overlap: +my $oxd = min($x2,$x4) - max($x1,$x3); +my $oyd = min($y2,$y4) - max($y1,$y3); +my $oarea = ($oxd>0 && $oyd>0) ? $oxd * $oyd : 0; + +say "overlapping area: $oarea" if $debug; + +my $total = $r1area + $r2area - $oarea; + +say $total; |