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 を含む) を全て取り除く

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

@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