Skip to content

Instantly share code, notes, and snippets.

@ngsw-taro
Last active August 29, 2015 13:56
Show Gist options
  • Save ngsw-taro/9083207 to your computer and use it in GitHub Desktop.
Save ngsw-taro/9083207 to your computer and use it in GitHub Desktop.
Scala朝練
package com.taroid.scala.practice
import scala.collection.immutable.Queue
object OnePersonGame {
def main(args: Array[String]) {
import Operations._
test(solve(List()), List())
test(solve(List(5)), List(REMOVE))
test(solve(List(1)), List(HALF, REMOVE))
test(solve(List(1, 5)), List(REMOVE, HALF, REMOVE))
test(solve(List(1, 10)), List(HALF, REMOVE))
test(solve(List(1, 2)), List(HALF, HALF, REMOVE))
test(solve(List(9)), List(HALF, HALF, HALF, HALF, REMOVE))
}
private def test(a: Any, b: Any) {
println(if (a == b) "ok" else "ng")
}
/**
* 一人ゲームを解いて、その手順を返します。
*
* @param ints
* @return
*/
private def solve(ints: Seq[Int]): Seq[Operations] = solve(Queue((ints, List()))).reverse
/** 最短手順を返す (注: 操作手順は逆順) */
private def solve(queue: Queue[(Seq[Int], Seq[Operations])]): Seq[Operations] = {
assert(!queue.isEmpty, "あり得ないはず")
val (ints, operations) = queue.head
if (ints.isEmpty)
operations
else
solve(queue.tail
.enqueue((Operations.HALF(ints), Operations.HALF +: operations))
.enqueue((Operations.REMOVE(ints), Operations.REMOVE +: operations))
.sortWith(_._2.length < _._2.length))
}
/** 操作 */
object Operations {
/** 全ての数を半分にする操作(端数は切り捨て) */
case object HALF extends Operations(_.map(_ / 2))
/** 5の倍数を全て取り除く操作 */
case object REMOVE extends Operations(_.filter(_ % 5 != 0))
}
sealed abstract class Operations(f: Seq[Int] => Seq[Int]) {
def apply(ints: Seq[Int]): Seq[Int] = f(ints)
}
}

一人ゲーム

ルール

数がいくつか与えられます。なるべく少ない手数で数を全て取り除いてください。 あなたは一手で、

  • 全ての数を半分にする(端数は切り捨て)
  • 5 の倍数 (0 を含む) を全て取り除く

のどちらかの操作をすることができます。

@cb372
Copy link

cb372 commented Feb 19, 2014

Operationsのところは読みやすい全然悪くないですが、sealed abstract class OperationsFunction1[List[Int], [List[Int]] を差し替えてもいいですよね。sealed できなくなるけど。

  type op = Function1[List[Int], [List[Int]]

  object Operations {

    /** 全ての数を半分にする操作(端数は切り捨て) */
    case object HALF extends Op  {
      override def apply(ints: List[Int]): List[Int] = ints.map(_ / 2)
    }

    /** 5の倍数を全て取り除く操作 */
    case object REMOVE extends Op {
      override def apply(ints: List[Int]): List[Int] = ints.filter(_ % 5 != 0)
    }

  }

(コンパイル未検証)

@ngsw-taro
Copy link
Author

そ、そうなんですね。
ぬるぽるなら出来るだけ早く知らせようという意図でした。

@ngsw-taro
Copy link
Author

これで十分かなとも思いました。

  object Operations {
    val HALF = (_: List[Int]).map(_ / 2)
    val REMOVE = (_: List[Int]).filter(_ % 5 != 0)
  }

@gakuzzzz
Copy link

sealed できないのはやっぱ気になるので僕ならこうするかなー

sealed abstract class Operations(f: List[Int] => List[Int]) {
  def apply(ints: List[Int]): List[Int] = f(ints)
}

object Operations {

  /** 全ての数を半分にする操作(端数は切り捨て) */
  case object HALF extends Operations(_.map(_ / 2))

  /** 5の倍数を全て取り除く操作 */
  case object REMOVE extends Operations(_.filter(_ % 5 != 0))

}

@gakuzzzz
Copy link

_1 とかは避けられるなら避けといた方が読みやすい気がしてます。

private def solve(queue: Queue[(List[Int], List[Operations])]): List[Operations] = {
  val ints = queue.head._1
  val operations = queue.head._2
private def solve(queue: Queue[(List[Int], List[Operations])]): List[Operations] = {
  val (ints, operations) +: _ = queue

@gakuzzzz
Copy link

あとはやはりインターフェイスに List を使ってるのが気になっています。

List は Java でいうと ArrayList とかみたいな具象クラスの型なので、インターフェイス的に使うのであれば、Seq を使った方がいいかなと思います。 reverse も呼んでますし。

@ngsw-taro
Copy link
Author

ListSeqに置き換えてみました。
Operations.HALF +: operationsの部分が、Listの先頭要素の追加が速いことに頼っていたのですが、Seqにするとどんな実装が来るかわからないので「先頭に追加して最後にリバース」をやめて単に「最後に追加」でいいですかね?

@gakuzzzz
Copy link

Operations.HALF +: operationsの部分が、Listの先頭要素の追加が速いことに頼っていたのですが、Seqにするとどんな実装が来るかわからないので「先頭に追加して最後にリバース」をやめて単に「最後に追加」でいいですかね?

あー確かに悩ましいですね。標準Collectionに関しては、先頭に追加するのが遅いものもありますし(ex. ArrayBuffer)末尾に追加するのが遅いものもありますし。

ただ、実体として渡してるのがList()と判ってるので「先頭に追加して最後にリバース」のままで良さそうな気もします。

@gakuzzzz
Copy link

@ngsw-taro
Copy link
Author

おおお!これは便利!ありがとうございます

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment