問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0225

result.md

実行方法

Shiritori.consume(Shiritori.input.lines.toList)

ログ

単語「apple」から探索を始めます
現在の単語=apple, 残りの単語=Map(y -> List(yellow), g -> List(georgia), k -> List(king), e -> List(email)), 次の単語=Some(List(email))
現在の単語=email, 残りの単語=Map(y -> List(yellow), g -> List(georgia), k -> List(king), e -> List()), 次の単語=None
結果 => NG
単語「yellow」から探索を始めます
現在の単語=yellow, 残りの単語=Map(a -> List(apple), g -> List(georgia), k -> List(king), e -> List(email)), 次の単語=None
結果 => NG
単語「georgia」から探索を始めます
現在の単語=georgia, 残りの単語=Map(a -> List(apple), y -> List(yellow), k -> List(king), e -> List(email)), 次の単語=Some(List(apple))
現在の単語=apple, 残りの単語=Map(a -> List(), y -> List(yellow), k -> List(king), e -> List(email)), 次の単語=Some(List(email))
現在の単語=email, 残りの単語=Map(a -> List(), y -> List(yellow), k -> List(king), e -> List()), 次の単語=None
結果 => NG
単語「king」から探索を始めます
現在の単語=king, 残りの単語=Map(a -> List(apple), y -> List(yellow), g -> List(georgia), e -> List(email)), 次の単語=Some(List(georgia))
現在の単語=georgia, 残りの単語=Map(a -> List(apple), y -> List(yellow), g -> List(), e -> List(email)), 次の単語=Some(List(apple))
現在の単語=apple, 残りの単語=Map(a -> List(), y -> List(yellow), g -> List(), e -> List(email)), 次の単語=Some(List(email))
現在の単語=email, 残りの単語=Map(a -> List(), y -> List(yellow), g -> List(), e -> List()), 次の単語=None
結果 => NG
単語「email」から探索を始めます
現在の単語=email, 残りの単語=Map(a -> List(apple), y -> List(yellow), g -> List(georgia), k -> List(king)), 次の単語=None
結果 => NG
単語「apple」から探索を始めます
現在の単語=apple, 残りの単語=Map(e -> List(email), y -> List(yellow), g -> List(georgia), l -> List(lucky), w -> List(wink), k -> List(king)), 次の単語=Some(List(email))
現在の単語=email, 残りの単語=Map(e -> List(), y -> List(yellow), g -> List(georgia), l -> List(lucky), w -> List(wink), k -> List(king)), 次の単語=Some(List(lucky))
現在の単語=lucky, 残りの単語=Map(e -> List(), y -> List(yellow), g -> List(georgia), l -> List(), w -> List(wink), k -> List(king)), 次の単語=Some(List(yellow))
現在の単語=yellow, 残りの単語=Map(e -> List(), y -> List(), g -> List(georgia), l -> List(), w -> List(wink), k -> List(king)), 次の単語=Some(List(wink))
現在の単語=wink, 残りの単語=Map(e -> List(), y -> List(), g -> List(georgia), l -> List(), w -> List(), k -> List(king)), 次の単語=Some(List(king))
現在の単語=king, 残りの単語=Map(e -> List(), y -> List(), g -> List(georgia), l -> List(), w -> List(), k -> List()), 次の単語=Some(List(georgia))
現在の単語=georgia, 残りの単語=Map(e -> List(), y -> List(), g -> List(), l -> List(), w -> List(), k -> List()), 次の単語=None
結果 => OK

結果

List(NG, OK)

shiritori.scala

object Shiritori {

  import annotation.tailrec

  val input = """5
apple
yellow
georgia
king
email
7
apple
yellow
georgia
king
email
wink
lucky
0"""

  // OK, NG以外を結果として返すコードを書いたらコンパイルエラーにして欲しかったので、結果に型(VaidationResult)を与える
  sealed case class ValidationResult(text: String)
  object OK extends ValidationResult("OK")
  object NG extends ValidationResult("NG")

  // 入力データを処理するプログラムの状態
  case class State(
    input: List[String],
    chunkSize: Option[Int] = None,
    chunkedLines: List[String] = List.empty,
    results: List[ValidationResult] = List.empty
  )

  def toVocabulary(input: List[String]): Map[Char, List[String]] = input.foldLeft(Map.empty[Char, List[String]]) { (result, word) =>
    val firstChar = word(0)
    result.updated(firstChar, result.getOrElse(firstChar, List.empty) :+ word)
  }

  def validate(input: List[String]): ValidationResult = {
    @tailrec
    def _validate(currentWord: String, vocabularyLeft: Map[Char, List[String]]): ValidationResult = {
      println("現在の単語=" + currentWord + ", 残りの単語=" + vocabularyLeft + ", 次の単語=" + vocabularyLeft.get(currentWord.last))
      if (vocabularyLeft.values.flatten.isEmpty) {
        OK
      } else {
        vocabularyLeft.get(currentWord.last) match {
          case Some(nextWord :: rest) =>
            _validate(nextWord, vocabularyLeft.updated(nextWord(0), rest))
          case _ =>
            NG
        }
      }
    }

    val exists = input.exists { firstWord =>
      println("単語「" + firstWord + "」から探索を始めます")
      val result = _validate(firstWord, toVocabulary(input.filter(firstWord !=)))
      println("結果 => " + result.text)
      result == OK
    }
    if (exists) OK else NG
  }

  def consume(input: List[String]): List[String] = {
    @tailrec
    def _consume(state: State): List[ValidationResult] = {
      state match {
        case State(head :: tail, None, Nil, _) =>
          _consume(state.copy(input = tail, chunkSize = Some(head.toInt)))
        case State(head :: tail, Some(chunkSize), chunkedLines, _) if chunkSize > 0 =>
          _consume(state.copy(input = tail, chunkSize = Some(chunkSize - 1), chunkedLines = chunkedLines :+ head))
        case State(Nil, Some(0), Nil, results) =>
          state.results
        case State(head :: tail, Some(0), chunkedLines, results) =>
          _consume(state.copy(chunkSize = None, chunkedLines = List.empty, results = results :+ validate(chunkedLines)))
      }
    }
    _consume(State(input)).map(_.text)
  }

}