[Easy] Palindromes

Michael Morris
Ranch Hand
Posts: 3451
A palindrome is a sequence of characters such that they read the same backwards as they do forwards. For example "Live on Time emit no evil". Numbers can also be palindromes like: 88, 1331, 242. Write a method that will return the quantity of integers that are found in a given range. The signature should be something like:

where low and high are positive integers and the range is inclusive. As an example if low=1 and high=50 the result should be 13 for the palindromes 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33 and 44.
Let's give the rookies first shot at this one.
[ June 24, 2003: Message edited by: Michael Morris ]

Timothy Chen Allen
Ranch Hand
Posts: 161

[ June 25, 2003: Message edited by: Tim Allen ]

Timothy Chen Allen
Ranch Hand
Posts: 161
Here's another version of the same thing-- I thought mayber there would be a more advanced way of testing for "palindrome-ness":

Michael Morris
Ranch Hand
Posts: 3451
Good job Tim. Your code seems to work fine. But you have a pretty severe performance problem for large ranges. Your code took over 6 seconds to find all the palindromes between 0 and 500000. At that rate it would take over 7 hours to calculate the full range of positive integers (0-Integer.MAX_VALUE). Let's see if anyone can optimize the code to handle large ranges in a reasonable time frame. Hint: see if you can find any range patterns.

Michael Morris
Ranch Hand
Posts: 3451
I'm not going to post my full brute force solution, but would like to post a pertinent section of it to discuss a performance issue that I was unaware of.
Snippet 1:

Snippet 2:

Snippet 3:

On my machine, Snippet 1 performs the best, taking about 2.9 secs run the range 1-1000000. Snippet 3 takes about 3.7 seconds and amazingly Snippet 2 takes about 4.6 seconds. I would have thought Snippet 2 would have been the fastest since we are dealing with the String pool. Anybody got an explaination?

David O'Meara
Rancher
Posts: 13459

Metrics: 1,000,000 in 2.6s (on a p2-400)
For snippet 2, I think the problem is the String concatenation. It gets optimised (and therefore is not as bad as it once was), but there is still a bunch of work that needs to be done.
The trick may be to decide whether you're using ints, Strings or StringBuffers, and do as little conversion as possible. the conversion is fast, but still not free.

Roy Tock
Ranch Hand
Posts: 83
Here's my solution. It uses a few interesting facts about the palindrome function (abbreviated to "pal" here):
• If 0 < a < b < c <= Integer.MAX_VALUE, then pal(a,c) = pal(a,b) + pal(b+1,c).
• If 0 < a < b < c <= Integer.MAX_VALUE, then pal(b,c) = pal(a,c) - pal(a,b-1).
• There are 9 two-digit palindromes, 90 three-digit palindromes, 90 four-digit palindromes, 900 five-digit palindromes, etc. Why? Let's take five-digit palindromes, for instance. There's one beginning with "100" (10001), one beginning with "101" (10101), one beginning with "102" (10201), etcetera, up to 999. So there are 999 - 100 + 1 = 900 five-digit palindromes. A more general formula: there are 9 * 10^(floor((N-1)/2)) N-digit palindromes.

• These facts yield the following code, which computed pal(0,Integer.MAX_VALUE) almost instantly on my PC:

Sample output:

[ June 25, 2003: Message edited by: Roy Tock ]
[ June 25, 2003: Message edited by: Roy Tock ]

