Merge pull request #1983 from dcw803/master

imported this week's solutions; two easy problems

3 files changed, 203 insertions, 26 deletions

diff --git a/challenge-070/duncan-c-white/README b/challenge-070/duncan-c-white/README
index b2d39277b7..6f2a919fd6 100644
--- a/challenge-070/duncan-c-white/README
+++ b/challenge-070/duncan-c-white/README
@@ -1,45 +1,81 @@
-Task 1: "Strobogrammatic Number
+Task 1: "Character Swapping
 
-A strobogrammatic number is a number that looks the same when looked at
-upside down.
+You are given a string $S of size $N.
 
-You are given two positive numbers $A and $B such that 1 <= $A <= $B <= 10^15.
+You are also given swap count $C and offset $O such that $C >= 1, $O >=
+1, $C <= $O and $C + $O <= $N.
 
-Write a script to print all strobogrammatic numbers between the given
-two numbers.
+Write a script to perform character swapping like below:
 
-Example
+for i = 1 to $C
+  S[ i % N ] <=> S[ (i + O) % N ]
+
+Example 1
+
+Input:
+    $S = 'perlandraku'
+    $C = 3
+    $O = 4
+
+01234567890
+perlandraku
 
-Input: $A = 50, $B = 100
-    Output: 69, 88, 96
+Character Swapping:
+    swap 1: pos 1 and 5: e <=> n = pnrlaedraku
+    swap 2: pos 2 and 6: r <=> d = pndlaerraku
+    swap 3: pos 3 and 7: l <=> r = pndraerlaku
+
+Output:
+    pndraerlaku
 "
 
-My notes: ok.  Wikipedia suggests 0, 1, 6, 8 and 9 are only digits to consider,
-0, 1 and 8 are their own inverses, and 6 and 9 form the only inverse pair
-(unless you include 2 and 5 like on an 8-segment lcd display).
+My notes: ok.  none of $i % N (for i=1..$C) needs the % N
+given that $C + $O <= $N and min $O is 1.  So that becomes:
+
+for i = 1 to $C
+  S[ i ] <=> S[ (i + O) % N ]
+
+and the only one of the (i + O) % N expressions that may need
+the % N part is i=C, when C+O == N.  Of course i + O increments
+so pre-calculate it, and set it back to 0 hit it hits N.
 
 
-Task 2: "0/1 String
+Task 2: "Gray Code Sequence
 
-A 0/1 string is a string in which every character is either 0 or 1.
+You are given an integer 2 <= $N <= 5.
 
-Write a script to perform switch and reverse to generate S30 as described below:
+Write a script to generate $N-bit gray code sequence.
 
-switch:
+2-bit Gray Code Sequence: [0, 1, 3, 2]
 
-Every 0 becomes 1 and every 1 becomes 0. For example, '101' becomes '010'.
+To generate the 3-bit Gray code sequence from the 2-bit Gray code sequence,
+follow the step below:
 
-reverse:
+2-bit Gray Code sequence:                  [0, 1, 3, 2]
 
-The string is reversed. For example, "001" becomes "100".
+Binary form of the sequence        a) S1 = [00, 01, 11, 10]
 
-Please follow the rule as below:
+Reverse of S1                      b) S2 = [10, 11, 01, 00]
 
-S0 = ""
-S1 = "0"
-S2 = "001"
-S3 = "0010011"
+Prefix all entries of S1 with '0'  c) S1 = [000, 001, 011, 010]
 
-SN = SN-1 + '0' + switch(reverse(SN-1))
+Prefix all entries of S2 with '1'  d) S2 = [110, 111, 101, 100]
+
+Concatenate S1 and S2 gives 3-bit Gray Code sequence
+				   e) [000, 001, 011, 010, 110, 111, 101, 100]
+
+Now convert them back to decimal:
+
+3-bit Gray Code sequence              [0, 1, 3, 2, 6, 7, 5, 4]
+
+Example
+
+Input: N = 4
+Output: [0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]
+"
 
