1
\$\begingroup\$

I am working on Project Euler problem 37 and I have the following program:

#!/usr/bin/ruby -w

require 'prime'
h=11
y=0
x=0
while x < 11
    if h.prime? == true
        boo = true
        f=0
        n=h
        c=0
            while n > 0
                f += (n%10) * 10**(10-c)
                n/=10
                boo = false if n.prime? == false && n != 0
                c+=1
            end
            n=h
            c=10
            while c > 0
            n = n % (10**c)
            boo = false if n.prime? == false && n != 0
            c-=1
            end
        f /= 10 while f % 10 == 0
        if boo == true
            y+=h
            x+=1
            p h
        end
    end
h+=2
end
p y

It's designed to catch all of the eleven truncatable primes and does a good job of it, it catches the first ten is under one second, but it takes forty-nine seconds to find the last one, which happens to be, admittedly, a much larger number than the rest, is there any way to speed this up so that the eleventh one does not take so much time?

\$\endgroup\$
2
\$\begingroup\$

Some small notes on style:

  • if h.prime? == true should be if h.prime?; never use method? == true or method? == false, use if and unless.

  • I would replace your if h.prime? with next unless h.prime? and unindent the entire inner block; I hate having the entire body of your loop wrapped in a single if statement.

  • You should really, really choose better variable names. Single character names are a terrible practice. This is borderline obfuscated, who wants to figure out what a blob of uncommented difficult to read code does, in order to help you improve its performance?

Here's a simple refactor which is (on my system) 4x faster than your code, mostly because I'm aborting the outer loop early if the first inner while fails:

#!/usr/bin/ruby -w

require 'prime'


h, y, x = 9, 0, 0

while x < 11
  h += 2
  next unless h.prime?

  boo, f, n, c = true, 0, h, 0

  while n > 0
    f += (n % 10) * 10 ** (10 - c)
    n /= 10
    boo = false if !n.prime? && n != 0
    c += 1
  end

  # Don't keep checking if we already know this number fails
  next unless boo

  n = h
  c = 10

  while c > 0
    n %= (10 ** c)
    boo = false if !n.prime? && n != 0
    c-=1
  end

  f /= 10 while f % 10 == 0

  if boo
    y += h
    x += 1
    p h
  end
end

p y
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for the tips, I'll improve my use of variable names in the future. You helped me cut down my run time by 75% \$\endgroup\$ – user24658 May 3 '13 at 20:30
1
\$\begingroup\$

When dealing with mathematical/logical problems, you should consider ditching imperative style altogether and use functional programming instead. Ruby is not a functional language, but you can apply a lot of its principles. The point is: describe what you are doing, what values are, not how you get them.

Let's start coding taking the description of the problem, isn't that what you'd like to write?

solution = primes.select { |n| truncatable_prime?(n) }.take(11).sum

Well, so write it and just fill the blanks. I'd write (Ruby 2.x):

require 'prime'

def truncatable_prime?(n)
  if n >= 11
    s = n.to_s # using strings for simplicity
    truncated_left = (0...s.length-1).map { |i| s[0..i] }.map(&:to_i)
    truncated_right = (1...s.length).map { |i| s[i..-1] }.map(&:to_i)
    (truncated_left + truncated_right + [n]).all?(&:prime?)
  else
    false
  end  
end

module Array
  def sum
    reduce(0, :+)
  end
end

primes = Prime.instance.lazy
solution = primes.select { |n| truncatable_prime?(n) }.take(11).sum
#=> 7....7 (in 3.7s)
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Instead of testing for prime-nes of odd numbers you can just generate primes:

require 'prime'
prime_generator = Prime.instance
prime_generator.each do |prime|
  break if prime > 1000
  puts prime #well, do testing for truncatability here
end
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.