オフラインどう書く第18回問題解答

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

regiの要素X-O-M:Nは（X->並んだ人数、O->レジの番号、M->レジの処理能力、
　　　　　　N->xが並んでいないとき変数、並んだ時並んだ順番をセット）
proc/3で会計か並ぶかを判断します。
並ぶ場合は
msortで並んだ人数-レジの番号の優先順でソートしてヘッドの要素のレジを選択し、
push/3でxの場合、push/2でその他の場合の処理をおこないます。
会計時（pop/2）はそれぞれのレジで
xが並んでいないとき
  処理できる人数と並んだ人数（X-O-M:NのXとM）の少ないほうをXから引きます。
xが並んだ場合
  処理できる人数とxより前の人数（X-O-M:NのMとN）の少ないほうをXとNから引きます。

```Prolog
%SWI-Prolog version 7.4.2,7.6.4
%swi-prolog
%:-initialization(start).  %ideone
%start.

regi([0-1-2:_,0-2-7:_,0-3-3:_,0-4-5:_,0-5-2:_]).

pop(X-O-M:N,X1-O-M:_):-var(N),!,X1 is X-min(X,M).
pop(X-O-M:N,X1-O-M:N1):-K is min(N,M),X1 is X-K,N1 is N-K.

push(X-O-M:K,N,R):-X1 is X+N,R=X1-O-M:K.
push(X-O-M:N,X1-O-M:N1):-X1 is X+1,(var(N)->N1=X;N1=N).

proc(.,L,R):-maplist(pop,L,R),!.
proc(x,L,R):-msort(L,[H|T]),push(H,H1),R=[H1|T],!.
proc(N,L,R):-atom_number(N,N1),msort(L,[H|T]),push(H,N1,R1),R=[R1|T],!.

chan(X-O-_:_,O-X).

solve(L,R):-
     regi(L1),foldl(proc,L,L1,R1),maplist(chan,R1,R2),
     sort(R2,R3),pairs_keys_values(R3,_,R).

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

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

disp(R,N):-maplist(atom_number,R1,R),atomics_to_string(R1,",",S),
        (S==N->Str=" yes ";Str=" no  "),write(Str),writeln(S).

str("0  42873x.3.       0,4,2,0,0
1       1       1,0,0,0,0
2       .       0,0,0,0,0
3       x       1,0,0,0,0
4       31.     1,0,0,0,0
5       3x.     1,1,0,0,0
6       99569x  9,9,6,6,9
7       99569x33        9,9,9,9,9
8       99569x33.       7,2,6,4,7
9       99569x33..      5,0,4,0,5
10      12345x3333.     4,0,3,2,3
11      54321x3333.     3,0,3,0,4
12      51423x3333.     3,4,4,0,4
13      12x34x.         1,0,1,0,2
14      987x654x.32     7,6,4,10,5
15      99999999999x99999999.......9.   20,10,12,5,20
16      997     9,9,7,0,0
17      .3.9    1,9,0,0,0
18      832.6   6,6,0,0,0
19      .5.568  3,5,6,8,0
20      475..48         4,8,0,0,0
21      7.2..469        1,4,6,9,0
22      574x315.3       3,3,1,7,1
23      5.2893.x98      10,9,5,4,1
24      279.6xxx..4     2,1,4,1,1
25      1.1.39..93.x    7,1,0,0,0
26      7677749325927   16,12,17,18,12
27      x6235.87.56.9.  7,2,0,0,0
28      4.1168.6.197.6.         0,0,3,0,0
29      2.8.547.25..19.6        6,2,0,0,0
30      .5.3x82x32.1829..       5,0,5,0,7
31      x.1816..36.24.429.      1,0,0,0,7
32      79.2.6.81x..26x31.1     1,0,2,1,1
33      574296x6538984..5974    14,13,10,15,14
34      99.6244.4376636..72.6   5,6,0,0,3
35      1659.486x5637168278123  17,16,16,18,17
36      .5.17797.x626x5x9457.3.         14,0,3,5,8
37      ..58624.85623..4.7..23.x        1,1,0,0,0
38      716.463.9.x.8..4.15.738x4       7,3,5,8,1
39      22xx.191.96469472.7232377.      10,11,18,12,9
40      24..4...343......4.41.6...2     2,0,0,0,0
41      32732.474x153.866..4x29.2573    7,5,7,8,5
42      786.1267x9937.17.15448.1x33.4   4,4,8,4,10
43      671714849.149.686852.178.895x3  13,16,13,10,12
44      86x.47.517..29621.61x937..xx935         7,11,8,8,10
45      .2233.78x.94.x59511.5.86x3.x714.        4,6,10,8,8
46      .793...218.687x415x13.1...x58576x       8,11,8,6,9
47      6.6x37.3x51x932.72x4x33.9363.x7761      15,13,15,12,15
48      6..4.x187..681.2x.2.713276.669x.252     6,7,8,6,5
49      .6.xx64..5146x897231.x.21265392x9775    19,17,19,20,17
50      334.85413.263314.x.6293921x3.6357647x   14,14,12,16,10
51      4.1..9..513.266..5999769852.2.38x79.x7  12,10,13,6,10").
```
別解
人数が多くないので、リスト処理重視にしてみました。

