CodeKataをKotlinでやってみた 〜Anagrams編〜

今回も[CodeKata](http://codekata.com/)をKotlinでやっていきたいと思います。
「そもそもCodeKataって何？」と言う方は"[CodeKataをKotlinでやってみた 〜Karate Chop編〜](https://qiita.com/Takuyaaaa/items/1d47fb67a43fb4f3c919)"をご参照ください。

## トライしてみる
今回の課題は21あるKataのうち5つ目に当たる"[Anagrams](http://codekata.com/kata/kata06-anagrams/)"です。
> The challenge is fairly simple: given a file containing one word per line, print out all the combinations of words that are anagrams; each line in the output contains all the words from the input that are anagrams of each other. 

つまり、あるテキストファイルに含まれる単語について、アナグラムが存在する単語を全て出力するプログラムを作成することが今回の課題となります。

### アナグラムとは？

下記アナグラムについて[wikipedia](https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%8A%E3%82%B0%E3%83%A9%E3%83%A0)の引用です。
> アナグラム (anagram)とは、言葉遊びの一つで、単語または文の中の文字をいくつか入れ替えることによって、全く別の意味にさせる遊びである

例えば、"a,e,p,s,t"の5文字で構成される単語は"paste"と記述すれば"ペースト"になり、"peats"と記述すれば"ピーツ(泥炭)"の意味になるので、"paste"は"peats"のアナグラムである、と言えます。

### 実装

```kotlin
class Anagrams {
    companion object {
        /**
         * execute processes and print all anagrams
         */
        fun File.extractAllAnagrams() =
            this.useLines { lines: Sequence<String> ->
                lines.groupBy { it.sortAlphabetically() }
                        .asSequence()
                        .filter { it.value.count() > 1 }
                        .map { it.value }

            }

        /**
         * sort string alphabetically
         */
        private fun String.sortAlphabetically(): String =
            this.toCharArray().sorted().joinToString("")
    }
}
```

任意のファイルに対して呼び出されるインターフェイスとして`extractAllAnagrams`を用意しています。こちらのメソッド内で諸々の処理を行い、最後にアナグラムに該当する各単語群をリストにまとめて返却しています。

まず`this.useLines`とすることでファイルの内容をSequenceとして読み出していきます。
次に`.groupBy { it.sortAlphabetically() }`とすることで、単語で用いられている文字をキーとするMap形式のデータにします。つまり、こちらでそれぞれまとめられている単語群がアナグラムということになります。遅延評価を徹底するため、念のため`asSequence()`を呼び出すことで再度Sequenceとして処理を継続していきます。

`.filter { it.value.count() > 1 }`とすることで単語で用いられている文字の組み合わせで重複する物が無い=アナグラムが存在しない単語をフィルターアウトします。後は`.map { it.value }`でキー情報を捨てることでアナグラムが存在する各単語群のみを含むリストとします。

### テストケース整備

それでは、意図通り動いているかテストケースを整備して確認してみます。

```kotlin
class AnagramsTest {
    @Test
    fun testAnagrams() {
        val anagrams = File("resources/wordlist_for_anagrams.txt")
                .extractAllAnagrams()

        anagrams.forEach {
            assertTrue(it.size > 1)
            println(it)
        }
    }
}
```

`wordlist_for_anagrams.txt`を読み込み、そちらにアナグラムが存在する単語を全て出力していきます。ちなみに`wordlist_for_anagrams.txt`はブログ上で紹介されているサンプルデータで、338882単語が含まれています。冒頭だけ示すと下記のような形です。

```
A
A'asia
A's
AA
AA's
AAA
AAM
AB
AB's
ABA
ABC
ABC's
ABCs
ABD
......
```

それではテストを実行してみます。下記のように意図通りコンソールに出力されました!

```
> Task :test
[AAM, AMA]
[AB, BA]
[AB's, BA's]
[ABC, CAB]
[ABM, MBA]
[ABM's, MBA's]
......
```

`assertTrue(it.size > 1)`で各単語群の大きさが1以上であることも担保できているので、anagramが存在しない単語については問題なく取り除かれていることも確認できます。ちなみに、自分のPC上での実行時間は750ms強でした。


## まとめ
データ数が大きいのもありますが、現状のアルゴリズムでは実行に少し時間を要してしまっているのでもっと計算量を減らすような実装も見ていきたいです。もし「こうすればもっと速くできるよ」など御座いましたら、ご指摘お待ちしております。

**(2021/01/05追記)**
@kts_h さんにコメントいただき、Sequenceを利用したロジックに修正しました。ご教示いただきまして、ありがとう御座いました！

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

**関連記事一覧**

* [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)