I found this interesting Ruby question on StackOverflow and thought I’d use it to learn a little more Ruby too. The original Euler problem description:
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
One search solution is to go through all possible values in two loops.
for a in (100...1000).to_a.reverse do for b in (100...1000).to_a.reverse do
and look for a number that is the same when reversed (a palindrome).
c = a * b best=c if c > best && c.to_s == c.to_s.reverse
The problem is we have to go through all combinations because there might be a higher palindome on the 997 row than on the 998 row. One thing we can try is to reduce the set of “all combinations”.
First we can limit the inner loop to values less than or equal to a (since a*b == b*a). This always puts the larger multiplicand in a and substantially reduces the number of combinations we have to try.
for a in (100...1000).to_a.reverse do for b in (100..a).to_a.reverse do
The next thing we can do is break out of the inner loop whenever the product is less than the current best value.
c = a*b break if c < best
My tests show that we try some 405K combinations… there has to be a more efficient way. Can we do something different so that we search for palindomes from highest to lowest? How about pulling out the product? The largest possible product of two 3-digit numbers is 999 * 999 = 998001 and the smallest is 100*100 = 10000. If we iterate this range we can stop as soon as we find a palindrome that is a product of two 3-digit numbers.
for c in (10000...998001).to_a.reverse do
We get to a palindrome after only 202 tests… the problem is it isn’t a product of two 3-digit numbers. So now we have to check whether every palindrome we’ve found is the product of two 3-digit numbers. My tests show we find the highest palindrome that meets the requirement after less than 93K trys. But since we have the overhead of checking that all palindromes to that point were products of two 3-digit numbers it may not be more efficient than the previous solution.
So lets go back to the original double loop.
for a in range.to_a.reverse do for b in (100..a).to_a.reverse do
We’re looping rows then columns and trying to be efficient by detecting a point where we can go to the next row because any additional trys on the current row could not possibly be better than our current best. What if, instead of going across the rows, we go across the diagonals?
Since the products get smaller diagonal by diagonal we can stop as soon as we find a palindome number. This is a really efficient solution but with a more complex implementation. It turns out this method finds the highest palindrome that is the product of two 3-digit numbers after slightly more than 2200 trys.
We could also probably do something with evens and odds. For example if the first digit of the product is even then both multiplicands would also have to be even for the last digit of the product to be even… but this level of optimization and complexity isn’t necessary for this problem. If we were going after larger products, say two 7-digit integers (that’s the point where the runtime of this implementation hits the wall on my box), we might have to look at this and other number-theory based optimizations.
Ruby things I learned:
- generating integer ranges: 100…1000
- converting a range to an array: (x…1000).to_a
- reversing the order of the values in an array: .reverse e.g. (x…1000).to_a.reverse and “pans”.reverse
- .ToString() equivalent: 6.to_s
- exiting a program (with a return code): exit 0