Combine input strings to generate all possible palindromes

Palindromes.scala

/** Given a list of (unique) strings, find all combinations (containing each of the strings at
  * most once), that, if concatenated in that particular order, make up a palindrome string
  * (ignoring case).  Combinations, containing the same strings in different order are considered
  * different, as well as those, that contain different strings, but produce the same palindrome.
  *
  * Single character and empty strings are trivial palindromes, and not treated specially
  * (including an empty string into inputs, "explodes" the number of combinations, because you
  * can insert an empty string anywhere in a valid sequence, and it will still be valid).
  *
  * See [[Palindromes.apply]] for the main entry point.
  *
  * This implementation works by assigning each of the input strings in turn to the start of the
  * possible palindromic sequence, and then trying find another input string, that can be used as
  * the end of sequence by "cancelling" (some of) the chars fixed on the left. If all characters
  * have been matched, a palindrome is built. If some of the characters remaing "dangling" on
  * either side of the sequence, the process continues recursively to look for additional strings
  * in the input that could cancel those.
  *
  * The complexity of this highly depends on the number of "candidate" strings, available at each
  * iteration. The worst case can be built (I think), where the complexity becomes n! (if number
  * of candidates is proportional to the size of inputs). Under the "real life" conditions
  * (with an available and reasonably low upper boundary for the number of candidates), the
  * performance should remain linear (after the process of compiling list of candidates -
  * [[Palindromes.complements()]]  - is trivially optimized to use a Trie instead of direct scan).
  *
  */
object Palindromes {

  /** Represents an partially built palindrome: two ordered lists of words on each side of the
    * "maybe palindrome", with possibly a "dangle" string - innermost sequence of characters,
    * that has not been matched.
    *
    * For example: ("foo", "barbaz") on the left, and ("bra", "boof") on the right, is a
    * candidate for a palindrome strign, starting with "foobarbaz..." with "az" as a "dangle on
    * the left", meaning that "az" characters included into the left list, are not yet matched by
    * a word on the right - so, to continue building this palindrome, one must find a word,
    * ending with "za" (or just "a" by itself) to be prepended to the list on the right. If the
    * next word is shorter then the "dangle" (just "a" in this case), then "dangle" is shortened
    * by that much (and stays on the right) after the word is appended, if the next word is longer,
    * then the prefix becomes the new dangle (on the left now). See [[append]] and [[consume]]
    * for implementation of this logic.
    *
    * The [[Candidate]] is a complete palindrome when the dangle becomes empty, or if it itself
    * is a palindrome.
    *
    * @param dangle - the innermost sequence of characters in one of the owrd lists, that is not
    *               matched by corresponding characters on opposite side
    * @param dangleOnLeft - whether the unmatched characters represented by [[dangle]] are found
    *                     in the [[left]] list (if true) or in the [[right]] one.
    * @param left - the list of words that, concatenated, make up the beginning substring of this
    *             (maybe) palindrome. Note that this list is kept in _reversed order_ for
    *             performance reasons (prepending is faster than appending).
    *             For instance, `List("ar", "ob", "fo")` represents a string, starting with
    *             "foobar..."
    * @param right - the list of words that, concatenated, make of the ending
    *              substring of this (maybe) palindrome.
    *              For instance, `List("ra", "boof")` represents a string, ending with "...raboof".
    *              In a valid [[Candidate]] instance the [[left]] and [[right]] lists are
    *              balanced, except, maybe, for the [[dangle]], e.g.:
    *              {{{
    *                   left = List("ob", "fo")
    *                   right = List("ra", "boof")
    *                   dangle = "ar"
    *                   dangleOnLeft = false
    *              }}}
    *              This represents a palindrome: "foob[ar]...[ra]boof"
    */
  case class Candidate(
    dangle: String = "",
    dangleOnLeft: Boolean = false,
    left: List[String] = Nil,
    right: List[String] = Nil
  ) {

    /** Indicates, whether this [[Candidate]] represents a complete palindrome: there is at least
      * one word included into the string (empty strings are not considered palindromes), and
      * [[dangle]] is either empty or itself a palindrome.
      */
    lazy val isPalindrome = dangle == dangle.reverse &&
      (left.nonEmpty || right .nonEmpty)

    /** If this [{Candidate]] is a complete palindrome (see [[isPalindrome]]), this contains a
      * complete list of words, used to compose in in the correct order (so that
      * {{{candidate.words.map(_.mkString)}}} is the (`Option` of) resulting palindrome string),
      * otherwise, `None` value indicates that this palindrome is not completed.
      */
    lazy val words = if(isPalindrome) Some(left.reverse ++ right) else None

    /** Applies the incoming (matching) string to the current [[dangle]], and returns the
      * characters, that are still unmatched (new value for [[dangle]], after `str` is applied to
      * the corresponding word list.
      *
      * If input is _shorter_ than the dangle, the latter is truncated by the former's length, by
      * stripping the corresponding number of characters from either the end (when dangle is on the
      * left) or the beginning (dangle on right) of the current dangle.
      *
      * Conversely, if input is _longer_ than the dangle, then the `dangle.length` characters are
      * stripped from either the end (dangle on left) or the beginning (dangle on right) of the
      * input string, and the remaining characters (lowercased) are returned as the new dangle.
      *
      * Note, that in either case, the characters being stripped are assumed to be common between
      * [[dangle]] and the input string, see [[complements]] for the description of matching logic.
      * If `str` does not satisfy this requirement, the returned string is meaningless.
      *
      * @param str - incoming string to be consumed, matching the current [[dangle]] either on
      *            the left or on the right as per [[complements]].
      * @return - the sequence of characters, that are still unmatched as described above.
      */
    def consume(str: String) = if(str.length <= dangle.length) {
      if(dangleOnLeft)
        dangle.drop(str.length)
      else
        dangle.take(dangle.length - str.length)
    } else {
      val s = str.toLowerCase
      if(dangleOnLeft) s.take(str.length - dangle.length) else s.drop(dangle.length)
    }

    /** Creates a new [[Candidate]] instance by adding the given string to the word list, and
      * consuming the corresponding portion of the dangle.
      *
      * The incoming word is added to the side opposite to the dangle:
      *  - if [[dangleOnLeft]] is true, the [[right]] word list is prepended with the new word, and
      *  _suffix_ of the [[dangle]], matching the incoming word is stripped. If the word is longer
      *  than the [[dangle]], the unmatched _suffix_ becomes the new dangle (which is now on the
      *  right).
      *  - if [[dangle]] is on right, then [[left]] word list is prepended (because it is kept in
      *  reverse order) with the word, and the matching _prefix_ of the [[dangle]] is stripped. If
      *  the word is longer then the dangle, the unmatched _prefix_ becomes the new dangle (which
      *  is now on left).
      *
      *  *NOTE* that the match between `str` and [[dangle]] is _assumed_ to have been established
      *  according to the [[complements]] logic, and _is not verified_. If this does not hold, the
      *  returned [[Candidate]] instance will be invalid (meaning that it may not be
      *  representative of any possible palindrome, and [[isPalindrome]] value may also be wrong).
      *
      * @see [[consume]]
      * @see [[complements]]
      * @param str - input word to consume the (part of the) current dangle, and be applied to
      *            the current word list
      * @return new [[Candidate]] instance, with word lists and [[dangle]] reflecting the added word
      */
    def append(str: String) = copy(
      consume(str),
      dangleOnLeft == (str.length < dangle.length),
      if(dangleOnLeft) left else str :: left,
      if(dangleOnLeft) str :: right else right
    )

  }

