Longest palindromes

Question

I've been tasked to solve this exercise lately, and this is what I wrote:

object Main {
    def isSubstringPalindrome(inp: String)(start: Int, end: Int): Boolean =
        (start.compareTo(end), inp(start)==inp(end)) match {
        case (0, _) => true
        case (1, _) => true
        case (-1, true) => isSubstringPalindrome(inp)(start+1, end-1)
        case _ => false
    }

    def vecToPair[T](vec: IndexedSeq[T]): (T, T) = vec match {
        case Vector(a, b) => (a, b)
    }

    def isContained(slice1: (Int, Int))(slice2: (Int, Int)): Boolean = (slice1, slice2) match{
        case ((x, y), (w, z)) => x > w && y < z
    }

    def palindromes(inp: String): Seq[(Int, Int)] = {
        val isPalindrome: ((Int, Int)) => Boolean = (isSubstringPalindrome(inp)_).tupled
        val palindromeIndexes = inp.zipWithIndex
            .groupBy(_._1).values // group by char
            .map(_.map(_._2)).filter(_.length > 1) // retain sequence of indexes
            .flatMap(_.combinations(2).map(vecToPair))
            .filter(isPalindrome).toSeq
            .sortBy{case (start, end)=> -(end+1-start)}
        palindromeIndexes.filter(slice => ! palindromeIndexes.exists(isContained(slice)_))
    }

    def main(args: Array[String]) = {
        val inp = if (args.isEmpty) "sqrrqabccbatudefggfedvwhijkllkjihxymnnmzpop" else args(0)
        palindromes(inp).take(3)
            .map{case (start, end) => (inp.slice(start, end+1), start, end+1-start)}.foreach{
            case (str, start, length) => println(s"Text: $str, Index: $start, Length: $length")
        }
    }
}

I tried to care about conciseness and good functional style, tests/TDD wasn't supposedly a focus for this, and my algorithm should already be better than a naive \$ O \left( n^3 \right) \$ (the worst case of the string composed of the same letter all over is still pretty bad, though). The partially applied isSubstringPalindrome also avoids to wastefully reallocate substrings, and only needs the indexes to work upon.

If performance is a concern, isSubstringPalindrome can be trivially memoized, which should trade off memory for faster execution on very large strings.

With this taken care of, I've been told:

the solution should be correct, reliable, maintainable, reusable, portable and efficient.

My solution is obviously not ideal: I could've added some scaladoc to explain the code. Another trivial improvement could've been to factorize out end+1-start into a length function... that way I could've written something like .sortBy(length).reverse or .sortBy(-length(_)).

Also, it would've been nicer if .compareTo in Scala would return a data Ordering = LT | EQ | GT just like in Haskell: that way isSubstringPalindrome would be more explicitly/guarantee in the fact that it's handling all cases: (string not fully checked for palindromeness yet: start < end, odd length palindrome: start==end, even length palindrome: end < start)... but this is not really a shortcoming of my code.

Anyhow, given the algorithm, I think that the code itself is somewhat readable and clean. Functions of only 2/3 statements each, no temporal coupling, etc.

That said, it wasn't appreciated. My suspicion is that they expected some classes to be defined, and gain some insight on my data modeling thought process. If that's so, I'm a bit disappointed, because a test that asks to solve a principally algorithmic problem wouldn't/shouldn't naturally lead to define/create your own data types (anything already available in the stdlib should be enough)... something more real world might've been more appropriate.

I've been given this task by people using Scala professionally. Conversely, I never used Scala at work, so I'd expect that my code might be unidiomatic.

Do you have any other idea on how to improve, even by rewriting it completely with a different algorithm? One of the goals was efficiency, but performance shouldn't be a concern. What I'd like to see this code improved upon is in its readability, cleanliness and general good design.

Answer 1

EDIT First attempt at answering was not optimal, so you should read to the end EDIT

Well, it is a bit hard to say, what the people who tasked you with that wanted to see, but

1. imho that is a lot of code for a relatively simple problem. So, I guess the maintainability requirement might be the culprit.

2. Also, what is pretty important when doing scala professionally is a solid knowledge of scala collections, their API and maybe how to work with Iterators. E.g a palindrome check is easily done by string == string.reverse

3. When working with tuples, accessing values with ._1 ._2 and so on is horrible to read. I would almost always prefer to have the values extracted to local vals with meaningful names.

4. Premature optimization is the root of all evil!

That said, here is how I would do something like this:

EDIT BEGIN

BAD, DON'T COPY, MUCH LESS PASTE!

EDIT END

@inline
private[this] def isPalindrome(inp: String): Boolean = inp == inp.reverse

def palindromes(inp: String) =  {
  (inp.length until 2 by -1).foldLeft(IndexedSeq.empty[String]) { 
    case (pals, palindromeLength) =>
      pals ++ inp.sliding(palindromeLength, 1).collect {
        case subString if isPalindrome(subString) && !pals.exists(_.contains(subString)) =>
          // only retain substring if it is a palindrome 
          // and not a substring of an already found palindrome
          subString
      }.toSeq
  }
}

I admit the foldLeft is not exactly easy to read, too, but it is quickly clarified in a review. Otherwise, for a first implementation it should be efficient enough.

There are probably far more string allocations, but unless reducing string allocations is not explicitly required, this code is, well, shorter and more maintainable.

Update/Edit

I'm sorry if I'm annoying anyone, but this didn't leave me alone because something just didn't feel right.

Probably, because my answer is incomplete at best. So here is what got me thinking:

