スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

油分け算(その2)

CATEGORYruby

「油分け算」なんてキーワードで検索に来てる人がいた。
レシピばっか書いてるから、「油」にゃあ反応するわね。
...
しばらくコードを書いてないし、冬休みの自由研究のつもりで書いてみた。
...
んー、イマイチ。
油分け算


やっぱり、気になって仕方ない。
仕事中に改善してみた :-p

  • 深さ優先じゃなく、幅優先で探してみる
  • 「手」のリストじゃなくて、探索経路全体をグラフで持つ
幅優先にすることで、探索が(不細工な)再帰じゃなくなったことと、 最短手の途中に至るような冗長な解を排除することができる。

求められた解は
■解は 2 通り

★9 手
              v10,v7,v3 = [10, 0, 0]
v10 → v7   : v10,v7,v3 = [ 3, 7, 0]
v7  → v3   : v10,v7,v3 = [ 3, 4, 3]
v3  → v10  : v10,v7,v3 = [ 6, 4, 0]
v7  → v3   : v10,v7,v3 = [ 6, 1, 3]
v3  → v10  : v10,v7,v3 = [ 9, 1, 0]
v7  → v3   : v10,v7,v3 = [ 9, 0, 1]
v10 → v7   : v10,v7,v3 = [ 2, 7, 1]
v7  → v3   : v10,v7,v3 = [ 2, 5, 3]
v3  → v10  : v10,v7,v3 = [ 5, 5, 0]


★10 手
              v10,v7,v3 = [10, 0, 0]
v10 → v3   : v10,v7,v3 = [ 7, 0, 3]
v3  → v7   : v10,v7,v3 = [ 7, 3, 0]
v10 → v3   : v10,v7,v3 = [ 4, 3, 3]
v3  → v7   : v10,v7,v3 = [ 4, 6, 0]
v10 → v3   : v10,v7,v3 = [ 1, 6, 3]
v3  → v7   : v10,v7,v3 = [ 1, 7, 2]
v7  → v10  : v10,v7,v3 = [ 8, 0, 2]
v3  → v7   : v10,v7,v3 = [ 8, 2, 0]
v10 → v3   : v10,v7,v3 = [ 5, 2, 3]
v3  → v7   : v10,v7,v3 = [ 5, 5, 0]

改善したソースコード (やっぱり Ruby) は、こんな感じ。
=begin

	油分け算

=end


class Bottle
	attr_reader :name
	attr_accessor :q
	def initialize name, c, q = 0
		@name, @capacity, @q = name, c, q
	end

	def available
		@capacity - @q
	end

	def empty?
		@q == 0
	end

	def full?
		available == 0
	end

	def to_s
		"#{@name}:#{@q}/#{@capacity}"
	end

	def == b
		@q == b.q && @name == b.name
	end

end


class Status
	attr_accessor :cause		# Choice
	def initialize bottles
		@bottles = bottles.collect { |b| b.clone }
		@cause = nil
	end

	def bottle index
		@bottles[index]
	end

	def index_of name
		@bottles.each_with_index { |b, i|
			return i   if b.name == name
		}
		return nil
	end

	def bottle_names
		@bottles.collect { |b| b.name }
	end

	def bottle_amounts
		@bottles.collect { |b| b.q }
	end

	def bottle_count
		@bottles.length
	end

	def clone
		Status.new @bottles
	end

	def == s
		@bottles.each_with_index { |b, i|
			return false    if b != s.bottle(i)
		}
		return true
	end

	def eql? s
		self == s
	end

	def hash
		if @hash.nil? then
			h = 1
			bottle_amounts.each { |v| h = h * 31 + v }
			@hash = h
		end
		@hash
	end

	def to_s
		@bottles.collect{ |b| "(#{b})"}.join(',')
	end
end


class Choice
	attr_reader (:from, :to, :before, :after)
	def initialize before, from, to
		@from, @to = from, to				# bottle index
		@before, @after = before, nil		# Status
	end

	#
	# Bottle A から B に、中身を注ぐ
	#
	def pour
		@after = nil
		return self    if @from == @to
		s = @before.clone
		from, to = s.bottle(@from), s.bottle(@to)
		unless from.empty? || to.full? then
			d = min from.q, to.available
			from.q -= d
			to.q   += d
			@after = s
			@after.cause = self
		end
		self
	end

	def success?
		! @after.nil?
	end

	def to_s
		"#{from} --> #{to}"
	end

