[Easy] Palindromes

[Michael Morris]

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:

public int palindromes(int low, int high);

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]

This answer worked for me:

public class Palindrome {
  public static void main(String[] args) {
    Palindrome p = new Palindrome();
    // Check for correct usage
    if (args.length != 2) {
      p.usage();
    } else {
      int count = 0;
      for (int i = Integer.parseInt(args[0]); i <= Integer.parseInt(args[1]); i++) {
        if (p.isPalindrome(i)) {
          count++;
        }
      }
      System.out.println("Number of palindromes between " + args[0] + " and " + args[1] + ": " + count);
    }
  }
  void usage() {
    System.out.println("usage: Palindrome low high");
  }
  // Checks a string against its reversed version
  boolean isPalindrome(int number) {
    String stringVersion = String.valueOf(number);
    return stringVersion.equals(reverse(stringVersion));
  }
  // Returns the reversed version of a string
  String reverse(String s) {
    int i = 0;
    String r = "";
    for (i = s.length() - 1; i >= 0; i--) {
      r += s.charAt(i);
    }
    return r;
  }
}

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

[Timothy Chen Allen]

Here's another version of the same thing-- I thought mayber there would be a more advanced way of testing for "palindrome-ness":

public class Palindrome {
  public static void main(String[] args) {
    Palindrome p = new Palindrome();
    if (args.length != 2) {
      p.usage();
    } else {
      int count = 0;
      for (int i = Integer.parseInt(args[0]); i <= Integer.parseInt(args[1]); i++) {
        if (p.isPalindrome(i)) {
          count++;
        }
      }
      System.out.println("Number of palindromes between " + args[0] + " and " + args[1] + ": " + count);
    }
  }
  void usage() {
    System.out.println("usage: Palindrome low high");
  }
  boolean isPalindrome(int number) {
    String stringVersion = String.valueOf(number);
    for (int i = 0; i < (stringVersion.length()/2); i++) {
      if (stringVersion.charAt(i) != stringVersion.charAt(stringVersion.length() - 1 - i)) {
        return false;
      }
    }
    return true;
  }
}

[Michael Morris]

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]

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:

