7
\$\begingroup\$

I wrote this palindrome extractor. And even though it works, and I can solve the challenge with it, it feels very Java-like. I was wondering what adjustments I could make in order for it to be more functional.

import collection.mutable._

object Level1 {
    def palindrome(input:String) = input.reverse == input

    def extractPalindromes(input:String) = 
    {
        var counter = 0
        val palindromes = new ListBuffer[String]()
        while(counter < input.length)
        {
            var localCounter = 2
            while((counter + localCounter) < input.length)
            {
                //println("counter:"+counter+" localCounter:"+localCounter)
                val tempString = input.substring(counter, input.length - localCounter)
                if(palindrome(tempString)) palindromes += tempString
                localCounter += 1
            }       
            counter += 1
        }
        palindromes
    }

    def main(args:Array[String]) = {
        val input = "I like racecars that go fast"
        extractPalindromes(input).filter(_.length > 4).foreach(println)
    }
}
\$\endgroup\$
12
\$\begingroup\$

It can be as simple as:

scala> val str =  "I like racecars that go fast"
str: java.lang.String = I like racecars that go fast

scala> for { i <- 2 to str.size; s <- str.sliding(i) if s == s.reverse} yield s
res5: scala.collection.immutable.IndexedSeq[String] = Vector(cec, aceca, racecar)
\$\endgroup\$
  • 1
    \$\begingroup\$ Oh, and by the way: .maxBy(_.size) will give you the longest of those... \$\endgroup\$ – Nicolas Payette Oct 7 '11 at 22:38
  • \$\begingroup\$ Can you please explain why the for loop starts from 2, not from 0. I tried in REPL but got the error of java.lang.IllegalArgumentException: requirement failed: size=0 and step=1, but both must be positive And If I start the for loop from 1. It gives the result ` Vector(b, a, n, a, n, a, s, ana, nan, ana, anana)`. \$\endgroup\$ – royki Jan 6 '18 at 14:28
  • 1
    \$\begingroup\$ We loop through possible sizes of palindromic sub-expressions. Two is arguably the smallest size that makes sense. When you tried with one, it gave you back single letters. Can you really say that those are palindromes? And as for why zero gives you an error: what should str.sliding(0) give you back? Iterating through groups of zero items doesn't make sense, hence the illegal argument exception. \$\endgroup\$ – Nicolas Payette Jan 6 '18 at 15:46
3
\$\begingroup\$

Improvement on @Zwirb's answer:

If you are only seeking for palindrome of maximum length, it's better to try longest slides first. Laziness (triggered by view) will decrease complexity as well.

(for { i <- (str.size to 2 by -1).view ; s <- str.sliding(i) if s == s.reverse} yield s) headOption
\$\endgroup\$
2
\$\begingroup\$

Since we've got a working implementation, we may now optimise it. Each steps will be shown, to mimic a code review session (albeit a schizophrenic one).

Phase 1 : Limit objects creation.

reverse creates new string. But reversing a view only creates a new (lightweight) view. Indeed, replacing str.sliding by str.view.sliding halve process time. For 6 keystrokes, it's not too bad.

Phase 2 : Refine the algorithm.

Actually it should be phase 0, but you never know when ideas pop up.
Each palindrome contains matryoshka-nested palindromes. This means all n sized ones can be detected from n-2 sized, just by checking 2 new chars at boundaries.

We introduce an helper

def collectPalindrome(str: String, from: Int, to: Int): List[String] =
  if (str(from) == str(to)) {
    str.slice(from, to+1) :: (if (from > 0 && to < str.size - 1) collectPalindrome(str, from-1, to+1) else Nil)
} else Nil

No superfluous object creation is involved. So it's a double win ! Since collected sizes increase by 2, we need 2 passes :

def extractPalindromes (str: String) : List[String] =
{
  val evenSized: List[String] = ((for (i <- (0 to str.size - 2)) yield collectPalindrome(str,i,i+1)) flatten).toList
  val oddSized:  List[String] = ((for (i <- (0 to str.size - 3)) yield collectPalindrome(str,i,i+2)) flatten).toList
  evenSized ++ oddSized
}

