jijixi's diary - キミならどう書く 2.0 - 2007 - その 1 (問題 1 : 油売り算) ほか経由で、Karetta|キミならどう書く 2.0 - 2007 - その 1 より。
斗桶 (a) に油が 1 斗 (10 升) ある。これを等分したい。7 升枡 (b) と 3 升枡 (c) しかない。この 2 つの枡だけで、5 升ずつ等分する方法を記述せよ。
答を寄せている関連エントリー群を徘徊していて、遅まきながら幅優先探索という便利なものを知ったり、バックトラックが許されるのは小学生までなのか！ｗ…と驚いたりしたので、ならばと覚え立ての幅優先探索を使って Squeak Smalltalk でチャレンジ。関数にすることや引数や出力について出題の指示をまったく無視している点は、どうぞあしからず(^_^;)。
なお、幅優先探索の実装のしかたについてはこちらを参考にさせていただきました。
| start goal set queue curr | start := {10->10. 7->0. 3->0} as: Dictionary. goal := {10->5. 7->5. 3->0} as: Dictionary. set := Set with: start. queue := OrderedCollection with: (OrderedCollection with: start). [queue notEmpty and: [(curr := queue removeFirst) last ~= goal]] whileTrue: [ curr last associationsDo: [:assoc | (curr last associations copyWithout: assoc) do: [:dest | | delta next | next := curr last deepCopy. delta := assoc value min: dest key - dest value. next at: assoc key put: (next at: assoc key) - delta. next at: dest key put: (next at: dest key) + delta. (set includes: next) ifFalse: [ set add: next. queue add: (curr copyWith: next)]]]]. World findATranscript: nil. curr allButFirst inject: curr first into: [:prev :each | Transcript cr; show: {each values - prev values. each associations}. each]
set に要素を #includes: でその存在を問いただしてから改めて #add: するのは、Set>>#add: がやっていることを思うと少々気持ちが悪いですが、なにぶん適切なメソッドが見あたらなかったので…。
出力はこんなかんじ。
{#(-7 7 0) . {10->3 . 7->7 . 3->0}}
{#(0 -3 3) . {10->3 . 7->4 . 3->3}}
{#(3 0 -3) . {10->6 . 7->4 . 3->0}}
{#(0 -3 3) . {10->6 . 7->1 . 3->3}}
{#(3 0 -3) . {10->9 . 7->1 . 3->0}}
{#(0 -1 1) . {10->9 . 7->0 . 3->1}}
{#(-7 7 0) . {10->2 . 7->7 . 3->1}}
{#(0 -2 2) . {10->2 . 7->5 . 3->3}}
{#(3 0 -3) . {10->5 . 7->5 . 3->0}}
そういえば、似たような問題がこないだテレビでやっていた『ダイハード３』に出ていたなぁ…と思い出したので、同じスクリプトでそれも解いてみます。「５ガロンと３ガロンの入れ物で４ガロンを作れ」というもの。水を汲んできたり捨てたりする先を Float infinity な入れ物と見なすと原則そのまま表現できるのですが、ただ、Float infinity 同士の引き算で出てくる Float nan が悪さをしないように一行追加してあります。
| start goal set queue curr |
{#(NaN 5 0) . {Infinity->Infinity . 5->5 . 3->0}}
{#(NaN -3 3) . {Infinity->Infinity . 5->2 . 3->3}}
{#(NaN 0 -3) . {Infinity->Infinity . 5->2 . 3->0}}
{#(NaN -2 2) . {Infinity->Infinity . 5->0 . 3->2}}
{#(NaN 5 0) . {Infinity->Infinity . 5->5 . 3->2}}
{#(NaN -1 1) . {Infinity->Infinity . 5->4 . 3->3}}
例によって Ruby でも直訳気味に。
start = {10=>10, 7=>0, 3=>0}
goal = {10=>5, 7=>5, 3=>0}
a = [start]
q = [[start]]
while !q.empty? && (c = q.shift).last != goal
c.last.each_pair do |sk,sv|
(c.last.to_a - [[sk,sv]]).each do |(dk,dv)|
n = c.last.dup
d = [sv, dk - dv].min
n[sk] -= d
n[dk] += d
if !a.include?(n) then
a << n
q << c + [n]
end
end
end
end
c.inject do |pv,ea|
p [ea.values.zip(pv.values).map{ |a,b| a-b }, ea.to_a]
ea
end
ただ、Ruby の Set はどうやら腐っているっぽい…
require 'set' s = Set.new s << {} #=> #<Set: {{}}> s << {} #=> #<Set: {{}, {}}>
のと、まあ、Set を使うほどの問題でもないだろうということで Array で代用しています。
[[7, 0, -7], [[7, 7], [3, 0], [10, 3]]] [[-3, 3, 0], [[7, 4], [3, 3], [10, 3]]] [[0, -3, 3], [[7, 4], [3, 0], [10, 6]]] [[-3, 3, 0], [[7, 1], [3, 3], [10, 6]]] [[0, -3, 3], [[7, 1], [3, 0], [10, 9]]] [[-1, 1, 0], [[7, 0], [3, 1], [10, 9]]] [[7, 0, -7], [[7, 7], [3, 1], [10, 2]]] [[-2, 2, 0], [[7, 5], [3, 3], [10, 2]]] [[0, -3, 3], [[7, 5], [3, 0], [10, 5]]]
