スポンサーサイト

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

油分け算

CATEGORYruby
「油分け算」なんてキーワードで検索に来てる人がいた。
レシピばっか書いてるから、「油」にゃあ反応するわね。

気になって、ちょっと検索してみた。
『油分け算』

これ、問題自体は知ってるけど、「油分け算」って言うんだねぇ。

検索で来た人は、ソースを探してたみたい。気になるじゃない :-)


しばらくコードを書いてないし、冬休みの自由研究のつもりで書いてみた。

プログラムで解くので、まずは、基本の力ずく。
  • ある状態から取りうる手の数は、升の数×(升の数-1) しかない
  • 空の升からは移せない
  • 移し先の升に空きがなければ移せない
  • 移した後の状態が、過去に試した状態になっていればあきらめる (ループするから)
で、選択肢を絞り込んで、正解の状態になるまで繰り返しチャレンジする。

ruby で書いてみたソースコードは、こんな感じ。
=begin

	油分け算

=end


class Bottle
	attr_accessor :q
	def initialize name, m, q = 0
		@name = name
		@m = m
		@q = q
	end

	#
	# この Bottle から dest に、中身を注ぐ
	# 注げたら true を返す
	#
	def pour_into dest
		return false if empty?
		return false if dest.full?
		d = 0
		if dest.available > self.q then
			d = self.q
		else
			d = dest.available
		end
		self.q -= d
		dest.q += d
		return true
	end

	def available
		@m - @q
	end

	def empty?
		@q == 0
	end

	def full?
		available == 0
	end

	def name
		n = @name
		n << "    "
		n.sub! /^(...).*/, '\1'
	end

	def to_s
		"#{@q}"
	end

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


class Status
	def initialize s
		@bottles = Array.new
		s.each { |i|
			@bottles << i.clone
		}
	end

	#
	# Bottle A から B に、中身を注ぐ
	#
	def pour a, b, debug = false
		a = bottle(a)
		b = bottle(b)
		puts "#{a.name} → #{b.name}"		if debug
		a.pour_into(b)
	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 to_s
		@bottles.collect { |b| b.name }.join(',') + " = [#{@bottles.collect { |b| format('%2d', b.q) }.join(',')}]"
	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
end


class Engine
	def initialize
		@answer = []
		@start = nil
	end

	def challenge start, &check_block
		@start = start.clone
		challengeImpl [start], [], start, &check_block
	end

	def challengeImpl status_history, pour_history, s, &check_block
		if yield(s) then
			@answer << pour_history.clone
		else
			(0..2).each { |i|
				(0..2).each { |j|
					next	if i == j
					s2 = s.clone
					next	unless s2.pour i, j
					next	if status_history.include? s2
					challengeImpl(status_history + [s2], pour_history + [[i, j]], s2, &check_block)
				}
			}
		end
		return false
	end

	def printAnswer verbose = false
		# 手順が短い順に並べ替える
		@answer.sort! { |a, b|
			a.length <=> b.length
		}
		# 冗長な解を切り捨てる
		unless verbose then
			(0 ... @answer.length).each { |i|
				next    if @answer[i].nil?
				a = @answer[i]
				(i+1 ... @answer.length).each { |j|
					next    if @answer[j].nil?
					b = @answer[j]
					#  ※これだけじゃ、切り捨てが甘い!
					if a == b[b.length - a.length, a.length] then
						@answer[j] = nil
					end
				}
			}
			@answer.compact!
		end

		puts "■解は #{@answer.length} 通り"
		@answer.each { |a|
			s = @start.clone
			puts "\n\n★#{a.length} 手"
			puts "              #{s}"
			a.each { |h|
				from = h[0]
				to   = h[1]
				s.pour from, to
				puts "#{s.bottle(from).name} → #{s.bottle(to).name}  : #{s}"
			}
			puts ""
		}
	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
cc.challenge(start) { |s| ok.call(s) }
cc.printAnswer

んー、イマイチ。
  • 升を表すクラス (Bottle) がダラダラと長くなっちゃった
  • 短い解を冗長にするような解まで拾っちゃう (多少、刈るようにしてみた)
  • 再帰で解いてるのに、その過程を二つも引数で受け継いでるのがかっこ悪い

10升から、7升と3升の升で、5升ずつに分ける問題で、求められた解のうち、短いほうから二つを。

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

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


んー、60点。
関連記事
スポンサーサイト

油分け算 ruby

0 Comments

Leave a comment

1 Trackbacks

Click to send a trackback(FC2 User)
この記事へのトラックバック
  •  油分け算(その2)
  • 「油分け算」なんてキーワードで検索に来てる人がいた。 レシピばっか書いてるから、「油」にゃあ反応するわね。 ... しばらくコードを書い...
  • 2010.01.06 (Wed) 23:54 | それって食えるのか?
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。