|back to board|
Ruby non, C++ oui
For my first try I wrote this:
sum = 0
while (n > 0)
sum += n % 10
n /= 10
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)
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):
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
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.