CodeKataをKotlinでやってみた 〜Karate Chop編〜

CodeKataとは？

『達人プログラマー』『⁠プログラミングRuby』 などの著者であるDave Thomasさんが自身のブログで公開している21のコーディング課題。「偉大な音楽家になるためには、理論を理解することや才能を持ち合わせていることも助けになるが、究極的には偉大さというものは練習に由来するものであろう」、「しかし、ソフトウェア産業では我々は実務を通して練習を積むことになっており、それが仕事上でのミスにつながっている」とDaveさんは指摘をしています。

「CodeKataはソフトウェア開発に練習の要素を持ち込もうという試みである。"型"は空手の練習であり、度重なる繰り返しを通して、少しずつ毎回向上していくものだ」とDaveさんは日本人には馴染みの深い武道の"型"について説明しており、CodeKataについても同様の意図であるとのことです。

つまり、ブログで紹介している21の"型"を練習として取り組むことでコーディングの能力を向上させよう、というコンセプトになります。

トライしてみる

上述の通りCodeKataには21の型が用意されていますが、こちらはそのうちの二つ目のものです。課題内容としてはシンプルです。

This Kata is straightforward. Implement a binary search routine (using the specification below) in the language and technique of your choice. Tomorrow, implement it again, using a totally different technique. Do the same the next day, until you have five totally unique implementations of a binary chop.

つまり、「バイナリサーチを実装してみよう！5つの異なる方法で実装できるまで、一日置きに新しい方法で実装を試してみよう。」ということです。その他の詳細についてはKarate Chopのページを参照してください。

条件として、実装するメソッドのインターフェースは下記のようにする必要があります。

chop(int, array_of_int)  -> int

実装

class KarateChop {
    companion object {
        // int value returned when targetNum is not found
        private const val NOT_FOUND = -1

        /**
         * chop a list by binary search with iterating
         */
        fun iteratorChop(targetNum: Int, list: List<Int>): Int {
            ......
        }

        /**
         * chop a list by binary search recursively
         */
        fun recursiveChop(targetNum: Int, list: List<Int>, offsetIndex: Int = 0): Int {
            ......
        }

        /**
         * chop a list by library binary search function
         */
        fun libraryChop(targetNum: Int, list: List<Int>): Int {
            ......
        }
    }
}

①反復的な実装

        /**
         * chop a list by binary search with iterating
         */
        fun iteratorChop(targetNum: Int, list: List<Int>): Int {
            var low = 0
            var high = list.lastIndex

            while (low <= high) {
                val mid = (low + high).div(2)
                val midNum = list[mid]
                val result = compareValues(midNum, targetNum)

                when {
                    result < 0 -> low = mid + 1
                    result > 0 -> high = mid - 1
                    else -> return mid
                }
            }
            return NOT_FOUND
        }

whileを利用して反復的に処理を行う実装です。indexの下限lowとindexの上限highを合計したものを2で除算してindexの中間midを算出します。list[mid]とすることでリストの中間値midValを参照し、その値をtargetNumと比較します。

もしmidNum < targetNumの場合にはlowをmid+1として下半分を放棄、midNum > targetNumの場合にはhighをmid-1として上半分を放棄します。この処理をlow <= highになるまで繰り返します。

もしlow <= highとなった場合には対象のリストが存在しない=対象値がリストに含まれないことになるので、-1の定数として設定しているNOT_FOUNDを返却します。

②再帰的な実装

        /**
         * chop a list by binary search recursively
         */
        fun recursiveChop(targetNum: Int, list: List<Int>, offsetIndex: Int = 0): Int {
            var low = 0
            var high = list.lastIndex

            if (list.isEmpty()) return NOT_FOUND

            val mid = (low + high).div(2)
            val midNum = list[mid]
            val result = compareValues(midNum, targetNum)

            return when {
                result < 0 -> {
                    low = mid + 1
                    // pass offsetIndex param to adjust original index position
                    recursiveChop(targetNum, list.slice(low..list.lastIndex), offsetIndex.plus(low))
                }
                result > 0 -> {
                    high = mid - 1
                    recursiveChop(targetNum, list.slice(0 .. high))
                }
                else -> mid.plus(offsetIndex)
            }
        }

