Merge pull request #2496 from dcw803/master

imported my solutions to this week's questions..

4 files changed, 254 insertions, 44 deletions

diff --git a/challenge-081/duncan-c-white/README b/challenge-081/duncan-c-white/README
index 425057dfc6..520282b4cf 100644
--- a/challenge-081/duncan-c-white/README
+++ b/challenge-081/duncan-c-white/README
@@ -1,69 +1,85 @@
-Task 1: "Smallest Positive Number
+Task 1: "Common Base String
 
-You are given unsorted list of integers @N.
+You are given 2 strings, $A and $B.
+
+Write a script to find out common base strings in $A and $B.
+
+A substring of a string $S is called base string if repeated concatenation
+of the substring results in the string.
 
-Write a script to find out the smallest positive number missing.
 Example 1:
 
-Input: @N = (5, 2, -2, 0)
-Output: 1
+Input:
+    $A = "abcdabcd"
+    $B = "abcdabcdabcdabcd"
+
+Output:
+    ("abcd", "abcdabcd")
 
 Example 2:
 
-Input: @N = (1, 8, -1)
-Output: 2
+Input:
+    $A = "aaa"
+    $B = "aa"
 
-Example 3:
+Output:
+    ("a")"
 
-Input: @N = (2, 0, -1)
-Output: 1
-"
+My notes: ok.  interesting.  sounds like a job for regex matching
 
-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: "Frequency Sort
 
-Task 2: "Count Candies
+You are given file named input.
 
-You are given rankings of @N candidates.
+Write a script to find the frequency of all the words.
 
-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:
+It should print the result as first column of each line should be the
+frequency of the the word followed by all the words of that frequency
+arranged in lexicographical order. Also sort the words in the ascending
+order of frequency.
 
-Input: @N = (1, 2, 2)
+INPUT file
 
-Explanation:
+West Side Story
 
-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.
+The award-winning adaptation of the classic romantic tragedy "Romeo and
+Juliet". The feuding families become two warring New York City gangs,
+the white Jets led by Riff and the Latino Sharks, led by Bernardo. Their
+hatred escalates to a point where neither can coexist with any form
+of understanding. But when Riff's best friend (and former Jet) Tony
+and Bernardo's younger sister Maria meet at a dance, no one can do
+anything to stop their love. Maria and Tony begin meeting in secret,
+planning to run away. Then the Sharks and Jets plan a rumble under the
+highway--whoever wins gains control of the streets. Maria sends Tony
+to stop it, hoping it can end the violence. It goes terribly wrong,
+and before the lovers know what's happened, tragedy strikes and doesn't
+stop until the climactic and heartbreaking ending.
 
-Output: 4
+NOTE
 
-Example 2:
+For the sake of this task, please ignore the following in the input file:
+
+. " ( ) , 's --
+
+OUTPUT
+
+1 But City It Jet Juliet Latino New Romeo Side Story Their Then West York
+adaptation any anything at award-winning away become before begin best
+classic climactic coexist control dance do doesn't end ending escalates
+families feuding form former friend gains gangs goes happened hatred
+heartbreaking highway hoping in know love lovers meet meeting neither no
+one plan planning point romantic rumble run secret sends sister streets
+strikes terribly their two under understanding until violence warring
+what when where white whoever wins with wrong younger
 
-Input: @N = (1, 4, 3, 2)
+2 Bernardo Jets Riff Sharks The by it led tragedy
 
-Explanation:
+3 Maria Tony a can of stop
 
-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.
+4 to
 
-Output: 7
+9 and the
 "
 
