バケツ問題

某プログラム勉強会で、お題が出たので解いてみる。

問題

水がいっぱい入ったバケツ一個と、空のバケツがいくつかあり、それぞれのバケツの容量は正確にわかっている。この状態から指定された容量を量りとる、最

小手数の手順を求めよ。

ただし

・バケツからバケツに水を移す操作を１手と数える。

・バケツからバケツに水を移す際は、注がれるバケツがいっぱいになるか、注ぐバケツが空になるまで行う。

・従って、水は一滴も漏れない。

例えば。バケツが4つ。10リットル,8リットル,3リットル。10リットルのバケツが満タンで、あとは空っぽ。ここから4リットル量りとりたい。

最小手数の手順は

　10リットルのバケツから、3リットルのバケツに注ぐ

　3リットルのバケツから、8リットルのバケツに注ぐ

　10リットルのバケツから、3リットルのバケツに注ぐ

の3手（要するに、10リットルから3リットルを2回減じている）となる。

表示を短くするために、バケツに順に 0, 1, 2 と番号を振ると、

  0→2, 2→1, 0→2

と、表示することができる。 

最初の状態から、他のバケツに注いだ状態、さらに他のバケツに注いだ状態と遷移させて状態を評価、解が出たら停止すればよい。
ただし、状態Ａ→状態Ｂ→状態Ａとなると永久に終了しないので、過去に評価した状態は記憶しておき同じ状態を繰り返さないようにする。
あと、状態Ａ→状態Ｂ→状態Ｃと縦型探索をすると、状態Ａ→状態Ｃという最適解を見逃してしまうので横型探索をする。

def solve(target, buckets)
  done = {}                                                      # 評価済みの状態保持用
  cur_fill = [["", [buckets.first] + [0] * (buckets.size - 1)]]  # 現在の状態
  while (!cur_fill.empty?)
    next_fill = []                                               # 生成された次の状態保存用
    cur_fill.each do |record, fill|
      buckets.size.times do |i|
        next if fill[i] == 0
        buckets.size.times do |j|
          next if i == j
          next if fill[j] == buckets[j]
          mv_vol = [fill[i], buckets[j] - fill[j]].min
          new_fill = fill.clone
          new_fill[i] -= mv_vol
          new_fill[j] += mv_vol
          next if done[new_fill]
          done[new_fill] = true
          new_record = record + " #{i}→#{j}"
          if new_fill[i] == target or new_fill[j] == target
            puts "#{new_record.chars.count('→')} 手 :#{new_record}"
            return
          end
          next_fill << [new_record, new_fill]
        end
      end
    end
    cur_fill = next_fill
  end
  puts "***解なし***"
end

val, *elem = ARGV.map(&:to_i)
solve(val, elem)

同様のアルゴリズムのscala実装。
なぜかruby版より、かなり遅い。オブジェクトの生成回数が多いのがネックなのか。

object Bucket {
  import scala.collection.mutable.HashMap
  import scala.collection.mutable.Stack
  def main(args: Array[String]) {
    args.map(_.toInt).toList match {
      case x::xs => println(solve(x, xs))
      case _ => println("argument error")
    }
  }

  case class Bucket(id:Int, size:Int, fill:Int)
  case class State(parent:State, buckets:List[Bucket]) {
    def key:List[Int] = buckets.sort((a,b) => a.id < b.id).map(_.fill)
    def record:String = {
      if (parent == null) return ""
      var dst, src = 0
      var mv = parent.key.zip(key).zip(List.range(0,buckets.size))
      for (((a, b),i) <- mv if a != b) yield {
        if (a > b) src = i else dst = i
      }
      parent.record + " " + src.toString + "->" +dst.toString
    }
  }

  def solve(ans:Int, buckets:List[Int]):String = {
    val done = new HashMap[List[Int], Boolean]
    var curStates = new Stack[State]
    var rootState = Array.fromFunction(i => new Bucket(i, buckets(i), if (i==0) buckets(0) else 0))(buckets.size).toList
    curStates.push(new State(null,rootState))
    while (!curStates.isEmpty) {
      var nextStates = new Stack[State]
      for (cs <- curStates) yield {
        for (src <- cs.buckets if src.fill > 0; dst <- cs.buckets if dst.size > dst.fill && src != dst) yield {
          var mvVol = Math.min(src.fill, dst.size - dst.fill)
          var newSrc = new Bucket(src.id, src.size, src.fill - mvVol)
          var newDst = new Bucket(dst.id, dst.size, dst.fill + mvVol)
          var newState = new State(cs, newSrc::newDst::cs.buckets.filter((bc) => bc != src && bc != dst))
          var key = newState.key
          if (!done.contains(key)) {
            done.put(key, true)
            if (newSrc.fill == ans || newDst.fill == ans) return newState.record
            nextStates.push(newState)
          }
        }
      }
      curStates = nextStates
    }
    "no answer"
  }
}