diff options
| -rw-r--r-- | challenge-141/duncan-c-white/README | 89 | ||||
| -rwxr-xr-x | challenge-141/duncan-c-white/perl/ch-1.pl | 55 | ||||
| -rwxr-xr-x | challenge-141/duncan-c-white/perl/ch-2.pl | 122 |
3 files changed, 223 insertions, 43 deletions
diff --git a/challenge-141/duncan-c-white/README b/challenge-141/duncan-c-white/README index 90ddabae47..40b57c7ac8 100644 --- a/challenge-141/duncan-c-white/README +++ b/challenge-141/duncan-c-white/README @@ -1,67 +1,70 @@ -TASK #1 - Add Binary +TASK #1 - Number Divisors -You are given two decimal-coded binary numbers, $a and $b. +Write a script to find lowest 10 positive integers having exactly 8 divisors. -Write a script to simulate the addition of the given binary numbers. +Example -Example 1 + 24 is the first such number having exactly 8 divisors. + 1, 2, 3, 4, 6, 8, 12 and 24. - Input: $a = 11; $b = 1; - Output: 100 +MY NOTES: Very easy. -Example 2 - Input: $a = 101; $b = 1; - Output: 110 +TASK #2 - Like Numbers -Example 3 +You are given positive integers, $m and $n. Write a script to find +total count of integers created using the digits of $m which is also +divisible by $n. - Input: $a = 100; $b = 11; - Output: 111 +Repeating of digits are not allowed. Order/Sequence of digits can't +be altered. You are only allowed to use (n-1) digits at the most. For +example, 432 is not acceptable integer created using the digits of +1234 (because the digits are in the wrong order). Also for 1234, you can +only have integers having no more than three digits. -MY NOTES: Very easy. Extract least significant binary digit via $a % 10, -implement full adder (bit,bit,carryin)->(bit,carryout), recurse and recombine. +Example 1: + Input: $m = 1234, $n = 2 + Output: 9 -TASK #2 - Multiplication Table + Possible integers created using the digits of 1234 are: + 1, 2, 3, 4, 12, 13, 14, 23, 24, 34, 123, 124, 134 and 234. -You are given 3 positive integers, $i, $j and $k. + There are 9 integers divisible by 2 such as: + 2, 4, 12, 14, 24, 34, 124, 134 and 234. -Write a script to print the $kth element in the sorted multiplication -table of $i and $j. +Example 2: -Example 1 - - Input: $i = 2; $j = 3; $k = 4 + Input: $m = 768, $n = 4 Output: 3 -Since the multiplication of 2 x 3 is as below: - - 1 2 3 - 2 4 6 - -The sorted multiplication table: - - 1 2 2 3 4 6 - -Now the 4th element in the table is "3". - -Example 2 + Possible integers created using the digits of 768 are: + 7, 6, 8, 76, 78 and 68. - Input: $i = 3; $j = 3; $k = 6 - Output: 4 + There are 3 integers divisible by 4 such as: + 8, 76 and 68. -Since the multiplication of 3 x 3 is as below: - 1 2 3 - 2 4 6 - 3 6 9 +MY NOTES: Sounds pretty easy. However, there's one mistake: +"You are only allowed to use (n-1) digits at the most" +is flatly contradicted by the examples. I assume it meant +"length(m)-1" which is what the examples show. -The sorted multiplication table: +So each digit can either be present or absent - it's another "subsets" +task. One wrinkle: the length(m)-1 rule means that (all-present) is +not a valid combination. Plus of course (all-absent) isn't either. - 1 2 2 3 3 4 6 6 9 +Last time we did a "subsets" task was in Challenge 136 Task 2, +Fibonacci Seqence. In that, I wrote: -Now the 6th element in the table is "4". +"How do we sum subsets of values? Two obvious ways: +1. recursive function, iterating over the values: each value is either in the + subset or not, try both possibilities. +2. binary-counting method, iterate over every combination C from 1 .. + 2**(number values)-1, then sum up only the elements where the corresponding + bit in C is on. +" -MY NOTES: Sounds pretty easy. The table's ith row is (1..$j) * $i. +That time, I wrote a (2) binary-counting method. So this time round, let's +try a recursive function instead, just for variety. diff --git a/challenge-141/duncan-c-white/perl/ch-1.pl b/challenge-141/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..d74e3ef6a8 --- /dev/null +++ b/challenge-141/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,55 @@ +#!/usr/bin/perl +# +# TASK #1 - Number Divisors +# +# Write a script to find lowest 10 positive integers having exactly 8 divisors. +# +# Example +# +# 24 is the first such number having exactly 8 divisors. +# 1, 2, 3, 4, 6, 8, 12 and 24. +# +# MY NOTES: Very easy. +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +#use Data::Dumper; + +# +# my @div = divisors( $n ); +# Find and return all the divisors of $n, including 1. +# +sub divisors +{ + my( $n ) = @_; + my @d = (1); + my $halfn = int($n/2); + for( my $i=2; $i<=$halfn; $i++ ) + { + push @d, $i if $n%$i==0; + } + push @d, $n; + return @d; +} + + +my $debug=0; +die "Usage: number-divisors [--debug] Nresults Ndivisors\n" unless + GetOptions( "debug"=>\$debug ) && @ARGV==2; +my( $nresults, $ndivisors ) = @ARGV; + +die "number-divisors: Ndivisors ($ndivisors) must be > 1\n" + if $ndivisors < 2; + +my $found = 0; +for( my $n = 1; $found < $nresults; $n++ ) +{ + my @div = divisors( $n ); + next if @div != $ndivisors; + $found++; + say "$n has $ndivisors divisors"; + say " they are ", join(', ',@div) if $debug; +} diff --git a/challenge-141/duncan-c-white/perl/ch-2.pl b/challenge-141/duncan-c-white/perl/ch-2.pl new file mode 100755 index 0000000000..87b281389b --- /dev/null +++ b/challenge-141/duncan-c-white/perl/ch-2.pl @@ -0,0 +1,122 @@ +#!/usr/bin/perl +# +# TASK #2 - Like Numbers +# +# You are given positive integers, $m and $n. Write a script to find +# total count of integers created using the digits of $m which is also +# divisible by $n. +# +# Repeating of digits are not allowed. Order/Sequence of digits can't +# be altered. You are only allowed to use (n-1) digits at the most. For +# example, 432 is not acceptable integer created using the digits of +# 1234 (because the digits are in the wrong order). Also for 1234, you can +# only have integers having no more than three digits. +# +# Example 1: +# +# Input: $m = 1234, $n = 2 +# Output: 9 +# +# Possible integers created using the digits of 1234 are: +# 1, 2, 3, 4, 12, 13, 14, 23, 24, 34, 123, 124, 134 and 234. +# +# There are 9 integers divisible by 2 such as: +# 2, 4, 12, 14, 24, 34, 124, 134 and 234. +# +# Example 2: +# +# Input: $m = 768, $n = 4 +# Output: 3 +# +# Possible integers created using the digits of 768 are: +# 7, 6, 8, 76, 78 and 68. +# +# There are 3 integers divisible by 4 such as: +# 8, 76 and 68. +# +# +# MY NOTES: Sounds pretty easy. However, there's one mistake: +# "You are only allowed to use (n-1) digits at the most" +# is flatly contradicted by the examples. I assume it meant +# "length(m)-1" which is what the examples show. +# +# So each digit can either be present or absent - it's another "subsets" +# task. One wrinkle: the length(m)-1 rule means that (all-present) is +# not a valid combination. Plus of course (all-absent) isn't either. +# +# Last time we did a "subsets" task was in Challenge 136 Task 2, +# Fibonacci Seqence. In that, I wrote: +# +# "How do we sum subsets of values? Two obvious ways: +# +# 1. recursive function, iterating over the values: each value is either in the +# subset or not, try both possibilities. +# 2. binary-counting method, iterate over every combination C from 1 .. +# 2**(number values)-1, then sum up only the elements where the corresponding +# bit in C is on. +# " +# +# That time, I wrote a (2) binary-counting method. So this time round, let's +# try a recursive function instead, just for variety. +# + +use strict; +use warnings; +use feature 'say'; +use Function::Parameters; +use Getopt::Long; +use Data::Dumper; + +my $debug = 0; + + +# +# my @result = recursivefind( $prefix, @l ); +# Given an array of letters @l and a prefix $prefix, find all +# subsets of @l (with $prefix prepended to it). +# eg if @l==(2,3), and $prefix="1", return ( 12,13 ) +# +fun recursivefind( $prefix, @l ) +{ + #say "debug: rf($prefix,".join(', ',@l).")" if $debug; + return ( $prefix ) if @l==0; + my $first = shift @l; + # $first is either present in the subset or not - + # so try both possibilities + my @result = recursivefind( $prefix, @l ); + push @result, recursivefind( $prefix.$first, @l ); + return @result; +} + + +# +# my @result = find_all_subsets( $m ); +# Given a string $m, find all non-empty shorter subsets of $m. +# eg if $m==123, return ( 12,13,23 ) +# +fun find_all_subsets( $m ) +{ + my @result = recursivefind( "", split( //, $m ) ); + shift @result; # remove empty subset + pop @result; # remove full subset ($m itself) + return @result; +} + + +die "Usage: like-numbers [-d|--debug] M N\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV==2; +my( $m, $n ) = @ARGV; + +die "like-numbers: M ($m) must be > 9\n" if $m<10; +die "like-numbers: N ($n) must be >= 2\n" if $n<2; + +my @result = sort { $a <=> $b } find_all_subsets( $m ); + +say "debug: subsets of $m are ", join(', ',@result) if $debug; +@result = grep { $_ % $n == 0 } @result; +say "debug: divisible by $n are ", join(', ',@result) if $debug; + +my $nr = @result; + +say "Input: m=$m, n=$n"; +say "Output: $nr"; |