-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.
+My notes: classic.  data structure is freq -> list of words of that frequency.
diff --git a/challenge-081/duncan-c-white/perl/WestSideStory b/challenge-081/duncan-c-white/perl/WestSideStory
new file mode 100644
index 0000000000..dfdbdc7766
--- /dev/null
+++ b/challenge-081/duncan-c-white/perl/WestSideStory
@@ -0,0 +1,14 @@
+West Side Story
+
+The award-winning adaptation of the classic romantic tragedy "Romeo and
+Juliet". The feuding families become two warring New York City gangs,
+the white Jets led by Riff and the Latino Sharks, led by Bernardo. Their
+hatred escalates to a point where neither can coexist with any form
+of understanding. But when Riff's best friend (and former Jet) Tony
+and Bernardo's younger sister Maria meet at a dance, no one can do
+anything to stop their love. Maria and Tony begin meeting in secret,
+planning to run away. Then the Sharks and Jets plan a rumble under the
+highway--whoever wins gains control of the streets. Maria sends Tony
+to stop it, hoping it can end the violence. It goes terribly wrong,
+and before the lovers know what's happened, tragedy strikes and doesn't
+stop until the climactic and heartbreaking ending.
diff --git a/challenge-081/duncan-c-white/perl/ch-1.pl b/challenge-081/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..f059f9aa03
--- /dev/null
+++ b/challenge-081/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,76 @@
+#!/usr/bin/perl
+#
+# Task 1: "Common Base String
+# 
+# You are given 2 strings, $A and $B.
+# 
+# Write a script to find out common base strings in $A and $B.
+# 
+# A substring of a string $S is called base string if repeated concatenation
+# of the substring results in the string.
+# 
+# Example 1:
+# 
+# Input:
+#     $A = "abcdabcd"
+#     $B = "abcdabcdabcdabcd"
+# 
+# Output:
+#     ("abcd", "abcdabcd")
+# 
+# Example 2:
+# 
+# Input:
+#     $A = "aaa"
+#     $B = "aa"
+# 
+# Output:
+#     ("a")"
+# 
+# My notes: ok.  interesting.  sounds like a job for regex matching
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Data::Dumper;
+
+die "Usage: common-base-strings a b\n" unless @ARGV==2;
+my( $a, $b ) = @ARGV;
+
+#
+# my @base = find_base_strings( $str );
+#	Find all base strings of $str, where a base string
+#	is a substring that, if repeated some number of times,
+#	makes up the string.
+#
+fun find_base_strings( $str )
+{
+	my $l = length($str);
+	my @result;
+	my %seensub;
+	for( my $i=0; $i<$l; $i++ )
+	{
+		for( my $j=$i; $j<$l; $j++ )
+		{
+			# try substring from pos $i..$j
+			my $sub = substr( $str, $i, 1+$j-$i );
+			next if $seensub{$sub}++;
+			next unless $str =~ /^($sub)+$/;
+			#say "str=$str, sub=$sub";
+			push @result, $sub;
+		}
+	}
+	return @result;
+}
+
+
+my @abase = find_base_strings( $a );
+#say Dumper \@abase;
+my %abaseset = map { $_ => 1 } @abase;
+
+my @bbase = find_base_strings( $b );
+#say Dumper \@bbase;
+
+my @common = grep { $abaseset{$_} } @bbase;
+say for @common;
diff --git a/challenge-081/duncan-c-white/perl/ch-2.pl b/challenge-081/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..7c14950415
--- /dev/null
+++ b/challenge-081/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,104 @@
+#!/usr/bin/perl
+#
+# Task 2: "Frequency Sort
+# 
+# You are given file named input.
+# 
+# Write a script to find the frequency of all the words.
+# 
+# It should print the result as first column of each line should be the
+# frequency of the the word followed by all the words of that frequency
+# arranged in lexicographical order. Also sort the words in the ascending
+# order of frequency.
+# 
+# INPUT file
+# 
+# West Side Story
+# 
+# The award-winning adaptation of the classic romantic tragedy "Romeo and
+# Juliet". The feuding families become two warring New York City gangs,
+# the white Jets led by Riff and the Latino Sharks, led by Bernardo. Their
+# hatred escalates to a point where neither can coexist with any form
+# of understanding. But when Riff's best friend (and former Jet) Tony
+# and Bernardo's younger sister Maria meet at a dance, no one can do
+# anything to stop their love. Maria and Tony begin meeting in secret,
+# planning to run away. Then the Sharks and Jets plan a rumble under the
+# highway--whoever wins gains control of the streets. Maria sends Tony
+# to stop it, hoping it can end the violence. It goes terribly wrong,
+# and before the lovers know what's happened, tragedy strikes and doesn't
+# stop until the climactic and heartbreaking ending.
+# 
+# NOTE
+# 
+# For the sake of this task, please ignore the following in the input file:
+# 
+# . " ( ) , 's --
+# 
+# OUTPUT
+# 
+# 1 But City It Jet Juliet Latino New Romeo Side Story Their Then West York
+# adaptation any anything at award-winning away become before begin best
+# classic climactic coexist control dance do doesn't end ending escalates
+# families feuding form former friend gains gangs goes happened hatred
+# heartbreaking highway hoping in know love lovers meet meeting neither no
+# one plan planning point romantic rumble run secret sends sister streets
+# strikes terribly their two under understanding until violence warring
+# what when where white whoever wins with wrong younger
+# 
+# 2 Bernardo Jets Riff Sharks The by it led tragedy
+# 
+# 3 Maria Tony a can of stop
+# 
+# 4 to
+# 
+# 9 and the
+# "
+# 
+# My notes: classic.  data structure is freq -> list of words of that frequency.
+#
+
+use strict;
+use warnings;
+use feature 'say';
+use Data::Dumper;
+
+die "Usage: frequency-sort filename\n" unless @ARGV==1;
+my $filename = shift;
+
+my %freq;
+open( my $infh, '<', $filename ) || die;
+while( <$infh> )
+{
+	chomp;
+	# ignore: . " ( ) , 's --
+	tr/."(),//d;
+	s/'s//g;
+	s/--/ /g;
+	#say;
+	my @wd = split( /\s+/, $_ );
+	$freq{$_}++ for @wd;
+}
+close($infh);
+
+#say Dumper \%freq;
+
+# build main data structure: array of freq -> list of words
+
+my @fw;
+foreach my $wd (sort keys %freq)
+{
+	my $f = $freq{$wd};
+	$fw[$f] //= [];
+	push @{$fw[$f]}, $wd;
+}
+
+#say Dumper \@fw;
+
+# Display the desired output
+
+foreach my $f (0..$#fw)
+{
+	next unless defined $fw[$f];
+	my @w = @{$fw[$f]};
+	say "\n$f ", join(' ',@w);
+}