Palindromes using Scala

Question

I ran into this problem from CodeChef . The problem is this:

A positive integer is called a palindrome if its representation in the decimal system is the same when reading from left to right and from right to left. For a given positive integer K no more than 1,000,000 digits, write the value of the smallest palindrome larger than K to output.

I can define the isPalindrome method as follows:

def isPalindrome(someNumber:String):Boolean = someNumber.reverse.mkString == someNumber 

The problem I am facing is how to loop from the original given number and split and return the first palindrome when the integer satisfies the isPalindrome method? Also, is there a better (efficient) way to write the isPalindrome method?

It would be great to get some recommendations here.

Answer 1

If you have number 123xxx, you know that either xxx must be below 321, then the next palindrome is 123321.

Or xxx above, then 3 cannot be saved, and 124421 should be next.

Here is some code without guarantees, not very elegant, but the case is (somewhat) Nine in the middle is a little 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 think he will handle the case with a million digits.

Answer 2

Reverse is not a good idea. It’s better to start from the beginning and end of the line, iterate and compare elements by elements. You lose time by copying the entire line and changing it even in cases where the first and last elements do not match. Something with a million numbers, it will be a huge waste.

This is several orders of magnitude faster than the opposite for large 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 is probably an even faster method based on mirroring the first half of the line. I'll see if I can get it now ...

update So this should find the next palindrome almost at a constant time. No cycles. I just scratched it, so I'm sure it can be cleaned.

 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; } } } 

Answer 3

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

 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 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 } 

Answer 4

According to your suggestion without restrictions: the same, but using Stream:

 def isPalindrome(n:Int):Boolean = n.toString.reverse == n.toString def ints(n: Int): Stream[Int] = Stream.cons(n, ints(n+1)) val result = ints(100).find(isPalindrome) 

And with an iterator (and another calling method, the same thing you can do with Stream):

 val result = Iterator.from(100).find(isPalindrome) 

But since the unknown @user is unknown, it is direct brute force and not practical with large numbers.

Answer 5

To check if a List of Any Type is a palindrome using a slice, without any loops

 def palindrome[T](list: List[T]): Boolean = { if(list.length==1 || list.length==0 ){ false }else { val leftSlice: List[T] = list.slice(0, list.length / 2) var rightSlice :List[T]=Nil if (list.length % 2 != 0) { rightSlice = list.slice(list.length / 2 + 1, list.length).reverse } else { rightSlice = list.slice(list.length / 2, list.length).reverse } leftSlice ==rightSlice } 

}

Although the simplest solution would be

  def palindrome[T](list: List[T]): Boolean = { list == list.reverse } 

Answer 6

You can simply use the find method for collections to find the first element matching the given predicate:

  def isPalindrome(n:Int):Boolean = n.toString.reverse == n.toString val (start, end) = (100, 1000) val result: Option[Int] = (start to end).find(isPalindrome) result foreach println >Some(101) 

Answer 7

Solution to check if string is a palindrome

This solution does not cancel the line. However, I am not sure that it will be faster.

 def isPalindrome(s:String):Boolean = { s.isEmpty || ((s.last == s.head) && isPalindrome(s.tail.dropRight(1))) } 

Solution for finding the next palindrome by string

This solution is not suitable for scala (almost the same as the Java solution), but it deals only with strings and is suitable for large numbers

You just need to reflect the first half of the number you want, check if it is higher than the starting number, otherwise increase by one last digit of the first half and mirror it again.

Firstly, a function to increase the string representation of an int by 1:

 def incrementString(s:String):String = { if(s.nonEmpty){ if (s.last == '9') incrementString(s.dropRight(1))+'0' else s.dropRight(1) + (s.last.toInt +1).toChar }else "1" } 

Then the function to compare with the string representation of ints: (the function 'compare' does not work for this case)

 /* is less that 0 if x<y, is more than 0 if x<y, is equal to 0 if x==y */ def compareInts(x:String, y:String):Int = { if (x.length !=y.length) (x.length).compare(y.length) else x.compare(y) } 

Now the function to calculate the following palindrome:

 def nextPalindrome(origin_ :String):String = { /*Comment if you want to have a strictly bigger number, even if you already have a palindrome as input */ val origin = origin_ /* Uncomment if you want to have a strictly bigger number, even if you already have a palindrome as input */ //val origin = incrementString(origin_) val length = origin.length if(length % 2 == 0){ val (first, last) = origin.splitAt(length/2); val reversed = first.reverse if (compareInts(reversed,last) > -1) first ++ reversed else{ val firstIncr = incrementString(first) firstIncr ++ firstIncr.reverse } } else { val (first,last) = origin.splitAt((length+1)/2) val reversed = first.dropRight(1).reverse if (compareInts(reversed,last) != -1) first ++ reversed else{ val firstIncr = incrementString(first) firstIncr ++ firstIncr.dropRight(1).reverse } } } 

Answer 8

You can try something like this, I use basic recursion:

  object Palindromo { def main(args: Array[String]): Unit = { var s: String = "arara" println(verificaPalindromo(s)) } def verificaPalindromo(s: String): String = { if (s.length == 0 || s.length == 1) "true" else if (s.charAt(0).toLower == s.charAt(s.length - 1).toLower) verificaPalindromo(s.substring(1, s.length - 1)) else "false" } }