Numeric Palindrome Finder in Ruby

Somebody recently asked me how many palindromes there are between 1 and 10,000. Just for fun, here's a Ruby script to find the answer.

Update: Well, apparently I was too tired when I did this and I missed the obvious solution: just reverse the string and compare (thanks to Lee N and Jim Freeze). Doh! I'm taking down the original code because it's just silly now.  :)

puts (0..10000).find_all{|n| n.to_s == n.to_s.reverse}.size

or

x ="0"; puts x if x == x.reverse until x.succ! == "10000"
Design Element
Numeric Palindrome Finder in Ruby
Posted Dec 5, 2005 — 21 comments below




 

Carl — Dec 05, 05 587

Ah, brute force. The other method is to realize that palindromes must be mirror images.

So,
1 -> 11
2 -> 22

99 -> 9999

Those are the first 99 palindromes. Then you have issues where the center number is a pivot.

1->101, 111, 121, … 191. (ten items)

Since the limit is 10,000, the largest number you can get with this method is 9 -> 999.

Then add in numbers 0 through 9.

So, my guess is 99 + 90 + 9 = 198. Was I right?

Carl — Dec 05, 05 588

Ran it through my Ruby decoder ring and got 199. Heh, I guess I forgot to count 0 in my count from 0 to 9.

Olivier — Dec 05, 05 589

A paper table cloth would have done the trick: 9 between 1 and 9, 9 between 10 and 99, 90 between 100 and 999 and 90 between 1,000 and 9,999. Total: 198 (your script starts at 0 so it gives 199.)

The interesting question is: for what upper number is the table cloth faster than the ruby script?

:-)

Scott Stevenson — Dec 05, 05 590 Scotty the Leopard

Well you guys sure missed the point. :) Guess who wins when it's between 1 and 14,678?

rob mayoff — Dec 05, 05 591

Way, way too complicated. Try this:

counter = 0
for n in (0...10000)
counter += 1 if (n.to_s == n.to_s.reverse)
end
puts counter

Daniel Jalkut — Dec 05, 05 592

Well, the Ruby script will always be faster, now that it's written :)

But the paper napkin route has some interesting optimizations. Here are some observations:

1. Given a starting upper bound, you can instantly "normalize it" by insisting that it be a mirror of itself. For your example, examining 14678 is the same as examining 14641.

2. We need to account for all the palindromes at N digits plus all the palindromes at N-1 digits, etc. So on the paper napkin, if you start by writing out "14641" then you can, next to it, write out 9999, 999, 99, and 9. For the other "N-digit" values that make up the targeted range.

3. The sum at any range can be determined by examining the "head" of the palindrome: the part that leads to and includes the pivot in the center, if any. We want to know how many times we can decrement this value before it becomes an illegal palindrome head. Since the head we're examining is the most significant half of the value, numerically, we are guaranteed that any decremented value of the head will yield a counterpart on the tail that is within legal range for the bounds we're given. The only thing that can make the decremented value "illegal" is if it begins with zero. That's because we're not allowing numbers like "00300". To us, that would be "300" - not a palindrome.

4. To obtain the count of all N-digit palindromes not exceeding a given number, simply subtract one from the first digit of the head, and add one to the resulting "number. This accounts for the "lost" zero.

5. Putting this to work on our example:

14641. Head = 146. Count = 046 + 1 => 47.
9999. Head = 99. Count = 89 + 1 => 90.
999. Head = 99. Count = 89 + 1 => 90.
99. Head = 9. Count = 8 + 1 => 9.
9. Head = 9. Count = 8 + 1 => 9.

Total = 47 + 90 + 90 + 9 + 9 => 245.

Now, as you see, the math becomes pretty darned predictable after the "starting case." In fact, a shorthand for all the "9" cases is this: how many digits in this case? If odd, add 1 to N. The count is 9 * 10^(N/2 - 1). So, for "999999" we have N=6, count = 9 * 10 ^ (3-1) => 900. It's harder looking in math than it is on the napkin. On the napkin just start at the first 9 and add zeroes for each 9 after until you get to the "pivot." 9 x 10 x 10 => 900. What about for 999999999? Should be 9 x 10 x 10 x 10 x 10 => 90000.

Exercise for the reader: can you take the highly predictable math for the "9s" cases and turn them into an equation? Reduce this napkin algorithm to two cases: the "special case" starting palindrome at N digits, and a memorized math trick for all the other digit cases of all-9s.

Lee N — Dec 05, 05 593

or:

puts (0..10000).find_all{|n| n.to_s == n.to_s.reverse}.size

Jim Freeze — Dec 05, 05 594

Here's a one liner:

x ="0"; puts x if x == x.reverse until x.succ! == "100000"

David — Dec 05, 05 595

A PHP version (shorter than Ruby) ...

while ($i++ < 10000) if ($i == strrev($i)) echo "$i\n";

Scott Stevenson — Dec 05, 05 596 Scotty the Leopard

puts (0..10000).find_all{|n| n.to_s == n.to_s.reverse}.size

Oh wow, that is embarassing. My excuse is that it was 2am when I wrote it. :)

Daniel Jalkut — Dec 05, 05 597

Hey - there is no embarrassment in experimentation. Thanks for sharing your curiosity and the proposed solution. I don't think anybody gets the "perfect solution" on the first try every time, and when it comes to Ruby, I would never get such a perfect solution as those that were suggested above.

Eaten Alive — Dec 06, 05 598

I like the first one the most, but it would be even better like this--

("0".."10000").find_all{|n| n == n.reverse}.size

vasi — Dec 07, 05 600

Here's the perl version:

printf "%d\n", scalar(grep { "$_" eq reverse "$_" } (0..10000));

vasi — Dec 07, 05 601

And Haskell, just for fun :-)

length [ n | n <- [0..10000], show n == (reverse $ show n) ]

Abhi Beckert — Dec 08, 05 602

Off topic, but even though I know PHP and don't know Ruby, it seems pretty clear to me that the PHP version is much... cleaner.

*grabs fireproof jacket*

Scott Stevenson — Dec 08, 05 603 Scotty the Leopard

The PHP version doesn't actually count the total hits, though.

Eaten Alive — Dec 08, 05 604

while ($i++ < 10000) if ($i == strrev($i)) echo "$i\n"; Are all variables initialized to 0 in PHP? I don't write in PHP.

I would say the Perl version wins the prize for being the most ugly.

Abhi Beckert — Dec 08, 05 605

Oh come on, it's not as though you couldn't replace echo with $count++

hitoro — Dec 10, 05 606

((1 to: 10000) select: [ :n | n asString = n asString reversed ]) size

Can you guess which language I used?

Eaten Alive — Dec 11, 05 607

smalltalk

Peter M Jones — Jun 09, 06 1356

Your site is very useful.




 

Comments Temporarily Disabled

I had to temporarily disable comments due to spam. I'll re-enable them soon.





Copyright © Scott Stevenson 2004-2015