LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@Takuyaaaa(たくや)

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

Last updated at Posted at 2021-01-16

今回もCodeKataをKotlinでやっていきたいと思います。
「そもそもCodeKataって何？」と言う方は"CodeKataをKotlinでやってみた 〜Karate Chop編〜"をご参照ください。

トライしてみる

今回の課題は21あるKataのうち19つ目に当たる"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"

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

実装

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つ用意していて、それぞれブログ内で紹介されている各例に対応しています。

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文字違いの単語が複数存在する場合の次に続く単語の選定ロジック考慮など）。

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

関連記事一覧

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?