Home > Python, scala, Uncategorized > Car Talk Puzzler #3: The Palindromic Odometer

Car Talk Puzzler #3: The Palindromic Odometer

The Palindromic Odometer

Driving along, Terry notices that the last four digits on the odometer are palindromic. A mile later, the last five digits are palindromic. [A mile later, the middle four digits are palindromic.] [One mile after that], all six are palindromic. What was the odometer reading when Terry first looked at it?

Full question

This is the third in my series of Car Talk puzzler solutions using whatever programming language strikes my fancy. Just like the last one I wrote, this one uses Scala. This is a much shorter post, as I am assuming some familiarity with Scala; go back and read the last post if you haven’t already.

object PalindromicPuzzlerSolver {
    // Pad out numbers to 6 places
    // Note that I can cal Java library functions seamlessly
    val df = new java.text.DecimalFormat("000000")

    // A string is a palindrome if it reversed equals itself
    def isPalindrome(word: String): Boolean = {
        // Reverse is a method of a RichString, which a String can be implicitly converted
        // into. Necessary to convert the RichString back into String after the reversal
        word == word.reverse.toString()

    def fitsDescription(miles: Int): Boolean = {
        // Last 4 are palindome (dropping first 2)
        isPalindrome(df.format(miles).drop(2)) &&
        // Add one, last 5 are palindrome
        isPalindrome(df.format(miles + 1).drop(1)) &&
        // Add two more, all six are a palindrome
        isPalindrome(df.format(miles + 3))

    def main(args: Array[String]) {
        val max = 1000000
        println( 0 until max filter fitsDescription )
        // Prints out
        // RangeF(198888, 199999)

        // This is the same as the java style:
        // println( (0.until(max)).filter(fitsDescription) )
        // This syntax only works when you are dealing with
        // methods that take one argument.

Thus the solution is 198888, just as the answer proclaims. Another win for brute force.

There are three noteworthy things in this example, which didn’t come up in the last post (or weren’t explained fully)

1. Interoperability with Java
2. Use of drop
3. Convenience methods for specifying a range

Interoperability with Java

Any Java class can be imported and used with Scala; that is one of its strongest selling points. Scala runs in the same JVM as Java, so it makes sense that it should have access to Java classes. In fact many Scala classes are thin wrappers around Java objects, with syntactic sugar built in. For instance, Scala has a BigInt class which wraps a Java BigInteger, while providing overloaded methods to allow them to be used more like standard numbers. For instance,

scala> BigInt("103058235287305927350") + BigInt("288888203959230529352")
res16: BigInt = 391946439246536456702

scala> new java.math.BigInteger("103058235287305927350").add(new java.math.BigInteger("288888203959230529352"))
res21: java.math.BigInteger = 391946439246536456702

Note that the + is actually a method call; this is exactly the same thing as calling

scala> BigInt("103058235287305927350").+(BigInt("288888203959230529352"))
res22: BigInt = 391946439246536456702

In Scala, method names don’t have to be alphanumeric, which is how it gets away with what looks like operator overloading. This makes it a lot nicer to work with classes like BigDecimal or BigInteger, as you can use the more commonly used addition and subtraction symbols rather than explicitly calling “add” and “subtract” methods. Just realize that you are really calling methods like any other under the hood. When you understand this, you’ll also understand why Scala uses an underscore instead of * for wildcard – * can be used in method names, as it is used for multiplication!


Scala has full support for slicing iterable objects; see my previous discussion on slices if this term is unfamiliar.

scala> List(1,2,3,4).slice(1,3)
res27: List[Int] = List(2, 3)

scala> List(1,2,3,4).slice(1)
warning: there were deprecation warnings; re-run with -deprecation for details
res28: Seq[Int] = List(2, 3, 4)

scala> List(1,2,3,4).drop(1)
res29: List[Int] = List(2, 3, 4)

So drop(n) is exactly the same as slice(n) – it provides a new list with the first n elements removed. I use drop instead of slice due to the deprecation of the single argument form of slice.

Specifying a range
If you need to iterate over a range of numbers in Java, you’d do something like
for (int i = 0; i < max; i++) {

whereas in Python you can do something like
for x in range(max):

Scala similarly provides methods to create a range of numbers to iterate over.

scala> 0 until 10
res9: Range = Range(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

scala> 0 to 10
res10: Range.Inclusive = Range(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

Again, I want to stress that until is a method like any other; you are just free to leave off the . and the parens when it is unambiguous what you mean. Note that these commands are actually creating a sequence in memory. If you only need to access each element one at a time, and you are dealing with a large range, you might instead create an Iterator rather than a sequence. The Iterator will create each subsequent number as necessary, rather than building up the whole list ahead of time. This is much more space efficient.

Note that Python makes this distinction as well:

>>> range(10)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> xrange(10)

xrange returns a generator object, as opposed to range which returns the actual list.

Returning to Scala, if I wanted an iterator instead I would do

scala> Iterator.range(0,10)
res11: Iterator[Int] = non-empty iterator

scala> Iterator.range(0,10).foreach(println)

I have shown another solution using Scala, while illustrating a few more features. In particular one needs to understand that Scala’s syntactic sugar is actually masking standard function calls under the hood; x + y is the same as x.+(y), where “+” is a valid function name.

  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: