Finishing two in one day does feel nice.
I’m really liking Ruby’s ability to memoize. In this solution I used a Hash so I could avoid recreating large powers of 10 over and over again. That allowed me to cut the time down significantly.
The final solution required 20 digits of precision. I was hoping to be able to do it with fewer, but no luck. I had to run it a few times with different precisions in order to finally come to the answer.
Using ‘ruby-prof’ for a profiler really helps. It allowed me to test out different implementations and know exectly where my algorithm was most slow. I tried new ways thinking they’d be faster only to find they weren’t. It was very interesting at times.
The hardest part of this problem was determining if a number started with some
particular digits. The obvious solution is to change the number to a string
and then call String#start_with? on it. But that was incredibly slow.
class Problem
POWERS_OF_TEN = Hash.new { |hash, key| hash[key] = 10.pow(key) }
class << self
def p(l, n)
power = 0
num_found = 0
len = num_digits(l)
raised = 1
loop do
power += 1
raised *= 2
raised = truncate(raised, 20)
if truncate(raised, len) == l
num_found += 1
return power if num_found == n
end
end
end
def truncate num, len
return 0 if len < 1
diff = num_digits(num) - len
return num if diff < 1
power = POWERS_OF_TEN[diff]
return num.div(power)
end
def num_digits num
num.to_s.length
end
end
end
if __FILE__ == $0
puts Problem.p(123, 678910)
end
require 'test/unit'
require './problem'
class TestProblem < Test::Unit::TestCase
[
[ 12, 1, 7],
[ 12, 2, 80],
[123, 45, 12710],
].each do |l, n, expect|
define_method "test_p_#{l}_#{n}" do
assert_equal expect, Problem.p(l, n)
end
end
[
[12345, 0, 0],
[12345, 1, 1],
[12345, 2, 12],
[12345, 3, 123],
[12345, 4, 1234],
[12345, 5, 12345],
[12345, 40, 12345],
].each do |num, len, expect|
define_method "test_truncate_#{num}_#{len}" do
assert_equal expect, Problem.truncate(num, len)
end
end
end