CodeKataをKotlinでやってみた 〜Word Chains編〜

今回も[CodeKata](http://codekata.com/)をKotlinでやっていきたいと思います。
「そもそもCodeKataって何？」と言う方は"[CodeKataをKotlinでやってみた 〜Karate Chop編〜](https://qiita.com/Takuyaaaa/items/1d47fb67a43fb4f3c919)"をご参照ください。
  
## トライしてみる
今回の課題は21あるKataのうち19つ目に当たる"[Word Chains](http://codekata.com/kata/kata19-word-chains/)"です。  
> There’s a type of puzzle where the challenge is to build a chain of words, starting with one particular word and ending with another. Successive entries in the chain must all be real words, and each can differ from the previous word by just one letter. For example, you can get from “cat” to “dog” using the following chain.
>
```
cat
cot
cog
dog
```
> The objective of this kata is to write a program that accepts start and end words and, using words from the dictionary, builds a word chain between them. For added programming fun, return the shortest word chain that solves each puzzle. For example, you can turn “lead” into “gold” in four steps (lead, load, goad, gold), and “ruby” into “code” in six steps (ruby, rubs, robs, rods, rode, code).

つまり、始点("cat")と終点（"dog"）が1組渡された際に、始点の単語を実在する英単語になる様1文字ずつ変更して行って、終点の単語と一致させる様なアルゴリズムを実装することが今回の課題となります。  
ブログ記事の中では上述の物も含めてWord Chainsの例が3つ紹介されています

* "cat" -> "cot" -> "cog" -> "dog"
* "lead" -> "load" -> "goad -> "gold"
* "ruby" -> "rubs" -> "robs" -> "rods" -> "rode" -> "code"

これらの単語を全て含む公開されている英単語のリストデータを探したのですが、パッと適当なものを見つけることが出来なかったため、今回は上記で出てくる単語群をそのまま英単語のリストデータとして読み込むことにします。

### 実装

```kotlin
package com.code_kata.kata

import java.io.File

class WordChains(private val start: String, private val end: String) {
    // word list referred when executing word chains algorithm
    private val wordList = File("resources/wordlist_for_word_chains.txt").readLines()
    // list storing words calculated by word chains algorithm
    val wordResult = mutableListOf<String>()

    /**
     * execute word chains algorithm
     */
    fun executeWordChains() {
        // word list one of which is possibly next word
        val wordOptions = extractWordOptions()
        searchNextWord(wordOptions, start)
    }

    /**
     * extract word options from "wordList" which are possible next word
     */
    private fun extractWordOptions(): MutableList<List<Char>> =
        wordList.asSequence()
                .filter { it.length == start.length }
                .filter { it != start }
                .map { it.toList() }
                .toMutableList()

    /**
     * calculate a next word which has one character diff from "baseWord"
     */
    private fun searchNextWord(wordOptions: MutableList<List<Char>>, baseWord: String) {
        // record "baseWord" to record history of word chains algorithm
        wordResult.add(baseWord)
        val examinedList = examineWordOptions(wordOptions, baseWord)
        // get index pointing to next word
        val nextIndex = examinedList.getTargetIndex()
        val nextWord = wordOptions[nextIndex].joinToString("")

        // remove word picked as next word to continue processing recursively
        wordOptions.removeAt(nextIndex)
        when (nextWord) {
            // when "targetWord" is matched to "end", finish recursive calling
            end -> wordResult.add(nextWord)
            else -> searchNextWord(wordOptions, nextWord)
        }
    }

    /**
     * examine "wordOptions" and record which one has one character diff from "baseWord"
     */
    val ONLY_ONE_CHAR_DIFF = 1
    val NOT_NEXT_WORD = -1
    private fun examineWordOptions(wordOptions: MutableList<List<Char>>, baseWord: String): List<Int> =
            wordOptions
                    .asSequence()
                    // map each character diff to each word
                    .map { it.groupByCharDiff(baseWord.toList()) }
                    // map how many characters are NOT in common with "wordOptions"
                    .map { it.getByKey(false).count() }
                    .mapIndexed { index, count ->
                        return@mapIndexed when (count) {
                            // when the word's character has only one char diff
                            // against to "baseWord", map its index as value
                            ONLY_ONE_CHAR_DIFF -> index
                            // when the word's character has more than one char diff
                            // against to "baseWord", map "NOT_NEXT_WORD(-1)" as value
                            else -> NOT_NEXT_WORD
                        }
                    }
                    .toList()
}

/**
 * groupBy each character diff against "other"
 */
fun List<Char>.groupByCharDiff(other: List<Char>): Map<Boolean, List<Boolean>> {
    return this.mapIndexed { index, char ->
        char == other[index]
    }.groupBy { it }
}

/**
 * get element by "key"
 */
fun <T> Map<T, List<T>>.getByKey(key: T): List<T> =
    this[key] ?: throw IllegalArgumentException("Invalid key passed: $key")

/**
 * get targetIndex whose value is not equal to -1
 */
fun List<Int>.getTargetIndex(): Int =
        this.find { it != -1 } ?: throw NullPointerException("no match!")
```

始点の単語`start`と終点の単語`end`渡して作成する`WordChains`クラスのインスタンスに対して`executeWordChains`を呼び出すことでWordChainsアルゴリズムを実行します。  

`executeWordChains`内で`extractWordOptions`を呼び出すことで単語群の中から`start`のWordChainsになり得る単語を抽出します。その抽出された単語のリストである`wordOptions`と始点の単語`start`を引数として`searchNextWord`を呼び出すことで`start`に続く次の単語を算出します。

`searchNextWord`は引数`baseWord`の次の単語になり得る単語を`wordOptions`から取得して、その算出された単語に対して`searchNextWord`を再帰的に呼び出すことで終点の単語`end`に到達する様なアルゴリズムを実装しています。
同メソッド内で呼び出されている`examineWordOptions`では`baseWord`と1文字だけ違う単語のindex情報を保持する`examinedList`を作成し、その情報から次の単語として設定される単語`nextWord`を取得してます。

### テスト
それではテストケースを整備してアルゴリズムが意図通り動作しているか確認してみます。テストケースは3つ用意していて、それぞれブログ内で紹介されている各例に対応しています。

```kotlin
class WordChainsTest {
    @Test
    fun testWordChains1() {
        val wordChains = WordChains("cat", "dog")
        wordChains.executeWordChains()

        assertEquals("cat", wordChains.wordResult.first())
        assertEquals("dog", wordChains.wordResult.last())

        // print [cat, cot, cog, dog]
        println(wordChains.wordResult)
    }

    @Test
    fun testWordChains2() {
        val wordChains = WordChains("lead", "gold")
        wordChains.executeWordChains()

        assertEquals("lead", wordChains.wordResult.first())
        assertEquals("gold", wordChains.wordResult.last())

        // print [lead, load, goad, gold]
        println(wordChains.wordResult)
    }

    @Test
    fun testWordChains3() {
        val wordChains = WordChains("ruby", "code")
        wordChains.executeWordChains()

        assertEquals("ruby", wordChains.wordResult.first())
        assertEquals("code", wordChains.wordResult.last())

        // print [ruby, rubs, robs, rods, rode, code]
        println(wordChains.wordResult)
    }
}
```

無事全てのテストケースを通過し、アルゴリズムが意図通り動いていることを確認できました！

## まとめ
今回は英単語リストデータが例に登場する単語群のみとする簡便なものでしたが、実在する膨大な英単語リストデータを参照する様な場合にはより複雑な考慮が必要だと思いました（例えば、1文字違いの単語が複数存在する場合の次に続く単語の選定ロジック考慮など）。

お読みいただきまして、ありがとうございました！

**関連記事一覧**

* [CodeKataをKotlinでやってみた 〜Karate Chop編〜](https://qiita.com/Takuyaaaa/items/1d47fb67a43fb4f3c919)
* [CodeKataをKotlinでやってみた 〜Data Munging編〜](https://qiita.com/Takuyaaaa/items/a6b97ba6b1864451e771)
* [CodeKataをKotlinでやってみた 〜Bloom Filters編〜]
(https://qiita.com/Takuyaaaa/items/eaa3848bce3bccdd946f)
* [CodeKataをKotlinでやってみた 〜Anagrams編〜]
(https://qiita.com/Takuyaaaa/items/df06e24e6f2c7f8ced35)
* [CodeKataをKotlinでやってみた 〜Checkout編〜]
(https://qiita.com/Takuyaaaa/items/0a4b82e30c977444c0bc)
* [CodeKataをKotlinでやってみた 〜Sorting it Out編〜]
(https://qiita.com/Takuyaaaa/items/b5210c53bff3ff5f0512)
* [CodeKataをKotlinでやってみた 〜Counting Code Lines編〜]
(https://qiita.com/Takuyaaaa/items/cb9143fbcb9e0b2a7822)
* [CodeKataをKotlinでやってみた 〜Tom Swift Under the Milkwood編〜]
(https://qiita.com/Takuyaaaa/items/feccf69d2b9d95196a72)
* [CodeKataをKotlinでやってみた 〜Transitive Dependencies編〜]
(https://qiita.com/Takuyaaaa/items/9b43473b8feffe1ce9f7)
* [CodeKataをKotlinでやってみた 〜Word Chains編〜]
(https://qiita.com/Takuyaaaa/items/2539338252ad7e19ba18)
* [CodeKataをKotlinでやってみた 〜Simple Lists編〜]
(https://qiita.com/Takuyaaaa/items/36ef73522bfe8d054448)