2014/12/05 このエントリーをはてなブックマークに追加 はてなブックマーク - 【Functional Kotlin?】Kotlin Web Demoで遊んでみよう! #ktac2014

【Functional Kotlin?】Kotlin Web Demoで遊んでみよう! #ktac2014




Kotlinアドベントカレンダーの何日目かです。

今回はKotlin Web Demoに関してお話します。
Kotlin Web Demoとは、JetBrains社がKotlinをweb環境上で動作できるように作成した、デモ画面です。


ブラウザ上で簡単にKotlinを書くことが出来ます。 Kotlinの開発環境に関しては以前にもこちらの記事などで紹介されています。





こんなかんじです。


これが結構便利で。思いたった時にKotlin書きたくなる時ありますよね?
そんな時にすぐに試せるわけです。


左側のメニューを見ていただけるとわかると思いますが、
Kotlinのチュートリアルになっています。
メニューをクリックしていくと、実際のサンプルコードを確認できるわけです。


今回はこの中のProblems>Runsのコード解いてみます。
(ProblemsはKotlinのコードでFizzBuzz的な問題を解決するセクションです)






こちらが問題。


「 Write your solution here」の部分に皆さんのカッコ良いコードを書けば全てのテストが通る
というコードです。


皆さん解けますよね?




/*
 * Any array may be viewed as a number of "runs" of equal numbers.
 * For example, the following array has two runs:
 *   1, 1, 1, 2, 2
 * Three 1's in a row for the first run, and two 2's form the second.
 * This array has two runs of length one:
 *   3, 4
 * And this one has five runs:
 *   1, 0, 1, 1, 1, 2, 0, 0, 0, 0, 0, 0, 0
 * Your task is to implement the runs() function so that it returns the number
 * of runs in the given array.
 */
package runs

import java.util.*

fun runs(a : IntArray) : Int {
  // Write your solution here
  return "?"
}

fun main(args : Array<String>) {
  tests<Int> {
    on () expect 0
    on (1) expect 1
    on (1, 2, 3) expect 3
    on (1, 2, 2, 3) expect 3
    on (1, 2, 3, 3) expect 3
    on (1, 1, 2, 3) expect 3
    on (1, 1, 1) expect 1
    on (1, 1, 1, 0, 1, 1) expect 3
    on (1, 1, 1, 0, 1) expect 3
    on (1, 0, 1, 0, 1) expect 5
  } forFunction {
    runs(it)
  }
}






// HELPER FUNCTIONS

fun tests<R>(tests : Tester<R>.() -> Unit) : TesterRunner<R> {
  return TesterRunner<R>(tests)
}

class TesterRunner<R>(val init : Tester<R>.() -> Unit) {
  fun forFunction(functionUnderTest : (IntArray) -> R) {
    val tester = Tester(functionUnderTest)
    tester.(init)()
    tester.done()
  }
}

class Tester<R>(val f : (IntArray) -> R, val skipSuccessful : Boolean = true) {
  private var errors = 0
  fun done() {
      if (errors != 0 || !skipSuccessful)
        println("============================")
      if (errors > 0) {
        val suf = if (errors > 1) "s" else ""
        println("FAILURE: $errors test$suf failed")
      }
      else
        println("All tests passed")
  }

  fun on(vararg data : Int) : IntArray = data

  fun IntArray.expect(expected : R) {
    if (!skipSuccessful) {
      print("Run on: ${Arrays.toString(this)}...")
    }
    val result = (f)(this)
    assertEquals(expected, result, "  data     = ${Arrays.toString(this)}\n" +
                                   "  result   = $result\n" +
                                   "  expected = $expected\n")
  }

  private fun assertEquals<T>(actual : T, expected : T, message : Any? = null) {
    if (actual != expected) {
      errors++
      println("Test failed")
      val trace: Array<StackTraceElement> = Thread.currentThread().getStackTrace()
      if (trace.size > 6) {
        // Finding relevant stack frames
        val location = trace.getFrameAfter("runs.Tester", "expect")
        val function = trace.getFrameAfter("runs.TesterRunner", "forFunction")
        println("at ${function?.getClassName()}.${function?.getMethodName()}(line:${location?.getLineNumber()})")
      }
      if (message != null)
        println(message)
    }
    else if (!skipSuccessful)
      println("OK")
  }
}

fun Array<StackTraceElement>.indexOf(className : String?, methodName : String?) : Int? {
  for (i in indices) {
    val frame = this[i]
    if (frame.getClassName() == className && frame.getMethodName() == methodName)
      return i
  }
  return null
}

fun Array<StackTraceElement>.getFrameAfter(className : String?, methodName : String?) : StackTraceElement? {
  val index = indexOf(className, methodName)
  if (index == null) return null
  return this[index + 1]
}






アルゴリズムというか、期待値がわかりましたでしょうか。
僕ははじめは「重複した値を消した配列の長さ」を返せば良いのかと思いましたが、違いました。
「隣り合った値が異なる場合カウントアップ」した値を返すというのがこの問題の答えです。

で、僕が書いたのがこんなかんじです。


  ぼく




fun runs(a: IntArray): Int {  
    return a.answer({(i: Int): Boolean -> i + 1 < a.size && a.get(i) != a.get(i + 1) })
} 

fun IntArray.answer(filter: (i: Int) -> Boolean): Int {  
    var result =when (this.size) { 0 -> 0 else -> 1}  
    for (i in this.indices) if (filter(i)) result++ 
    return result
}

どうしても、returnのところをワンライナーで書きたくて考えましたが、なかなかダサい。
IntArrayというKotlinのクラスに対して拡張関数を使っています。
引数で渡されたfunctionを評価して該当したものをリターンするというイメージで作りましたが
あんまり汎用性無いですね。