  /** Finds all strings among `inputs` that can complete a palindrome, that either starts or ends
    * with the specified substring.
    *
    * The idea is that if a palindrome _ends_ with the input string, then it must _start_
    * with one of its suffixes (reversed): e.g.
    * foobar --> "rabooffoobar", "rab[...foo]bar", "raboof[baz...]foobar" etc.
    *
    * Conversely, if a palindrome _starts_ with the given prefix, then it must _end_ with one of
    * prefixes (again, reversed):
    * raboof -> "foobarraboof", "foo[...rab]oof", "foobar[baz...]raboof" etc.
    *
    * This function will scan `inputs` list, and return all strings that match the criteria
    * described above:
    *  - when `left` is true (looking for palindrome _endings_), find all strings, that either
    *  end with a substring matching the entire reversed input, or match a suffix of the reversed
    *  input completely
    *  - otherwise (looking for _beginnings_), find all strings, that either start with the entire
    *  reversed input, or are entirely included into it as a prefix
    *
    *  For example, for input string "foobar", either "zabraboof" or "boof" would match,
    *  but neither "Xoof" nor raboofX" would when `left` is true.
    *  For the same input, "raboofbaz" or "rabo" would match when `left` is false, but raboofX or
    *  Xraboof will not.
    *
    *  All matching is case insensitive.
    *
    * This is a linear operation. It can trivially be optimized with a prefix tree, I just haven't
    * gotten around to spelling it out.
    *
    * @param orig - original string to find "suffixes" for
    * @param inputs - list of candidates to search
    * @param left - true if we are looking for _endings_ of a palindrome that starts with `orig`,
    *             false to return the _beginnings_ of palindromge, that _ends_ with `orig`.
    * @return - list of strings from `inputs`, matching the `orig` string as described above.
    */
  def complements(
    orig: String,
    inputs: Seq[String],
    left: Boolean
  ): List[String] = {
    val rev = orig.reverse.toLowerCase()
    val test: (String, String) => Boolean  = if(left) _ endsWith _ else _ startsWith _
    inputs
      .iterator
      .filter { in =>
        val lc = in.toLowerCase()
        test(lc, rev) || test(rev, lc)
      }.toList
  }

