got stuck on task 2, was tired, couldn't think straight, hacked a non-optimal solution together, will do C translations tomorrow

3 files changed, 260 insertions, 48 deletions

diff --git a/challenge-217/duncan-c-white/README b/challenge-217/duncan-c-white/README
index a64621c29b..8cb1e349ee 100644
--- a/challenge-217/duncan-c-white/README
+++ b/challenge-217/duncan-c-white/README
@@ -1,82 +1,76 @@
-Task 1: Registration Number
+Task 1: Sorted Matrix
 
-You are given a list of words and a random registration number.
-Write a script to find all the words in the given list that has every
-letter in the given registration number.
+You are given a n x n matrix where n >= 2.
+Write a script to find 3rd smallest element in the sorted matrix.
 
 Example 1
 
-  Input: @words = ('abc', 'abcd', 'bcd'), $reg = 'AB1 2CD'
-  Output: ('abcd')
+  Input: @matrix =  [3, 1, 2], [5, 2, 4], [0, 1, 3]
+  Output: 1
 
-  The only word that matches every alphabets in the given registration number is 'abcd'.
+  The sorted list of the given matrix: 0, 1, 1, 2, 2, 3, 3, 4, 5.
+  The 3rd smallest of the sorted list is 1.
 
 Example 2
 
-  Input: @words = ('job', 'james', 'bjorg'), $reg = '007 JB'
-  Output: ('job', 'bjorg')
+  Input: @matrix = ([2, 1], [4, 5])
+  Output: 4
+
+  The sorted list of the given matrix: 1, 2, 4, 5.
+  The 3rd smallest of the sorted list is 4.
 
 Example 3
 
-  Input: @words = ('crack', 'road', 'rac'), $reg = 'C7 RA2'
-  Output: ('crack', 'rac')
+  Input: @matrix = ([1, 0, 3], [0, 0, 0], [1, 2, 1])
+  Output: 0
 
-MY NOTES: I think the meaning is: form a set of all letters from the
-registration.  Select all words that contain every member of the set.
-That's easy.
+  The sorted list of the given matrix: 0, 0, 0, 0, 1, 1, 1, 2, 3.
+  The 3rd smallest of the sorted list is 0.
+
+MY NOTES: So basically flatten the matrix onto an array, sort it,
+pick out element 2.. easy.  BTW, why does the matrix have to be square,
+any matrix could be flattened and sorted.
 
 GUEST LANGUAGE: As a bonus, I've had a go at translating ch-1.pl into C,
 look in the C/ directory for that.
 
 
-Task 2: Word Stickers
+Task 2: Max Number
 
-You are given a list of word stickers and a target word.
-Write a script to find out how many word stickers is needed to make up
-the given target word.
+You are given a list of positive integers.
+Write a script to concatenate the integers to form the highest possible value.
 
 Example 1:
 
-  Input: @stickers = ('perl','raku','python'), $word = 'peon'
-  Output: 2
-
-  We just need 2 stickers i.e. 'perl' and 'python'.
-  'pe' from 'perl' and
-  'on' from 'python' to get the target word.
+  Input: @list = (1, 23)
+  Output: 231
 
 Example 2:
 
-  Input: @stickers = ('love','hate','angry'), $word = 'goat'
-  Output: 3
-
-  We need 3 stickers i.e. 'angry', 'love' and 'hate'.
-  'g' from 'angry'
-  'o' from 'love' and
-  'at' from 'hate' to get the target word.
+  Input: @list = (10, 3, 2)
+  Output: 3210
 
 Example 3:
 
-  Input: @stickers = ('come','nation','delta'), $word = 'accommodation'
-  Output: 4
-
-  We just need 2 stickers of 'come' and one each of 'nation' & 'delta'.
-  'a' from 'delta'
-  'ccommo' from 2 stickers 'come'
-  'd' from the same sticker 'delta' and
-  'ation' from 'nation' to get the target word.
+  Input: @list = (31, 2, 4, 10)
+  Output: 431210
 
 Example 4:
 
