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?

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.

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?

:-)

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

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

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.

or:

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

Here's a one liner:

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

A PHP version (shorter than Ruby) ...

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

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. :)

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.

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

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

Here's the perl version:

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

And Haskell, just for fun :-)

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

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*

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

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.

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

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

Can you guess which language I used?

smalltalk

Your site is very useful.