なんかネタをふられました．

はじめてのにき (2008-08-13) _ 棒けしゲーム

ニコニコ見れない人なので，テキトーに棒消しゲームの仕様を検索．

とりあえず swi-prolog で仕様を書いてみました．ET と Prolog と，確定節で書く限り，問題の表現能力自体に差はありません．そこから先，どういう仕様に対して正しい手続きを議論できるのか，は変わりますが．

% 棒消し(山の大きさ，ゲーム展開，結果)
% ゲーム展開 = 棒消し操作の情報 (X 番目の列の Y 番目から連続 Z 本消した) の列
% 自分は必ず先手
boukeshi(N, Os, R) :- initState(N, S), printState(N, S), !, me(S, N, Os, R).

% 自分とコンピュータで交互にプレイ
me(S, _, [], R) :- dropGame(S), R = lose, !.
me(S, N, [O | Os], R) :- choice(S, N, O), com(S, N, Os, R).
com(S, _, [], R) :- dropGame(S), R = win, !.
com(S, N, [O | Os], R) :- choice(S, N, O), me(S, N, Os, R).

% 行の非決定的な選択(状態, 行番号, [何列目の，何行目を，連続何本倒したか])
choice([S | _], N, [N, Y, Z]) :- kesu(S, 1, Y, Z).
choice([_ | Ss], N, O) :- N1 is N - 1, choice(Ss, N1, O).

% 非決定的印に棒をどこか消す （変数をテキトウに具体化）
kesu([R | Rs], N, N, Z) :- var(R), R = ' ', renzokuKeshi(Rs, 0, Z).
kesu([_ | Rs], N, Y, Z) :- N1 is N + 1, kesu(Rs, N1, Y, Z).

% 連続して非決定的に何本か消す
renzokuKeshi(_, N, N).
renzokuKeshi([R | Rs], N, Z) :- var(R), R = ' ', N1 is N + 1, renzokuKeshi(Rs, N1, Z).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%% misc %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 最大 N 行の棒山を作る
initState(0, []).
initState(N, [R | Rs]) :- makeRow(N, R), N1 is N - 1, initState(N1, Rs).

makeRow(0, []).
makeRow(N, [_ | R]) :- N1 is N - 1, makeRow(N1, R).

% 棒山の表示
printState(N, S) :- printState1(N, N, S), printRow0(N), print('\n----------\n').

printRow0(0) :- print(' ').
printRow0(N) :- N1 is N - 1, printRow0(N1), print(N).

printState1(_, _, []).
printState1(N, N1, [R | Rs]) :- N2 is N1 -1, printState1(N, N2, Rs), print(N1), printRow(R).

printRow([]) :- !, print('\n').
printRow([X | Xs]) :- var(X), print('|'), printRow(Xs).
printRow([_ | Xs]) :- print(' '), printRow(Xs).

% 終了判定．最後の棒（変数）だったら負け
dropGame(S) :- nvar(S, 0, N), N = 1, !.

% nvar(Term, に含まれる変数の数)
nvar([], N, N).
nvar([R | Rs], A, N) :- nvar1(R, A, A1), nvar(Rs, A1, N).

nvar1([V | Rs], A, N) :- var(V), !, A1 is A + 1, nvar1(Rs, A1, N).
nvar1([_ | Rs], A, N) :- nvar1(Rs, A, N).
nvar1([], N, N).

可能な状態空間を全て表示するだけです．

?- boukeshi(2, Os, R).
1|
2||
12
----------
Os = [[2, 1, 0], [2, 2, 0]],
R = lose ;
Os = [[2, 1, 0], [1, 1, 0]],
R = lose ;
Os = [[2, 1, 1]],
R = win ;
Os = [[2, 2, 0], [2, 1, 0]],
R = lose ;
Os = [[2, 2, 0], [1, 1, 0]],
R = lose ;
Os = [[1, 1, 0], [2, 1, 0]],
R = lose ;
Os = [[1, 1, 0], [2, 2, 0]],
R = lose ;
false.

あとは，どの手が良いかを評価する関数を作って，全通り計算しまくれば解けるはず．対戦ゲームの思考ルーチンとか書いたこと無いので，これ以上はパッと思いつきませんが，たぶん minmax 法とかそういうやつを使って，全ての手数に対して勝った負けたをボトムアップに積み上げて行って，値が最大になる手を常に選択していけば，たぶん必ず先手が勝てるのではないでしょうか ? (そのうち実装してみます．ナイーブに書くと，山の行の数が最大 5 でも状態数が多すぎて解けないかもしれないけど)