基本的な処理は上述の"①反復的な実装"と重複するので割愛します。こちらは再帰的にrecursiveChop自身を処理中で呼び出すことでバイなリサーチを実装しています。

つまり、もしmidNum < targetNumの場合には上半分を対象として、midNum > targetNumの場合には下半分を対象として関数を再帰的に呼び出します。

また、midNum < targetNumの場合には放棄される下半分のリストについても返却するindex位置を算出する際に折り込む必要があるため、引数offsetIndexをoffsetIndex.plus(low)として次の再帰処理の際にも放棄された下半分の範囲を返却値に反映できるようにしています。

③ライブラリを用いた実装

        /**
         * chop a list by library binary search function
         */
        fun libraryChop(targetNum: Int, list: List<Int>): Int {
            val result =  list.binarySearch(targetNum)
            // when targetNum is not found, need to return NOT_FOUND int value
            if (result < 0) return NOT_FOUND

            return result
        }

はい、こちらは自身で実装をしている訳ではなく完全にCollectionライブラリの力を借りています。。。
KotlinにはbinarySearchというそのものズバリのメソッドが用意されていて、こちらを呼び出すだけでバイナリサーチを実行することができます。

一点だけ追加対応としてもし値がリストに含まれなかった場合の返却値をどのような場合にも定数しているNOT_FOUNDを返却するように指定しています。これは、もし値がリストに含まれていない場合には反転した挿入index値が返却される仕様のためです。

詳細については公式ドキュメントをご参照ください。

テストケース整備

Daveさんはブログ上でテストケースについてもご用意してくださっています。そちらからデータを拝借し、下記のようにテストケースを整備してみました。

class KarateChopTest {
    @Test
    fun testIteratorChop() {
        chop(::iteratorChop)
    }

    @Test
    fun testRecursiveChop() {
        chop(::recursiveChop)
    }

    @Test
    fun testLibraryChop() {
        chop(::libraryChop)
    }

    /**
     * refer a chop function passed as argument and execute that
     */
    private fun chop(chopFunction: (Int, List<Int>) -> Int) {
        assertEquals(-1, chopFunction(3, listOf()))
        assertEquals(-1, chopFunction(3, listOf(1)))
        assertEquals(0,  chopFunction(1, listOf(1)))

        assertEquals(0,  chopFunction(1, listOf(1, 3, 5)))
        assertEquals(1,  chopFunction(3, listOf(1, 3, 5)))
        assertEquals(2,  chopFunction(5, listOf(1, 3, 5)))
        assertEquals(-1, chopFunction(0, listOf(1, 3, 5)))
        assertEquals(-1, chopFunction(2, listOf(1, 3, 5)))
        assertEquals(-1, chopFunction(4, listOf(1, 3, 5)))
        assertEquals(-1, chopFunction(6, listOf(1, 3, 5)))

        assertEquals(0,  chopFunction(1, listOf(1, 3, 5, 7)))
        assertEquals(1,  chopFunction(3, listOf(1, 3, 5, 7)))
        assertEquals(3,  chopFunction(7, listOf(1, 3, 5, 7)))
        assertEquals(2,  chopFunction(5, listOf(1, 3, 5, 7)))
        assertEquals(-1, chopFunction(0, listOf(1, 3, 5, 7)))
        assertEquals(-1, chopFunction(2, listOf(1, 3, 5, 7)))
        assertEquals(-1, chopFunction(8, listOf(1, 3, 5, 7)))
        assertEquals(-1, chopFunction(4, listOf(1, 3, 5, 7)))
        assertEquals(-1, chopFunction(6, listOf(1, 3, 5, 7)))
    }
}

無事全てのケースを通過することを確認できました！

まとめ

Daveさんの指定としては「異なる実装方法で５通りやってみてね！」とのことでしたが、今の自分がササっとできる範囲では3つ（しかも内1つはライブラリ呼んでいるだけ）でした。

幸い?にもあとCodeKataは19ケース残っているので、今後も取り組んでいきたいと思います。
お読みいただきまして、ありがとうございました！

関連記事一覧

• CodeKataをKotlinでやってみた 〜Karate Chop編〜
• CodeKataをKotlinでやってみた 〜Data Munging編〜
• [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)