PasswordCracker.scala

object Solution extends App {

  case class Trie[KE, V](v: Option[V], children: Map[KE, Trie[KE,V]]) {
    def insert(key: Seq[KE], v: V): Trie[KE, V] =
      if(key.isEmpty) copy(v = Some(v))
      else {
        val ke = key.head
        val newChild = children.getOrElse(ke, Trie.empty).insert(key.tail, v)
        copy(children = children + (ke -> newChild))
      }
  }

  object Trie {
    def empty[KE, V]: Trie[KE, V] = Trie(None, Map.empty)

    def apply[KE, V](entries: Seq[(Seq[KE], V)]): Trie[KE, V] =
      (empty[KE, V] /: entries) { case (acc, (key, v)) =>
        acc.insert(key, v)
      }
  }

  import io.StdIn._

  def recoverMessage(
                      dictionary: Trie[Char, String],
                      currentNode: Trie[Char, String],
                      remaining: Seq[Char],
                      acc: Seq[String] = Seq.empty): Option[Seq[String]] =
    if(remaining.isEmpty) currentNode.v.map(word => (word +: acc).reverse)
    else {
      val newRemaining = remaining.tail
      currentNode.children.get(remaining.head) flatMap { nextNode =>
        nextNode.v flatMap { word =>
          recoverMessage(dictionary, dictionary, newRemaining, word +: acc)
        } orElse recoverMessage(dictionary, nextNode, newRemaining, acc)
      }
    }

  (0 until readInt) foreach { _ =>
    val n = readInt()
    val words: Seq[String] = readLine.split(" ").map(_.trim)
    val message = readLine()

    val dictionary = Trie(words.map(_.toSeq) zip words)

    val wordsAlphabet = words.flatten.toSet

    val solution: Option[Seq[String]] = if(message.forall(wordsAlphabet contains _))
      recoverMessage(dictionary, dictionary, message)
    else None

    println {
      solution.map(_.mkString(" ")).getOrElse("WRONG PASSWORD")
    }

  }

}