Palindromes using Scala

If you have a number like 123xxx you know, that either xxx has to be below 321 - then the next palindrom is 123321.

Or xxx is above, then the 3 can't be kept, and 124421 has to be the next one.

Here is some code without guarantees, not very elegant, but the case of (multiple) Nines in the middle is a bit hairy (19992):

object Palindrome extends App {

def nextPalindrome (inNumber: String): String = {
  val len = inNumber.length ()
  if (len == 1 && inNumber (0) != '9') 
    "" + (inNumber.toInt + 1) else {
    val head = inNumber.substring (0, len/2)
    val tail = inNumber.reverse.substring (0, len/2)
    val h = if (head.length > 0) BigInt (head) else BigInt (0)
    val t = if (tail.length > 0) BigInt (tail) else BigInt (0)

    if (t < h) {
      if (len % 2 == 0) head + (head.reverse)
      else inNumber.substring (0, len/2 + 1) + (head.reverse)
    } else {
     if (len % 2 == 1) {
       val s2 = inNumber.substring (0, len/2 + 1) // 4=> 4
       val h2 = BigInt (s2) + 1  // 5 
       nextPalindrome (h2 + (List.fill (len/2) ('0').mkString)) // 5 + "" 
     } else {
       val h = BigInt (head) + 1
       h.toString + (h.toString.reverse)
     }
    }
  }
}

def check (in: String, expected: String) = {
  if (nextPalindrome (in) == expected) 
    println ("ok: " + in) else 
    println (" - fail: " + nextPalindrome (in) + " != " + expected + " for: " + in)
}
//
val nums = List (("12345", "12421"), // f
  ("123456", "124421"), 
  ("54321", "54345"), 
  ("654321", "654456"), 
  ("19992", "20002"),
  ("29991", "29992"),
  ("999", "1001"),
  ("31", "33"),
  ("13", "22"),
  ("9", "11"),
  ("99", "101"),
  ("131", "141"),
  ("3", "4")
)
nums.foreach (n => check (n._1, n._2))
println (nextPalindrome ("123456678901234564579898989891254392051039410809512345667890123456457989898989125439205103941080951234566789012345645798989898912543920510394108095"))

}

I guess it will handle the case of a one-million-digit-Int too.

Doing reverse is not the greatest idea. It's better to start at the beginning and end of the string and iterate and compare element by element. You're wasting time copying the entire String and reversing it even in cases where the first and last element don't match. On something with a million digits, that's going to be a huge waste.

This is a few orders of magnitude faster than reverse for bigger numbers:

def isPalindrome2(someNumber:String):Boolean = {
  val len = someNumber.length;
  for(i <- 0 until len/2) {
    if(someNumber(i) != someNumber(len-i-1)) return false; 
  }
  return true;
}

There's probably even a faster method, based on mirroring the first half of the string. I'll see if I can get that now...

update So this should find the next palindrome in almost constant time. No loops. I just sort of scratched it out, so I'm sure it can be cleaned up.

def nextPalindrome(someNumber:String):String = {
  val len = someNumber.length;
  if(len==1) return "11";
  val half = scala.math.floor(len/2).toInt;
  var firstHalf = someNumber.substring(0,half);
  var secondHalf = if(len % 2 == 1) {
    someNumber.substring(half+1,len);
  } else {
    someNumber.substring(half,len);
  }

  if(BigInt(secondHalf) > BigInt(firstHalf.reverse)) {
    if(len % 2 == 1) {
      firstHalf += someNumber.substring(half, half+1);
      firstHalf = (BigInt(firstHalf)+1).toString;
      firstHalf + firstHalf.substring(0,firstHalf.length-1).reverse
    } else {
      firstHalf = (BigInt(firstHalf)+1).toString;
      firstHalf + firstHalf.reverse;
    }
  } else {
    if(len % 2 == 1) {
      firstHalf + someNumber.substring(half,half+1) + firstHalf.reverse;
    } else {
      firstHalf + firstHalf.reverse;
    }
  }
}

This is most general and clear solution that I can achieve:
Edit: got rid of BigInt's, now it takes less than a second to calculate million digits number.

def incStr(num: String) = {  // helper method to increment number as String
  val idx = num.lastIndexWhere('9'!=, num.length-1)
  num.take(idx) + (num.charAt(idx)+1).toChar + "0"*(num.length-idx-1)
}

def palindromeAfter(num: String) = {
  val lengthIsOdd = num.length % 2 
  val halfLength  = num.length / 2 + lengthIsOdd
  val leftHalf  = num.take(halfLength)               // first half of number (including central digit)
  val rightHalf = num.drop(halfLength - lengthIsOdd) // second half of number (also including central digit)      

  val (newLeftHalf, newLengthIsOdd) =  // we need to calculate first half of new palindrome and whether it's length is odd or even
    if (rightHalf.compareTo(leftHalf.reverse) < 0) // simplest case - input number is like 123xxx and xxx < 321
      (leftHalf, lengthIsOdd) 
    else if (leftHalf forall ('9'==))              // special case - if number is like '999...', then next palindrome will be like '10...01' and one digit longer
      ("1" + "0" * (halfLength - lengthIsOdd), 1 - lengthIsOdd)
    else                                           // other cases - increment first half of input number before making palindrome
      (incStr(leftHalf), lengthIsOdd)

  // now we can create palindrome itself
  newLeftHalf + newLeftHalf.dropRight(newLengthIsOdd).reverse
}