-My notes: ok.  Defined by a recursive recurrence relation.  switch means 1s-complement.
+My notes: ok.  However, there's no point in taking the original N-1-bit gray
+code sequence, converting it to binary, prepending zeroes and converting it
+back to decimal - because leading zeroes don't change the decimal numbers.
+So the first half of the N-bit gray code sequence is simply the N-1-bit gray
+code sequence.
diff --git a/challenge-070/duncan-c-white/perl/ch-1.pl b/challenge-070/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..eae1dfe7f0
--- /dev/null
+++ b/challenge-070/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,71 @@
+#!/usr/bin/perl
+#
+# Task 1: "Character Swapping
+# 
+# You are given a string $S of size $N.
+# 
+# You are also given swap count $C and offset $O such that $C >= 1, $O >=
+# 1, $C <= $O and $C + $O <= $N.
+# 
+# Write a script to perform character swapping like below:
+# 
+# for i = 1 to $C
+#   S[ i % N ] <=> S[ (i + O) % N ]
+# 
+# Example 1
+# 
+# Input:
+#     $S = 'perlandraku'
+#     $C = 3
+#     $O = 4
+# 
+# 01234567890
+# perlandraku
+# 
+# Character Swapping:
+#     swap 1: pos 1 and 5: e <=> n = pnrlaedraku
+#     swap 2: pos 2 and 6: r <=> d = pndlaerraku
+#     swap 3: pos 3 and 7: l <=> r = pndraerlaku
+# 
+# Output:
+#     pndraerlaku
+# "
+# 
+# My notes: ok.  none of $i % N (for i=1..$C) needs the % N
+# given that $C + $O <= $N and min $O is 1.  So that becomes:
+# 
+# for i = 1 to $C
+#   S[ i ] <=> S[ (i + O) % N ]
+# 
+# and the only one of the (i + O) % N expressions that may need
+# the % N part is i=C, when C+O == N.  Of course i + O increments
+# so pre-calculate it, increment it each time through the loop,
+# and set it back to 0 hit it hits N.
+#
+
+use strict;
+use warnings;
+use feature 'say';
+#use Function::Parameters;
+#use Data::Dumper;
+
+die "Usage: char-swaps S C O\n" unless @ARGV==3;
+my( $s, $c, $o ) = @ARGV;
+my $n = length($s);
+
+die "char-swaps: C must be >= 1 ($c given)\n" unless $c>=1;
+die "char-swaps: O must be >= 1 ($o given)\n" unless $o>=1;
+die "char-swaps: C must be <= O (C:$c, O:$o given)\n" unless $c<=$o;
+die "char-swaps: C + O must be <= N (C:$c, O:$o, N:$n given)\n" unless
+	$c + $o <= $n;
+
+my $dst = $o+1;
+foreach my $i (1..$c)
+{
+	( substr($s,$i,1), substr($s,$dst,1) ) =
+		( substr($s,$dst,1), substr($s,$i,1) );
+	$dst++;
+	$dst = 0 if $dst == $n;
+}
+
+say "result: $s";
diff --git a/challenge-070/duncan-c-white/perl/ch-2.pl b/challenge-070/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..e651df68e3
--- /dev/null
+++ b/challenge-070/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,70 @@
+#!/usr/bin/perl
+#
+# Task 2: "Gray Code Sequence
+# 
+# You are given an integer 2 <= $N <= 5.
+# 
+# Write a script to generate $N-bit gray code sequence.
+# 
+# 2-bit Gray Code Sequence: [0, 1, 3, 2]
+# 
+# To generate the 3-bit Gray code sequence from the 2-bit Gray code sequence,
+# follow the step below:
+# 
+# 2-bit Gray Code sequence:                  [0, 1, 3, 2]
+# 
+# Binary form of the sequence        a) S1 = [00, 01, 11, 10]
+# 
+# Reverse of S1                      b) S2 = [10, 11, 01, 00]
+# 
+# Prefix all entries of S1 with '0'  c) S1 = [000, 001, 011, 010]
+# 
+# Prefix all entries of S2 with '1'  d) S2 = [110, 111, 101, 100]
+# 
+# Concatenate S1 and S2 gives 3-bit Gray Code sequence
+# 				   # e) [000, 001, 011, 010, 110, 111, 101, 100]
+# 
+# Now convert them back to decimal:
+# 
+# 3-bit Gray Code sequence              [0, 1, 3, 2, 6, 7, 5, 4]
+# 
+# Example
+# 
+# Input: N = 4
+# Output: [0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]
+# "
+# 
+# My notes: ok.  However, there's no point in taking the original N-1-bit gray
+# code sequence, converting it to binary, prepending zeroes and converting it
+# back to decimal - because leading zeroes don't change the decimal numbers.
+# So the first half of the N-bit gray code sequence is simply the N-1-bit gray
+# code sequence unmodified
+#
+
+use strict;
+use warnings;
+use feature 'say';
+#use Function::Parameters;
+use Data::Dumper;
+
+die "Usage: gray-code N\n" unless @ARGV==1;
+my $n = shift;
+
+die "gray-code: 1 <= N <= 5 ($n given)\n" unless $n>=1 && $n<=5;
+
+my @seq = (0,1);	# gray(1)
+foreach my $i (2..$n)
+{
+	# the core of the method:
+	#	- reverse:        @x = reverse @seq
+	#	- cvt to binary (i-1 digits long, leading zeroes):
+	#			  @x = map { sprintf( "%0*b", i-1, $_ ) } @x
+	#	- prepend 1:      @x = map { "1$_" } @x
+	#	- cvt to decimal: @x = map { eval "0b$_" }  @x )
+	my @mutate = map { eval sprintf( "0b1%0*b", $i-1, $_ ) } reverse @seq;
+	#die Dumper \@mutate;
+	push @seq, @mutate;
+	#warn Dumper \@seq;
+}
+
+say "gray($n) = ", join(',',@seq);