---

Prolog って何となく SWI-Prolog みたいなインタプリタや抽象マシンコードコンパイラしか無いような認識の人が多いみたいですが，一応フリーの実装でもスタンドアローン吐けるネイティブコンパイラがあるみたいです．

出るコードの質はよくわかりませんが，たぶん Perl とか Ruby よりは速いんじゃないでしょうか (笑)
Perl6 から Rules っていうパーサ DSL みたいなのが入るらしく，その能力はよくわかりませんが，Prolog のパーサ DSL である DCG (確定節文法) 記述は，計算可能な文法は全て記述できる (チョムスキー階層のタイプ 0 文法，制限無し文法．チューリングマシンが受理できる全ての言語を含む，帰納的可算言語というクラスらしい) そうなので，Perl など相手になりませんね :-)

The GNU Prolog web site

適当に，さっき見かけた言語ゲームさんの Verilog HDL っぽい Prolog コードをコンパイルしてみます (ちなみに，非常に Perl と紛らわしいですが，拡張子は pl じゃないとダメみたいです…)．

$ cat and.pl

% A Logic Gate for 3 + 4
%
% ?- add3bit([0, 1, 1], [1, 0, 0], Sum).

% Primitive Gates (Output, Input, ...)
and(0, 0, 0).
and(0, 1, 0).
and(0, 0, 1).
and(1, 1, 1).

or(0, 0, 0).
or(1, 1, 0).
or(1, 0, 1).
or(1, 1, 1).

not(1, 0).
not(0, 1).

% Half Adder
halfAdder(Carry, Sum, A, B) :-
    and(Carry, A, B),
    or(X, A, B),
    not(Y, Carry),
    and(Sum, X, Y).

% Full Adder
fullAdder(Carry, Sum, A, B, C) :-
    halfAdder(C1, X, A, B),
    halfAdder(C2, Sum, X, C),
    or(Carry, C1, C2).

% 3 Bit Addr
add3bit([Sum2, Sum1, Sum0], [A2, A1, A0], [B2, B1, B0]) :-
    halfAdder(C0, Sum0, A0, B0),
    fullAdder(C1, Sum1, A1, B1, C0),
    fullAdder(_, Sum2, A2, B2, C1).


$ gplc and.pl
$ ./and
GNU Prolog 1.2.18
By Daniel Diaz
Copyright (C) 1999-2004 Daniel Diaz
| ?- add3bit([0, 1, 1], [1, 0, 0], Sum).

Sum = [1,1,1] ? ;

no
| ?- halt.

Scheme とか Haskell とかをコンパイルすると，わりと巨大なランタイムがリンクされる気がしますが，gprolog は不要なビルトインの削除をがんばっているらしく，比較的サイズも小さく，ライブラリ依存も無い感じです．

$ ldd ./and
linux-gate.so.1 => (0xffffe000)
libm.so.6 => /lib/i686/cmov/libm.so.6 (0xb7efc000)
libc.so.6 => /lib/i686/cmov/libc.so.6 (0xb7dae000)
/lib/ld-linux.so.2 (0xb7f39000)

$ du -h ./and
853K ./and

いや，十分でかいか… まぁ，PyInstaller とか py2exe よりは小さいはず (そればっか)

細かいオプションとかは，マニュアルを参考にしてみてください．

Prolog のコンパイルスキームとかも解説してあって，なかなか面白いと思います．