Result for genlin input :

Reference (Zwirb)    : 233 s
Stopping at longest  : 232 s  (nb : only extract 1 palindrome)
                        So benchmarking proves my claim wrong.          
Idem + .view.        : 120 s  (nb : only extract 1 palindrome)
New algorithm        :   0.006 s

Phase 3 : Refactor.

So we've got a fast, memory friendly and still readable implementation. But we can always improve.

  • give the helper a more descriptive name : collectIncreasingPalindromes
  • move bound checking at top. The helper became robuster and more readable.
  • hide this helper
  • DRY
  • document
  • finally I prefer to map. Then map + flatten = flatMap

Result :

def extractPalindromes (str: String): List[String] = {

  //@brief Collect nested palindromes increasing by 1 char at each end.
  def collectIncreasing(from: Int, until: Int): List[String] =
    if (  from < 0 || until > str.size     //Out of bounds
       || str(from) != str(until-1)  ) Nil
    else str.slice(from, until) :: collectIncreasing(from-1, until+1)

  //@brief Start to collect from given size, for each position
  def collect (n: Int) = (0 to str.size - n) flatMap 
                           (i => collectIncreasing (i, i+n))

  (collect (2) ++ collect (3)).toList  // Even sized then odd sized palindromes
}

Phase 4 : Parallelize.

Thanks to functional approach, it should be just a matter of switching to parallel collections.

Phase 5 : Challenge a friend

\$\endgroup\$
1
\$\begingroup\$

The solutions given are simple but have quadratic complexity. I tried to improve upon it, while keeping it strictly functional.

The solution I came up with is huge, though some of that resulted from breaking it up into smaller pieces for readability. While it is much faster, I'm not sure if that's due to an improved complexity, or just better heuristics detecting when no more palindromes are possible.

I feel like it could be improved, perhaps with some Scalaz tricks. I see a couple places where I could remove some code by using an Scalaz abstraction, but not enough to be worth. On the other hand, I'm not particularly familiar with Scalaz.

So, here it is:

def palindromes(input: String): Set[String] = {                                                                 
  type PalPointers = (Set[Int], Set[Int])                                                                       
  type Candidates = Map[String, PalPointers]                                                                    

  def increment = (_: Int) + 1                                                                                  
  def decrement = (_: Int) - 1                                                                                  
  def withinBounds = input.indices contains (_: Int)                                                            
  def filterPositions(forwardSet: Set[Int], reverseSet: Set[Int]): PalPointers = {                              
    val hasReverse = (forward: Int) => reverseSet exists (forward <=)                                           
    val hasForward = (reverse: Int) => forwardSet exists (reverse >=)                                           
    (forwardSet filter hasReverse, reverseSet filter hasForward)                                                
  }                                                                                                             
  def hasViablePositions = (_: PalPointers) match {                                                             
    case (forwardSet, reverseSet) => forwardSet.nonEmpty && reverseSet.nonEmpty                                 
  }                                                                                                             

  def getSolutions(candidates: Candidates): Set[String] = {                                                     
    def getEven(candidate: String) = {                                                                          
      val (forwardSet, reverseSet) = candidates(candidate)                                                      
      if ((forwardSet & (reverseSet map decrement)).nonEmpty) Set(candidate + candidate.reverse)                
      else Set.empty                                                                                            
    }                                                                                                           

    def getOdd(candidate: String) = {                                                                           
      val (forwardSet, reverseSet) = candidates(candidate)                                                      
      if ((forwardSet & reverseSet).nonEmpty) Set(candidate + candidate.init.reverse)                           
      else Set.empty                                                                                            
    }                                                                                                           

    for {                                                                                                       
      candidate  <- candidates.keySet                                                                           
      palindrome <- getEven(candidate) ++ getOdd(candidate)                                                     
    } yield palindrome                                                                                          
  }       

  def findPal(currentSolution: Set[String], currentCandidates: Candidates) : Set[String] = {                    
    val newCandidates = for {                                                                                   
      (candidate, (leftToRightSet, rightToLeftSet)) <- currentCandidates                                        
      nextCh  <- leftToRightSet map increment filter withinBounds map input                                     
      isNextCh            = (i: Int) => withinBounds(i) && input(i) == nextCh                                   
      forwardSetCandidate = leftToRightSet map increment filter isNextCh                                        
      reverseSetCandidate = rightToLeftSet map decrement filter isNextCh                                        
      palPointers         = filterPositions(forwardSetCandidate, reverseSetCandidate)                           
      if hasViablePositions(palPointers)                                                                        
    } yield (candidate + nextCh, palPointers)                                                                   

    if (newCandidates.isEmpty) currentSolution                                                                  
    else findPal(currentSolution ++ getSolutions(newCandidates), newCandidates)                                 
  }                                                                                                             

  def setup(charPointers: List[(Char, Int)], candidates: Candidates): Candidates = charPointers match {         
    case (ch, pos) :: tail =>                                                                                   
      val candidate = ch.toString                                                                               
      val (forwardSet, reverseSet) = (candidates getOrElse (candidate, (Set.empty, Set.empty): PalPointers))    
      setup(tail, candidates.updated(candidate, (forwardSet + pos, reverseSet + pos)))                          
    case Nil =>                                                                                                 
      candidates map {                                                                                          
        case (key, (forwardSet, reverseSet)) => key -> filterPositions(forwardSet, reverseSet)                  
      } filter {                                                                                                
        case (_, positions) => hasViablePositions(positions)                                                    
      }                                                                                                         
  }                                                                                                             

  val initialCandidates = setup(input.zipWithIndex.toList, Map.empty)                                           
  val initialSolutions = getSolutions(initialCandidates)                                                        
  findPal(initialSolutions filter (_.length > 1), initialCandidates)                                            
}

