Algorithm Challenge

[Smac89]

I promise this is not an assignment, I found the question on a site and I am curious to see what people on this site come up with.

Given any string, add the least amount of characters possible to make it a palindrome.

Go crazy!

[Dy7SLyTq]

hmmm... thats a good one, but correct me if im wrong it doesnt seem too difficult

edit: does it have to be a real word?

[Smac89]

yes, I guess I should have given example:

ex input/output:

in: jeej
out: jeej

in:jeefgeej
out:jeegfgeej

in:a
out:a

in:ppalind
out:dnilappalind

[Catfish4]

I think some kind of similarity finder is needed to choose where the possible "middle" of the palindrome may be. After you locate the middle, you add the missing characters.

correct me if im wrong it doesnt seem too difficult

I won't even dare open the editor until I see more members post better ideas.

[S6k9GNh0]

This could be done algorithmically off the top of my head.

1. Make the string a palindrome. Easiest way to do this is to print a string the string in reverse order from the front or the back of the string. This is also the largest way to make the word a palindrome.

2. Take away characters in pairs from the middle towards the ends. If it doesn't take away the original word and it doesn't remove it from being a palindrome, then at the end, you'll have a reduced palindrome.

So...

jeej
jeejjeej
jeeeej
jeej

You're left with the original characters and smallest palindrome.

ppalind
ppalinddnilapp
palinddnilap

I haven't tested this and its 3AM... so use at your own risk.

[firedraco]

jeefgeej
so
jeefgeejjeegfeej

I don't think you can get the below from that by removing center pairs...or any pairs for that matter.
jeegfgeej

I don't think your method works for anything other then strings that are already palindromes or have cannot be made into them besides adding a copy to end basically.

[rapidcoder]

This is very easy.

1. Find the largest suffix that is a palindrome.
2. Append the reversed prefix (left after cutting off the suffix found in step 1.) to the end of the word.

def isPalindrome(s: String) = s.reverse == s

def makePalindrome(s: String) = 
  s + s.take((0 to s.length).find(i => isPalindrome(s.substring(i))).get).reverse 

scala> makePalindrome("")
res13: String = ""

scala> makePalindrome("a")
res14: String = a

scala> makePalindrome("ab")
res15: String = aba

scala> makePalindrome("abc")
res16: String = abcba

scala> makePalindrome("abcd")
res17: String = abcdcba

scala> makePalindrome("aaa")
res18: String = aaa

scala> makePalindrome("aba")
res19: String = aba

scala> makePalindrome("abcb")
res20: String = abcba

[keskiverto]

makePalindrome("noob")=="nooboon", len==7
#expected: len==6, "nboobn" or "bnoonb"

Dot-plots are fun, but would they help?

 jeefj
j.   .
e ..
e ..
f   .
j.   .

Insert 'f' =>

 jfeefj
j.    .
f .  .
e  ..
e  ..
f .  .
j.    .

[rapidcoder]

All right, the original challenge stated **add** and I misread it as "append". My code works only for appending. If you can prepend, insert and append, then this is a whole different story.

[devonrevenge]

I love a challenge me.

[keskiverto]

An idea following from the dot-plot: Needleman-Wunsch algorithm, but this time an alignment of string with its reverse. Then fill the gaps.

[abhishekm71]

Same question presently active on stackoverflow:

http://stackoverflow.com/questions/18732020/add-the-least-amount-of-characters-to-make-a-palindrome

[abhishekm71]

One idea perhaps can be:

We know that the upperbound of the answer is the length of string itself.

Say the original string is abcdeba

We check character-wise ( S[i] == S[length-i-1] ), when we get a false condition ('c' != 'e'), then we have two options:
-> add c to where e was, or add e to where c was.
We will have to evaluate both options and maybe do this recursively and pick out method with least number of character additions.

[Duthomhas]

The OP said to "add". Not "change". In the case of "abcdeba", you would have to add two characters. Order doesn't matter so long as the palindrome holds:

abcedecba
abecdceba


[edit] BTW: "ppaba"

