Merge pull request #1959 from E7-87-83/master

Cheok Yin's submission to Challenge #069

2 files changed, 178 insertions, 0 deletions

diff --git a/challenge-069/cheok-yin-fung/perl/ch-1.pl b/challenge-069/cheok-yin-fung/perl/ch-1.pl
new file mode 100644
index 0000000000..96d9900c90
--- /dev/null
+++ b/challenge-069/cheok-yin-fung/perl/ch-1.pl
@@ -0,0 +1,71 @@
+#!/usr/bin/perl
+#
+# Perl Weekly Challenge #069 Task 1 - Strobogrammatic Number
+# Usage: ch-1.pl $A $B,  where 1 <= $A <= $B <= 10^15
+# the following code goes "out of memory" around $B >= 10^11
+
+use Algorithm::Combinatorics qw/variations_with_repetition/;
+use strict;
+use warnings;
+
+sub rt180 {
+    my @digits = split // , $_[0];
+    my @newdigits = ();
+    for (@digits) {
+        my $nex;
+        $nex = 1 if $_ == 1;
+        $nex = 0 if $_ == 0;
+        $nex = 8 if $_ == 8;
+        $nex = 9 if $_ == 6;
+        $nex = 6 if $_ == 9;
+        unshift @newdigits, $nex;    
+    }
+    return join '', @newdigits;
+}
+
+my @ans = ();
+my $begin = 3;
+my $end = 4;
+if ($ARGV[0] and $ARGV[1]) {
+    $begin = $ARGV[0];
+    $end = $ARGV[1]; 
+}
+
+my $sbegin = length $begin;
+my $send = length $end;
+
+if ($sbegin == 1) {
+    $sbegin = 2;
+    if ($send != 1) {
+        @ans = ($begin..9);
+    } else {
+        @ans = ($begin..$end);
+    }
+}
+
+for my $s ($sbegin .. $send) {
+    foreach my $r (qw/1 6 8 9/) {
+        my $o = variations_with_repetition([0, 1, 6, 8, 9],$s-1);
+        while (my $y = $o->next) {
+            my $string = $r.(join '', @{$y});
+            push @ans, $string if $string eq rt180($string);
+        }
+    }
+}
+
+
+for (@ans) {
+    print $_, " " if $_ <= $end and $_ >= $begin;
+}
+
+
+print "\n";
+
+
+# $ time perl ch-1.pl 100000001 999999999 > ans069.txt (10^8+1 to 10^9-1)
+# 
+# real	0m9.288s
+# user	0m9.282s
+# sys	0m0.004s
+
+# not very satisfactory
diff --git a/challenge-069/cheok-yin-fung/perl/ch-2.pl b/challenge-069/cheok-yin-fung/perl/ch-2.pl
new file mode 100644
index 0000000000..f01259207d
--- /dev/null
+++ b/challenge-069/cheok-yin-fung/perl/ch-2.pl
@@ -0,0 +1,107 @@
+#!/usr/bin/perl
+#
+# Perl Weekly Challenge #069 Task 2
+# Usage: ch-2.pl $N
+
+# SN = SN-1 + “0” + switch(reverse(SN-1))
+# SN = SN-2 + “0” + switch(reverse(SN-2)) + "0" + SN-2 + "1" + switch(reverse(SN-2))
+# on my computer, ordinary action goes "out of memory" when $N>26.
+# Therefore I write a roundabout to tackle $N=30
+
+
+use strict;
+use warnings;
+
+my $N = 3;
+
+if ($ARGV[0]) {
+    $N = $ARGV[0];
+}
+
+sub sr {
+    my @digits = split // , $_[0]; 
+    my @newdigits;
+    for (@digits) {
+        unshift @newdigits, (1+$_) % 2;
+    }
+    return join "", @newdigits;
+}
+
+
+my @S = ("", "0");
+my @R;
+
+for (my $d = $N % 2 + 2; $d <= $N and $d<=26 ; $d += 2) {
+    $R[$d-2] = sr($S[$d-2]);
+    $S[$d] = $S[$d-2] . "0" . $R[$d-2]. "0" . $S[$d-2]. "1". $R[$d-2];
+}
+
+if ($N <= 26) {
+    print $S[$N];
+} elsif ($N !=30) {
+    print "too large!";
+}
+
+print "\n";
+
+
+#the following are for $N=30
+
+#   $S[$d] = $S[$d-2] . "0" . $R[$d-2]. "0" . $S[$d-2]. "1". $R[$d-2];
+#   $R[$d] = $S[$d-2] . "0" . $R[$d-2]. "1" . $S[$d-2]. "1". $R[$d-2];
+sub print_S28 {
+    print $S[26];
+    print "0";
+    print $R[26];
+    print "0";
+    print $S[26];
+    print "1";
+    print $R[26];
+}
+
+sub print_R28 {
+    print $S[26];
+    print "0";
+    print $R[26];
+    print "1";
+    print $S[26];
+    print "1";
+    print $R[26];
+}
+if ($N == 30) {
+    $R[26] = $S[24]."0".$R[24]."1".$S[24]."1".$R[24];
+    print_S28;
+    print "0";
+    print_R28;
+    print "0";
+    print_S28;
+    print "1";
+    print_R28;
+    
+} 
+print "\n";
+
+
+# $N = 25 -->
+# real	0m7.241s
+# user	0m3.701s
+# sys	0m0.681s
+#
+#
+#$ perl ch-2.pl 7
+#0010011000110110001001110011011000100110001101110010011100110110001001100011011000100111001101110010011000110111001001110011011
+
+# $ time perl ch-2.pl 26 > S26.txt
+# 
+# real	0m8.045s
+# user	0m7.172s
+# sys	0m0.863s
+
+#$ time perl ch-2.pl 30 > S30.txt
+#
+# real	0m12.099s
+# user	0m7.873s
+# sys	0m1.432s
+# 
+# size of S26.txt : 67.1 MB
+# size of S30.txt :  1.1 GB