I wanted to know how efficient all that set manipulation really was, so I benchmarked it all. My solution is two order of magnitude faster than the one in the question, and three than the accepted solution for the greplin input. Since the big-Oh is different, this would change depending on characteristics of the input and input size.

\$\endgroup\$
1
\$\begingroup\$

Here's a general idea about how I'd probably approach the problem:

def extractPalindromes(input:String) = 
{
    var minLength = 4;
    val palindromes = new ListBuffer[String]()
    if (palindrome(input)) palindromes += input
    if (input.length > minLength) {
        palindromes += extractPalindromes(input.substring(1, input.length-1))
        palindromes += extractPalindromes(input.substring(0, input.length-1))
    }
    palindromes
}

Be warned, however, that I don't normally write Scala, so I've undoubtedly gotten at least a few details wrong. I'm particularly uncertain about the part that tries to concatenate two ListBuffer's together using += (and minLength should really be a constant or a parameter). The general notion of how it works should be about right though:

if the current input is a palindrome, add it to the list
find palindromes with the first character removed
find palindromes with the last character removed
put all those results together and return them

Note that rather than generate all the palindromes, then filter out any that are too short, I've written this to only generate those of at least the specified minimum length (4, in this case). As noted above, minLength should really be a constant or a parameter, not a var, but that should be a fairly minor adjustment.

\$\endgroup\$
  • \$\begingroup\$ To concatenate two ListBuffers, use ++= instead of +=. \$\endgroup\$ – Nicolas Payette Oct 8 '11 at 3:42
  • \$\begingroup\$ Since your function is recursive, the compiler will ask you for its return type. \$\endgroup\$ – Nicolas Payette Oct 8 '11 at 3:43
  • \$\begingroup\$ Your function will return palindromes of length minLength - 1 since the call to input.substring(1, input.length-1) shortens the string by 2. \$\endgroup\$ – Nicolas Payette Oct 8 '11 at 3:45
  • \$\begingroup\$ Finally, the way you scan the string, duplicate palindromes will be generated since both paths of the recursion will cover part of the same ground. \$\endgroup\$ – Nicolas Payette Oct 8 '11 at 3:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.