オフラインどう書く過去問(第27回,E05)

E27の参考問題の解答を投稿しようとしましたところ、下書きが溜まっていて投稿できませんでしたので、
似た様な問題の解答をまとめて投稿します。

問題はこちら->http://nabetani.sakura.ne.jp/hena/ord27raswi

ルートを記述するのに、続く二点のみ書く方法とつながる複数の点を書く方法があります。
前者の方がプログラムは簡単ですが、入力が多くなります。（後者の方が入力ミスがあったりしますが）
解答が”,"で区切られていて数が不定なので、答え合わせのコードを書くほうが時間がかかりました。
前者のプログラムです。

```Prolog
%swi-Prolog  version 7.4.2

r(1,[a,g]).
r(2,[d,h]).
r(3,[b,f]).
r(a,[b]).
r(b,[c,5]).
r(c,[4,6]).
r(d,[c,e]).
r(e,[5]).
r(f,[g]).
r(g,[c,e,h]).
r(h,[4,i]).
r(i,[6]).

pass(B,R):-between(1,3,F),between(4,6,T),pas1(F,T,B,[F],R).

pas1(T,T,_,L,R):-reverse([T|L],R).
pas1(F,T,B,L,R):-pas2(F,X,B),pas1(X,T,B,L,R).

pas2(F,T,B):-r(F,L),member(T,L),not(member(T,B)).

solve(B,L):-findall(R,pass(B,R),L).

disp(R,Q):-atomics_to_string(Q,Q1),(R==[]->S="-";
     (maplist(concat_atom,R,L),sort(L,L1),atomics_to_string(L1,",",S))),
     (S==Q1->Str=" yes ";Str=" no  "),write(Str),writeln(S).

start:-str(S),atomics_to_string(L,"\n",S),maplist(split,L,L1),
      maplist(sp,L1,L2),pre(L2).

split(S,L):-split_string(S,"\s","\s",L).

pre([]).
pre([[_,B,Q]|T]):-atom_chars(B,L),solve(L,R),disp(R,Q),pre(T).

sp([X,Y|T],L):-L=[X,Y,T].

%start.

str("0       befi    14,16,24,26
1       abc     14,15,16,24,25,26,34,35,36
2       de      14,15,16,24,26,34,35,36
3       fghi    14,15,16,24,25,26,34,35,36
4       abcdefghi       -
5       ag      24,25,26,34,35,36
6       dh      14,15,16,34,35,36
7       bf      14,15,16,24,25,26
8       ch      15,25,35
9       be      14,16,24,26,34,36
10      ci      14,15,24,25,34,35
11      cgi     15,24,25,35
12      acgi    24,25,35
13      cdefghi         15,35
14      acdefghi        35
15      cdegi   15,24,35
16      bcdegi  24
17      afh     14,15,16,24,25,26,34,35,36
18      abfh    14,15,16,24,25,26
19      dfh     14,15,16,34,35,36
20      cdfh    15,35
21      deh     14,15,16,34,35,36
22      cdeh    15,35
23      abefgh  24,26
24      abdefgh         -
25      acfghi  25,35
26      acdfghi         35
27      cegi    15,24,35
28      abcfhi  15,25
29      abcefhi         -
30      abdi    14,15,16,24,34,35,36
31      abdfi   14,15,16,24
32      bdi     14,15,16,24,34,35,36
33      bdfi    14,15,16,24
34      adfh    14,15,16,34,35,36
35      adfgh   34,35,36
36      acdfhi  15,35
37      bcdfgi  24
38      bcdfghi         -
39      defi    14,15,16,24,34,35,36
40      defhi   14,15,16,34,35,36
41      cdefg   15,24,26,35
42      cdefgi  15,24,35
43      bdefg   24,26
44      bdefgi  24").
```
後者の方法のひとつで分岐部までのつながりを記述する方法です。
各区域の到着点をheadに持ってくるため、リスト内の要素を逆順にしてあります。
異なる部分のみ載せました。

```Prolog
r(1,[[b,a],[g]]).
r(2,[[d],[h]]).
r(3,[[b],[g,f]]).
r(b,[[c],[5]]).
r(c,[[4],[6]]).
r(d,[[c],[5,e]]).
r(g,[[h],[5,e],[c]]).
r(h,[[6,i],[4]]).

pass(B,R):-between(1,3,F),between(4,6,T),pas1(F,T,B,[F],R).

pas1(T,T,_,L,R):-reverse([T|L],R).
pas1(F,T,B,L,R):-pas2(F,X,B),pas1(X,T,B,L,R).

pas2(F,T,B):-r(F,L),member(X,L),forall(member(Y,X),not(member(Y,B))),X=[T|_].
```
第27回と似た問題を見つけ解いてみました。
問題はこちら->http://nabetani.sakura.ne.jp/hena/orde05dokitruck/

fork/2で1-9のコースの分岐の状態を表していますが、
横路のみ通れる分岐部はありませんので、それぞれの道のリストは、
行き止まりは空リスト、それ以外はheadに分岐前の道を入れています。
そうすることによって、path/3のmember/2で行き止まりの検出もしています。

```Prolog
%        [ a->   b->   c->]
fork('1',[[a,b],[b,c],[c]]).
fork('2',[[a,c],[b],[c,b]]).
fork('3',[[a,c],[b,a],[c]]).
fork('4',[[a],[b,a],[c,b]]).
fork('5',[[a],[b,c],[c,a]]).
fork('6',[[a,b],[b],[c,a]]).
fork('7',[[a],[],[c]]).
fork('8',[[],[b],[c]]).
fork('9',[[a],[b],[]]).

path([],L,L).
path([H|T],X,R):-fork(H,L),member([X|T2],L),member(Y,[X|T2]),path(T,Y,R),!.

solve(L,R):-findall(Y,(member(Y,[a,b,c]),path(L,Y,_)),R),!.

start:-str(S),split_string(S,"\n,\s","\s",L),pre(L).

pre([]).
pre([_,A,B|T]):-atom_chars(A,L),solve(L,R),disp(R,B),pre(T).

disp(R,B):-(R==[]->S="-";atom_string(R,S)),
      (B==S->Str=" pass ";Str=" fail "),write(Str),writeln(S).

%start.

str("0       1728398         bc
1       789     -
2       274     ac
3       185     abc
4       396     ab
5       1278    abc
6       7659832         a
7       178     bc
8       189     ab
9       197     a
10      278     ac
11      289     bc
12      297     a
13      378     ac
14      389     b
15      397     ab
16      478     c
17      489     bc
18      497     ab
19      578     bc
20      589     b
21      597     ac
22      678     c
23      689     ab
24      697     ac
25      899     b
26      7172    ac
27      54787   bc
28      83713   bc
29      149978  -
30      159735  abc
31      1449467         abc
32      9862916         b
33      96112873        ab
34      311536789       -
35      281787212994    abc
36      697535114542    ac").
```