|
|
back to boardRuby 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. |
|
|