Ruby non, C++ oui

For my first try I wrote this:

def sum_of_digits(n)

sum = 0

while (n > 0)

sum += n % 10

n /= 10

end

sum

end

num_digits = gets.chomp.to_i

exponent = num_digits/2

divisor = 10**exponent

limit = (10**num_digits) - 1

total = 0

0.upto(limit) do |cur|

upper = cur / divisor

lower = cur % divisor

total += 1 if sum_of_digits(upper) == sum_of_digits(lower)

end

puts total

# eof

For 2, 4 and 6 digits it got the requisite answers of 10, 670, and 55252. There was a bit of a pause while it crunched away at the 6-digit case, though.

For 8 digits it … well, I let it run and went to do something else. Then I had the bright idea to time it (on mac OS X, using the time command):

4816030

real 1m42.596s

user 1m34.222s

sys 0m1.837s

The right answer, but the last time I checked, one minute anything was greater than two seconds. What to do?

It’s pretty clear that calling sum_of_digits a bunch more times than necessary is the biggest problem. For try #2, I precomputed the sums and stuffed them into an array, and indexed the array in place

of calling sum_of_digits in the main loop. Here’s the result:

time ruby lucky.rb < t8.txt

4816030

real 0m19.176s

user 0m18.017s

sys 0m0.313s

A better than 80% speedup. Most times I would kill for that, but I still need to lose 95% of the remaining run time. How to do it?

I checked … initializing the array of sums takes virtually no time, even if I write out the entire array contents to a file.

So the main loop is killing me, and unfortunately I need a dramatic change of algorithm but I

don’t see one. So …

1. Recode in C or C++

2. Hell if I know

Taking option 1, I got Accepted, with run times around 1.1 seconds or so for 8 digits. It's a straightforward translation to C++, very brute force.