僕があーだこーだ言ってたら、しおしおさんがめちゃくちゃアイデア出してくれました。


  しおしおさん1



fun runs(a : IntArray) : Int = a.zip(a.drop(1)).count { it.first != it.second } + when(a.size){ 0 -> 0 else -> 1}




素晴らしい。ワンライナーで書いてます。
zipとdropとcountを使っているのがポイントですね。

zip
zipで呼び出したインスタンスと引数をペアにします。この場合だとPair(key,value)の値を持ったListのようになります。
drop
引数の要素文切り落として配列を生成します。a.drop(1)だとIntArrayの1番目の要素を切り落としたIntArrayを返します。
count
要素数のカウントですね。関数を引数として渡すことで、条件式を満たす要素数を返してくれます。


実際の動きとしては
a が [1,2,3]だとすると
a.drop(1) は [2,3]
a.zip(a.drop(1)) は [1,2,3] + [2,3]で[(1, 2), (2, 3)]



  しおしおさん2



fun runs(a: IntArray): Int = a.withIndices().filter { a.drop(it.first + 1).head != it.second }.size



次は、withIndicesというのを使っています。しおしおさんの引き出し恐るべし。

withIndices
IntArrayを配列のindexと値のペアのリストに変換します。
filter
要素を絞りこみます。条件を満たす要素のみのオブジェクトをかえします。


実際の動きとしては
a が [1,2,3]だとすると
a.withIndices() は[(0, 1), (1, 2), (2, 3)]
filter内でindexに1を加算したものでdropします。この操作で「自分(it)の次の要素を先頭に持つ配列」を取得し、その1番目の要素と自分(it)の要素の値とを比較します。
※自分(it) = a.withIndices()
そして、filterで評価されたリストのサイズを取得します。



ただ、この処理だとfilter評価の際に毎回dropされます。ということは、配列のループが多く処理が遅くなってしまいます。
そこらへんを検討して、しおしおさん3が生まれましたw


  しおしおさん3



fun runs(a : IntArray) : Int {  
    return a.withIndices().count {when (it.first) { 0 -> true else -> a.get(it.first - 1) != it.second  } }
}




これは上手く考えて実装されていますね。
先ほどと同じようにwithIndicesして、初回は無条件でカウント、それ以降は前後を比較しています。
IndexOutOfBoundsを回避するためにどうしても分岐が必要になってしまいますね。






  しおしおさん3改良版



fun runs(a: IntArray): Int = a.withIndices().count { it.first == 0 || a.get(it.first - 1) != it.second}



[しおしおさん3]とほぼ同じですが、whenを使わずに分岐しているので更にシンプルになっています。





  しおしおさん4



fun runs(a: IntArray): Int = a.indices.count {when (it) { 0 -> true else -> a.get(it - 1) != a.get(it)}}




これも[しおしおさん3]と基本的な考え方は同じです。
ただ、withIndicesを使っていないため、無駄なオブジェクト生成が無く処理が効率化しています。

indicesはIntArrayが持つメンバ変数なので、IntArray生成時に設定されています。
indices変数はIntRange型であり、例えば、[1,2,3]というIntArrayであれば、
1..3とあらわすことが出来ます。




  しおしおさん5



fun runs(a: IntArray): Int = stream(a.toList(), {
    (l) -> l.dropWhile { it == l.first() } }).takeWhile { it.isNotEmpty() 
}.count()


これはかなり変態な書き方だと思います笑
IntArrayをリストにしてlambdaで書いていますね。
dropWhileでdropしたものとdropされる前のリストの先頭を順次比較しています。
dropWhileは文字通りdropしながらリスト分ループします。
takeWhileでリストが空になるまでループさせています。
結果的にtrueと評価された要素で構成されたリストが返されるので、それをcountしてリターンしています。



  しおしおさん6



fun class Ret(val count:Int, val prev:Int?) {
    fun next(number:Int) = if (prev == number)    Ret(count, number)     else    Ret(count + 1, number)
}

fun runs(a: IntArray): Int {  
    return a.fold(Ret(0, null), {(ret, num) ->    ret.next(num)  }).count
}


foldです。畳み込み関数というやつですね。




  たろうさん1



fun runs(a: IntArray): Int {
    return a.fold(Pair<Int?, Int>(null, 0), {       
         (pair : Pair<Int?, Int>, current : Int) : Pair<Int?, Int> -> val (last, count) = pair
         if(last != null && last == current ) Pair(current, count)
         else Pair(current, count + 1)
    }).second
}


ここでたろうさん登場!!
こちらもfoldを使っています。畳み込み関数です。
Pairを生成して比較しまくっています。




  たろうさん2



fun runs(a : IntArray) : Int {  
    return a.merge(a.prependNull()) {    (x, y) -> if(x == y) 0 else 1  }.sum()
} 

fun IntArray.prependNull(): List<Int?> { 
    val list = toLinkedList()  list.addFirst(null)  return list
}


最後、たろうさんの2つめです。
これ、かなり綺麗ですよね!!


配列を1つずらして、元の配列とずらした配列の各indexの要素を比較します。
比較して値が同じであれば0,違えば1の配列を生成し、最後に中の要素を加算します。
結果的に求めたい値になるというわけです。






正直、うまく解説出来ている気はしませんw
でも面白いですよね?

Web上に簡単にこうやって遊べる環境があるので皆様お試しください。
1つの問題を解決するにも色々な方法があることがわかりますね。

それに加えて、Kotlinが簡潔でFunctionalなことが出来る事も分かってもらえたと思います。

柔軟な言語ですよー。


完全に他力本願な記事をお送りいたしました笑



0 件のコメント:

コメントを投稿