Merge pull request #1950 from simongreen-net/swg-069

Simon's Challenge 069 solutions

3 files changed, 138 insertions, 27 deletions

diff --git a/challenge-069/sgreen/README.md b/challenge-069/sgreen/README.md
index c19c15e7d2..a4a45d0687 100644
--- a/challenge-069/sgreen/README.md
+++ b/challenge-069/sgreen/README.md
@@ -1,41 +1,40 @@
 Solution by Simon Green
+# Perl Weekly Challenge 069
 
-I've decided to jump the of Perl Weekly Challenge bandwagon. Seems like too much fun to miss out on :)
+## TASK #1 › Strobogrammatic Number
 
-# TASK #1 › Zero Matrix
+This is a lot harder than it looks. My first thought is to just do a foreach loop between `$a` and `$b` and add it to the list if the number is strobogrammatic. However when I ran
 
-It wasn't clear on how the values of the matrix were to be supplied, so I assumed it was to be supplied in the program. It's been a long time since I needed to read from STDIN in Perl, nothing that a quick Internet search didn't solve. When processing the input, I strip all characters that aren't 0 or 1 so the user could specify `[1, 0, 1]` or `101` or even `1some0thing1`.
+    perl -E '$b = 0; foreach my $a (0 ..  10**10) { $b++ } say $b;'
 
-Once we had the values, there were a few ways this could be solved. It seemed the easiest way was to note all the columns and rows that had a zero value. When displaying the matrix, it would only show '1' if the value is one, and neither the column or row was marked as a negative value.
+on my PC, that took nearly 3 minutes. With $b being up to 10<sup>15</sup> this was not a feasible approach. Even if I only had all the numbers between 1 and 10<sup>15</sup> containing only the digits 0, 6, 8, 9 that was still going to be in the billions.
 