My example code above is in fact quite inefficient as it does a lot of unnecessary work. It searches for palindromes by size starting at 2 ending at input string length. So the lookups for all sizes from longest palindrome length to input string length are just burning cpu time.

The original code is much more efficient. However, there is still one advantage to my code: During a review process (which should be pretty common by now) the flaw is obvious enough that there is a good chance a reviewer will find it. So (imo) it is no crime to write bad code as long as you write it readable.

Thus, from what you wrote in your comments I guess that this

val palindromeIndexes = inp.zipWithIndex
  .groupBy(_._1).values // group by char
  .map(_.map(_._2)).filter(_.length > 1) // retain sequence of indexes
  .flatMap(_.combinations(2).map(vecToPair))
  .filter(isPalindrome).toSeq
  .sortBy{case (start, end)=> -(end+1-start)}

is what got the bad evaluation, because one has to burn a lot of sugar (and more importantly time) to wrap ones brain around what you are doing here (well, at least I had to, and for my first attempt at an answer I kinda didn't). Now I even did some mini benches.

Now, here are some additional review points on your code:

1. The least you could do to improve readability of the code is to extract each statement to a local val with a meaningful name.
2. Concerning efficiency, you are instantiating a lot of Vectors, that should be avoided (for input string lengths around 5000 you quickly run into an OOME).
3. I already said something about the tuples, but there is another point to the; Tuples are case classes, too. Using simple classes to wrap the indices might be slightly cheaper.
4. Your printlns cut of the last character of each palindrome.

And I cannot help myself, I have to offer an alternative solution, that, in my opinion, might have served you better.

/** Extends strings with functions to lookup all palindromes. */
implicit class PalindromeLookup(in: String) {
  private[this] val stringLength = in.length

  class Palindrome(val start: Int, val end: Int) {
    val length = end - start

    override def toString = s"Palindrome(${in.substring(start, end)}) from $start to $end, length = $length"
  }

  object Palindrome {
    // doesn't cost much and makes the code look better
    def apply(start: Int, end: Int): Palindrome = new Palindrome(start, end)
  }

  private[this] def pivots = {
    @tailrec
    def findPalindromePivots(index: Int, result: List[Palindrome]): List[Palindrome] = {
      if (index >= stringLength - 1) {
        result
      } else {
        val char = in(index)
        val nextIndex = index + 1
        val nextNextIndex = index + 2

        // TODO: the 'oo' in 'fooof' would be ingored. 
        // (who needs palindromes of length 2 that are sub-palindromes of longer palindromes?) ;)
        if (nextNextIndex < stringLength && char == in(nextNextIndex)) {
          findPalindromePivots(nextIndex, Palindrome(index, nextNextIndex + 1) :: result)
        } else if (char == in(nextIndex)) {
          findPalindromePivots(nextIndex, Palindrome(index, nextIndex + 1) :: result)
        } else {
          findPalindromePivots(nextIndex, result)
        }
      }
    }

    findPalindromePivots(0, Nil)
  }

  @tailrec
  private[this] def expand(palindrome: Palindrome): Palindrome = {
    val newStart = palindrome.start - 1
    val newEnd = palindrome.end + 1

    if (newStart < 0 || newEnd > stringLength) {
      palindrome
    } else if (in(newStart) == in(newEnd - 1)) {
      expand(Palindrome(newStart, newEnd))
    } else {
      palindrome
    }
  }

  /**
   * Finds all palindromes in this classes input string.
   *
   * The algorithm iterates through the string once to find all palindrome pivots
   * and then iterates through the pivots and expands them to their full size.
   */
  def palindromes = pivots.map(expand)
}

Using the implicit class you can get the longest palindromes of any input string by e.g.

  inputString.palindromes.sortBy(p => -p.length)

Hope this is more helpful.

Answer 2

As already mentioned, your code is not easy to read. Also, your algorithm probably isn't nowhere near \$ O \left( n^3 \right) \$ in practice because of groupBy, combinations, and many calls to exists. All those introduce large overhead.

Here's my attempt (with a bug in findLongestPalindromeAtPos, but the general idea should be clear and I'll try to fix it in my free time):

object BruteForce {

  def apply(text: String): Seq[(Int, Int)] = {
    val all = findAllPalindromes(text)
    removeContainedPalindromes(all).sortBy(palindromeLength)
  }

  private def findAllPalindromes(text: String) = {
    for {
      i ← 0.5f until text.length by 0.5f
      (from, to) ← findLongestPalindromeAtPos(text, i)
    } yield (from, to)
  }

  private def removeContainedPalindromes(all: Seq[(Int, Int)]) = {
    var currentMaxTo = 0
    for {
      (from, to) ← all.sortBy(palindromeLength).sortBy(palindromePosition)
      if to > currentMaxTo
      _ = currentMaxTo = to
    } yield (from, to)
  }

  private def findLongestPalindromeAtPos(text: String, pos: Float): Option[(Int, Int)] = {
    var from = math.floor(pos - 0.5f).toInt
    var to = math.round(pos + 0.5f)
    while (palindromeProperty(text, from - 1, to + 1)) {
      from -= 1
      to += 1
    }
    if (palindromeProperty(text, from, to)) Some((from, to)) else None
  }

  private def palindromeProperty(text: String, from: Int, to: Int) =
    from >= 0 && to < text.length && to - from > 1 && text(from) == text(to)

  private def palindromeLength(range: (Int, Int)) = {
    val (start, end) = range
    start - end
  }

  private def palindromePosition(range: (Int, Int)) = {
    val (start, _) = range
    start
  }

}