油売り算(Prolog)

こういう問題にはきっと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のユーザが「関係ない」と言う以上に関係ないと思う