Jim Yingst
Wanderer
Sheriff
Posts: 18671
I would have thought Snippet 2 would have been the fastest since we are dealing with the String pool. Anybody got an explaination?
Ummm... what String pool? That is, where would the string pool come into play? It only pertains to String-valued compile-time constant expressions, and any Strings which are explicitly interned. Which doesn't happen an any of the snippets (other than the trivial literal ""). So what's wrong with snippet 2? Well, it evaluates "" + i twice rather than once - that's the main thing. As for snippet 3 - StringBuffers are less efficient if you call toString() and then change the buffer further; the later change is almost as expensive as allocating a new StringBuffer. That's because the StringBuffer is optimized to to the original toString() really quickly by simply wrapping its current internal array in a String object (using a special package-access constructor which the rest of us aren't allowed to use because it would allow the creation of a mutable String). The catch is the StringBuffer is now responsible for guarding the immutability of the String it just created - if additional changes are made to the StringBuffer, it can't just make the changes in its internal array, as that would also change the "immutable" String it just created. So instead it copies the internal array to a new array, and discards the old one (so it's now only being used by the String created earlier). Weird, I know. What it boils down to is, StringBuffer is optimized so that if toString() is the last thing you do with it, it's fast - but if you call other mutating methods after that, you pay a penalty.
public class IpalindromeI
Special recognition to DOM for best class name.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
And good job, Roy. No need for a for loop in this class, certainly not.

Francis Siu
Ranch Hand
Posts: 867
Palindromes
I think that many cookies will be posted to ranchers home

Does anyone know who's method is the fastter and efficient way to solve the problem?
thanks

[ June 25, 2003: Message edited by: siu chung man ]

David O'Meara
Rancher
Posts: 13459
Just for (my) interests sake, I'll drop an integer version I wrote:

The interesting part is that on the same machine it takes almost 17 seconds, significantly more than the String version. Stick that in a pipe and hand to anyone who has a problem with String performance.
I haven't profiled it, but is the problem the log function? Caching the value of Math.log(10) only cut a second off the time.
There are a couple of problems such as reverse(20)=2, but I ignored it since it doesn't effect the detection of palindromes.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
David - I haven't profiled it either, but I'm betting it's Math.log() and Math.pow(). And caching isn't necessarily that much faster for something like this - (a) it takes some time to calulate the hash function, (b) it takes some time to create the wrapper objects for the keys, and (c) depending on how you set it up, individual keys may not get reused much anyway. But simple math can be much faster - try this substitute for your reverse:

Does anyone know who's method is the fastter and efficient way to solve the problem?
thanks

Oh, definitely Roy's. It can cover any possible int range, returning pretty much immediately. (Not worth timing really.) It's O(log n) rather than the O(n * log n) which all the other solutions have. Note that the original problem did not require that we find all the palindromes - just that we count them. As an example - how many palindromes are there between 1000000 and 5835000? Answer: 5835. Think about why that would be true. If you can't see why - try making a list of the palindromes in this range, and look for a pattern.

David O'Meara
Rancher
Posts: 13459
Originally posted by Jim Yingst:
try this substitute for your reverse:

Yep, 1 second now.
Silly me for not seeing it. :roll:
Thanks!

Michael Morris
Ranch Hand
Posts: 3451
Ummm... what String pool?
Damn. I guess there ain't no StringBuffer pools huh?

Michael Morris
Ranch Hand
Posts: 3451
Good job Roy. Those patterns is what I was referring to. Now Gregg has to show his.

Greg Harris
Ranch Hand
Posts: 1012
Now Gregg has to show his.
i removed my reference to %... i was thinking of something else!
anyway, it is a simple matter of combinitorics... i like roy's answer because that is pretty much what i was thinking about while i was trying to take a midterm exam last night.
obviously, you have 9 choices for the first (and last) digit... and then 10 choices for each of the inner pairs of digits.
from there, you have 9*10*10... for each pair. unless, of course, you are given a boundary... in that case, you have to compute the totals for (n-1) and then compute the rest.
in other words, if you are given the range (1, 521), you can compute 4*10 = 40 for 404 - 494. then, because 1 < 5, you have 2 (505 and 515) for 521.
all that is left is adding in 9 for 1, 2,...,9 and another 9 for 11,22,...,99.
the total will be 40 + 2 + 9 + 9 = 60.
i was going to code it this morning, but i see that a lot of people beat me to it.