-  Input: @stickers = ('come','country','delta'), $word = 'accommodation'
-  Output: 0
+  Input: @list = (5, 11, 4, 1, 2)
+  Output: 542111
 
-as there's no "i" in the inputs.
+Example 5:
 
+  Input: @list = (1, 10)
+  Output: 110
 
-MY NOTES: ok, so the only tricky part is that each sticker may be used any
-number of times (if any of it's letters remain in the word).  It will be
-worth checking that every letter in the word is present in one or more stickers
-before starting the main search process.
+MY NOTES: First thought: try all combinations.  Second thought: hang on,
+don't we always pick the number with the biggest initial digit, and if
+there's a tie, pick from the numbers with the biggest initial digit the
+one with the biggest prefix?  For example, if we vary example 4 to be:
+Input: @list = (5, 12, 4, 1, 2), the output would be 542121, ie. 5-4-2-12-1.
+Third thought: do I just mean "sort the numbers alphabetically"?
 
-GUEST LANGUAGE: I will have a go at translating ch-2.pl into C tomorrow;
-look in the C/ directory when that's done.
+GUEST LANGUAGE: As a bonus, I had a go at translating ch-2.pl into C,
+look in the C/ directory for that.
diff --git a/challenge-217/duncan-c-white/perl/ch-1.pl b/challenge-217/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..c0399bca26
--- /dev/null
+++ b/challenge-217/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,72 @@
+#!/usr/bin/perl
+# 
+# Task 1: Sorted Matrix
+# 
+# You are given a n x n matrix where n >= 2.
+# Write a script to find 3rd smallest element in the sorted matrix.
+# 
+# Example 1
+# 
+#   Input: @matrix =  [3, 1, 2], [5, 2, 4], [0, 1, 3]
+#   Output: 1
+# 
+#   The sorted list of the given matrix: 0, 1, 1, 2, 2, 3, 3, 4, 5.
+#   The 3rd smallest of the sorted list is 1.
+# 
+# Example 2
+# 
+#   Input: @matrix = ([2, 1], [4, 5])
+#   Output: 4
+# 
+#   The sorted list of the given matrix: 1, 2, 4, 5.
+#   The 3rd smallest of the sorted list is 4.
+# 
+# Example 3
+# 
+#   Input: @matrix = ([1, 0, 3], [0, 0, 0], [1, 2, 1])
+#   Output: 0
+# 
+#   The sorted list of the given matrix: 0, 0, 0, 0, 1, 1, 1, 2, 3.
+#   The 3rd smallest of the sorted list is 0.
+# 
+# MY NOTES: So basically flatten the matrix onto an array, sort it,
+# pick out element 2.. easy.  BTW, why does the matrix have to be square,
+# any matrix could be flattened and sorted.
+# 
+# GUEST LANGUAGE: As a bonus, I also had a go at translating ch-1.pl into C
+# (look in the C directory for that).
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Data::Dumper;
+use List::Util qw(any);
+
+my $debug=0;
+die "Usage: third-from-sorted-matrix [--debug] list-of-rows-in-csv\n"
+	unless GetOptions( "debug"=>\$debug ) && @ARGV>0;
+
+my @m = map { [ split( /,/, $_ ) ] } @ARGV;
+
+my $cols = @{$m[0]};
+my $rows = @m;
+
+say "m: ", Dumper(\@m) if $debug;
+
+die "sorted-matrix: all rows must be $cols columns\n" if any { @$_ != $cols } @m;
+die "sorted-matrix: need at least 3 elements\n" if $rows * $cols < 3;
+
+# flatten
+my @arr;
+foreach my $row (@m)
+{
+	push @arr, @$row;
+}
+
+# sort
+@arr = sort @arr;
+
+# pick third
+say $arr[2];
diff --git a/challenge-217/duncan-c-white/perl/ch-2.pl b/challenge-217/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..fa53d87164
--- /dev/null
+++ b/challenge-217/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,146 @@
+#!/usr/bin/perl
+#
+# Task 2: Max Number
+# 
+# You are given a list of positive integers.
+# Write a script to concatenate the integers to form the highest possible value.
+# 
+# Example 1:
+# 
+#   Input: @list = (1, 23)
+#   Output: 231
+# 
+# Example 2:
+# 
+#   Input: @list = (10, 3, 2)
+#   Output: 3210
+# 
+# Example 3:
+# 
+#   Input: @list = (31, 2, 4, 10)
+#   Output: 431210
+# 
+# Example 4:
+# 
+#   Input: @list = (5, 11, 4, 1, 2)
+#   Output: 542111
+# 
+# Example 5:
+# 
+#   Input: @list = (1, 10)
+#   Output: 110
+# 
+# MY NOTES: First thought: try all combinations.  Second thought: hang on,
+# don't we always pick the number with the biggest initial digit, and if
+# there's a tie, pick (from the numbers with the biggest initial digit) the
+# one with the biggest prefix?  For example, if we vary example 4 to be:
+# Input: @list = (5, 12, 4, 1, 2), the output would be 542121, ie. 5-4-2-12-1.
+# Third thought: do I just mean "sort the numbers alphabetically"?
+# Fourth thought: damn, not quite.  "1-10" beats "10-1". Blast. Can we
+# specify a variant comparator that compares strings favouring shorter ones?
+# Fifth thought: forget sorting.  Back to second thought:-)
+# 
+# GUEST LANGUAGE: As a bonus, I had a go at translating ch-2.pl into C,
+# look in the C/ directory for that.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Data::Dumper;
+use List::Util qw(max);
+use Function::Parameters;
+
+my $debug=0;
+die "Usage: max-concat-number [--debug] intlist\n"
+	unless GetOptions( "debug"=>\$debug ) && @ARGV > 0;
+
+my @list = split( /,/, join(',',@ARGV) );
+
+say "debug: list: ", join(',',@list) if $debug;
+
+#say join('', reverse sort { $a cmp $b } @list);
+
+
+#
+# my @l = delete_first( $v, @list );
+#	Delete the first occurrence of $v from @list,
+#	returning what's left.
+#
+fun delete_first( $v, @list )
+{
+	my $delete = 1;
+	@list = grep { $_ != $v || ($delete-- <= 0) } @list;
+	return @list;
+}
+
+
+#
+# my $big = complex( $listref, @x );
+#	Given @$listref, a list of numbers, and @x, a list of all the values
+#	in @$listref that start with the biggest first digit, try playing
+#	each of @x first, removing it from @$listref and finding the biggest
+#	of what's left, then finding and returning the maximum of all those
+#	possibilities.
+#
+fun complex( $listref, @x )
+{
+	# try each of these @x's plus all the rest, picking the biggest
+	my $max = -1;
+	foreach my $v (@x)
+	{
+		my $result = $v;
+		my @newl = delete_first( $v, @$listref );
+		say "debug: trying result $v, newl=". join(',',@newl)
+			if $debug;
+		$result .= find_biggest( @newl );
+		say "debug: after trying $v + finding biggest, result=$result"
+			if $debug;
+		if( $result > $max )
+		{
+			$max = $result;
+			say "debug: after trying $v, max=$max" if $debug;
+		}
+	}
+	return $max;
+
+}
+
+
+#
+# my $big = find_biggest( @list );
+#	Given a list of numbers, try all concatenations
+#	and find and return the biggest.
+#
+fun find_biggest( @list )
+{
+	my $result = "";
+
+	while( @list )
+	{
+		# find max first digit
+		my $maxdig = max( map { /^(.)/ && $1 } @list );
+		my @x = grep { /^$maxdig/ } @list;
+		say "debug: result=$result, list=". join(',',@list). ", maxdig=$maxdig, x=". join(',',@x)
+			if $debug;
+
+		if( @x == 1 )
+		{
+			$result .= $x[0];
+			@list = delete_first( $x[0], @list );
+			say "debug: 1 x: result=$result, new list=". join(',',@list). " after deleting $x[0]"
+				if $debug;
+		} else
+		{
+			say "debug: >1 x" if $debug;
+			$result .= complex( \@list, @x );
+			return $result;
+		}
+	}
+	return $result;
+}
+
+
+my $big = find_biggest( @list );
+say $big;