基本的には，Prolog → WAM (Warren's Abstract Machine) コード → 抽象アセンブリコード → 実アセンブリみたいな流れで，それぞれのステージごとにコードを出せます．FD (有限領域) 制約ソルバーとかは，別パスで C 経由でコンパイル・リンクされるようです．

余談ですが，Prolog と一口に言っても，古典的な純 Prolog ってのは現在ではほとんど無くて，CLP(FD) （有限領域上の制約論理プログラミング言語) とか CHR とか，いろんな制約(データ構造) を対象とした言語やライブラリの複合体みたいな感じの言語族になってるのが普通です (C++ みたいなもん．Prolog をベースに，いろんな拡張パラダイムがパッチワークになってる）．んで，そこらへんが混沌としてきて見通しが悪くなってきたので，データ構造や制約解消アルゴリズムに依存しない，一般的な計算理論を作ろうというモチベーションで生まれたのが，等価変換(ET) の理論です (という歴史的な流れがあったりも)

---

今日の twitter でも @m0h1can という偉大な prologer によって多くの名言が生まれました．新しい言語を覚える際に最も優れた方法は，その言語で書かれたポルノ小説を読むことだそうで，まっことエロスの力は偉大ですね．

これは素晴らしい他言語紹介．次のるびまに載るね！

m0h1can twitterだけ見てる人はprologという処理系をエロゲか何かと間違わないか心配でなりません

m0h1can prologというのは"バック"したりしながら、一体化を行う事で快を求めるプログラミング言語です

m0h1can 他の言語で"バック"トラックする言語はそうそうありません、これがprologの(気持ち)良さです

m0h1can 学校では人工知能の講義の中や論理学の中でprologを教えますが間違いです。保健体育の内容です

m0h1can 第五世代コンピュータの研究開発がかつてあって、そこでは乱交に適した言語が考え出されました

m0h1can 残念ながら"バック"トラックは乱交に適さず、GHCという(ゴム)ガードを使って記述する言語が出来ました

m0h1can 敗者＝悪ならprologはまさに悪そのものであり、背徳的なサド侯爵

natsutan また、 prolog タイムか・・・・

natsutan Prolog の浸透率と性犯罪は相関関係があるんじゃないか？

alohakun natsutan によって広げられる prolog 脳の恐怖．prolog と性犯罪は関係ありません ＞＜

alohakun そんなこと言ったら，ポケモンと暴行拉致監禁洗脳使役系の事件は何か関係があるんじゃないか ?

natsutan ポケモンも Prolog にかかると、弱らせて捕まえるから、危険。とにかく Prolog 危険。

alohakun とりあえず弱らせてから捕まえれば良いというポケモン脳の恐怖．

natsutan 北海道は、エロいニュース多い。それだけはガチ。うらｙ・・

m0h1can みんなちん■こやまん■こをポケモンと呼べば善いよ

# 管理人により検閲

yuki_neko_nyan ちょっと北海道移住する!!

yadokarielectri prologと北海道と性犯罪の関連について

natsutan （ごめんなさい。黄金聖闘士を召還してしまった。本当にごめんなさい）

yuki_neko_nyan ポケモンはなんでPrologにかかるとよわるん?

natsutan ひんと）北海道 と みだらな行為 で検索

m0h1can 「個」の時代が到来したというけれど、人の世は遠い昔からちん「個」とまん「個」の時代だった

m0h1can ただそこにジェンダー論が持ち込まれ、どちらのインスタンスも「個」のサブクラスじゃないか？とか言い出したオブジェクト指向論者が現れておかしくなった

北海道在住で，1983 年生まれで，乙女座で，prolog 使える僕は，もうすっかり性犯罪者予備軍の変態ですね．困ったものです．

僕はこの m0h1can を中心とした技術者による超電導ナイトクラブ的な脈絡の無い会話が大好きなのですが (m0h1can を follow してから twitter は 256 倍面白くなりました)うかつに夜の twitter ログを fc2 に張ると，青少年に悪影響を与えるということで追い出されそうなのが怖い．22 時以降の twitter は 21 禁にすべきですね．ある日突然このブログが消えたり公開不可能になっていたら，prolog のせいです．

---

LL魂ブログ もしLLがサザエさん一家だったら

大学とかの Prolog プログラミング演習の 99 % は，「サザエさん一家の親子関係」から始まるのではないかという説が有力です (笑) parent(namihei,sazae) とか．

どうしても脊髄反射してしまう．

例えば，ちょっとテキトーに google ると…

Try to run Prolog

プログラムを動かしてみる


Ｐｒｏｌｏｇは記号処理向けのプログラミング言語です。もっと具体的な言い方をすると、何らかの「もの（対象）」と「もの（対象）」との関係に関する問題解決に適しています。この章では例題を通してＰｒｏｌｏｇの基本的なメカニズムについて考えてみます。何はともあれ、Ｐｒｏｌｏｇを動かしてみましょう。

1.1磯野家の家族関係

ｷﾀ━━━━｡ﾟ+.ヽ(´∀`*)ﾉ ﾟ+.ﾟ━━━━!!

# 最近だと ちびまる子ちゃんなどの変種も多いみたいです．


てか，鳥取大学 Sugeee

(おそらく) 講義資料が高橋メソッド ！

---

と，これだけではあんまりなので… ついでに，

LL魂ブログ キミならどう書く 2.0 - 2007 - 問題 2 : 小町算

をやってみた．

といっても… Prolog は，小町算みたいなパズルを解くための専用言語みたいなものなので，本当に何も考えなくても解けてしまいます．

基本方針 :

(1) まずはテキトーに 1 〜 9 の数字列を区切る．
(2) 区切った数字の間に，優先度順に (*, rdiv) (+, /) のいずれかを挿入してみる．

# 誤差が入るとマズイので，有理数除算 rdiv を使ってる．そのせいで出力が多少見苦しいけど… まぁ，やろうと思えば整形は簡単なので．

(3) (2) で組み立てた項が 100 なら，項を出力して，失敗駆動ループ (わざと fail させて，全ての可能性を探索)．

以下がプログラム．make_expr1 で数字列を区切る，make_expr2 で * と rdiv を非決定的に挿入，make_expr3 で + と - を非決定的に挿入と，優先度順に項を組み立てて算術単一化してるだけです．

ポイントは，非決定的 = 入るか，入らないかの 2 PATH に過ぎないということ．

区切るか，区切らないか，演算子を入れるか入れないかの場合分けを書いておけば，あとは Prolog が勝手に全可能性を探索してくれます．

komachi(Exp, N) :-
  make_expr1(Exp, E1),
  make_expr2(E1, E2),
  make_expr3(E2, [E]),
  N is E,
  format('~w = ~a~n', [E, N]),
  fail.
komachi(_, _).

make_expr1([], []).
// 区切った場合   例 : [1, 2, | R] => [12 | R]
make_expr1([A, B | R], T) :- X is A * 10 + B, make_expr1([X | R], T).
// 区切らないで素通しした場合
make_expr1([X | Xs], T) :- T = [X | T1], make_expr1(Xs, T1).

make_expr2([], []).
make_expr2([A, B | R], T) :- X =.. [*, A, B], make_expr2([X | R], T).
make_expr2([A, B | R], T) :- X =.. [rdiv, A, B], make_expr2([X | R], T).
make_expr2([X | Xs], T) :- T = [X | T1], make_expr2(Xs, T1).

make_expr3([], []).
make_expr3([A, B | R], T) :- X =.. [+, A, B], make_expr3([X | R], T).
make_expr3([A, B | R], T) :- X =.. [-, A, B], make_expr3([X | R], T).
make_expr3([X | Xs], T) :- T = [X | T1], make_expr3(Xs, T1).

ちなみに， 「=..」というのは，リストから項を組み立てる特殊な単一化です．

?- X =.. [*, A, B].

X = A*B ;

No

実行結果 (Windows の SWI-Prolog なので，他の環境だと =.. とかが無くて動かないかも…)

?- consult('C:/Documents and Settings/aloha/My Documents/prolog/komachi.pl').
% C:/Documents and Settings/aloha/My Documents/prolog/komachi.pl compiled 0.00 sec, 0 bytes

Yes
?- komachi([1,2,3,4,5,6,7,8,9], 100).
123-45-67+89 = 100
123+45-67+8-9 = 100
123+4-5+67-89 = 100
123+4*5-6*7+8-9 = 100
123-4-5-6-7+8-9 = 100
12+34+5*6+7+8+9 = 100
12+34-5+6*7+8+9 = 100
12+34-5-6+7*8+9 = 100
12+34-5-6-7+8*9 = 100
12+3*45+6*7-89 = 100
12+3+4-56 rdiv 7+89 = 100
12*3-4*5+67+8+9 = 100
12+3-4+5+67+8+9 = 100
12*3-4+5-6+78-9 = 100
12 rdiv 3 rdiv 4+5*6+78-9 = 100
12+3*4-5-6+78+9 = 100
12 rdiv 3+4*5-6-7+89 = 100
12+3+4+5-6-7+89 = 100
12-3-4+5-6+7+89 = 100
12*3-4-5-6+7+8*9 = 100
12 rdiv 3+4*5*6*7 rdiv 8-9 = 100
12 rdiv 3+4*5*6-7-8-9 = 100
12+3*4+5+6+7*8+9 = 100
12+3*4+5+6-7+8*9 = 100
12-3+4*5+6+7*8+9 = 100
12-3+4*5+6-7+8*9 = 100
12-3-4+5*6+7*8+9 = 100
12-3-4+5*6-7+8*9 = 100
1+234-56-7-8*9 = 100
1*234+5-67-8*9 = 100
1+234*5*6 rdiv 78+9 = 100
1+234*5 rdiv 6-7-89 = 100
1*23-4-56 rdiv 7+89 = 100
1*23*4-56 rdiv 7 rdiv 8+9 = 100
1*23+4+56 rdiv 7*8+9 = 100
1+23*4+56 rdiv 7+8-9 = 100
1+23-4+56 rdiv 7+8*9 = 100
1+23-4+56+7+8+9 = 100
1*23+4+5+67-8+9 = 100
1+23-4+5+6+78-9 = 100
1*23-4+5-6-7+89 = 100
1-23+4*5+6+7+89 = 100
1-23-4+5*6+7+89 = 100
1-23-4-5+6*7+89 = 100
1+23*4+5-6+7-8+9 = 100
1+23*4-5+6+7+8-9 = 100
1+23-4-5+6+7+8*9 = 100
1+2*34-56+78+9 = 100
1*2*34+56-7-8-9 = 100
1*2+34-56 rdiv 7+8*9 = 100
1*2+34+56+7-8+9 = 100
1-2-34+56+7+8*9 = 100
1+2+34-5+67-8+9 = 100
1 rdiv 2*34-5+6-7+89 = 100
1*2+34+5+6*7+8+9 = 100
1*2+34+5-6+7*8+9 = 100
1*2+34+5-6-7+8*9 = 100
1+2+34*5+6-7-8*9 = 100
1 rdiv 2 rdiv 3*456+7+8+9 = 100
1*2*3-45+67+8*9 = 100
1*2+3+45+67-8-9 = 100
1+2+3-45+67+8*9 = 100
1-2-3+45+6*7+8+9 = 100
1-2+3+45+6+7*8-9 = 100
1-2-3+45-6+7*8+9 = 100
1-2-3+45-6-7+8*9 = 100
1*2-3+4+56 rdiv 7+89 = 100
1+2*3-4+56 rdiv 7+89 = 100
1 rdiv 2*3 rdiv 4*56+7+8*9 = 100
1+2+3*4*56 rdiv 7-8+9 = 100
1-2-3+4*56 rdiv 7+8*9 = 100
1+2*3+4+5+67+8+9 = 100
1-2+3*4+5+67+8+9 = 100
1-2-3+4*5+67+8+9 = 100
1*2*3*4-5-6+78+9 = 100
1*2*3-4+5+6+78+9 = 100
1*2+3*4+5-6+78+9 = 100
1*2+3+4*5+6+78-9 = 100
1*2-3+4*5-6+78+9 = 100
1*2+3-4+5*6+78-9 = 100
1+2+3*4*5 rdiv 6+78+9 = 100
1+2+3-4+5+6+78+9 = 100
1*2 rdiv 3+4*5 rdiv 6+7+89 = 100
1*2-3+4-5+6+7+89 = 100
1+2*3-4-5+6+7+89 = 100
1+2+3*4-5-6+7+89 = 100
1*2*3*4+5+6+7*8+9 = 100
1*2*3*4+5+6-7+8*9 = 100
1*2*3-4*5+6*7+8*9 = 100
1*2*3+4+5+6+7+8*9 = 100
1+2*3*4*5 rdiv 6+7+8*9 = 100
1+2*3+4*5-6+7+8*9 = 100
1-2*3+4*5+6+7+8*9 = 100
1-2*3-4+5*6+7+8*9 = 100
1-2*3-4-5+6*7+8*9 = 100
1-2+3*4*5+6*7+8-9 = 100
1-2+3*4*5-6+7*8-9 = 100
1+2-3*4+5*6+7+8*9 = 100
1+2-3*4-5+6*7+8*9 = 100
1+2+3-4*5+6*7+8*9 = 100
1+2+3+4+5+6+7+8*9 = 100

Yes

ちなみに，電卓のように逐次計算する版は，*/+- の優先度が全て等しいのと同じなのでこうなります．

komachi_dentaku(Exp, N) :-
  make_expr_dentaku(Exp, Exp1),
  make_expr_dentaku1(Exp1, [E]),
  N is E,
  format('~w = ~a~n', [E, N]),
  fail.
komachi_dentaku(_, _).

make_expr_dentaku([], []).
make_expr_dentaku([A, B | R], T) :- X is A * 10 + B, make_expr_dentaku([X | R], T).
make_expr_dentaku([X | Xs],   T) :- T = [X | T1],    make_expr_dentaku(Xs, T1).

make_expr_dentaku1([], []).
make_expr_dentaku1([A, B | R], T) :- X =.. [*, A, B],    make_expr_dentaku1([X | R], T).
make_expr_dentaku1([A, B | R], T) :- X =.. [rdiv, A, B], make_expr_dentaku1([X | R], T).
make_expr_dentaku1([A, B | R], T) :- X =.. [+, A, B],    make_expr_dentaku1([X | R], T).
make_expr_dentaku1([A, B | R], T) :- X =.. [-, A, B],    make_expr_dentaku1([X | R], T).
make_expr_dentaku1([X | Xs],   T) :- T = [X | T1],       make_expr_dentaku1(Xs, T1).

実行結果 (無理矢理カッコ付けて計算するのと同じ)

?- komachi_dentaku([1,2,3,4,5,6,7,8,9], 100).
123-45-67+89 = 100
123+45-67+8-9 = 100
(123-45)rdiv 6+78+9 = 100
123+4-5+67-89 = 100
123-4-5-6-7+8-9 = 100
(12+3)*4-56+7+89 = 100
(12-3)*4+56+7-8+9 = 100
12+3-4+5+67+8+9 = 100
12*3-4+5-6+78-9 = 100
(12-3-4)*5+6+78-9 = 100
(12 rdiv 3*4+5+6)*7-89 = 100
(12 rdiv 3+4-5)*6-7+89 = 100
(12+3)*4 rdiv 5+6-7+89 = 100
(12+3+4+5)rdiv 6+7+89 = 100
12+3+4+5-6-7+89 = 100
12-3-4+5-6+7+89 = 100
(12-3+4+5)*6-7+8-9 = 100
1+23-4+56+7+8+9 = 100
1*23+4+5+67-8+9 = 100
1+23-4+5+6+78-9 = 100
(1*23-4+5)rdiv 6+7+89 = 100
1*23-4+5-6-7+89 = 100
(1+23+4+5-6)*7-89 = 100
(1+23-4)*5+6-7-8+9 = 100
(1+23-4)*5-6+7+8-9 = 100
(1+23-4-5)*6-7+8+9 = 100
1*2*34+56-7-8-9 = 100
1*2+34+56+7-8+9 = 100
1+2+34-5+67-8+9 = 100
1 rdiv 2*34-5+6-7+89 = 100
1 rdiv 2 rdiv 3*456+7+8+9 = 100
1*2+3+45+67-8-9 = 100
(1*2+3)*4+56+7+8+9 = 100
(1+2)*3*4+56+7-8+9 = 100
(1*2*3+4)*5+67-8-9 = 100
(1+2+3+4)*5+67-8-9 = 100
1*2*3*4-5-6+78+9 = 100
(1*2*3-4+5)rdiv 6*78+9 = 100
1*2*3-4+5+6+78+9 = 100
(1*2 rdiv 3 rdiv 4+5)*6+78-9 = 100
(1*2 rdiv 3 rdiv 4-5+6)*78+9 = 100
(1*2+3)*4+5+6+78-9 = 100
(1 rdiv 2+3)*4+5-6+78+9 = 100
((1+2)*3-4)*5+6+78-9 = 100
((1+2)rdiv 3+4)*5+6+78-9 = 100
(1+2+3)*4-5-6+78+9 = 100
(1+2+3-4+5)rdiv 6*78+9 = 100
1+2+3-4+5+6+78+9 = 100
(1*2*3-4)*5-6+7+89 = 100
1*2-3+4-5+6+7+89 = 100
(1 rdiv 2+3-4+5)*6*7-89 = 100
(1 rdiv 2-3)*4 rdiv 5+6+7+89 = 100
(1+2)*3-4+5-6+7+89 = 100
(1+2)rdiv 3+4+5-6+7+89 = 100
(1+2+3-4)*5-6+7+89 = 100
(1-2)*3-4+5+6+7+89 = 100
((1-2)rdiv 3-4+5)*6+7+89 = 100
((1-2+3)*4-5)*6-7+89 = 100
(1-2+3-4+5)*6-7+89 = 100
(1*2*3+4+5)*6-7+8+9 = 100
(1*2+3)*4*5+6-7-8+9 = 100
(1*2+3)*4*5-6+7+8-9 = 100
((1*2+3)*4-5)*6-7+8+9 = 100
(1*2-3+4)*5*6-7+8+9 = 100
(1 rdiv 2+3)*4*5+6+7+8+9 = 100
((1+2)*3+4+5)*6-7+8-9 = 100
(1+2+3+4+5)*6-7+8+9 = 100
((1-2)rdiv 3+4)*5*6+7-8-9 = 100

Yes

ちなみに，このブログの Prolog の記事は，全てきむらさんのために書いてるので，わかりやすさ優先 (最も宣言的… 要するに，単純愚直 (straightforward)) で書いてるつもりです (手抜きプログラムの言い訳 笑)

いくらでも，もっと簡潔に書けるはず．ただ，ヘッド部でなんでもかんでも単一化すると，急激に処理の方向性がわかりにくくなる (というか，もともと処理に方向が無いから，プログラムが追い難いんだけど) ので，わざとルールっぽく手続き的に書いたり．

ちょっとググッたら，こんなの発見．うはー，短い．なるほど．

Marginal Leaves 2007-07-18 ■Prologで小町算

member とかを使って，何らかのグループの全ての可能性を探索させるってのも，Prolog の常套手段ですな．

というか，M.Hiroi さんとこに，油分けも小町もどっちも既にあったという．そりゃそうだよなぁ，こういうのは，Prolog Programming を習うとき，真っ先に教材になるところだもんなぁ．

M.Hiroi's Home Page Prolog Programming お気楽 Prolog プログラミング入門 パズルに挑戦 (2)

# ということは，たぶん過去に何回かカンニングしてるかも (笑) 僕は学部の 3 年生ぐらいの時に「知能機械と自然言語処理」というやたら物々しい講義名の講義で必要になって (というか，曖昧な文法のパーザを書くのに，Prolog が一番楽そうに思えた) M.Hiroi さんのサイトを舐めるように眺めて Prolog を覚えたクチなので．あと，たぶん 「Prolog の技芸」でも，この手のパズルは何度も何度も出てきてるはず (担当教官に借りてた本なので，今は手元に無いけど)．

---

というか，問題文をよく読むと，可能な等式の数を答えないと駄目なのか… 失敗駆動ループを使うと，繰り返し回数をカウントするのが面倒なような．まぁ，forall とかいう反則高階述語 (Prolog は一階述語論理のサブセット) を使えば楽勝だと思うけど．なんかもうやる気が無くなったので，あとは読者の宿題とする (dankogai メソッド)

---

LL魂ブログ キミならどう書く 2.0 - 2007 - その 1

基本的にこういう探索系の問題は Prolog が最強です．というわけで，きむらさんに催促される前に解いておく (笑)

… と思ったら，手元に Prolog 処理系すら無かったので (駄目)，SWI-Prolog のサイトから RPM ファイルをダウンロードしてきた．

# alien pl-5.6.36-287.i586.rpm
pl_5.6.36-288_i386.deb generated

# dpkg -i pl_5.6.36-288_i386.deb

というわけで，非常に投げやりなプログラム．特に面白いことは何もしてません．というか，何も考えなくても，問題を書くだけで解ける (実際に，何も考えないで惰性でプログラムを書いている．夜中に変な時間にうっかり目が覚めてしまったのでだるい．まじめにアルゴリズムとか考えられるぐらい覚醒してない)．なんせデフォルトの挙動が深さ優先探索の言語なので．

aburauri(A, B, C) :- aburauri(A, B, C, [], []).

aburauri(5, 5, 0, RR, RP) :- reverse(RP, P),reverse([[5, 5, 0] | RR], R), print_result(R, P).
aburauri(0, 5, 5, RR, RP) :- reverse(RP, P),reverse([[0, 5, 5] | RR], R), print_result(R, P).
aburauri(5, 0, 5, RR, RP) :- reverse(RP, P),reverse([[5, 0, 5] | RR], R), print_result(R, P).

aburauri(A, B, C, R, P) :-   
  not_member([A, B, C], R), move(A, B, 7, A1, B1, M),
  aburauri(A1, B1, C, [[A, B, C] | R], [[a, b, M] | P]).
aburauri(A, B, C, R, P) :- 
  not_member([A, B, C], R), move(A, C, 3, A1, C1, M),
  aburauri(A1, B, C1, [[A, B, C] | R], [[a, c, M] | P]).
aburauri(A, B, C, R, P) :- 
  not_member([A, B, C], R), move(B, A, 10, B1, A1, M),
  aburauri(A1, B1, C, [[A, B, C] | R], [[b, a, M] | P]).
aburauri(A, B, C, R, P) :- 
  not_member([A, B, C], R),  move(B, C, 3, B1, C1, M),
  aburauri(A, B1, C1, [[A, B, C] | R], [[b, c, M] | P]).
aburauri(A, B, C, R, P) :- 
  not_member([A, B, C], R),  move(C, A, 10, C1, A1, M),
  aburauri(A1, B, C1, [[A, B, C] | R], [[c, a, M] | P]).
aburauri(A, B, C, R, P) :- 
  not_member([A, B, C], R),  move(C, B, 7, C1, B1, M),
  aburauri(A, B1, C1, [[A, B, C] | R], [[c, b, M] | P]).

move(X, Y, Ymax, X1, Y1, M) :-
  Yrest is Ymax - Y, X =< Yrest, X1 is 0, Y1 is Y + X, M is X.
move(X, Y, Ymax, X1, Y1, M) :-
  Yrest is Ymax - Y, X >= Yrest, X1 is X - Yrest, Y1 is Ymax, M is Yrest.

not_member(_, []).                     
not_member(X, [X | _]) :- !, fail.
not_member(X, [_ | Xs]) :- !, not_member(X, Xs).

print_result([R],[]) :- format("[~a ~a ~a]~n", R).
print_result([R | RR], [[b, a, 7] | PR]) :- !, 
  format("[~a ~a ~a]~nb を a に全部戻して~n", R), print_result(RR, PR).
print_result([R | RR], [[c, a, 3] | PR]) :- !, 
  format("[~a ~a ~a]~nc を a に全部戻して~n", R), print_result(RR, PR).
print_result([R | RR], [[c, b, 3] | PR]) :- !, 
  format("[~a ~a ~a]~nc を b に全部戻して~n", R), print_result(RR, PR).
print_result([[A, B, C] | RR], [P | PR]) :- !, 
  format("[~a ~a ~a]~n~a から ~a へ ~a 升移す~n", [A, B, C | P]), print_result(RR, PR).

しっかし，いかにももっと縮まりそうなダラダラコードだな… なんせ，本当にただ問題を羅列しているだけだし．何やってるかは，見れば一目瞭然でしょう (酷) 一見複雑に見えますが，全部単なるパターン分けだけです．

# やたら長く見えるかもしれませんが，それはこのブログの行間の仕様です．あと，プリンタとか瑣末な部分が無駄に長い．

ただし，本当に問題をそのまま書いただけだと，何回も同じ手順を繰り返して無限ループしてしまうので，とりあえず一回見た局面にきたらそこで探索終了という感じにしてみた．油売り算に限らず，だいたい Prolog でこの手のプログラムを書くと，こういうリストにとりあえずプッシュして記録して not_member という投げやりなコードになります．

結果はこんな感じに．

?- ['aburauri.prolog'].
% aburauri.prolog compiled 0.00 sec, 600 bytes

Yes
?- aburauri(10, 0, 0).
[10 0 0]
a から b へ 7 升移す
[3 7 0]
a から c へ 3 升移す
[0 7 3]
b を a に全部戻して
[7 0 3]
c を b に全部戻して
[7 3 0]
a から c へ 3 升移す
[4 3 3]
c を b に全部戻して
[4 6 0]
a から c へ 3 升移す
[1 6 3]
c から b へ 1 升移す
[1 7 2]
b を a に全部戻して
[8 0 2]
c から b へ 2 升移す
[8 2 0]
a から c へ 3 升移す
[5 2 3]
c を b に全部戻して
[5 5 0]

Yes

なんか模範解答と違う気がするけど… 追ってみると，いちおう正しい答っぽいので，まぁ，いいんじゃないかと
(眠すぎてやる気が無い管理人)

---

そうかー，幅優先探索じゃないと出ないのか… というか，問題の趣旨がそれだったらしい．

まぁ，今日のところはこんぐらいにしといたるわ ！

(吉本新喜劇管理人)

---

追記 : 2007/7/19

すっかり忘れてた．もの凄い遅レスですが…

ときどきの雑記帖 リターンズ■_ む。(催促する前に)先手を打たれたか

ところで複数解がある場合は、全部見つけるまで頑張ってくれるんじゃなかったんでしょうか ＞Prolog プログラムの組み方による?

結果を表示した後に，fail を入れると，全ての可能性を失敗駆動ループで探索できる (と思います ← 面倒で試してない)．

aburauri(5, 5, 0, RR, RP) :- reverse(RP, P),reverse([[5, 5, 0] | RR], R), print_result(R, P), fail.
aburauri(0, 5, 5, RR, RP) :- reverse(RP, P),reverse([[0, 5, 5] | RR], R), print_result(R, P), fail.
aburauri(5, 0, 5, RR, RP) :- reverse(RP, P),reverse([[5, 0, 5] | RR], R), print_result(R, P), fail.

ただ，やってみるとバーッとエライ数の結果が表示される (と思う) ので，まぁ特に「最短」や「何通りの可能性が存在するか」という指定などは無いみたいなので，最初の一つで良いかなと．

---