今回もCodeKataをKotlinでやっていきたいと思います。
「そもそもCodeKataって何？」と言う方は"CodeKataをKotlinでやってみた 〜Karate Chop編〜"をご参照ください。
トライしてみる
今回の課題は21あるKataのうち11つ目に当たる"Sorting It Out"です。大別すると、"Sorting Balls"と"Sorting Characters"の二つの課題が用意されています。まず1つ目から見ていきましょう。
① Sorting Balls
In the Pragmatic Lottery (motto: There’s One Born Every Minute, and it Might Just Be You!), we select each week’s winning combination by drawing balls. There are sixty balls, numbered (not surprisingly, as we are programmers) 0 to 59. The balls are drawn by the personable, but somewhat distracted, Daisy Mae. As a result, some weeks five numbers are drawn, while other weeks seven, nine, or even fifteen balls make it to the winner’s rack. Regardless of the number of balls drawn, our viewers need to see the list of winning numbers in sorted order just as soon as possible. So, your challenge is to come up with some code that accepts each number as it is drawn and presents the sorted list of numbers so far. The tests might look something like:
rack = Rack.new
assert_equal([], rack.balls)
rack.add(20)
assert_equal([ 20 ], rack.balls)
rack.add(10)
assert_equal([ 10, 20 ], rack.balls)
rack.add(30)
assert_equal([ 10, 20, 30 ], rack.balls)
つまり、番号の書いてある玉を引くとして、その番号をaddで保存できるようにします。そのようにして記録された番号をballsで参照する際に、常にソートされた番号順となっているように実装を行うことが1つ目の課題です。但し、これらの実装をlibrary提供メソッド（sortなど）を呼び出して行うのではなく、スクラッチで車輪の再発明的に実装を行う必要があります。
実装
class Rack {
// balls stored at Rack instance by "add" method
var balls = mutableListOf<Int>()
/**
* store ball number at "balls" in the sorted order
*/
fun add(ball: Int) {
balls.add(ball)
// balls.sort() will do, but this time try to implement by scratch
balls = balls.bubbleSort()
}
/**
* sort list by bubble sort algorithm
*/
private fun MutableList<Int>.bubbleSort(): MutableList<Int> {
return this.reversAsMutable()
.processBubbleSort()
.reversAsMutable()
}
/**
* reverse list and make it as mutableList
*/
private fun MutableList<Int>.reversAsMutable(): MutableList<Int> {
return this.reversed().toMutableList()
}
/**
* process bubble sort algorithm
*/
private fun MutableList<Int>.processBubbleSort(): MutableList<Int> {
this.forEachIndexed { index, num ->
if (this.lastIndex == index) {
return@forEachIndexed
}
val nextNum = this[index+1]
if (num < nextNum) {
// swap each position to sort
this[index] = nextNum
this[index+1] = num
}
}
return this
}
}
先述のテストケースで示されている通り、番号の追加はaddメソッドにより行われます。番号の追加が行われた際にballsに記録されている番号をソートするにはballs.sort()とすれば一発なのですが、前述の通り今回の課題は「builtinのlibraryを使わないで実装してみよう」とのことなのでバブルソートのアルゴリズムを実装していきたいと思います。
bubbleSortメソッドではリストの最終要素から処理をするため一度リバースし、バブルソートの処理を行った後に昇順とするために再度リバースしてその結果を返却しています。
実際にバブルソートのアルゴリズムが実装されている箇所はprocessBubbleSortメソッドになります。各番号について自身の次の番号と比較を行い、もし次の番号の方が自身よりも大きければ位置をスワップすることでソートを行います。最終要素については比較対象が存在しないため、return@forEachIndexedとして処理を行わずにループを終了します。
テストケース整備
それではテストケースを実行して、意図通りプログラムが動いているか確認してみます。冒頭で参照したブログで紹介されているテストケースは少し網羅性が低いと思ったので、自身でケースを追加しています。
@Test
fun testRack() {
val rack = Rack()
assertEquals(mutableListOf(), rack.balls)
rack.add(20)
assertEquals(mutableListOf(20), rack.balls)
rack.add(10)
assertEquals(mutableListOf(10, 20), rack.balls)
rack.add(9)
assertEquals(mutableListOf(9, 10, 20), rack.balls)
rack.add(30)
assertEquals(mutableListOf(9, 10, 20, 30), rack.balls)
rack.add(21)
assertEquals(mutableListOf(9, 10, 20, 21 ,30), rack.balls)
rack.add(11)
assertEquals(mutableListOf(9, 10, 11, 20, 21 ,30), rack.balls)
rack.add(31)
assertEquals(mutableListOf(9, 10, 11, 20, 21 ,30, 31), rack.balls)
rack.add(0)
assertEquals(mutableListOf(0, 9, 10, 11, 20, 21 ,30, 31), rack.balls)
}
無事全てのテストケースを通過し、プログラムが意図通り動いていることを確認できました！
② Sorting Characters
Our resident conspiracy expert, Dr. X, is looking for hidden messages in the collected publications of Hugh Hefner. Dr. X believes the message is hidden in the individual letters, so rather than get distracted by the words, he’s asked us to write a program to take a block of text and return the letters it contains, sorted. Given the text:
When not studying nuclear physics, Bambi likes to play
beach volleyball.
our program would return:
aaaaabbbbcccdeeeeeghhhiiiiklllllllmnnnnooopprsssstttuuvwyyyy
The program ignores punctuation, and maps upper case to lower case.
つまり、Dr.XがHugh Hefneさん（PlayBoy誌の発刊者です）が隠しているメッセージを解き明かすため、ある文章を構成している単語に分解し、アルファベット順に並べて表示できるようにすることが課題となります。その際、句読点などは取り除き文字は小文字にする必要があります。設定の不可解さに頭のリソースが持っていかれそうになりますが、踏ん張って実装を見ていくことにします。
class Sentence(private val sentence: String) {
/**
* make "sentence" sorted alphabetically and remove punctuations
*/
fun extractSortedChars(): String {
return sentence.replace(" ", "")
.removePunctuations()
.map { it.toLowerCase() }
// sort alphabetically
.sortedBy { it }
// make List to String
.joinToString("")
}
/**
* remove punctuations from String
*/
private fun String.removePunctuations(): String {
return this.filter { it != ',' }
.filter { it != '.' }
}
}
こちらの実装は比較的シンプルになります。sentenceとしてインスタンス作成時に渡された文章をextractSortedCharsでアルファベット順に並んだ構成単語として返却します。"句読点の除去 -> 小文字化 -> アルファベット順にソート -> ListをStringに変換"として処理を進めていきます。
テストケース整備
それでは元記事で参照されている文章を元に作成したテストケースを実行して、意図通りプログラムが動いているか確認してみます。
@Test
fun testSentence() {
val sentence = Sentence(
"When not studying nuclear physics, Bambi likes to play beach volleyball."
)
val sortedChars = sentence.extractSortedChars()
assertEquals(
"aaaaabbbbcccdeeeeeghhhiiiiklllllllmnnnnooopprsssstttuuvwyyyy",
sortedChars)
}
無事にテストを通過し、プログラムが意図通りの挙動となっていることが確認できました！
まとめ
builtinのlibraryを用いないで実装しようとのことでそのようになるよう努めましたが、もしかしたらKata作成者の意図としてはより厳密にスクラッチで実装することかもしれないなとうっすら思いました（joinToString("")とせずに、ループを回してListをStringにしていく、など）。。。
お読みいただきまして、ありがとうございました！
関連記事一覧
- 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)