incorporated my solution of this week's tasks.. 2 mildly tricky questions, especially the second

3 files changed, 280 insertions, 38 deletions

diff --git a/challenge-075/duncan-c-white/README b/challenge-075/duncan-c-white/README
index 57d2a79ea6..07716b97a6 100644
--- a/challenge-075/duncan-c-white/README
+++ b/challenge-075/duncan-c-white/README
@@ -1,52 +1,71 @@
-Task 1: "Majority Element
+Task 1: "Coins Sum
 
-You are given an array of integers of size $N.
+You are given a set of coins @C, assuming you have infinite amount of each coin in the set.
 
-Write a script to find the majority element. If none found then print -1.
-The majority element in a list is the element, if any, that appears more than
-floor(size_of_list/2) TIMES.
+Write a script to find how many ways you make sum $S using the coins from the set @C.
+Example:
 
-Example 1
+Input:
+    @C = (1, 2, 4)
+    $S = 6
 
-  Input: @A = (1, 2, 2, 3, 2, 4, 2)
-  Output: 2, as 2 appears 4 times in the list - more than floor(7/2)==3 TIMES.
+Output: 6
+There are 6 possible ways to make sum 6.
+a) (1, 1, 1, 1, 1, 1)
+b) (1, 1, 1, 1, 2)
+c) (1, 1, 2, 2)
+d) (1, 1, 4)
+e) (2, 2, 2)
+f) (2, 4)
+"
 
-Example 2
+My notes: ok.  Reasonably easy: bag of coins shows what coins we've used,
+at every stage explore 2 paths: 1). add another instance of each possible coin,
+2). don't add another instance..
 
-  Input: @A = (1, 3, 1, 2, 4, 5)
-  Output: -1 as none of the elements appears more than floor(6/2)==3 TIMES.
-"
+Task 2: "Largest Rectangle Histogram
 
-My notes: ok.  Very easy.
+You are given an array of positive numbers @A.
 
+Write a script to find the largest rectangle histogram created by the given array.
+BONUS: Try to print the histogram as shown in the example, if possible.
 
-Task 2: "FNR Character
+Example 1:
 
-You are given a string $S.
+Input: @A = (2, 1, 4, 5, 3, 7)
 
-Write a script to print the series of first non-repeating character (left -> right) for the given string. Print # if none found.
+     7           #
+     6           #
+     5       #   #
+     4     # #   #
+     3     # # # #
+     2 #   # # # #
+     1 # # # # # #
+     _ _ _ _ _ _ _
+       2 1 4 5 3 7
 
-Example 1
-  Input: $S = 'ababc'
-  Output: 'abb#c'
-  Pass 1: 'a', the FNR character is 'a'
-  Pass 2: 'ab', the FNR character is 'b'
-  Pass 3: 'aba', the FNR character is 'b'
-  Pass 4: 'abab', no FNR found, hence '#'
-  Pass 5: 'ababc' the FNR character is 'c'
+Looking at the above histogram, the largest rectangle (4 x 3) is formed by columns (4, 5, 3 and 7).
+Output: 12
 
-Example 2
-  Input: $S = 'xyzzyx'
-  Output: 'xyzyx#'
-  Pass 1: 'x', the FNR character is 'x'
-  Pass 2: 'xy', the FNR character is 'y'
-  Pass 3: 'xyz', the FNR character is 'z'
-  Pass 4: 'xyzz', the FNR character is 'y'
-  Pass 5: 'xyzzy', the FNR character is 'x'
-  Pass 6: 'xyzzyx', no FNR found, hence '#'
-"
+Example 2:
+
+Input: @A = (3, 2, 3, 5, 7, 5)
+
+     7         #
+     6         #
+     5       # # #
+     4       # # #
+     3 #   # # # #
+     2 # # # # # #
+     1 # # # # # #
+     _ _ _ _ _ _ _
+       3 2 3 5 7 5
+
+Looking at the above histogram, the largest rectangle (3 x 5) is formed by columns (5, 7 and 5).
+Output: 15"
 
