Scala朝練

OnePersonGame.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)
  }

}

rule.md

一人ゲーム

ルール

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

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

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

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

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

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

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

この表おすすめです。
http://docs.scala-lang.org/ja/overviews/collections/performance-characteristics.html

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