Skip to content

Instantly share code, notes, and snippets.

@mumoshu
Last active Dec 16, 2015
Embed
What would you like to do?

実行方法

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)
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)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment