Euler Solution 51
From ProgSoc Wiki
Contents |
Solutions for Problem 51
Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.
Caml by SanguineV
Runtime: 374ms
(* The sieve of Eratosthenes, takes an array and sets all non-prime positions to "false" *)
let setprimes arr =
let lim = (Array.length arr) - 1 in
let rec sieve = function
| c when c >= lim -> ()
| c -> (for i = 2 to (lim / c) do Array.set arr (c * i) false done; sieve (c + 2))
in
for i = 2 to (lim /2) do Array.set arr (i * 2) false done;
sieve 3
;;
(* Converts an integer into a list of it's digits (reverse order) *)
let rec todigs = function
| n when n < 10 -> [n]
| n -> n mod 10 :: todigs (n / 10)
;;
(* Counts how many instances of "i" in a list *)
let rec count i = function
| x::xs when i == x -> count i xs + 1
| _::xs -> count i xs
| [] -> 0
;;
(* Given an integer, it is a candidate for this problem if it has the same
* digit three times. Return the digit if there is one, and 10 otherwise. *)
let candidate n =
let rec inner = function
| x::xs when count x xs == 2 -> x
| _::xs when List.length xs == 2 -> 10
| _::xs -> inner xs
| [] -> 10
in
inner (todigs n)
;;
(* Replace the "i" digits with "j"s in the integer "n" *)
let repl i j n =
let rec inner pow = function
| 0 -> 0
| n when n mod 10 == i -> inner (pow * 10) (n / 10) + (pow * j)
| n -> inner (pow * 10) (n / 10) + (pow * (n mod 10))
in
inner 1 n
;;
(* Given a number "n" and a digit "i" to work on, build a list of numbers
* that are "n" with "i" replaced by "j" for some "j" up to 9. *)
let rec build n i = function
| 9 -> [repl i 9 n]
| j -> repl i j n :: (build n i (j + 1))
;;
(* Given an array that determines primes and a staring position, find the
* first prime to have 8 variations by replacing one digit. *)
let findprimebase ps st =
let rec inner i =
if Array.get ps i
then (let ci = candidate i in
if ci < 3 && List.fold_left (fun x y -> x + (if Array.get ps y then 1 else 0)) 1 (build i ci (ci + 1)) == 8
then i
else inner (i + 2))
else inner (i + 2)
in
inner st
;;
(* Create an array initialised to "true", set non-primes to false, then start at
* 100001 and look for the prime base. *)
let primes = Array.create 1000000 true;;
setprimes primes;;
print_int (findprimebase primes 100001);;
I am surprised it is much faster then python as there is nothing in this code that really takes advantage of functional programming, so a C implementation should be faster still. I guess the algorithm is the win here.
Python by Althalus
Runtime: 110.4 seconds
from primeFunctions import genPrimes
from time import time
import re
from array import array
from copy import copy
start = time()
primes = genPrimes(1000000) # A seive implementation written a while back for use with Euler problems
primes = [array('c',str(x)) for x in primes if x > 99999]
for i in range(0,3):
for j in range (i+1,4):
for k in range(i+1,5):
candidates = []
for l in [str(l) for l in range(0,10)]:
candidates += [x for x in primes if x[i] == l and x[j] == l and x[k] == l]
if len(candidates) > 6:
#At this point, we have a pool of candidates for the current i and j.
for c in candidates:
c2 =copy(c)
c2[i] = '.'
c2[j] = '.'
c2[k] = '.'
p = re.compile(c2.tostring())
#print c,c2, sum([1 for x in map(p.match,candidates) if x != None])
if sum([1 for x in map(p.match,candidates) if x != None]) == 8:
print c
print time()-start
exit()
Ruby by tomchristmas
A tale of epic proportions!
Runtimes on niflheim:
Version 1: From now until Hell freezes over (estimate)
Version 2: 8 hours, 55 minutes, 12.420 seconds
Version 3: Coming soon
Once upon a time, there was a sprightly young programmer named Tom. Tom loved nothing more than to write computer programs; morning, noon and night. He would forgo meals, sleep, social outings, even offers of intimate congress if they ever arose, just to tackle problems of a particularly difficult nature.
One day, Tom came across such a problem, although due perhaps to his considerable naivete, did not realise at the time just how difficult it would be. There it was; a seemingly simple problem involving prime numbers and combinations. Why no-one in his programming club had solved it yet, or at least published their solution, was quite a mystery to him. Nevertheless, he decided to give it a go, seeing as he had nothing better to do, apart from studying for a couple exams. "No worries, " he said. "I'll have this problem solved in a jiffy!"
Tom began in earnest, writing code to generate primes on the fly, and even gleaning an algorithm from a book (Oliver, pp. 76, 98-102) in the programming club room to generate combinations, shaking his head over the book's copious use of one-indexed arrays in its example algorithms throughout. "It should be using zero-indexed arrays, as used by real programmers such as myself," thought Tom. Sometime later, after a whole lot of debugging and cans of cola, Tom came up with the following code:
def next_prime(p)
primeFound = false
q = p
while not primeFound
isDiv = false
q += 1
2.upto(q/2){|d| isDiv = ((q % d == 0) || (isDiv == true)) ? true : false }
primeFound = true if not isDiv
end
q
end
def enumerate(a, n, r)
b1 = 0
b2 = 0
tmp = 0
lastBit = a[n - 1]
change = n
change -= 1 while (a[change - 1] == lastBit)
rightHash = (lastBit == 0) ? n : change
nextStar = change
nextStar -= 1 while (nextStar != 0 && a[nextStar - 1] != 1)
if (r - (n - rightHash)) % 2 == 0
b1 = change
b2 = ((change + 1 + lastBit) < n ) ? (change + 1 + lastBit) : n
else
if nextStar == 1
b1 = 1
b2 = rightHash
else
b1 = nextStar - 1
b2 = (a[b1 - 1] == 0) ? change + lastBit : rightHash
end
end
tmp = a[b1 - 1]
a[b1 - 1] = a[b2 - 1]
a[b2 - 1] = tmp
a
end
def comb(n, r)
c = 1.0
0.upto(r - 1){|x| c = c * ((n - x) / (r - x).to_f)}
c.to_i
end
def combs(n, r)
c = []
s = []
0.upto(r-1){|x| s << 1}
r.upto(n-1){|x| s << 0}
1.upto(comb(n,r)){|x|
tmp = ""
0.upto(n - 1){|y|
if s[y] == 1
tmp << "*"
else
tmp << "#"
end
}
c << tmp
s = enumerate(s, n, r)
}
c
end
def prime_patterns(p)
patterns = []
(p.length - 1).downto(1){|r|
combs(p.length, r).each{|c|
pp = p.dup
0.upto(p.length - 1){|x| pp[x] = c[x] if (c[x].chr == "*")}
patterns << pp
}
}
patterns
end
prime = 7
prime_family = []
while prime_family.length != 8
prime_family = []
prime = next_prime(prime)
prime_patterns(prime.to_s).each{|pp|
if prime_family.length != 8
prime_family = []
1.upto(9){|d|
ppp = pp.dup
ppp.gsub!("*", d.to_s)
prime_family << ppp if (ppp.to_i == next_prime(ppp.to_i - 1))
}
end
puts prime_family.join(",")
}
end
puts "\n Smallest prime and its family: #{prime_family.join(",")}"
Tom was mighty pleased with what he wrote. He took a deep breath and commenced execution of his masterpiece. The terminal screen began to fill with prime numbers in neat little rows, rapidly at first but then slowing down considerably. Tom waited. And waited. And waited some more. Then Tom came to the realisation that maybe - just maybe - his program might be taking longer than it should be to come up with an answer. Nevertheless, he left it to run. "It would be good to give the computer a bit of a prolonged stress test, anyhow," he thought.
Four days later, Tom returned to his computer and, much to his dismay, found that his program was still running, having yet to come up with the set of eight primes he was searching for! He terminated the running program, and reflected on what he had done wrong. "OK, so maybe generating the primes every single time using the division method isn't such a good idea," thought Tom. "Perhaps I should take the Sieve of Eratosthenes approach to the problem. Sure it'll eat up more memory, but at least it'll come up with a solution within a reasonable time frame, I hope. Besides, it's not as if I'm programming on a Commodore VIC-20 with its paltry 5K RAM. Memory's cheap and plentiful these days." So, with that in mind, Tom made a few changes to his program and came up with:
# Executed using: time ( ruby euler51-2.rb 1>&2 ) 2> 51out.txt &
def sieve(c)
a = []
b = Array.new(c)
b[0] = "*"
d = 2
while d < c
(c / d).times{|x| b[((x + 1) * d) + (d - 1)] = "*"}
d += 1
end
d = 2
while d < c
a << d if b[d - 1] == nil
d += 1
end
a
end
def enumerate(a, n, r)
b1 = 0
b2 = 0
tmp = 0
lastBit = a[n - 1]
change = n
change -= 1 while (a[change - 1] == lastBit)
rightHash = (lastBit == 0) ? n : change
nextStar = change
nextStar -= 1 while (nextStar != 0 && a[nextStar - 1] != 1)
if (r - (n - rightHash)) % 2 == 0
b1 = change
b2 = ((change + 1 + lastBit) < n ) ? (change + 1 + lastBit) : n
else
if nextStar == 1
b1 = 1
b2 = rightHash
else
b1 = nextStar - 1
b2 = (a[b1 - 1] == 0) ? change + lastBit : rightHash
end
end
tmp = a[b1 - 1]
a[b1 - 1] = a[b2 - 1]
a[b2 - 1] = tmp
a
end
def comb(n, r)
c = 1.0
0.upto(r - 1){|x| c = c * ((n - x) / (r - x).to_f)}
c.to_i
end
def combs(n, r)
c = []
s = []
0.upto(r-1){|x| s << 1}
r.upto(n-1){|x| s << 0}
1.upto(comb(n,r)){|x|
tmp = ""
0.upto(n - 1){|y|
if s[y] == 1
tmp << "*"
else
tmp << "#"
end
}
c << tmp
s = enumerate(s, n, r)
}
c
end
def prime_patterns(p)
patterns = []
(p.length - 1).downto(1){|r|
combs(p.length, r).each{|c|
pp = p.dup
0.upto(p.length - 1){|x| pp[x] = c[x] if (c[x].chr == "*")}
patterns << pp
}
}
patterns
end
primes = sieve(999999)
prime_family = []
prime_idx = 0
while prime_family.length != 8 && prime_idx < primes.length
prime_family = []
prime_patterns(primes[prime_idx].to_s).each{|pp|
if prime_family.length != 8
prime_family = []
1.upto(9){|d|
ppp = pp.dup
ppp.gsub!("*", d.to_s)
prime_family << ppp if (primes.index(ppp.to_i) != nil)
}
end
}
prime_idx += 1
end
puts (prime_family.length == 8) ? "\n Smallest prime and its family: #{prime_family.join(",")}" : "\n Sorry, boy-o, no primes for you!"
Tom commenced execution of the updated program and went to bed.
The next morning, Tom went to his computer as before. This time, however, he was pleased to find that the program had come up with a solution. "Much better!" exclaimed Tom. "But I'm sure I can do even better than this. I mean, do we really need to check every prime? Wouldn't it make more sense just to generate a bunch of patterns and check those for primality?"
Stay tuned for the conclusion to this tale!
Reference
Oliver, I. (1993), Programming Classics: Implementing the World's Best Algorithms, Sydney: Prentice Hall. (ISBN 0-13-100413-1)
