どう書くE05「どきどきトロッコ〜怒りのデスコース」を Prolog で解いた #どう書く

@cia_rana さんが、NFA風に解けると示してくださいました。
「なるほど」と思い、Prolog で書いてみました。

なぜ「なるほど」と思ったのかは、手前味噌ながら、こちらのブログのエントリを読んでいただくと何かしらの足しになるかと。

有限オートマトン Finite Automaton はPrologで書くと簡単だった件 - エンジニアのソフトウェア的愛情

問題とみなさんの回答：

問題はこちら: http://nabetani.sakura.ne.jp/hena/orde05dokitruck/
みなさんの回答へのリンクはこちら: http://qiita.com/Nabetani/items/c516875b13a4d282affe

利用した処理系は今回は GNU-Prolog です。

インタプリタで実行する場合は、オプションでソースファイルとエントリポイントになる述語を指定してください。

$ gprolog --entry-goal main --consult-file orde05dokitruck.pro
.....................................

コンパイラで実行する場合は、:- initialization(main). ディレクティブを追加してください。

$ gplc orde05dokitruck.pro 
$ ./orde05dokitruck 
.....................................

orde05dokitruck.pro

% $ gprolog --entry-goal main --consult-file orde05dokitruck.pro

rule(0'a, 0'1, 0'a). rule(0'a, 0'1, 0'b).  rule(0'b, 0'1, 0'b). rule(0'b, 0'1, 0'c).  rule(0'c, 0'1, 0'c).
rule(0'a, 0'2, 0'a). rule(0'a, 0'2, 0'c).  rule(0'b, 0'2, 0'b).                       rule(0'c, 0'2, 0'b). rule(0'c, 0'2, 0'c).
rule(0'a, 0'3, 0'a). rule(0'a, 0'3, 0'c).  rule(0'b, 0'3, 0'a). rule(0'b, 0'3, 0'b).  rule(0'c, 0'3, 0'c).
rule(0'a, 0'4, 0'a). rule(0'b, 0'4, 0'a).  rule(0'b, 0'4, 0'b).                       rule(0'c, 0'4, 0'b). rule(0'c, 0'4, 0'c).
rule(0'a, 0'5, 0'a). rule(0'b, 0'5, 0'b).  rule(0'b, 0'5, 0'c).                       rule(0'c, 0'5, 0'a). rule(0'c, 0'5, 0'c).
rule(0'a, 0'6, 0'a). rule(0'a, 0'6, 0'b).  rule(0'b, 0'6, 0'b).                       rule(0'c, 0'6, 0'a). rule(0'c, 0'6, 0'c).
rule(0'a, 0'7, 0'a).                                                                  rule(0'c, 0'7, 0'c).
                                           rule(0'b, 0'8, 0'b). rule(0'c, 0'8, 0'c).
rule(0'a, 0'9, 0'a).                       rule(0'b, 0'9, 0'b).

nfa(S, [], S).
nfa(S1, [I|Is], S2) :- rule(S1, I, S0), nfa(S0, Is, S2).

solve(Course, "-") :- findall(Truck, nfa(Truck, Course, _), []).
solve(Course, Survivors) :- findall(Truck, nfa(Truck, Course, _), Trucks), sort(Trucks, Survivors).

judge(_, E, E) :- print('.'), !.
judge(I, E, A) :- format("~ninput:    ~s~nexpected: ~s~nactual:   ~s~n", [I, E, A]).

test(Input, Expected) :-
  solve(Input, Actual),
  judge(Input, Expected, Actual).

orde05dokitruck :-
  test("1728398", "bc"),
  test("789", "-"),
  test("274", "ac"),
  test("185", "abc"),
  test("396", "ab"),
  test("1278", "abc"),
  test("7659832", "a"),
  test("178", "bc"),
  test("189", "ab"),
  test("197", "a"),
  test("278", "ac"),
  test("289", "bc"),
  test("297", "a"),
  test("378", "ac"),
  test("389", "b"),
  test("397", "ab"),
  test("478", "c"),
  test("489", "bc"),
  test("497", "ab"),
  test("578", "bc"),
  test("589", "b"),
  test("597", "ac"),
  test("678", "c"),
  test("689", "ab"),
  test("697", "ac"),
  test("899", "b"),
  test("7172", "ac"),
  test("54787", "bc"),
  test("83713", "bc"),
  test("149978", "-"),
  test("159735", "abc"),
  test("1449467", "abc"),
  test("9862916", "b"),
  test("96112873", "ab"),
  test("311536789", "-"),
  test("281787212994", "abc"),
  test("697535114542", "ac"),
  nl.

:- initialization(main).

main :-
  orde05dokitruck,
  halt.