diff options
18 files changed, 1635 insertions, 0 deletions
diff --git a/challenge-168/roger-bell-west/javascript/ch-1.js b/challenge-168/roger-bell-west/javascript/ch-1.js new file mode 100755 index 0000000000..d3fc9016b2 --- /dev/null +++ b/challenge-168/roger-bell-west/javascript/ch-1.js @@ -0,0 +1,81 @@ +#! /usr/bin/node +function deepEqual(a,b) +{ + if( (typeof a == 'object' && a != null) && + (typeof b == 'object' && b != null) ) + { + var count = [0,0] + for( var key in a) count[0]++ + for( var key in b) count[1]++ + if( count[0]-count[1] != 0) {return false} + for( var key in a) + { + if(!(key in b) || !deepEqual(a[key],b[key])) {return false} + } + for( var key in b) + { + if(!(key in a) || !deepEqual(b[key],a[key])) {return false} + } + return true + } + else + { + return a === b + } +} + +function isprime(candidate) { + if (candidate<2) { + return false + } else if (candidate==2) { + return true + } else if (candidate==3) { + return true + } else if (candidate % 2 == 0) { + return false + } else if (candidate % 3 == 0) { + return false + } + let anchor=0 + let limit=Math.floor(Math.sqrt(candidate)) + while (1) { + anchor+=6 + for (let t = anchor-1; t <= anchor+1; t += 2) { + if (t > limit) { + return true + } + if (candidate % t == 0) { + return false + } + } + } +} + +function perrinprime(n) { + let out = new Set; + let seq = [3, 0, 2]; + while (true) { + let nv = seq[0] + seq[1]; + seq.shift(); + seq.push(nv); + if (isprime(nv)) { + out.add(nv); + if (out.size >= n) { + break; + } + } + } + let o = []; + for (let p of out) { + o.push(p); + } + o.sort((a,b) => a-b); + return o; +} + +if (deepEqual(perrinprime(13),[2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977])) { + process.stdout.write("Pass"); +} else { + process.stdout.write("FAIL"); +} +process.stdout.write("\n"); diff --git a/challenge-168/roger-bell-west/javascript/ch-2.js b/challenge-168/roger-bell-west/javascript/ch-2.js new file mode 100755 index 0000000000..99486914e4 --- /dev/null +++ b/challenge-168/roger-bell-west/javascript/ch-2.js @@ -0,0 +1,93 @@ +#! /usr/bin/node + +function genprimes(mx) { + let primesh=new Set([2,3]) + for (let i = 6; i <= mx; i += 6) { + for (let j = i-1; j <= i+1; j += 2) { + if (j <= mx) { + primesh.add(j); + } + } + } + let q=[2,3,5,7]; + let p=q.shift(); + let mr=Math.floor(Math.sqrt(mx)); + while (p <= mr) { + if (primesh.has(p)) { + let i=p*p + for (let i=p*p; i <= mx; i += p) { + primesh.delete(i); + } + } + if (q.length < 2) { + q.push(q[q.length-1]+4); + q.push(q[q.length-1]+2); + } + p=q.shift(); + } + let primes=[...primesh]; + primes.sort(function(a,b) { + return a-b; + }); + return primes; +} + +function primefactor (n) { + let f=new Map() + let m=n + for (let p of genprimes(1+Math.floor(Math.sqrt(n)))) { + while (m % p == 0) { + m=Math.floor(m/p) + if (f.has(p)) { + f.set(p,f.get(p)+1) + } else { + f.set(p,1) + } + if (m == 1) { + break + } + } + } + if (m > 1) { + if (f.has(m)) { + f.set(m,f.get(m)+1) + } else { + f.set(m,1) + } + } + return f +} + +function homeprime (n0) { + let n = n0; + while (true) { + let t = primefactor(n); + if (t.size == 1 && [...t.values()][0] == 1) { + break; + } + let ns = ""; + let tk = [...t.keys()]; + tk.sort((a,b) => a-b); + for (let d of tk) { + for (let i=0; i<t.get(d); i++) { + ns = ns.concat(d); + } + } + n = parseInt(ns); + } + return n; +} + +if (homeprime(10) == 773) { + process.stdout.write("Pass"); +} else { + process.stdout.write("FAIL"); +} +process.stdout.write(" "); + +if (homeprime(16) == 31636373) { + process.stdout.write("Pass"); +} else { + process.stdout.write("FAIL"); +} +process.stdout.write("\n"); diff --git a/challenge-168/roger-bell-west/kotlin/ch-1.kt b/challenge-168/roger-bell-west/kotlin/ch-1.kt new file mode 100644 index 0000000000..a8628b4c2d --- /dev/null +++ b/challenge-168/roger-bell-west/kotlin/ch-1.kt @@ -0,0 +1,58 @@ +import kotlin.math.* + +fun isprime(candidate: Long): Boolean { + if (candidate < 2L) { + return false + } else if (candidate==2L) { + return true + } else if (candidate==3L) { + return true + } else if (candidate % 2L == 0L) { + return false + } else if (candidate % 3L == 0L) { + return false + } + var anchor=0L + val limit = Math.sqrt(candidate.toDouble()).toLong() + while (true) { + anchor += 6L + for (t in anchor-1L..anchor+1L step 2L) { + if (t > limit) { + return true + } + if (candidate % t == 0L) { + return false + } + } + } +} + +fun perrinprime(n: Long): ArrayList<Long> { + var ot = mutableSetOf<Long>() + var seq = mutableListOf(3L, 0L, 2L) + while (true) { + val nv = seq[0] + seq[1] + seq.removeAt(0) + seq.add(nv) + if (isprime(nv)) { + ot.add(nv) + if (ot.size >= n) { + break; + } + } + } + var o = ArrayList(ot) + o.sort() + return o +} + +fun main() { + if (perrinprime(13) == listOf(2, 3, 5, 7, 17, 29, 277, 367, 853, + 14197, 43721, 1442968193, + 792606555396977)) { + print("Pass") + } else { + print("FAIL") + } + println("") +} diff --git a/challenge-168/roger-bell-west/kotlin/ch-2.kt b/challenge-168/roger-bell-west/kotlin/ch-2.kt new file mode 100644 index 0000000000..7083d8f76f --- /dev/null +++ b/challenge-168/roger-bell-west/kotlin/ch-2.kt @@ -0,0 +1,94 @@ +import kotlin.math.* + +fun genprimes(mx: Int): ArrayList<Int> { + var primesh=mutableSetOf<Int>() + for (i in 2..3) { + primesh.add(i) + } + for (i in 6..mx+1 step 6) { + for (j in i-1..i+1 step 2) { + if (j <= mx) { + primesh.add(j) + } + } + } + var q=ArrayDeque(listOf(2,3,5,7)) + var p=q.removeFirst() + val mr=sqrt(mx.toDouble()).toInt() + while (p <= mr) { + if (primesh.contains(p)) { + for (i in p*p..mx step p) { + primesh.remove(i) + } + } + if (q.size < 2) { + q.add(q.last()+4) + q.add(q.last()+2) + } + p=q.removeFirst() + } + var primes=ArrayList(primesh.distinct()) + primes.sort() + return primes +} + +fun primefactor(n: Int): Map<Int,Int> { + var f=mutableMapOf<Int,Int>() + var m=n + for (p in genprimes(sqrt(m.toDouble()).toInt())) { + while (m % p == 0) { + m /= p + if (f.containsKey(p)) { + f[p] = f[p]!!+1 + } else { + f[p]=1 + } + } + if (m == 1) { + break + } + } + if (m > 1) { + if (f.containsKey(m)) { + f[m] = f[m]!!+1 + } else { + f[m]=1 + } + } + return f +} + +fun homeprime(n0: Int): Int { + var n = n0 + while (true) { + val t = primefactor(n) + val tk = t.keys.sorted() + if (t.size == 1 && t[tk[0]] == 1) { + break + } + var ns = "" + for (d in tk) { + val ds = d.toString() + for (i in 1..t[d]!!) { + ns += ds + } + } + n = ns.toInt() + } + return n +} + +fun main() { + if (homeprime(10) == 773) { + print("Pass") + } else { + print("FAIL") + } + print(" ") + if (homeprime(16) == 31636373) { + print("Pass") + } else { + print("FAIL") + } + println("") +} diff --git a/challenge-168/roger-bell-west/lua/ch-1.lua b/challenge-168/roger-bell-west/lua/ch-1.lua new file mode 100755 index 0000000000..2b0f43b734 --- /dev/null +++ b/challenge-168/roger-bell-west/lua/ch-1.lua @@ -0,0 +1,102 @@ +#! /usr/bin/lua + +-- by Michael Anderson at +-- https://stackoverflow.com/questions/8722620/comparing-two-index-tables-by-index-value-in-lua +function recursive_compare(t1,t2) + -- Use usual comparison first. + if t1==t2 then return true end + -- We only support non-default behavior for tables + if (type(t1)~="table") then return false end + -- They better have the same metatables + local mt1 = getmetatable(t1) + local mt2 = getmetatable(t2) + if( not recursive_compare(mt1,mt2) ) then return false end + + -- Check each key-value pair + -- We have to do this both ways in case we miss some. + -- TODO: Could probably be smarter and not check those we've + -- already checked though! + for k1,v1 in pairs(t1) do + local v2 = t2[k1] + if( not recursive_compare(v1,v2) ) then return false end + end + for k2,v2 in pairs(t2) do + local v1 = t1[k2] + if( not recursive_compare(v1,v2) ) then return false end + end + + return true +end + +function isprime(candidate) + if candidate<2 then + return false + elseif candidate==2 then + return true + elseif candidate==3 then + return true + elseif candidate % 2 == 0 then + return false + elseif candidate % 3 == 0 then + return false + end + local anchor=0 + local limit=math.floor(math.sqrt(candidate)) + while true do + anchor = anchor + 6 + for t = anchor-1,anchor+1,2 do + if t > limit then + return true + end + if candidate % t == 0 then + return false + end + end + end +end + +function hammingweight(x0) + local x = x0 + local count = 0 + while x > 0 do + x = x & (x-1) + count = count + 1 + end + return count +end + +function perrinprime(n) + local out={} + local ol = 0 + local seq = {3, 0, 2} + while true do + local nv = seq[1] + seq[2] + seq[1] = seq[2] + seq[2] = seq[3] + seq[3] = nv + if isprime(nv) then + if out[nv] == nil then + ol = ol + 1 + end + out[nv] = true + if ol >= n then + break + end + end + end + local o = {} + for k,v in pairs(out) do + table.insert(o,k) + end + table.sort(o) + return o +end + +if recursive_compare(perrinprime(13), {2, 3, 5, 7, 17, 29, 277, 367, + 853, 14197, 43721, 1442968193, + 792606555396977}) then + io.write("Pass") +else + io.write("FAIL") +end +print("") diff --git a/challenge-168/roger-bell-west/lua/ch-2.lua b/challenge-168/roger-bell-west/lua/ch-2.lua new file mode 100755 index 0000000000..978f8ed462 --- /dev/null +++ b/challenge-168/roger-bell-west/lua/ch-2.lua @@ -0,0 +1,101 @@ +#! /usr/bin/lua + +function genprimes(mx) + local primesh = {} + for i = 2, 3 do + primesh[i] = true + end + for i = 6, mx, 6 do + for j = i-1, i+1, 2 do + if j <= mx then + primesh[j]=true + end + end + end + local q={2,3,5,7} + local p=table.remove(q,1) + local mr=math.floor(math.sqrt(mx)) + while p <= mr do + if primesh[p] ~= nil then + for i = p*p,mx,p do + primesh[i] = nil + end + end + if #q < 2 then + table.insert(q,q[#q]+4) + table.insert(q,q[#q]+2) + end + p=table.remove(q,1) + end + local primes = {} + for k,v in pairs(primesh) do + table.insert(primes,k) + end + table.sort(primes) + return primes +end + +function primefactor(n) + local f={} + local m=n + for k,p in pairs(genprimes(1+math.floor(math.sqrt(m)))) do + while m % p == 0 do + m=math.floor(m/p) + if f[p] == nil then + f[p]=1 + else + f[p] = f[p] + 1 + end + if m==1 then + break + end + end + end + if m>1 then + if f[m] == nil then + f[m]=1 + else + f[m] = f[m] + 1 + end + end + return f +end + +function homeprime(n0) + local n = n0 + while true do + local pfc = 0 + local ns = "" + local t = primefactor(n) + local kl = {} + for k,v in pairs(t) do + pfc = pfc + v + table.insert(kl,k) + end + table.sort(kl) + if pfc == 1 then + break + end + for k,v in pairs(kl) do + for i = 1,t[v] do + ns = ns .. v + end + end + n = 0 + ns + end + return n +end + +if homeprime(10) == 773 then + io.write("Pass") +else + io.write("FAIL") +end +io.write(" ") + +if homeprime(16) == 31636373 then + io.write("Pass") +else + io.write("FAIL") +end +print("") diff --git a/challenge-168/roger-bell-west/perl/ch-1.pl b/challenge-168/roger-bell-west/perl/ch-1.pl new file mode 100755 index 0000000000..3d2d398a9d --- /dev/null +++ b/challenge-168/roger-bell-west/perl/ch-1.pl @@ -0,0 +1,56 @@ +#! /usr/bin/perl + +use strict; +use warnings; +use experimental 'signatures'; + +use Test::More tests => 1; + +is_deeply(perrinprime(13), + [2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, + 1442968193, 792606555396977], + 'example 1'); + +sub isprime { + my $candidate=shift; + if ($candidate<2) { + return 0; + } elsif ($candidate==2) { + return 1; + } elsif ($candidate==3) { + return 1; + } elsif ($candidate % 2 == 0) { + return 0; + } elsif ($candidate % 3 == 0) { + return 0; + } + my $anchor=0; + my $limit=int(sqrt($candidate)); + while (1) { + $anchor+=6; + foreach my $t ($anchor-1,$anchor+1) { + if ($t > $limit) { + return 1; + } + if ($candidate % $t == 0) { + return 0; + } + } + } +} + +sub perrinprime($n) { + my %out; + my @seq = (3, 0, 2); + while (1) { + push @seq,$seq[0]+$seq[1]; + shift @seq; + if (isprime($seq[-1])) { + $out{$seq[-1]} = 1; + if (scalar keys %out >= $n) { + last; + } + } + } + return [sort {$a <=> $b} keys %out]; +} diff --git a/challenge-168/roger-bell-west/perl/ch-2.pl b/challenge-168/roger-bell-west/perl/ch-2.pl new file mode 100755 index 0000000000..0191fac52f --- /dev/null +++ b/challenge-168/roger-bell-west/perl/ch-2.pl @@ -0,0 +1,80 @@ +#! /usr/bin/perl + +use strict; +use warnings; +use experimental 'signatures'; + +use Test::More tests => 2; + +is(homeprime(10),773,'example 1'); +is(homeprime(16),31636373,'example 2'); + +sub genprimes($mx) { + my @primes; + { + my %primesh=map {$_ => 1} (2,3); + for (my $i=6;$i <= $mx+1; $i += 6) { + foreach my $j ($i-1,$i+1) { + if ($j <= $mx) { + $primesh{$j}=1; + } + } + } + my @q=(2,3,5,7); + my $p=shift @q; + my $mr=int(sqrt($mx)); + while ($p <= $mr) { + if ($primesh{$p}) { + my $i=$p*$p; + while ($i <= $mx) { + delete $primesh{$i}; + $i += $p; + } + } + if (scalar @q < 2) { + push @q,$q[-1]+4; + push @q,$q[-1]+2; + } + $p=shift @q; + } + @primes=sort {$a <=> $b} keys %primesh; + } + return \@primes; +} + +sub primefactor($n) { + my %f; + my $m=$n; + foreach my $p (@{genprimes(int(sqrt($n)))}) { + while ($m % $p == 0) { + $f{$p}++; + $m=int($m/$p); + if ($m == 1) { + last; + } + } + } + if ($m > 1) { + $f{$m}++; + } + return \%f; +} + +sub homeprime($n0) { + my $n=$n0; + while (1) { + my $t = primefactor($n); + my @tk = sort {$a <=> $b} keys %{$t}; + if (scalar @tk == 1 && $t->{$tk[0]} == 1) { + last; + } + my $ns = ''; + foreach my $d (@tk) { + foreach (1..$t->{$d}) { + $ns .= $d; + } + } + $n = 0 + $ns; + } + return $n; +} diff --git a/challenge-168/roger-bell-west/postscript/ch-1.ps b/challenge-168/roger-bell-west/postscript/ch-1.ps new file mode 100644 index 0000000000..a568fb7425 --- /dev/null +++ b/challenge-168/roger-bell-west/postscript/ch-1.ps @@ -0,0 +1,244 @@ +%!PS + +% begin included library code + +/test.end { + ( ) print + test.count 0 gt { + (Passed ) print + test.pass (...) cvs print + (/) print + test.count (...) cvs print + ( \() print + test.pass 100 mul test.count idiv (...) cvs print + (%\)) print + (\r\n) print + } if +} bind def + +/quicksort.swap { + 2 dict begin + /bi exch def + /ai exch def + arr ai get + arr bi get + arr exch ai exch put + arr exch bi exch put + end +} bind def + +/test { + /test.count test.count 1 add def + { + /test.pass test.pass 1 add def + } { + ( ) print + test.count (....) cvs print + (-fail) print + } ifelse +} bind def + +/quicksort.main { % lo hi -> (null) + 3 dict begin + /hi exch def + /lo exch def + /xit false def + lo 0 lt { + /xit true def + } if + hi 0 lt { + /xit true def + } if + lo hi ge { + /xit true def + } if + xit not { + /p quicksort.partition def + lo p quicksort.main + p 1 add hi quicksort.main + } if + end +} bind def + +/keys { % dict -> array of dict keys + [ exch + { + pop + } forall + ] +} bind def + +/quicksort { % [ a c b ] -> [ a b c ] + 1 dict begin + /arr exch def + 0 arr length 1 sub quicksort.main + arr + end +} bind def + +/deepeq { + 2 dict begin + /a exch def + /b exch def + a type b type eq { + a type /dicttype eq { + a length b length eq { + << + a { + pop + true + } forall + b { + pop + true + } forall + >> + true exch + { + pop + dup a exch known { + dup b exch known { + dup a exch get exch b exch get deepeq not { + pop false + } if + } { + false + } ifelse + } { + false + } ifelse + } forall + } { + false + } ifelse + } { + a type dup /arraytype eq exch /stringtype eq or { + a length b length eq { + true + 0 1 a length 1 sub { + dup a exch get exch b exch get deepeq not { + pop false + exit + } if + } for + } { + false + } ifelse + } { + a b eq + } ifelse + } ifelse + } { + false + } ifelse + end +} bind def + +/isprime { + 4 dict begin + /candidate exch def + 1 { + candidate 2 lt { + false + exit + } if + candidate 2 eq { + true + exit + } if + candidate 2 mod 0 eq { + false + exit + } if + candidate 3 eq { + true + exit + } if + candidate 3 mod 0 eq { + false + exit + } if + /prime true def + /limit candidate sqrt cvi 1 add def + /anchor 0 def + { + /anchor anchor 6 add def + anchor limit gt { + exit + } if + [ -1 1 ] { + anchor add candidate exch mod 0 eq { + /prime false def + exit + } if + } forall + prime false eq { + exit + } if + } loop + prime + } repeat + end +} bind def + +/quicksort.partition { + 3 dict begin + /pivot arr hi lo add 2 idiv get def + /i lo 1 sub def + /j hi 1 add def + { + { + /i i 1 add def + arr i get pivot ge { + exit + } if + } loop + { + /j j 1 sub def + arr j get pivot le { + exit + } if + } loop + i j ge { + j + exit + } if + i j quicksort.swap + } loop + end +} bind def + +/test.start { + print (:) print + /test.pass 0 def + /test.count 0 def +} bind def + +% end included library code + +/perrinprime { + 4 dict begin + /n exch def + /out n dict def + /seq [ 3 0 2 ] def + { + /nv seq 0 get seq 1 get add def + seq 0 seq 1 get put + seq 1 seq 2 get put + seq 2 nv put + nv isprime { + out nv true put + out length n ge { + exit + } if + } if + } loop + out keys quicksort + end +} bind def + +(perrinprime) test.start +13 perrinprime +[ 2 3 5 7 17 29 277 367 853 14197 43721 1442968193 792606555396977 ] +deepeq test +test.end diff --git a/challenge-168/roger-bell-west/postscript/ch-2.ps b/challenge-168/roger-bell-west/postscript/ch-2.ps new file mode 100644 index 0000000000..138a084180 --- /dev/null +++ b/challenge-168/roger-bell-west/postscript/ch-2.ps @@ -0,0 +1,237 @@ +%!PS + +% begin included library code + +/quicksort.main { % lo hi -> (null) + 3 dict begin + /hi exch def + /lo exch def + /xit false def + lo 0 lt { + /xit true def + } if + hi 0 lt { + /xit true def + } if + lo hi ge { + /xit true def + } if + xit not { + /p quicksort.partition def + lo p quicksort.main + p 1 add hi quicksort.main + } if + end +} bind def + + +/test.start { + print (:) print + /test.pass 0 def + /test.count 0 def +} bind def + +/quicksort { % [ a c b ] -> [ a b c ] + 1 dict begin + /arr exch def + 0 arr length 1 sub quicksort.main + arr + end +} bind def + + +/values { % dict -> array of dict values + [ exch + { + exch pop + } forall + ] +} bind def + +/primefactor { + 4 dict begin + /n exch def + /f 1 dict def + /m n def + n sqrt cvi genprimes quicksort { + /p exch def + { + m p mod 0 eq { + f p known { + f p f p get 1 add put + } { + f p 1 put + } ifelse + /m m p idiv def + } { + exit + } ifelse + } loop + m 1 eq { + exit + } if + } forall + m 1 gt { + f m known { + f m f m get 1 add put + } { + f m 1 put + } ifelse + } if + f + end +} bind def + +/test { + /test.count test.count 1 add def + { + /test.pass test.pass 1 add def + } { + ( ) print + test.count (....) cvs print + (-fail) print + } ifelse +} bind def + +/strconcat % (a) (b) -> (ab) +{ exch dup length + 2 index length add string + dup dup 4 2 roll copy length + 4 -1 roll putinterval +} bind def + +/quicksort.swap { + 2 dict begin + /bi exch def + /ai exch def + arr ai get + arr bi get + arr exch ai exch put + arr exch bi exch put + end +} bind def + +/keys { % dict -> array of dict keys + [ exch + { + pop + } forall + ] +} bind def + + +/apush { apush.right } bind def + +/apush.right { % [a b] c -> [a b c] + exch + [ exch aload length 2 add -1 roll ] +} bind def + +/genprimes { + /mx exch def + /primesh mx dict def + 2 1 3 { + primesh exch true put + } for + 6 6 mx 1 add { + dup 1 sub exch 1 add 2 exch { + dup mx le { + primesh exch true put + } { + pop + } ifelse + } for + } for + /q [ 3 5 7 ] def + /qi 0 def + /p 2 def + /mr mx sqrt cvi def + { + p mr le not { + exit + } if + primesh p known { + p dup mul p mx { + primesh exch undef + } for + } if + q length qi sub 2 le { + /q q q q length 1 sub get 4 add apush def + /q q q q length 1 sub get 2 add apush def + } if + /p q qi get def + /qi qi 1 add def + } loop + primesh keys +} bind def + +/quicksort.partition { + 3 dict begin + /pivot arr hi lo add 2 idiv get def + /i lo 1 sub def + /j hi 1 add def + { + { + /i i 1 add def + arr i get pivot ge { + exit + } if + } loop + { + /j j 1 sub def + arr j get pivot le { + exit + } if + } loop + i j ge { + j + exit + } if + i j quicksort.swap + } loop + end +} bind def + +/test.end { + ( ) print + test.count 0 gt { + (Passed ) print + test.pass (...) cv |