-My notes: why is the FNR of "ab" (in pass 2) 'b' rather than 'a'?  Last non-repeating
-character would be more like it.  Basically: in each pass, take substr(1,len PASS) and then
-remove each LAST char if it's duplicated earlier in the substring, otherwise that's the FNR.
-If the string is empty, no FNR, print #.
+My notes: hmm.. so max(area of all rectangles "in" a histogram).  But what does that mean?
+Hang on: the "graphs" are NOT actually histograms: each is simply the array of values itself.
+So forgot frequency hashes.  The simplest way that I can see is to calculate the area of all
+possible rectangles (where 1 or more adjacent values are at least some minimum height) and
+then to find the maximum of all those.
diff --git a/challenge-075/duncan-c-white/perl/ch-1.pl b/challenge-075/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..d36bb3dbdd
--- /dev/null
+++ b/challenge-075/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,96 @@
+#!/usr/bin/perl
+#
+# Task 1: "Coins Sum
+#
+# You are given a set of coins @C, assuming you have infinite amount of each coin in the set.
+# 
+# Write a script to find how many ways you make sum $S using the coins from the set @C.
+#
+# Example:
+# 
+# Input:
+#     @C = (1, 2, 4)
+#     $S = 6
+# 
+# Output: 6
+# There are 6 possible ways to make sum 6.
+# a) (1, 1, 1, 1, 1, 1)
+# b) (1, 1, 1, 1, 2)
+# c) (1, 1, 2, 2)
+# d) (1, 1, 4)
+# e) (2, 2, 2)
+# f) (2, 4)
+# "
+# 
+# My notes: ok.  Reasonably easy: bag of coins shows what coins we've used,
+# at every stage explore 2 paths: 1). add another instance of each possible coin,
+# 2). don't add another instance..
+#
+#
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Data::Dumper;
+
+die "Usage: coin-sum target list_of_coinvalues\n" if @ARGV<2;
+my( $s, @list ) = @ARGV;
+
+#
+# my @ways = findall( $s, $coins, $used );
+#	Find all possible ways of achieving sum $s given @$coins.  %$used
+#	is the bag of all coins used so far.  Returns @ways, an array of
+#	each complete %$used bag.
+#
+fun findall( $s, $coins, $used )
+{
+	my @result;
+	foreach my $c (@$coins)
+	{
+		next if $c > $s;	# coin too big..
+		my %u2 = %$used;	# make bag u2: used + 1 more $c
+		$u2{$c}++;
+		if( $c == $s )
+		{
+			push @result, \%u2;
+		} else
+		{
+			# 2 possibilities: either include zero or one more $c
+			# zero: remove $c from copy of @$coins
+			my @c2 = grep { $_ ne $c } @$coins;
+			
+			push @result, findall( $s, \@c2, $used );
+
+			# one more:
+			push @result, findall( $s-$c, $coins, \%u2 );
+		}
+	}
+	return @result;
+}
+
+#
+# my $csv = h2c( %h );
+#	Turn a bag %h into a CSV string of (c1) x n1, (c2) x n2..
+#
+fun h2c( %h )
+{
+	my @result;
+	foreach my $c (sort keys %h)
+	{
+		push @result, (($c) x $h{$c});
+	}
+	return join(',',@result);
+}
+
+
+my @ways = map { h2c(%$_) } findall( $s, \@list, {} );
+my @uniqueways;
+my %seen;
+foreach my $w (sort @ways)
+{
+	push @uniqueways, $w unless $seen{$w}++;
+}
+my $n = @uniqueways;
+say "There are $n possible ways to make sum $s";
+say for @uniqueways;
diff --git a/challenge-075/duncan-c-white/perl/ch-2.pl b/challenge-075/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..7a7fff7338
--- /dev/null
+++ b/challenge-075/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,127 @@
+#!/usr/bin/perl
+#
+# Task 2: "Largest Rectangle Histogram
+#
+# You are given an array of positive numbers @A.
+# 
+# Write a script to find the largest rectangle histogram created by the given array.
+# BONUS: Try to print the histogram as shown in the example, if possible.
+# 
+# Example 1:
+# 
+# Input: @A = (2, 1, 4, 5, 3, 7)
+# 
+#      7           #
+#      6           #
+#      5       #   #
+#      4     # #   #
+#      3     # # # #
+#      2 #   # # # #
+#      1 # # # # # #
+#      _ _ _ _ _ _ _
+#        2 1 4 5 3 7
+# 
+# Looking at the above histogram, the largest rectangle (4 x 3) is formed by columns
+# (4, 5, 3 and 7).
+# Output: 12
+# 
+# Example 2:
+# 
+# Input: @A = (3, 2, 3, 5, 7, 5)
+# 
+#      7         #
+#      6         #
+#      5       # # #
+#      4       # # #
+#      3 #   # # # #
+#      2 # # # # # #
+#      1 # # # # # #
+#      _ _ _ _ _ _ _
+#        3 2 3 5 7 5
+# 
+# Looking at the above histogram, the largest rectangle (3 x 5) is formed by columns (5, 7 and 5).
+# Output: 15"
+# 
+# My notes: hmm.. so max(area of all rectangles "in" a histogram).  But what does that mean?
+# Hang on: the "graphs" are NOT actually histograms: each is simply the array of values itself.
+# So forgot frequency hashes.  The simplest way that I can see is to calculate the area of all
+# possible rectangles (where 1 or more adjacent values are at least some minimum height) and
+# then to find the maximum of all those.
+#
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Data::Dumper;
+use List::Util qw(max);
+
+die "Usage: largest-histogram-rect values\n" if @ARGV==0;
+
+
+#
+# my @areas = rectangleareasofheight( $h, @value );
+#	Find all rectangle areas of height $h in @value. Returns an array of
+#	one or more numbers (each area).
+#
+fun rectangleareasofheight( $h, @value )
+{
+	# want to locate runs of adjacent values >= $h, each such run has
+	# a width, that w * h is the area.  use a 2-state state machine:
+	# state 0 is: not currently in such a run.
+	# state 1 is: currently in such a run, $area is the current area of the run.
+	my @result;
+	my $state = 0;
+	my $area = 0;
+	foreach my $v (@value)
+	{
+		#say "debug: state=$state, v=$v, h=$h, area=$area";
+		if( $state == 0 && $v>=$h )
+		{
+			# enter state 1, start counting the area
+			$state=1; $area=$h;
+		} elsif( $state == 1 && $v>=$h )
+		{
+			# stay in state 1: increase the area
+			$area+=$h;
+		} elsif( $state == 1 && $v<$h )
+		{
+			# finish one run, revert to state 0
+			push @result, $area;
+			#say "height $h: run area: $area, back to state 0 at value $v";
+			$state = 0; $area = 0;
+		}
+	}
+	# final possible extra area..
+	if( $state == 1 )
+	{
+		push @result, $area;
+		#say "height $h: run area: $area";
+	}
+	return @result;
+}
+
+
+#
+# my @areas = allrectangleareas( @value );
+#	Find all rectangle areas of @value.  Works by checking each height
+#	separately.
+#
+fun allrectangleareas( @value )
+{
+	my @result;
+	my $maxv = max @value;
+	foreach my $h (1..$maxv)
+	{
+		#say "looking for rectangles of height $h";
+		push @result, rectangleareasofheight($h,@value);
+	}
+	return @result;
+}
+
+
+my @values = @ARGV;
+my @areas = allrectangleareas( @values );
+#say Dumper \@areas;
+my $max = max @areas;
+say $max;