こういう問題にはきっとPrologが一番(わざと変な言語で実装する心の余裕がないときは特に)
「キミならどう書く 2.0 – 2007 – その 1」より
斗桶 (a) に油が 1 斗 (10 升) ある。これを等分したい。7 升枡 (b) と 3 升枡 (c) しかない。この 2 つの枡だけで、5 升ずつ等分する方法を記述せよ。
ふだんProlog使わないから覚えてないなあ、と言い訳しながら「お気楽 Prolog プログラミング入門」あたりを参考に実装(oil.pl)
moveは順番にAからB、AからC、BからA、BからC、CからA、CからB
move(M,_,[A,B,C],[D,E,C]) :- (A<(M-B) -> D=0,E is A+B ; E=M,D is A+B-M).
move(_,S,[A,B,C],[D,B,F]) :- (A<(S-C) -> D=0,F is A+C ; F=S,D is A+C-S).
move(_,_,[A,B,C],[D,E,C]) :- (E=0,D is A+B).
move(_,S,[A,B,C],[A,E,F]) :- (B<(S-C) -> E=0,F is B+C ; F=S,E is B+C-S).
move(_,_,[A,B,C],[D,B,F]) :- (F=0,D is A+C).
move(M,_,[A,B,C],[A,E,F]) :- (C<(M-B) -> F=0,E is B+C ; E=M,F is B+C-M).
safe(M,S,[A,B,C]) :- 0=<A, 0=<B, B=<M, 0=<C, C=<S.
search(L,M,S) :- depth_search(L,M,S,[[L,0,0]]).
depth_search(L,_,_,[State|History]) :- X is L/2, State==[X,X,0], !, print_answer([State|History]).
depth_search(L,M,S,[State|History]) :-
move(M,S,State,NewState),
safe(M,S,NewState),
not(member(NewState,[State|History])),
depth_search(L,M,S,[NewState,State|History]).
print_answer([]) :- !.
print_answer([State|Rest]) :- print_answer(Rest),write(State),nl.
SWI-Prolog(Cygwinにも入ってる)なら、シェルから「pl」で起動して、
?- [oil]. % oil compiled 0.02 sec, 4,572 bytes Yes ?- search(10,7,3). [10, 0, 0] [3, 7, 0] [0, 7, 3] [7, 0, 3] [7, 3, 0] [4, 3, 3] [4, 6, 0] [1, 6, 3] [1, 7, 2] [8, 0, 2] [8, 2, 0] [5, 2, 3] [5, 5, 0] Yes
出力形式が違うけど、まあ、答えがわかればいいってことで(手抜き)
safeがあるのだから、moveは次のように書いても大丈夫
move(_,_,[A,B,C],[D,E,C]) :- D=0,E is A+B. move(M,_,[A,B,C],[D,E,C]) :- E=M,D is A+B-M. move(_,_,[A,B,C],[D,B,F]) :- D=0,F is A+C. move(_,S,[A,B,C],[D,B,F]) :- F=S,D is A+C-S. move(_,_,[A,B,C],[D,E,C]) :- E=0,D is A+B. move(_,_,[A,B,C],[A,E,F]) :- E=0,F is B+C. move(_,S,[A,B,C],[A,E,F]) :- F=S,E is B+C-S. move(_,_,[A,B,C],[D,B,F]) :- F=0,D is A+C. move(_,_,[A,B,C],[A,E,F]) :- F=0,E is B+C. move(M,_,[A,B,C],[A,E,F]) :- E=M,F is B+C-M.
ちなみに、SWI-PrologはThe Computer Language Benchmarks Gameではダントツの最下位だけど、ブービーであるRubyのユーザが「関係ない」と言う以上に関係ないと思う