private
	def min a, b
		a > b ? b : a
	end

end


class Engine

	def search_answer start
		answer = Array.new
		status_map = Hash.new
		next_target = [ start.clone ]
		n = start.bottle_count

		until next_target.empty?

			target, next_target = next_target, Array.new

			target.each { |s|

				if yield(s) then
					answer << get_history_to (s)

				elsif ! status_map.include? s then
					status_map[s] = s
					n.times { |i|   n.times { |j|
						choice = Choice.new (s, i, j)
						if choice.pour.success? then
							next_target << choice.after
						end
					} }
				end
			}
		end

		return answer
	end

	def get_history_to goal
		history = Array.new
		s = goal
		until s.cause.nil?
			history << s.cause
			s = s.cause.before
		end
		history.reverse!
	end


	def printAnswer answer

		puts "■解は #{answer.length} 通り"
		answer.each { |a|
			puts "\n\n★#{a.length} 手"
			puts "              #{status_to_s(a[0].before)}"
			a.each { |choice|
				puts "#{choice_to_s(choice)}  : #{status_to_s(choice.after)}"
			}
			puts ""
		}
	end

private
	def bottle_name b
		(b.name + "       ")[0, 3]
	end
	def choice_to_s ch
		bf = ch.before
		"#{bottle_name(bf.bottle(ch.from))} → #{bottle_name(bf.bottle(ch.to))}"
	end
	def status_to_s st
		st.bottle_names.join(',') +
		" = [#{st.bottle_amounts.collect { |a| format('%2d', a) }.join(',')}]"
	end
end






#	(1)桶に油が10升入っています。
#	  これを7升のますと3升のますを用いて、5升ずつに分けてください。
#	  方法は2通りあります。

start = Status.new [Bottle.new('v10', 10, 10), Bottle.new('v7', 7), Bottle.new('v3', 3)]
ok = lambda { |s|
		(s.bottle(0).q == 5 && s.bottle(1).q == 5) ||
		(s.bottle(1).q == 5 && s.bottle(2).q == 5) ||
		(s.bottle(2).q == 5 && s.bottle(0).q == 5)
	}


#	(2)桶に油が8升入っています。
#	  これを5升のますと3升のますを用いて、4升ずつに分けてください。
#	  方法は2通りあります。

#start = Status.new [Bottle.new('v8', 8, 8), Bottle.new('v5', 5), Bottle.new('v3', 3)]
#ok = lambda { |s|
#		(s.bottle(0).q == 4 && s.bottle(1).q == 4) ||
#		(s.bottle(1).q == 4 && s.bottle(2).q == 4) ||
#		(s.bottle(2).q == 4 && s.bottle(0).q == 4)
#	}


#	桶に油がたくさん入っています。
#	7升のますと4升のますを用いて、10升の油をはかってください。

#start = Status.new [Bottle.new('', 99999, 99999), Bottle.new('v7', 7), Bottle.new('v4', 4)]
#ok = lambda { |s|
#		s.bottle(1).q + s.bottle(2).q == 10
#	}


#	 桶に油がたくさん入っています。
#	23升のますと15升のますを用いて、3升の油をはかってください。

#start = Status.new [Bottle.new('', 99999, 99999), Bottle.new('v23', 23), Bottle.new('v15', 15)]
#ok = lambda { |s|
#		s.bottle(1).q + s.bottle(2).q == 3
#	}



cc = Engine.new
answer = cc.search_answer(start) { |s| ok.call(s) }
cc.printAnswer answer


探索途中で、冗長な解の候補を捨てることができるので、ちょっと時間がかかってた最後の問題も、 すんなり解けるようになってる :-)


もし、仕事だったとしたら、
  • Status のアクセッサは、結果をキャッシュしておく
  • 探索候補は、二重ループじゃなくて、最初に順列で求めておいて、イテレータでまわす
って、感じにするかな。

今、やってる仕事は、こういうタイプのプログラムを書く機会があまりないけど、 こういう「アルゴリズム」っぽいプログラムは、面白いね。
関連記事
スポンサーサイト

油分け算 ruby

0 Comments

Leave a comment

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。