diff options
| -rw-r--r-- | challenge-167/duncan-c-white/README | 92 | ||||
| -rw-r--r-- | challenge-167/duncan-c-white/perl/MakePrimes.pm | 90 | ||||
| -rwxr-xr-x | challenge-167/duncan-c-white/perl/ch-1.pl | 90 |
3 files changed, 214 insertions, 58 deletions
diff --git a/challenge-167/duncan-c-white/README b/challenge-167/duncan-c-white/README index c0f50441d9..e34765e0f0 100644 --- a/challenge-167/duncan-c-white/README +++ b/challenge-167/duncan-c-white/README @@ -1,75 +1,51 @@ -TASK 1: Hexadecimal Words +TASK 1: Circular Prime -As an old systems programmer, whenever I needed to come up with a 32-bit -number, I would reach for the tired old examples like 0xDeadBeef and -0xC0dedBad. I want more! +Write a script to find out first 10 circular primes having at least 3 +digits (base 10). -Write a program that will read from a dictionary and find 2- to 8-letter -words that can be "spelled" in hexadecimal, with the addition of the -following letter substitutions: +Please checkout https://en.wikipedia.org/wiki/Circular_prime for more information. - o -> 0 (e.g., 0xf00d = "food") - l -> 1 - i -> 1 - s -> 5 - t -> 7 +A circular prime is a prime number with the property that the number +generated at each intermediate step when cyclically permuting its (base +10) digits will also be prime. -You can use your own dictionary or you can simply open -../../../data/dictionary.txt (relative to your script's location in -our GitHub repository) to access the dictionary of common words from -Week #161. +Quote from the Wikipedia page: -Optional Extras (for an 0xAddedFee, of course!) +"For example, 1193 is a circular prime, since 1931, 9311 and 3119 all +are also prime.[3] A circular prime with at least two digits can only +consist of combinations of the digits 1, 3, 7 or 9, because having 0, 2, +4, 6 or 8 as the last digit makes the number divisible by 2, and having +0 or 5 as the last digit makes it divisible by 5" - Limit the number of "special" letter substitutions in any one result - to keep that result at least somewhat comprehensible. (0x51105010 - is an actual example from my sample solution you may wish to avoid!) +OUTPUT - Find phrases of words that total 8 characters in length (e.g., - 0xFee1Face), rather than just individual words. +113, 197, 199, 337, 1193, 3779, 11939, 19937, 193939, 199933 -MY NOTES: ok. Not a terribly fascinating task, forget the optional extras. -Should be simple enough. +MY NOTES: ok, sounds relatively easy. The wikipedia page clarifies it. +I'm reusing my old favourite MakePrimes.pm. -Task 2: K-Directory Diff +HOWEVER, my solution finds far more circular primes than the above output +shows. If 113 is a CP (and it is cos 131 and 311 are also prime), then SO +IS 131 AND SO IS 311, but the above list doesn't show it. Also, my solution +computes ALL CPs with exactly N digits, rather than the first 10 with N or +more digits. -Given a few (three or more) directories (non-recursively), display a -side-by-side difference of files that are missing from at least one of -the directories. Do not display files that exist in every directory. -Since the task is non-recursive, if you encounter a subdirectory, append -a /, but otherwise treat it the same as a regular file. +Task 2: Task 2: Gamma Function -Example - -Given the following directory structure: - -dir_a: -Arial.ttf Comic_Sans.ttf Georgia.ttf Helvetica.ttf Impact.otf Verdana.ttf Old_Fonts/ +Implement subroutine gamma() using the Lanczos approximation method. -dir_b: -Arial.ttf Comic_Sans.ttf Courier_New.ttf Helvetica.ttf Impact.otf Tahoma.ttf Verdana.ttf +Ryan Thompson wrote an interesting blog explaining the subject in +details. Highly recommended if you are looking for more information: +https://ry.ca/2022/05/lanczos-approximation -dir_c: -Arial.ttf Courier_New.ttf Helvetica.ttf Impact.otf Monaco.ttf Verdana.ttf - -The output should look similar to the following: - -dir_a | dir_b | dir_c --------------- | --------------- | --------------- -Comic_Sans.ttf | Comic_Sans.ttf | - | Courier_New.ttf | Courier_New.ttf -Georgia.ttf | | - | | Monaco.ttf -Old_Fonts/ | | - | Tahoma.ttf | +Example +print gamma(3); # 1.99 +print gamma(5); # 24 +print gamma(7); # 719.99 -MY NOTES: this is much more appealing to me; right up my street. Generally, -it seems pretty simple, build a "fileindirs" mapping from file -> a list of -which directories it's in, and form a set of all named files, then iterate -over the "all named files" set, skipping files present in all the dirs, -then iterating over all the dirs, using the fileindirs info to determine -which columns to leave blank. Need to auto-width each dir column, but that's -trivial to do. +MY NOTES: Hell no. Complex numbers, ridiculously complicated formula, +plus I've no idea what the Gamma function even is. This is far too +mathematical for me, so I've no interest in doing it. diff --git a/challenge-167/duncan-c-white/perl/MakePrimes.pm b/challenge-167/duncan-c-white/perl/MakePrimes.pm new file mode 100644 index 0000000000..e268fa06a3 --- /dev/null +++ b/challenge-167/duncan-c-white/perl/MakePrimes.pm @@ -0,0 +1,90 @@ +# +# mkprimes module (converted from mkprimes.c) +# + +use strict; +use warnings; +use Function::Parameters; + +my $debug = 0; +my @foundprimes; # remember all primes we've found.. + + +# +# my @primes = primes_upto( $n ); +# Find all primes up to N; return a list of all such primes +# (note that 1 is not usually considered a prime) +# +fun primes_upto( $n ) +{ + my @isprime; + + for( my $i=1; $i<=$n; $i++ ) + { + $isprime[$i] = 1; # initially + } + + # now sieve the non-primes out.. + my $upper = int(sqrt($n)); + printf( "debug: n=%d, upper=%d\n", $n, $upper ) if $debug; + for( my $i=2; $i<=$upper; $i++ ) + { + if( $isprime[$i] ) + { + #printf( "debug: crossing out multiples of %d\n", $i ); + for( my $j=$i*$i; $j<=$n; $j+=$i ) + { + $isprime[$j] = 0; + } + } + } + + # after sieving, extract the primes + my @primes = grep { $isprime[$_] } 2..$n; + + # remember them + @foundprimes = @primes; + + return @primes; +} + + +# +# my @moreprimes = more_primes( $n, $m ); +# Need more primes! Have @foundprimes up to $n, but need +# to sieve primes from $n+1..$m, so re-sieve, return +# a list of all new primes (in the range $n+1..$m) that we find. +# +fun more_primes( $n, $m ) +{ + my %isprime; + + print "finding more primes from ", $n+1, "..$m\n"; + + for( my $i=$n+1; $i<=$m; $i++ ) + { + $isprime{$i} = 1; # pre-sieving + } + + # now sieve the non-primes out.. + foreach my $prime (@foundprimes) + { + # find first multiple of $prime > $n + my $mult = $prime * (int($n/$prime)+1); + + #print "debug: xo multiples of $prime from $mult to $m\n"; + + for( my $j=$mult; $j<=$m; $j+=$prime ) + { + delete $isprime{$j}; + } + } + + # after sieving, extract the primes + my @primes = grep { $isprime{$_} } $n+1..$m; + push @foundprimes, @primes; + return @primes; +} + + +1; diff --git a/challenge-167/duncan-c-white/perl/ch-1.pl b/challenge-167/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..c9301da291 --- /dev/null +++ b/challenge-167/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,90 @@ +#!/usr/bin/perl +# +# TASK 1: Circular Prime +# +# Write a script to find out first 10 circular primes having at least 3 +# digits (base 10). +# +# Please checkout https://en.wikipedia.org/wiki/Circular_prime for more information. +# +# A circular prime is a prime number with the property that the number +# generated at each intermediate step when cyclically permuting its (base +# 10) digits will also be prime. +# +# Quote from the Wikipedia page: +# +# "For example, 1193 is a circular prime, since 1931, 9311 and 3119 all +# are also prime.[3] A circular prime with at least two digits can only +# consist of combinations of the digits 1, 3, 7 or 9, because having 0, 2, +# 4, 6 or 8 as the last digit makes the number divisible by 2, and having +# 0 or 5 as the last digit makes it divisible by 5" +# +# OUTPUT +# +# 113, 197, 199, 337, 1193, 3779, 11939, 19937, 193939, 199933 +# +# MY NOTES: ok, sounds relatively easy. The wikipedia page clarifies it. +# I'm reusing my old favourite MakePrimes.pm. +# +# HOWEVER, my solution finds far more circular primes than the above output +# shows. If 113 is a CP (and it is cos 131 and 311 are also prime), then SO +# IS 131 AND SO IS 311, but the above list doesn't show either. Also, my +# solution computes ALL CPs with exactly N digits (on the assumption that +# there are probably 10 or more), rather than only the first 10 with N or +# more digits. +# +# btw, for checking primeness I use +# perl -I. -MMakePrimes -E 'say join(",",primes_upto(999))' +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +#use Data::Dumper; + +use lib qw(.); +use MakePrimes; + +my $debug=0; +die "Usage: circular-prime [--debug] [NDIGITS default 3]\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV<2; +my $ndigits = shift // 3; + +my %isprime; + + +# +# my $iscp = iscircularprime($prime); +# Check whether prime $prime is a circular prime, using %isprime. +# Return 1 iff it is a circular prime, 0 otherwise. +# +sub iscircularprime ($) +{ + my( $prime ) = @_; + my $len = length($prime); + print "debug: iscp: checking whether $prime is a cp\n" if $debug; + foreach my $i (1..$len-1) + { + $prime =~ /^(.)(.+)$/; + my( $firstdigit, $rest ) = ( $1, $2 ); + $prime = $2.$1; + print "debug: rotate circular gives $prime\n" if $debug; + return 0 unless $isprime{$prime}; + } + return 1; +} + + +my $limit = 10**$ndigits-1; +print "getting primes up to $limit\n" if $debug; +my @primes = primes_upto( $limit ); +%isprime = map { $_ => 1 } @primes; + +# discard primes not ndigits long, or containing 0,2,4,5, or 8 +@primes = grep { length($_) == $ndigits && $_ !~ /[024568]/ } @primes; + +# discard non-circular primes +@primes = grep { iscircularprime($_) } @primes; + +say join(', ', @primes); |