-An alternate approach would be to do the calculations without using the negative columns and rows logic. This would however require more computation and require a bit more logic.
+So I took a different approach. I calculated the first half of all valid numbers, and then generated the second half. The logic is pretty simple. The first digit must be 6, 8 or 9 (as 0 isn't valid as a first digit). If the number of digits is odd, the middle number can only be 0 or 8.
 
-## Examples
-    » ./ch-1.pl 3 3
-    Enter values for row 1: [1, 0, 1]
-    Enter values for row 2: [1, 1, 1]
-    Enter values for row 3: [1, 1, 1]
-    [ 0, 0, 0 ]
-    [ 1, 0, 1 ]
-    [ 1, 0, 1 ]
+Taking this approach, I can generate all 49,150 strobogrammatic numbers between 1 and 10<sup>15</sup> in less than half a second.
 
-    » ./ch-1.pl 3 3
-    Enter values for row 1: [1, 0, 1]
-    Enter values for row 2: [1, 1, 1]
-    Enter values for row 3: [1, 0, 1]
-    [ 0, 0, 0 ]
-    [ 1, 0, 1 ]
-    [ 0, 0, 0 ]
+### Examples
+    » ./ch-1.pl 50 100
+    69 88 96
 
+    » ./ch-1.pl 50 900
+    69 88 96 609 689 808 888
 
-# TASK #2 › Reorder List
+## TASK #2 › 0/1 String
 
-This was definitely the easier of the two tasks. Essentially I caclulated the half value of the length of the array, and then used a loop to add the Xth element and Xth from the end element. If the list is an odd value, I added the middle value as that wouldn't have been added in the loop.
+After the first task, these seemed a lot easier. But it wasn't entirely straight forward. I thought I had a bug in my code when it was spewing out digits on my screen. It turns out that is expected. The length of a number is twice the length of a previous number plus one. This meant the expected length was:
 
-## Examples
+    1st  1
+    2nd  3
+    3rd  7
+    4th  15
+    5th  31
+    10th 1,023
+    15th 32,767
+    20th 1,048,575
+    25th 33,554,431
+    30th 1,073,741,823
 
-    » ./ch-2.pl 1 2 3 4
-    1 4 2 3
+No wonder the task was changed from 1,000 iterations to 30! It goes without saying I'm not posting an example here, as the final line is 1,073,741,823 characters long.
 
-    » ./ch-2.pl 1 2 3 4 5
-    1 5 2 4 3
\ No newline at end of file
+Thankfully perl has a built in [reverse](https://perldoc.pl/functions/reverse) operator which does what you expect to do on a scalar (string). For the switch I used `tr/01/10/` which [translates](https://perldoc.pl/perlop#tr/SEARCHLIST/REPLACEMENTLIST/cdsr) the zeros to one and visa versa.
\ No newline at end of file
diff --git a/challenge-069/sgreen/perl/ch-1.pl b/challenge-069/sgreen/perl/ch-1.pl
new file mode 100755
index 0000000000..4c35b26d1b
--- /dev/null
+++ b/challenge-069/sgreen/perl/ch-1.pl
@@ -0,0 +1,88 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+use 5.10.1;
+
+sub _generate_number ($$) {
+    # Given the first half of a number, generate the whole number
+    my ( $number, $length ) = @_;
+    my %switch = ( 0 => 0, 6 => 9, 8 => 8, 9 => 6 );
+    my @digits = reverse( split //, $number );
+
+    # If an odd number of digits required, the middle (last) digit needs
+    #  to be 0 or 8
+    return 0 if $length % 2 and shift(@digits) !~ /[08]/;
+
+    # Take each remaining digitis (in reverse order) to calculate the
+    #  whole number
+    foreach my $digit (@digits) {
+        $number .= $switch{$digit};
+    }
+
+    return $number;
+}
+
+sub _half_length ($) {
+    # Calculate the minimum number of digits to generate at least half
+    #  the number of digits
+    return int( ( shift() + 1 ) / 2 );
+}
+
+sub main (@) {
+    my ( $a, $b ) = @_;
+    my @numbers = ();
+
+    # Sanity checks of the input
+    die "First value is not between 1 and 10^15"
+      unless $a =~ /^[0-9]+$/
+      and $a >= 1
+      and $a <= 10**15;
+
+      die "Second value is not between 1 and 10^15"
+      unless $b =~ /^[0-9]+$/
+      and $b >= 1
+      and $b <= 10**15;
+
+    # 10^15 isn't strobogrammatic, so do one less
+    $b -= 1 if $b == 10**15;
+
+    # Digits that are strobogrammatic
+    my @d = ( 0, 6, 8, 9 );
+
+    # ... however 0 can't be the first digit
+    my @list = ( 6, 8, 9 );
+
+    for my $length ( 1 .. length($b) ) {
+        # Do we need to an another digit to the list
+        if ( length( $list[0] ) < _half_length($length) ) {
+            my @new_list = ();
+            foreach my $old_list (@list) {
+                push @new_list, map { $old_list . $_ } @d;
+            }
+            @list = @new_list;
+        }
+
+        # We now have the first half of all the digits that are
+        #  strobogrammatic for the given length. Time to generate
+        #  the whole number
+        for my $item (@list) {
+            my $number = _generate_number( $item, $length );
+
+            # Don't add the number if it isn't valid (middle digit != 0, 8)
+            #  or less than the minimum
+            next if !$number or $number < $a;
+
+            # If the number is grater than than the maximum, we can exit
+            #  as we know @list is in order.
+            last if $number > $b;
+
+            push @numbers, $number if $number;
+        }
+    }
+
+    say join( ' ', @numbers );
+}
+
+main(@ARGV);
+
diff --git a/challenge-069/sgreen/perl/ch-2.pl b/challenge-069/sgreen/perl/ch-2.pl
new file mode 100755
index 0000000000..82110d1258
--- /dev/null
+++ b/challenge-069/sgreen/perl/ch-2.pl
@@ -0,0 +1,24 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+use 5.10.1;
+
+sub main() {
+    my $string = "";
+    for my $n ( 1 .. 30 ) {
+        my $previous = $string;
+
+        #Reverse the string
+        $string = reverse($string);
+
+        # Switch the digits
+        $string =~ tr/01/10/;
+
+        # Prefix by the original string, a zero and print it
+        $string = "${previous}0$string";
+        say "S$n = $string";
+    }
+}
+
+main();