/r/dailyprogrammer Challenge #232 Bonus

TwoWordPalindrome.scala

import scala.collection.immutable.{HashSet, SortedSet}
import scala.collection.mutable.MutableList
import java.io.{BufferedWriter, FileWriter}

object TwoWordPalindrome {
  
  val milliPerNano = 1000000d // 1 million milliseconds in a nanosecond
  val outFileName = "two-word-palindromes.txt" // name of file found palindromes will be written to
  val twoWordPalindromes = MutableList[(String, String)]() // list that results will be appended to
  
  // load words from wordlist into memory
  // I chose a HashSet for the O(1) search time
  val wordList = {
    print("Loading words...")
    val startTime = System.nanoTime()
    val wordList = io.Source.fromFile("enable1.txt").getLines().to[HashSet]
    val elapsedTime = (System.nanoTime() - startTime) / milliPerNano
    print(f" Done after ${elapsedTime}%.2fms.\n")
    wordList // weird scala way of returning an object from a block
  }

  def main(args: Array[String]) {
    // get the writer ready
    // I do this first so that if it fails I don't waste time looking for palindromes
    val writer = new BufferedWriter(new FileWriter(outFileName))

    // iterate over all words once, looking for two-word palindromes
    {
      print("Looking for two-word palindromes...")
      val startTime = System.nanoTime()
      wordList foreach process
      val elapsedTime = (System.nanoTime() - startTime) / milliPerNano
      print(f" Done after ${elapsedTime}%.2fms.\n")
    }

    // sort the results (iteration over a HashSet doesn't happen in any particular order)
    // Didn't block this out because sortedTwoWordPalindromes needs scope for a while longer
    print("Sorting results...")
    val startTime = System.nanoTime()
    val sortedTwoWordPalindromes = twoWordPalindromes.to[SortedSet]
    val elapsedTime = (System.nanoTime() - startTime) / milliPerNano
    print(f" Done after ${elapsedTime}%.2fms.\n")

    // verify that all found two-word palindromes are actually palindromes
    {
      print("Verifying results...")
      val startTime = System.nanoTime()
      if (!verify(sortedTwoWordPalindromes)) {
        print(" Verification failed.\n")
        return
      }
      val elapsedTime = (System.nanoTime() - startTime) / milliPerNano
      print(f" Done after ${elapsedTime}%.2fms.\n")
    }
   
    // write output to file
    {
      print(s"""Writing ${twoWordPalindromes.size} two-word palindromes to "$outFileName"...""")
      val startTime = System.nanoTime()
      sortedTwoWordPalindromes.foreach(t => writer.write(s"${t._1} ${t._2}\n"))
      writer.close()
      val elapsedTime = (System.nanoTime() - startTime) / milliPerNano
      print(f" Done after ${elapsedTime}%.2fms.\n")
    }
  } // end of main()

