Return to Answer

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, 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, I'll try to fix it in 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
 }
}

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
 }
}

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, many calls to exists. All those introduce large overhead.

Here's my attempt (with a few bugs in checking first closest letters, I'll correct them in 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
 }
}

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, 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, I'll try to fix it in 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
 }
}