HelloWorld.scala

import scala.collection.mutable.ListBuffer
import scala.io.Source

/**
 * Created by portnov on 01.08.15.
 */
object HelloWorld {

  case class Word(wordIdx : Int, wordInt : List[Int])

  val t9 : Map[Int, List[Char]] =
    Map(1 -> List('i','j'),
        2 -> List('a','b','c'),
        3 -> List('d','e','f'),
        4 -> List('g','h'),
        5 -> List('k','l'),
        6 -> List('m','n'),
        7 -> List('p','r','s'),
        8 -> List('t','u','v'),
        9 -> List('w','x','y'),
        0 -> List('o','q','z')
    )

  val unt9 = t9.toList.flatMap({
    case (k, letters) => for (letter <- letters) yield (letter, k)
  }).toMap

  def decode(i: Int, x: String) : Word = {
    Word(i, x.toList.map(c => unt9.get(c).get))
  }

  class Test(phone : List[Int], words : List[Word], strings : List[String]) {
    override def toString : String = {
      s"<Test phone $phone, ${words.size} words, ${strings.size} source strings>"
    }

    def getWords : List[String] = {
      strings
    }

    def select(ws : List[String], i : Int, d : Int) : List[String] = {
      try {
        ws.filter(w => if (i < w.length) t9.get(d).get.contains(w(i)) else true)
      } catch {
        case e : NoSuchElementException =>
          throw new Exception(s"Unknown digit for t9: $d, at position $i")
      }
    }

    def matchWord(start : Int, word : Word) : Int = {
      if (phone.drop(start).startsWith(word.wordInt)) {
        start + word.wordInt.length
      } else {
        start
      }
    }

    case class Step(position : Int, selected : Word, other : List[Word])

    case class Solution(depth : Int, words : List[Word])

    def step(start : Int, words : List[Word]) : Stream[Step] = {
      words.flatMap(w => {
        val shifted = matchWord(start, w)
        if (shifted != start) {
          List(Step(shifted, w, words.filterNot(_ == w)))
        } else {
          List()
        }
      }).toStream
    }

    private def go(start : Int, words : List[Word]) : Stream[Solution] = {
      val xs = step(start,words)
      xs.flatMap(s =>
        if (s.position >= phone.length) {
          Stream(Solution(1, List(s.selected)))
        } else {
          val sols = go(s.position, s.other)
          if (sols.isEmpty) {
            Stream()
          } else {
            val minDepthIdx = sols.zipWithIndex.minBy(_._1.depth)._2
            val best = sols(minDepthIdx)
            Stream(Solution(best.depth + 1, s.selected :: best.words))
          }
        })
    }

    def solutions : List[List[Word]] = go(0, words).map(_.words).toList

    def solve : Option[String] = {
      solutions match {
        case Nil => None
        case _ => {
          val min = solutions.minBy(_.length)
          Some(min.map(w => strings(w.wordIdx)).mkString(" "))
        }
      }
    }
  }

  object Test {
    def parse(input : Iterator[String]) : Option[Test] = {
      val phoneStr = input.next()
      if (phoneStr == "-1") {
        return None
      } else {
        val phone = phoneStr.map(c => c - '0').toList
        val n = input.next().toInt
        val strings = input.take(n).toList
        val words = strings.zipWithIndex.map({ case (w, i) => decode(i, w) }).filter(w =>
          (w.wordInt.length <= phoneStr.length) &&
            (phone.indexOfSlice(w.wordInt) >= 0)
        )
        return Some( new Test(phone, words, strings) )
      }
    }

    def parseList(input : Iterator[String]) : List[Test] = {
      var result = new ListBuffer[Test]
      while (input.hasNext) {
        parse(input) match {
          case Some(test) =>
            result += test
          case None =>
        }
      }
      result.toList
    }
  }

  def main(args: Array[String]): Unit = {
    val tests = Test.parseList(Source.stdin.getLines())
    for (test <- tests) {
      //println(test)
      test.solve match {
        case None => println("No solution.")
        case Some(solution) => println(solution)
      }
    }
  }
}