  /* This is the important bit. 
   * Given one word, it finds the other words that make a two-word palindrome with it.
   * 
   * The Process:
   *   1. check if 'word.reverse' makes a two-word palindrome
   *   2. if 'word.reverse' != 'word' and 'word.reverse' exists, we've got a two-word palindrome
   *   3. if 'wor.reverse' or 'ord.reverse' exist, they are make two-word palindromes
   * 
   *   4. find all suffixes of 'word' greater than 1 char and less than 'word.length' in length
   *   5. if 'suffix' is a palindrome, search for 'prefix.reverse'
   *   6. if found, then it's the second word of a two-word palindrome
   * 
   *   7. find all prefixes of 'word' greater than 1 char and less than 'word.length' in length
   *   8. if 'prefix' is a palindrome, search for 'suffix.reverse'
   *   9. if found, then it's the first word of a two-word palindrome
   *
   * Note that in a two-word palindrome the words are either the same length or different lengths. (duh)
   * This method assumes that "word" is the longer (or equal) of the two words. This means that if I'm on
   * the word "dam" I will find "mad dam" but not "maddened dam". This works because we iterate over ALL
   * words, so when I get to the word "maddened" I'll find "maddened dam".  Also note that this causes both
   * "desserts stressed" and "stressed desserts" to be counted as separate two-word palindromes. This is
   * intentional.
   *
   * The reason I chose to assume "word" is the longer of the two words, over the shorter, is that in the
   * shorter-word approach, I need to search the wordlist for all words starting with a certain prefix.
   * This requires both a more complex search and more string operations to evauluate the results the search
   * returns. In the longer-word approach, I need to search the wordlist for several specific words. While this
   * seems like it causes more individual searches, this is not exactly the case because in the shorter-word
   * approach I must first perform the search and then check each result to make sure it is valid. In the
   * longer-word approach the search is the last operation performed, meaning we only do a search if we
   * absolutely have to.
   */
  def process(word: String) {
    // assuming this word comes first

    // check for 'word'
    {
      val secondWord = word.reverse
      if (secondWord != word) { // ensure we are not repeating a one-word palindrome
        checkSecondWord(word, secondWord)
      }
    }
    // check for 'wor'
    if (word.length > 1) {
      val wordExceptLast = word.substring(0, word.length - 1)
      val secondWord = wordExceptLast.reverse
      checkSecondWord(word, secondWord)
    }
    // check for everything else
    for (splitPoint <- getSuffixSplitPoints(word)) {
      val suffix = getSuffix(word, splitPoint)
      
      if (isPalindrome(suffix)) {
        val secondWord = getPrefix(word, splitPoint).reverse
        checkSecondWord(word, secondWord)
      }
    }

    // assuming this word comes second

    // check for 'ord' (we already checked for 'word')
    if (word.length > 1) {
      val wordExceptFirst = word.substring(1)
      val firstWord = wordExceptFirst.reverse
      checkFirstWord(word, firstWord)
    }
    // check for everything else
    for (splitPoint <- getPrefixSplitPoints(word)) {
      val prefix = getPrefix(word, splitPoint)
      if (isPalindrome(prefix)) {
        val firstWord = getSuffix(word, splitPoint).reverse
        checkFirstWord(word, firstWord)
      }
    }
  } // end of process()

  /* Check if a single word is a palindrome. Does NOT perform
   * any prefiltering of case or punctuation. To my knowledge,
   * this is the most efficient way to do this.
   */
  def isPalindrome(word: String):Boolean = {
    for (a <- 0 until word.length / 2) {
      val b = word.length - 1 - a
      if (word.charAt(a) != word.charAt(b)) return false
    }
    return true
  }

  // Check if "firstWord" is a real word, and if it is we've got ourselves a palindrome!
  def checkFirstWord(word: String, firstWord: String) {
    if (wordList.contains(firstWord)) twoWordPalindromes += ((firstWord, word))
  }

  // Check if "secondWord" is a real word, and if it is we've got ourselves a palindrome!
  def checkSecondWord(word: String, secondWord: String) {
    if (wordList.contains(secondWord)) twoWordPalindromes += ((word, secondWord))
  }

  // verify that all items in a list of string tuples are two-word palindromes
  def verify(list: Iterable[(String, String)]):Boolean = {
    list.foreach(t => {
      if (!isPalindrome(t._1 + t._2)) return false
    })
    return true
  }

  /* "splitPoint" is the index of the first character of "suffix"
   *                                       012345 6789AB
   * where a word is being split like so: "prefix|suffix"
   *                                              ^
   *                                         splitPoint = 6
   */

  // get split points for checking for palindrome prefixes
  def getPrefixSplitPoints(word: String) =  2 to word.length - 1

  // get split points for checking for palindrome suffixes
  def getSuffixSplitPoints(word: String) =  1 to word.length - 2

  // simple wrapper method for getting the prefix of a split string
  def getPrefix(word: String, splitPoint: Int) = word.substring(0, splitPoint)

  // simple wrapper method for getting the suffix of a split string
  def getSuffix(word: String, splitPoint: Int) = word.substring(splitPoint)

} // end of TwoWordPalindrome