  /** Given a list of strings, finds all combinations of them that are palindromes.
    *
    * @param inputs - strings to consider
    * @param candidate - the current partial (maybe) palindrome being built recursively. Use
    *                  default for top-level invocation.
    * @param exclude - filter to exclude from consideration (each string is used at most once in
    *                each palindrome, so, we dso not want to consider again those strings, that
    *                are already included into the `candidate`.
    * @return - A list of all palindromes that can be created by combining the `input` strings.
    *         Each element is a list of strings from `input` that, if concatenated in this
    *         sequence, will create a palindrome.
    */
  def apply(
    inputs: Seq[String],
    candidate: Candidate = Candidate(),
    exclude: String => Boolean = _ => false
  ): Seq[Seq[String]] =  {
    val available = inputs.filterNot(exclude)
    candidate.words.toList :::
    complements(candidate.dangle, available, candidate.dangleOnLeft)
      .flatMap { s =>
        apply(available, candidate.append(s), _ == s)
      }
  }

  def main(argv: Array[String]): Unit = {
    Palindromes(argv.toList)
      .foreach(println)
  }
}

PalindromesSpec.scala

import org.scalatest.{FunSpec, Matchers}
import org.scalatest.mockito.MockitoSugar

class PalindromesSpec extends FunSpec with Matchers with MockitoSugar {

  describe("Palindromes") {

    it("solves the original problem") {
      Palindromes(Seq("Gimli", "Fili", "Ilif", "Ilmig", "Mark")) shouldBe Seq(
        Seq("Gimli", "Ilmig"),
        Seq("Gimli", "Fili", "Ilif", "Ilmig"),
        Seq("Gimli", "Ilif", "Fili", "Ilmig"),
        Seq("Fili", "Ilif"),
        Seq("Fili", "Gimli", "Ilmig", "Ilif"),
        Seq("Fili", "Ilmig", "Gimli", "Ilif"),
        Seq("Ilif", "Fili"),
        Seq("Ilif", "Gimli", "Ilmig", "Fili"),
        Seq("Ilif", "Ilmig", "Gimli", "Fili"),
        Seq("Ilmig", "Gimli"),
        Seq("Ilmig", "Fili", "Ilif", "Gimli"),
        Seq("Ilmig", "Ilif", "Fili", "Gimli")
      )
    }

    it("returns nothing when there is no palindrome") {
      Palindromes(Seq("foo", "bar", "baz")) shouldBe Nil
    }

    it("finds a palindrom with simple pair") {
      Palindromes(Seq("foo", "oof")) shouldBe Seq(Seq("foo", "oof"), Seq("oof", "foo"))
    }

    it("finds a palindrom with common middle") {
      Palindromes(Seq("foo", "of")) shouldBe Seq(Seq("foo", "of"))
    }

    it("Recognizes single words as palindromes") {
      Palindromes(Seq("mom", "dad", "x")) shouldBe Seq(Seq("mom"), Seq("dad"), Seq("x"))
    }

    it("Inserts palindromes in the middle"){
      Palindromes(Seq("mom", "dad", "xy", "yx")) shouldBe Seq(
        Seq("mom"),
        Seq("dad"),
        Seq("xy", "yx"),
        Seq("xy", "mom", "yx"),
        Seq("xy", "dad", "yx"),
        Seq("yx", "xy"),
        Seq("yx", "mom", "xy"),
        Seq("yx", "dad", "xy")
      )
    }

    it("Handles unbalanced lists") {
      Palindromes(Seq("foobar", "zab", "rab", "oo", "f")) shouldBe Seq(
        Seq("foobar", "rab", "oo", "f"),
        Seq("rab", "oo", "foobar"),
        Seq("rab", "oo", "f", "foobar"),
        Seq("oo"),
        Seq("f")
      )
    }

    it("Combines multiple words in the middle of a palindrome") {
      Palindromes(Seq("foob", "rabo", "ar", "of")) shouldBe Seq(
        Seq("foob", "ar", "rabo", "of"),
        Seq("rabo", "of", "foob", "ar")
      )
    }

    it("Processes left dangle correctly") {
      Palindromes(Seq("foobar", "unrelated", "ra", "baz", "bo", "of")) shouldBe Seq(
        Seq("foobar", "ra", "bo", "of"),
        Seq("ra", "bo", "of", "foobar")
      )
    }

    it("Processes alternating dangle") {
      Palindromes(Seq("fo", "oof", "obar", "zabrab", "baz")) shouldBe Seq(
        Seq("fo", "oof"),
        Seq("fo", "obar", "baz", "zabrab", "oof"),
        Seq("zabrab", "obar", "baz"),
        Seq("zabrab", "oof", "fo", "obar", "baz")
      )
    }

    it("Processes right dangle") {
      Palindromes(Seq("fo", "abraboof", "ob", "ar", "baz")) shouldBe Seq(
        Seq("fo", "ob", "ar", "baz", "abraboof")
      )
    }

    it("does not dedupe") {
      Palindromes(Seq("foo", "of", "foo")) shouldBe Seq(
        Seq("foo", "of"),
        Seq("foo", "of")
      )
    }

    it("considers empty strings palindromes") {
      Palindromes(Seq("", "foo", "of")) shouldBe Seq(
        Seq(""),
        Seq("", "foo", "of"),
        Seq("foo", "of", ""),
        Seq("foo", "of"),
        Seq("foo", "", "of")
      )
    }
  }
}