diff options
| -rw-r--r-- | challenge-069/duncan-c-white/README | 56 | ||||
| -rwxr-xr-x | challenge-069/duncan-c-white/perl/ch-1.pl | 62 | ||||
| -rwxr-xr-x | challenge-069/duncan-c-white/perl/ch-2.pl | 55 |
3 files changed, 147 insertions, 26 deletions
diff --git a/challenge-069/duncan-c-white/README b/challenge-069/duncan-c-white/README index 36a77b6d74..b2d39277b7 100644 --- a/challenge-069/duncan-c-white/README +++ b/challenge-069/duncan-c-white/README @@ -1,41 +1,45 @@ -Task 1: "Number Combinations +Task 1: "Strobogrammatic Number -You are given two integers $m and $n. Write a script print all possible -combinations of $n numbers from the list 1 2 3 ... $m. +A strobogrammatic number is a number that looks the same when looked at +upside down. -Every combination should be sorted i.e. [2,3] is a valid combination but -[3,2] is not. +You are given two positive numbers $A and $B such that 1 <= $A <= $B <= 10^15. -Example: +Write a script to print all strobogrammatic numbers between the given +two numbers. -Input: $m = 5, $n = 2 +Example -Output: [ [1,2], [1,3], [1,4], [1,5], [2,3], [2,4], [2,5], [3,4], [3,5], [4,5] ] +Input: $A = 50, $B = 100 + Output: 69, 88, 96 " -My notes: generally I hate permutation questions, but this looks ok. +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). -Task 2: "Letter Phone +Task 2: "0/1 String -You are given a digit string $S. Write a script to print all possible letter combinations that the given digit string could represent. +A 0/1 string is a string in which every character is either 0 or 1. -(1 represents _ or @, -2 A,B or C, -3 D,E or F, -4 G, H or I, -5 J, K or L, -6 M, M or O, -7 P, Q, R or S, -8 T, U or V, -9 W, X, Y or Z -letters from a phone panel) +Write a script to perform switch and reverse to generate S30 as described below: -Example: +switch: - Input: $S = '35' +Every 0 becomes 1 and every 1 becomes 0. For example, '101' becomes '010'. - Output: ["dj", "dk", "dl", "ej", "ek", "el", "fj", "fk", "fl"]. +reverse: -My notes: sounds pretty easy. Lookup the set of possibilities for each -letter, then cross-product them. +The string is reversed. For example, "001" becomes "100". + +Please follow the rule as below: + +S0 = "" +S1 = "0" +S2 = "001" +S3 = "0010011" + +SN = SN-1 + '0' + switch(reverse(SN-1)) + +My notes: ok. Defined by a recursive recurrence relation. switch means 1s-complement. diff --git a/challenge-069/duncan-c-white/perl/ch-1.pl b/challenge-069/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..abe975077a --- /dev/null +++ b/challenge-069/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,62 @@ +#!/usr/bin/perl +# +# Task 1: "Strobogrammatic Number +# +# A strobogrammatic number is a number that looks the same when looked at +# upside down. +# +# You are given two positive numbers $A and $B such that 1 <= $A <= $B <= 10^15. +# +# Write a script to print all strobogrammatic numbers between the given +# two numbers. +# +# Example +# +# Input: $A = 50, $B = 100 +# Output: 69, 88, 96 +# " +# +# My notes: ok. Wikipedia suggests 0, 1, 6, 8 and 9 are only digits to +# consider, 0, 1 and 8 are their own inverses, 6 and 9 form the only +# inverse pair (unless you include 2 and 5 like on an 8-segment lcd display). +# + +use strict; +use warnings; +use feature 'say'; +use List::MoreUtils qw(pairwise any); +use Function::Parameters; +use Data::Dumper; + +die "Usage: strobogrammatic M N\n" unless @ARGV==2; + +my %inverse = qw(0 0 1 1 8 8 6 9 9 6); + +# +# my $isstrobo = strobo( $x ); +# Return 1 iff $x is strobogrammatic, else 0. +# +fun strobo( $x ) +{ + return 0 if $x =~ /[2-57]/; + my @d = split(//,$x); + my @r = reverse @d; + my @ok = pairwise { + #say "debug: a=$a, b=$b, inverse(a)=$inverse{$a}"; + $inverse{$a} == $b ? 1 : 0 + } @d, @r; + #say "debug: ok=", join(',',@ok); + return 0 if any { $_ == 0 } @ok; + return 1; +} + + + +my( $m, $n ) = @ARGV; + +say "strobogrammatic numbers between $m and $n are:"; + +foreach my $i ($m..$n) +{ + say $i if strobo($i); +} diff --git a/challenge-069/duncan-c-white/perl/ch-2.pl b/challenge-069/duncan-c-white/perl/ch-2.pl new file mode 100755 index 0000000000..faf1afe1b1 --- /dev/null +++ b/challenge-069/duncan-c-white/perl/ch-2.pl @@ -0,0 +1,55 @@ +#!/usr/bin/perl +# +# Task 2: "0/1 String +# +# A 0/1 string is a string in which every character is either 0 or 1. +# +# Write a script to generate S30 under the following rules: +# +# S0 = "" +# S1 = "0" +# S2 = "001" +# S3 = "0010011" +# +# SN = SN-1 + '0' + switch(reverse(SN-1)) +# +# switch: +# Every 0 becomes 1 and every 1 becomes 0. For example, '101' becomes '010'. +# +# reverse: +# The string is reversed. For example, "001" becomes "100". +# +# My notes: ok. Binary strings, defined by a recurrence relation, can be +# computed iteratively. btw, 'switch' means 1s-complement. +# + +use strict; +use warnings; +use feature 'say'; +use Function::Parameters; +use Data::Dumper; + +die "Usage: binary-switch-reverse N\n" unless @ARGV==1; +my $n = shift; + + +# +# my $ss = switch($s); +# Return the string 1-s complement of the binary string $s. +# eg. switch('001') is '110'. +# +fun switch( $s ) +{ + $s =~ tr/01/10/; + return $s; +} + + +my $s = ""; +foreach my $x (1..$n) +{ + # SN = SN-1 + '0' + switch(reverse(SN-1)) + $s .= '0' . switch(reverse($s)); + #say "s($x) = $s"; +} +say "s($n) = $s"; |