String s = "" + i;
if (s.equals(new StringBuffer(s).reverse().toString())) {

Snippet 2:

if (("" + i).equals(new StringBuffer("" + i).reverse().toString())) {

Snippet 3:

StringBuffer s = new StringBuffer("" + i);
if (s.toString().equals(s.reverse().toString())) {

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]

Yep, basically what I had:

public class IpalindromeI
{
public static void main(String[] args)
{
int start=0;
int stop=1000000;
long startTime = System.currentTimeMillis();
        int count = 0;
for(int i=start;i<stop+1;i++)
{
String tmp = ""+i;
            String pmt = new StringBuffer().append(tmp).reverse().toString();
            if( pmt.equals( tmp ) )
{
                count++;
}
}
System.out.println("Found "+count+" in: "+(System.currentTimeMillis()-startTime)+"ms");
}
}

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]

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:

import java.util.Hashtable;
/**
 * @author Roy Tock
 *
 */
public class Palindrome
{
    Hashtable powerOfTenCache = new Hashtable();
    
    public static void main(String[] args)
    {
        System.out.println( "Palindromes between " + args[0] + " and " + args[1] + ": "
            + new Palindrome().palindromes( Integer.parseInt(args[0]), Integer.parseInt(args[1]) ) );
    }
    public int palindromes(int low, int high)
    {
        int lowNumDigits = String.valueOf(low).length();
        int highNumDigits = String.valueOf(high).length();
        int digitCount;
        int functionValue = 0;
        
        if (lowNumDigits == highNumDigits)
        {
            return palindromes(low, high, lowNumDigits);
        }
        else
        {
            // Count the number of palindromes between low and the next power of ten
            functionValue += palindromes(low, powerOfTen(lowNumDigits)-1, lowNumDigits);
            
            // Count the number of palindromes between the power of ten just 
            // greater than low, and the power of ten just less then high.
            for (digitCount = lowNumDigits + 1; digitCount < highNumDigits; digitCount++)
            {
                functionValue += palindromes( powerOfTen(digitCount-1), powerOfTen(digitCount)-1, digitCount);
            }
            
            // Count the number of palindromes that are less than high and that have
            // the same number of digits as high.
            functionValue += palindromes(powerOfTen(highNumDigits-1), high, highNumDigits);
        }
        
        return functionValue;
    }
    
    private int palindromes(int low, int high, int digits)
    {
        int functionValue;
        System.out.print( "Computing palindrome(" + low + ", " + high + ", " + digits + ") = " );
        // simple case; let's excise it now.
        if (digits == 1)
        {
            functionValue = high - low + 1;
            System.out.println(functionValue);
            return functionValue;
        }
        
        if (low == powerOfTen(digits-1))
        {
            if (high == powerOfTen(digits)-1)
            {
                // In all positive numbers having N digits,
                // there are 9 * (10^(floor((N-1)/2))) palindromes.
                // i.e., there are 9 one-digit palindromes,
                // 9 two-digit palindromes,
                // 90 three-digit palindromes,
                // 90 four-digit palindromes,
                // 900 five-digit palindromes, etc.
                functionValue = 9 * powerOfTen(floor((digits-1)/2));
                System.out.println(functionValue);
                return functionValue;
            }
            else
            {
                // The number of palindromes between 1000...000 and high:
                // e.g., pal(1000000, 2345678) = pal(1000000, 2345000) + pal(2345001, 2345678)
                //                             = (2345 - 1000)         + 1
                int leadingHalfOfHigh = high / powerOfTen(floor(digits/2));
                int leadingHalfPalindrome;
                
                if ( (digits % 2) == 1 )
                {
                    // digits is ODD.  If leadingHalfOfHigh is 1234, then
                    // leadingHalfPalindrome is 1234321.
                    leadingHalfPalindrome = (leadingHalfOfHigh * powerOfTen(((digits-1)/2)))
                        + Integer.parseInt((new StringBuffer().append(leadingHalfOfHigh).reverse().deleteCharAt(0)).toString());
                }
                else 
                {
                    // digits is EVEN.    If leadingHalfOfHigh is 1234, then
                    // leadingHalfPalindrome is 12344321.
                    leadingHalfPalindrome = (leadingHalfOfHigh * powerOfTen((digits/2)) )
                        + Integer.parseInt((new StringBuffer().append(leadingHalfOfHigh).reverse()).toString());
                }
                
                functionValue = (leadingHalfOfHigh - powerOfTen(floor((digits-1)/2)))
                          + ( (leadingHalfPalindrome <= high) ? 1 : 0 );
                System.out.println(functionValue);
                return functionValue;
            }
        }
        else
        {
            functionValue = palindromes(powerOfTen(digits-1), high, digits)
                        - palindromes(powerOfTen(digits-1), low-1, digits);
            System.out.println(functionValue);
            return functionValue;
        }
    }
    
    /**
     * Returns the specified power of ten.
     * @param exponent A non-negative integer.
     */
    private int powerOfTen(int exponent)
    {
        Integer expWrapper = new Integer(exponent);
        Integer valueWrapper = (Integer)powerOfTenCache.get(expWrapper);
        if (valueWrapper == null)
        {
            int value = (int)Math.round(Math.pow(10,exponent));
            powerOfTenCache.put(expWrapper, new Integer(value));
            return value;
        }
        else
        {
            return valueWrapper.intValue();
        }
    }
    
    private int floor(double num)
    {
        return (int)Math.round(Math.floor(num));
    }
}

Sample output:

C:\eclipse\workspace\palindrome\bin>java Palindrome 1 2147483647
Computing palindrome(1, 9, 1) = 9
Computing palindrome(10, 99, 2) = 9
Computing palindrome(100, 999, 3) = 90
Computing palindrome(1000, 9999, 4) = 90
Computing palindrome(10000, 99999, 5) = 900
Computing palindrome(100000, 999999, 6) = 900
Computing palindrome(1000000, 9999999, 7) = 9000
Computing palindrome(10000000, 99999999, 8) = 9000
Computing palindrome(100000000, 999999999, 9) = 90000
Computing palindrome(1000000000, 2147483647, 10) = 11475
Palindromes between 1 and 2147483647: 121473

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

[Jim Yingst]

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]

And good job, Roy. No need for a for loop in this class, certainly not.

[Francis Siu]

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]

Just for (my) interests sake, I'll drop an integer version I wrote:

public class Ipalindrome2
{
    public static void main(String[] args)
    {
        int start=0;
        int stop=1000000;
        long startTime = System.currentTimeMillis();
        int count = 0;
        for(int i=start;i<stop+1;i++)
        {
            if(i==reverse(i))
                count++;
        }
        System.out.println("Found "+count+" in: "+(System.currentTimeMillis()-startTime)+"ms");
    }
    private static int reverse(int value)
    {
        double mag = Math.log(value)/Math.log(10);
        int magnitude = 0;
        magnitude = (int)mag +1;
        int result = 0;
        for(int i=0;i<magnitude;i++)
        {
            int digit = (int)(value/Math.pow(10,i))%10;
            result+= (int)(digit*(Math.pow(10,magnitude-i-1)));
        }
        return result;
    }
}

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]

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:

    private static int reverse(int value)
    {
        int newValue = 0;
        while (value > 0)
        {
            int digit = value % 10;
            newValue = newValue * 10 + digit;
            value /= 10;
        }
        return newValue;
    }

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]

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]

Ummm... what String pool?
Damn. I guess there ain't no StringBuffer pools huh?

[Michael Morris]

Good job Roy. Those patterns is what I was referring to. Now Gregg has to show his.

[Greg Harris]

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.