Merge pull request #2447 from dcw803/master

added my solutions to challenge 80, 2 easy questions

3 files changed, 185 insertions, 42 deletions

diff --git a/challenge-080/duncan-c-white/README b/challenge-080/duncan-c-white/README
index f173adcc40..425057dfc6 100644
--- a/challenge-080/duncan-c-white/README
+++ b/challenge-080/duncan-c-white/README
@@ -1,67 +1,69 @@
-Task 1: "Fibonacci Sum
+Task 1: "Smallest Positive Number
 
-You are given a positive integer $N.
-
-Write a script to find out all possible combination of Fibonacci Numbers
-required to get $N on addition.
-
-You are NOT allowed to repeat a number. Print 0 if none found.
+You are given unsorted list of integers @N.
 
+Write a script to find out the smallest positive number missing.
 Example 1:
 
-Input: $N = 6
-
-Output:
-    1 + 2 + 3 = 6
-    1 + 5 = 6
+Input: @N = (5, 2, -2, 0)
+Output: 1
 
 Example 2:
 
-Input: $N = 9
+Input: @N = (1, 8, -1)
+Output: 2
 
-Output:
-    1 + 8 = 9
-    1 + 3 + 5 = 9
-"
+Example 3:
 
-My notes: ok. pretty straightforward, especially after last weeks' first task.
-Not quite so trivial to do efficiently, my solution generates a lot of
-duplicate solutions (hence the dedup() function), and is very slow for large N.
-(See also ch-1a.pl for a tabulation of number of Fibonacci sums for i=1..N)
+Input: @N = (2, 0, -1)
+Output: 1
+"
 
+My notes: ok. very straightforward.  Is it worth forming a set of values
+for more efficient "is 1 a member?"  "is 2 a member?" etc? probably:-)
 
-Task 2: "Lonely X
 
-You are given m x n character matrix consists of O and X only.
+Task 2: "Count Candies
 
-Write a script to count the total number of X surrounded by O only. Print
-0 if none found.
+You are given rankings of @N candidates.
 
+Write a script to find out the total candies needed for all candidates. You are asked to follow the rules below:
+a) You must given at least one candy to each candidate.
+b) Candidate with higher ranking get more candies than their mmediate neighbors on either side.
 Example 1:
 
-Input: [ O O X ]
-       [ X O O ]
-       [ X O O ]
+Input: @N = (1, 2, 2)
+
+Explanation:
 
-Output: 1 as there is only one X at the first row last column surrounded
-by only O.
+Applying rule #a, each candidate will get one candy. So total candies
+needed so far 3. Now applying rule #b, the first candidate do not get any
+more candy as its rank is lower than it's neighbours. The second candidate
+gets one more candy as it's ranking is higher than it's neighbour. Finally
+the third candidate do not get any extra candy as it's ranking is not
+higher than neighbour. Therefore total candies required is 4.
+
+Output: 4
 
 Example 2:
 
-Input: [ O O X O ]
-       [ X O O O ]
-       [ X O O X ]
-       [ O X O O ]
+Input: @N = (1, 4, 3, 2)
 
-Output: 2
+Explanation:
 
-    a) First  X found at Row 1 Col 3.
+Applying rule #a, each candidate will get one candy. So total candies
+needed so far 4. Now applying rule #b, the first candidate do not get
+any more candy as its rank is lower than it's neighbours. The second
+candidate gets two more candies as it's ranking is higher than it's
+both neighbour. The third candidate gets one more candy as it's ranking
+is higher than it's neighbour. Finally the fourth candidate do not get
+any extra candy as it's ranking is not higher than neighbour. Therefore
+total candies required is 7.
 
-    b) Second X found at Row 3 Col 4.
+Output: 7
 "
 