[abhishekm71]

Yes I meant to insert only, not replace. Sorry it wasn't clear.

EDIT: for ppaba,

Iteration 1: appaba or ppabap
2: abppaba or appabpa or papabap or ppabapp

ppabapp is a paindrome so we stop. Answer is 2.

However, the memory required for this algorithm increases exponentially as the length of string increases.

EDIT 2: The algorithm may be improved if instead of just one letter, we check for the next one and (the next one if needed) as well to rule out the other options.

[rapidcoder]

Funny all the answers on StackOverflow assume the goal is to append only, and insertions are not allowed. So they won't handle the "noob" case properly.

[rapidcoder]

Ok, so here is the code:

def makePalindrome(str: String): String = {

  def paretoMin(points: Iterable[(Int, Int)]): List[(Int, Int)] = {
    val sorted = points.toSeq.sortBy(identity)
    (List.empty[(Int, Int)] /: sorted) { (result, e) =>
      if (result.isEmpty || e._2 <= result.head._2)
        e :: result
      else
        result
    }
  }

  /** Find all pairs directly nested within a given pair.
    * For performance reasons tries to not include suboptimal pairs (pairs nested in any of the pairs also in the result)
    * although it wouldn't break anything as prune takes care of this. */
  def pairs(left: Int, right: Int): Iterable[(Int, Int)] = {
    val builder = List.newBuilder[(Int, Int)]
    var rightMax = str.length
    for (i <- left until (str.length - right)) {
      rightMax = math.min(str.length - left, rightMax)
      val subPairs =
        for (j <- right until rightMax if str(i) == str(str.length - j - 1)) yield (i, j)

      subPairs.headOption match {
        case Some((a, b)) => rightMax = b; builder += ((a, b))
        case None =>
      }
    }

    builder.result()
  }

  /** Builds sequences of size n+1 from sequence of size n */
  def extend(path: List[(Int, Int)]): Iterable[List[(Int, Int)]] =
    for (p <- pairs(path.head._1 + 1, path.head._2 + 1)) yield p :: path

  /** Whether full or degenerated. Full-pairs save us 2 characters, degenerated save us only 1. */
  def isFullPair(pair: (Int, Int)) =
    pair._1 + pair._2 < str.length - 1

  /** Removes pareto-suboptimal sequences */
  def prune(sequences: List[List[(Int, Int)]]): List[List[(Int, Int)]] = {
    val allowedHeads = paretoMin(sequences.map(_.head)).toSet
    val containsFullPair = allowedHeads.exists(isFullPair)
    sequences.filter(s => allowedHeads.contains(s.head) && (isFullPair(s.head) || !containsFullPair))
  }

  /** Dynamic-Programming step */
  @tailrec
  def search(sequences: List[List[(Int, Int)]]): List[List[(Int, Int)]] = {
    val nextStage = prune(sequences.flatMap(extend))
    nextStage match {
      case List() => sequences
      case x => search(nextStage)
    }
  }

  /** Converts a sequence of nested pairs to a palindrome */
  def sequenceToString(sequence: List[(Int, Int)]): String = {
    val lStr = str
    val rStr = str.reverse

    val half =
      (for (List(start, end) <- sequence.reverse.sliding(2)) yield
        lStr.substring(start._1 + 1, end._1) + rStr.substring(start._2 + 1, end._2) + lStr(end._1)).mkString

    if (isFullPair(sequence.head))
      half + half.reverse
    else
      half + half.reverse.substring(1)
  }

  sequenceToString(search(List(List((-1, -1)))).head)
}

Testing:

scala> makePalindrome("noob")
res1: String = nboobn

scala> makePalindrome("ann")
res2: String = anna

scala> makePalindrome("aaa")
res3: String = aaa

scala> makePalindrome("123456789875432")
res4: String = 12345678987654321

For a 40-character word, the timing is below 0.5 ms, although the algorithm itself is pretty sloppy. There is a lot of room for improving performance of pairs and paretoMin.

[devonrevenge]

nice