O-M:Lは（O->レジの番号、M->レジの処理能力、
　　　L->並んだ人のリスト、1..9は普通の人、xが時間のかかる人）
proc/3で会計か並ぶかを判断。
並ぶ場合short/3で一番短い列の情報を取得しレジを選択。
(len/2でレジに並んだ人数を求め、レジ番号と並んだ人数のペアのリストを作ってソートし、
先頭の要素とレジ番号が一致するものをもとのリストから選びます。)
(できれば人数を求めずにリストの比較だけで済ませたかったのですが）
そしてxの場合は[x],それ以外はnumlist/3で並ぶ人のリストを作りpush/3で列に加えます。
会計時（pop/3）は一人ずつ並んだ人のリストからのぞいていき、
処理人数が終わったとき、並んだ人がいなくなった時、xが先頭に来た時に終了します。

```Prolog
%:-initialization(start).  %ideone
%start.

regi([1-2:[],2-7:[],3-3:[],4-5:[],5-2:[]]).

pop0(O-M:L,O-M:L1):-pop(M,L,L1).

pop(N,L,L):-N=:=0;L=[];L=[x|_].
pop(N,[_|T],R):-N1 is N-1,pop(N1,T,R).

push(L1,O-M:L2,O-M:L3):-append(L2,L1,L3).

len(O-_:L,N-O):-length(L,N).

short(L,O-M:L2,L3):-maplist(len,L,L1),msort(L1,[_-O|_]),select(O-M:L2,L,L3).

proc(.,L,R):-maplist(pop0,L,R),!.
proc(x,L,[R1|L3]):-short(L,Y,L3),push([x],Y,R1),!.     %Y->O-M:List
proc(C,L,[R1|L3]):-short(L,Y,L3),atom_number(C,N),numlist(1,N,L4),push(L4,Y,R1),!.

solve(L,R):-
     regi(L1),foldl(proc,L,L1,R1),maplist(len,R1,R2),
     sort(2,@<,R2,R4),pairs_keys(R4,R).

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

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

disp(R,N):-maplist(atom_number,R1,R),atomics_to_string(R1,",",S),
        (S==N->Str=" yes ";Str=" no  "),write(Str),writeln(S).
```
2020年12月10日追加
上記のpop/3はレジでの動きに沿っていますが、
psuh/3に合わせてappendを使って書き換えてみました。
append(X,Y,Z)はXとYからZを求める組み込み術語ですが、ここでは逆に、
Zに合うXとYの組み合わせを、条件を満たすまでバックトラックで作っています。

```Prolog
pop(N,L,R):-append(L1,R,L),(R=[];R=[x|_];length(L1,N)).
```