-My notes: interesting question, sounds simple but perhaps not quite
-as simple as it sounds.  Especially (obviously) "surrounded by only O"..
-Note that I counted rows and columns from 0, not 1.  So the output I
-generate for the second grid (file grid2) is:
-"2 lonely Xs in grid: [0, 2],[2, 3]"
+My notes: those rules could have written more clearly, but the examples
+clarify that the "neighbours" are linear, not in a ring, so the two
+end people's rankings each have only one neighbour to check.  Each person
+gets between 1..3 candies.  Pretty simple.
diff --git a/challenge-080/duncan-c-white/perl/ch-1.pl b/challenge-080/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..edcb7a5b5e
--- /dev/null
+++ b/challenge-080/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,43 @@
+#!/usr/bin/perl
+#
+# 
+# Task 1: "Smallest Positive Number
+# 
+# You are given unsorted list of integers @N.
+# 
+# Write a script to find out the smallest positive number missing.
+# Example 1:
+# 
+#   Input: @N = (5, 2, -2, 0)
+#   Output: 1
+# 
+# Example 2:
+# 
+#   Input: @N = (1, 8, -1)
+#   Output: 2
+# 
+# Example 3:
+# 
+#   Input: @N = (2, 0, -1)
+#   Output: 1
+# "
+# 
+# My notes: ok. very straightforward.  Is it worth forming a set of values
+# for more efficient "is 1 a member?"  "is 2 a member?" etc? probably:-)
+#
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Data::Dumper;
+
+die "Usage: smallest-+ve list_of_ints\n" unless @ARGV>=1;
+
+my %set = map { $_ => 1 } @ARGV;
+
+my $n;
+for( $n=1; $set{$n}; $n++ )
+{
+}
+say $n;
diff --git a/challenge-080/duncan-c-white/perl/ch-2.pl b/challenge-080/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..1fa0f1eb8d
--- /dev/null
+++ b/challenge-080/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,98 @@
+#!/usr/bin/perl
+#
+# Task 2: "Count Candies
+#
+# You are given rankings of @N candidates.
+# 
+# Write a script to find out the total candies needed for all candidates. You are asked to follow the rules below:
+# a) You must given at least one candy to each candidate.
+# b) Candidate with higher ranking get more candies than their mmediate neighbors on either side.
+# Example 1:
+# 
+# Input: @N = (1, 2, 2)
+# 
+# Explanation:
+# 
+# Applying rule #a, each candidate will get one candy. So total candies
+# needed so far 3. Now applying rule #b, the first candidate do not get any
+# more candy as its rank is lower than it's neighbours. The second candidate
+# gets one more candy as it's ranking is higher than it's neighbour. Finally
+# the third candidate do not get any extra candy as it's ranking is not
+# higher than neighbour. Therefore total candies required is 4.
+# 
+# Output: 4
+# 
+# Example 2:
+# 
+# Input: @N = (1, 4, 3, 2)
+# 
+# Explanation:
+# 
+# Applying rule #a, each candidate will get one candy. So total candies
+# needed so far 4. Now applying rule #b, the first candidate do not get
+# any more candy as its rank is lower than it's neighbours. The second
+# candidate gets two more candies as it's ranking is higher than it's
+# both neighbour. The third candidate gets one more candy as it's ranking
+# is higher than it's neighbour. Finally the fourth candidate do not get
+# any extra candy as it's ranking is not higher than neighbour. Therefore
+# total candies required is 7.
+# 
+# Output: 7
+# "
+# 
+# My notes: those rules could have written more clearly, but the examples
+# clarify that the "neighbours" are linear, not in a ring, so the two
+# end people's rankings each have only one neighbour to check.  Each person
+# gets between 1..3 candies.  Pretty simple.
+#
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Data::Dumper;
+use List::Util qw(max);
+
+die "Usage: count-candies list_of_ints\n" unless @ARGV>=1;
+my @r = @ARGV;
+
+#
+# my $candies = count_candies( @r );
+#	Count the number of candies to be given to people with
+#	rankings @r; return the number of candies.
+#
+fun count_candies( @r )
+{
+	my $candies=@r;
+	foreach my $pos (0..$#r)
+	{
+		$candies++ if $pos>0 && $r[$pos-1] < $r[$pos];
+		$candies++ if $pos<$#r && $r[$pos+1] < $r[$pos];
+	}
+	return $candies;
+}
+
+
+#
+# my $candies = count_candies2( @r );
+#	BETTER WAY to count the number of candies to be given to people with
+#	rankings @r; it occurred to me that an extra candy is given whenever
+#	each adjacent pair of rankings are different (if the first is bigger,
+#	the extra candy is given to the first person, otherwise to the second).
+#	only if the two adjacent rankings are the SAME is no extra candy given.
+#
+fun count_candies2( @r )
+{
+	my $candies=@r;
+	foreach my $pos (0..$#r-1)
+	{
+		$candies++ if $r[$pos] != $r[$pos+1];
+	}
+	return $candies;
+}
+
+
+my $candies = count_candies( @r );
+my $candies2 = count_candies2( @r );
+die "candies:$candies, candies2:$candies2\n" unless $candies==$candies2;
+say $candies;