問題はこちら->https://mtsmfm.github.io/2018/02/03/doukaku-e21.html
数理的な解法を思いつきませんでしたので、すべての可能な組み合わせを検証する方法と、
逐次実行して、全弾倉を試すまでに弾丸がなくなっているものをバックトラックで探す方法の、
二つのプログラムを書きました。
どちらも循環状態にならないようにチェックしました。
余談ですが、発射時弾倉が自動で回ると思っていましたので、少しまごつきました。
逐次実行のほう。
gcd(X,Y,G):-X=Y,G=X.
gcd(X,Y,G):-Y>X,Y1 is Y-X,gcd(X,Y1,G).
gcd(X,Y,G):-X>Y,gcd(Y,X,G).
lcm(X,Y,L):-gcd(X,Y,G), L is X*Y//G.
cir(N0,L,C):-foldl(plus,L,0,X),lcm(N0,X,C). %cyclic
solve(_,_,_,_,_,[],_,L,L):-!.
solve(N0,N,C,[H|T],[H1|T1],Hit,Mag,Bul,R):-
C>0,include(var,Mag,VL),not(VL=[]),nth0(N,Mag,X,Mag1),var(X),!,
((member(H,Hit),delete(Hit,H,Hit1),cir(N0,T1,C1),append(Bul,[N],Bul1),
nth0(N,Mag2,0,Mag1),solve(N0,N,C1,T,T1,Hit1,Mag2,Bul1,R));
(N1 is (N+H1) mod N0,append(T,[H],L),append(T1,[H1],L1),C1 is C-H1,nth0(N,Mag2,0,Mag1),
solve(N0,N1,C1,L,L1,Hit,Mag2,Bul,R))).
solve(N0,N,C,[H|T],[H1|T1],Hit,Mag,Bul,R):-
C>0,include(var,Mag,VL),not(VL=[]),N1 is (N+H1) mod N0,
append(T,[H],L),append(T1,[H1],L1),C1 is C-H1,solve(N0,N1,C1,L,L1,Hit,Mag,Bul,R).
start:-str(S),split_string(S,"\n,\s","\s",L0),pre(L0).
pre([]):-!.
pre([_,B,C|T]):-
concat_atom([H,N],/,B),atom_number(N,N0),atom_chars(H,L),maked(1,L,[],[],Tu,Hit),
length(Tu,N1),numlist(1,N1,Or),maplist(atom_number,Tu,Tu1),cir(N0,Tu1,Cir),length(Mag,N0),
solve(N0,0,Cir,Or,Tu1,Hit,Mag,[],R),disp(N0,R,C),pre(T).
ml(0,_,L,L).
ml(N1,R,L1,Re):-N is N1-1,(member(N,R)->L=[1|L1];L=[0|L1]),ml(N,R,L,Re).
disp(N0,R,C):-
ml(N0,R,[],L),atomics_to_string(L,"",S),(S==C->write("yes ");write(" no ")),writeln(S).
maked(_,[],Tu,Hit,Tu1,Hit):-reverse(Tu,Tu1).
maked(N,['['|T],Tu,Hit,R1,R2):-!,T=[H,_|T1],N1 is N+1,maked(N1,T1,[H|Tu],[N|Hit],R1,R2).
maked(N,[H|T],Tu,Hit,R1,R2):-N1 is N+1,maked(N1,T,[H|Tu],Hit,R1,R2).
%start.
str("0 3[2]3/6 000100
1 21[3]/6 000100
2 12[3]/6 000100
3 3[2]1/6 000100
4 3[2]3/6 000100
5 1[1]3/6 010000
6 [3]4[4]3/7 1000100
7 4[4]24/7 0000100
8 [4]41[1]/7 1000010
9 1[1]33[1]/8 01000001
10 [1]12[4][3]/8 10100001
11 2[2][1]12/8 01001000
12 1[2][2][1]34/9 011100000
13 [4]1141[2]/9 100000010
14 [3]33[3][2]2/9 100000110
15 [5]1[3]44[2][3]/10 0100101001
16 3[1][2]23[3][1]/10 0110110000
17 33[5]12[5][2]/10 0000010011
18 13[3]1[4][4][4][1]/11 00101100110
19 [5]3[2]35[1]1[4]/11 10001010001
20 4[1]4[5]342[5]/11 00001010100
21 [5][4]55[2][2][4]33/12 001111100000
22 3[2]415[1][4][4]3/12 010101000100
23 3[2][4][2][4]4[5]4[1]/12 011001110010
24 3555[6]33[6]4[1]/13 0010010000010
25 4[1]32[6]3[3]4[3]4/13 0001100001001
26 2[2]14[3][1][6][4]63/13 0010011001010
27 2[9][9][9]8[2]3[4][8]2[1]8/15 011010100001110
28 [1][2][6]64[1][3]68[3][8]8/15 111001000011010
29 [7][6][5]54[5]8[5]53[8]1/15 010001110010001").
組み合わせを検証するほう
gcd(X,Y,G):-X=Y,G=X.
gcd(X,Y,G):-Y>X,Y1 is Y-X,gcd(X,Y1,G).
gcd(X,Y,G):-X>Y,gcd(Y,X,G).
lcm(X,Y,L):-gcd(X,Y,G), L is X*Y//G.
cir(N0,L,C):-foldl(plus,L,0,X),lcm(N0,X,C).
comb(0,_,[]). %combination
comb(N,[H|T],[H|L]):-N>0,N1 is N-1,comb(N1,T,L).
comb(N,[_|T],L):-N>0,comb(N,T,L).
sol(_,_,_,_,_,[],[]):-!.
sol(N0,N,C,[H|T],[_|T1],Hit,Mag):-
C>0,select(N,Mag,Mag1),member(H,Hit),delete(Hit,H,Hit1),cir(N0,T1,C1),
sol(N0,N,C1,T,T1,Hit1,Mag1).
sol(N0,N,C,[H|T],[H1|T1],Hit,Mag):-
C>0,not(member(N,Mag)),N1 is (N+H1) mod N0,append(T,[H],L),append(T1,[H1],L1),
C1 is C-H1,sol(N0,N1,C1,L,L1,Hit,Mag).
solve(N0,Or,Tu,Hit,Mag):-cir(N0,Tu,C),N1 is N0-1,length(Hit,N),numlist(0,N1,L),comb(N,L,Mag),
sol(N0,0,C,Or,Tu,Hit,Mag).
start:-str(S),split_string(S,"\n,\s","\s",L0),pre(L0).
pre([]):-!.
pre([_,B,C|T]):-
concat_atom([H,N],/,B),atom_number(N,N0),atom_chars(H,L),maked(1,L,[],[],Tu,Hit),length(Tu,N1),
numlist(1,N1,Or),maplist(atom_number,Tu,Tu1),solve(N0,Or,Tu1,Hit,Mag),disp(N0,Mag,C),pre(T).
ml(0,_,L,L).
ml(N1,R,L1,Re):-N is N1-1,(member(N,R)->L=[1|L1];L=[0|L1]),ml(N,R,L,Re).
disp(N0,R,C):-
ml(N0,R,[],L),atomics_to_string(L,"",S),(S==C->write("yes ");write(" no ")),writeln(S).
maked(_,[],Tu,Hit,Tu1,Hit):-reverse(Tu,Tu1).
maked(N,['['|T],Tu,Hit,R1,R2):-!,T=[H,_|T1],N1 is N+1,maked(N1,T1,[H|Tu],[N|Hit],R1,R2).
maked(N,[H|T],Tu,Hit,R1,R2):-N1 is N+1,maked(N1,T,[H|Tu],Hit,R1,R2).
%start.
2018.2.6 すこし解説します。
逐次実行のほう。
solveのNには現在の弾倉の番号、Orには人の番号のリスト、TurにはOrに対応する人特有の弾倉の回転数、
Hitには犠牲者の番号、Magには弾倉のリスト(変数)が入っています。
選択された弾倉に0を代入(いずれにしても発射後は空砲になるため)し、
選んだ人(Orの先頭)が犠牲者なら、実弾の場合(Or,Tur,Hitから該当の要素を削除等)と空砲の場合の
双方の変化を追跡します。
Magが0で満たされるまでにHitが空になれば成功、でなければ失敗してバックトラックします。
組み合わせのほう
solveのMagには弾の入った弾倉の番号の候補が入っています。
現在の弾倉と選んだ人の番号がMagに含まれている場合、
その人が犠牲者ならMagからその番号を削除し、犠牲者でない場合失敗し、次の候補を検証します。
最終的にMag(Hit)が空になれば成功です。
循環のチェックには履歴を使えなさそうでしたので、同じメンバーで、
弾倉数と、人特有の弾倉の回転数の合計の最小公倍数を超える回転があった場合失敗としました。
2018.2.9 追加
前に循環のチェックに履歴を使えなさそうと書きましたが、使えました。
メンバーが変わるときに履歴をリセットすればよいのでした。
逐次実行のほうのみ他の微修正と一緒に載せます。
2018.2.10 追加
昨日のをsolve/9の記述がよりすっきりしたものに差し替えますのであしからず。
solve(_,_,_,_,_,[],_,L,L):-!.
solve(_,N,C,[H|_],_,_,L,_,_):-(member(N:H,C);(include(var,L,L1),L1=[])),!,fail.
solve(N0,N,_,[H|T],[_|T1],Hit,Mag,Bul,R):-
nth0(N,Mag,X),var(X),nth0(N,Mag,0),member(H,Hit),delete(Hit,H,Hit1),
C1=[N:H],append(Bul,[N],Bul1),solve(N0,N,C1,T,T1,Hit1,Mag,Bul1,R).
solve(N0,N,C,[H|T],[H1|T1],Hit,Mag,Bul,R):-
nth0(N,Mag,0),N1 is (N+H1) mod N0,append(T,[H],L),append(T1,[H1],L1),
C1=[N:H|C],solve(N0,N1,C1,L,L1,Hit,Mag,Bul,R).
start:-str(S),split_string(S,"\n,\s","\s",L0),pre(L0),!.
pre([]):-!.
pre([_,B,C|T]):-
concat_atom([H,N],/,B),atom_number(N,N0),atom_chars(H,L),maked(1,L,Tu,Hit),
length(Tu,N1),numlist(1,N1,Or),maplist(atom_number,Tu,Tu1),length(Mag,N0),
solve(N0,0,[],Or,Tu1,Hit,Mag,[],R),disp(N0,R,C),pre(T).
ml(0,_,L,L).
ml(N1,R,L1,Re):-N is N1-1,(member(N,R)->L=[1|L1];L=[0|L1]),ml(N,R,L,Re).
disp(N0,R,C):-
ml(N0,R,[],L),atomics_to_string(L,"",S),(S==C->write("yes ");write(" no ")),writeln(S).
maked(_,[],[],[]):-!.
maked(N,['['|T],[H|Tu],[N|Hit]):-!,T=[H,_|T1],N1 is N+1,maked(N1,T1,Tu,Hit).
maked(N,[H|T],[H|Tu],Hit):-N1 is N+1,maked(N1,T,Tu,Hit).