prolog advent calendar 12/16はタクシー数の記事で無限リストの話が出てきます。
私はそこでちょっと質問したのですが、それは「どう書く」の「多段階選抜」という問題を解いた時、
想定解では遅延評価（無限リスト）を使うようでしたが、
私は無限リストには不案内で普通の解き方で解いていましたので、
その辺の話題に興味があったからです。
ということで今回はその種の問題の解答を投稿します。
多段階選抜
問題はこちら->http://nabetani.sakura.ne.jp/hena/ord24eliseq/
Juliaではwhile ループで自然数の列を作りだし、必要なだけリストに貯めて置いて、コマンドが
2-9のときは割り切れない数のみ次の段階に送る
hのときは百個まで除きその後は次の段階に送る
c,sのときは、ペアの数の中大きいほうが平方数や立方数でないときのみ
小さいほうを次の段階に送る。
CやSのときは平方数や立方数が来たら、平方数や立方数でない数が来るまでため込み、
最小の数のみ次の段階に送る （平方数や立方数は消される場合もその前に一仕事するので）
Juliaにはcbrtという関数もありますが、誤差が小さいときに等しいと判定される可能性がありますので
組み込み関数は使いませんでした。（floorを使えばよいようですが完全かどうかわかりません）
# Julia 0.52,0.6
str="0 ss6cc24S 1,9,21,30,33,37,42,44,49,56
1 h 101,102,103,104,105,106,107,108,109,110
2 hh 201,202,203,204,205,206,207,208,209,210
3 hhh 301,302,303,304,305,306,307,308,309,310
4 2 1,3,5,7,9,11,13,15,17,19
5 22 1,5,9,13,17,21,25,29,33,37
6 222 1,9,17,25,33,41,49,57,65,73
7 3 1,2,4,5,7,8,10,11,13,14
8 33 1,2,5,7,10,11,14,16,19,20
9 333 1,2,7,10,14,16,20,23,28,29
10 s 1,2,4,5,6,7,9,10,11,12
11 ss 1,4,5,6,9,10,11,12,13,16
12 sss 4,5,9,10,11,12,16,17,18,19
13 S 1,3,4,6,7,8,9,11,12,13
14 SS 1,4,7,8,9,12,13,14,15,16
15 SSS 1,8,9,13,14,15,16,20,21,22
16 c 1,2,3,4,5,6,8,9,10,11
17 cc 1,2,3,4,5,8,9,10,11,12
18 ccc 1,2,3,4,8,9,10,11,12,13
19 C 1,3,4,5,6,7,8,10,11,12
20 CC 1,4,5,6,7,8,11,12,13,14
21 CCC 1,5,6,7,8,12,13,14,15,16
22 23 1,3,7,9,13,15,19,21,25,27
23 32 1,4,7,10,13,16,19,22,25,28
24 2h 201,203,205,207,209,211,213,215,217,219
25 h2 101,103,105,107,109,111,113,115,117,119
26 sC 1,4,5,6,7,9,10,11,12,13
27 Cs 1,4,5,6,7,8,10,11,12,13
28 s468 1,2,4,6,7,11,12,16,17,20
29 S468 1,3,4,7,8,12,13,16,18,21
30 cc579 1,2,3,4,8,9,11,13,15,16
31 CC579 1,4,5,6,8,11,13,15,17,18
32 85 1,2,3,4,6,7,9,10,12,13
33 sh 110,111,112,113,114,115,116,117,118,119
34 94h 150,151,154,155,156,158,159,160,163,164
35 h9c8 101,102,103,104,105,106,107,110,111,112
36 Cc3s 1,3,5,6,10,11,13,16,17,19
37 cs4h6 149,150,152,153,154,157,158,160,161,162
38 84523c 1,3,11,15,23,26,34,38,46,49
39 54C78hS 228,231,232,233,236,241,242,243,246,247
40 65h7ccs 151,152,153,154,157,158,160,163,164,165
41 c95hSc2C 145,147,151,153,156,159,162,164,168,171
42 c5h3Ss794 130,131,133,137,138,142,148,150,152,157
43 7ShscC846 129,130,131,134,135,139,141,142,146,148
44 cshSCCS7ch 253,254,256,259,260,261,263,264,265,266
45 hhC7849Ss6C 201,202,203,205,206,211,212,216,220,225
46 hhsc3C987Ccs 201,202,204,205,207,208,214,217,218,220
47 SC7S8hc59ss2 162,169,174,178,182,185,188,194,199,203
48 s7S6c35C9CShc 367,371,377,379,380,385,387,388,392,395
49 4scC3hh982Cc5s 422,426,430,434,447,451,459,463,471,479
50 23h465Ssc9CchC 1027,1033,1045,1047,1057,1069,1071,1075,1081,1093"
function pow(s,x)
if s=='S' || s=='s'
return x^2
else
return x^3
end
end
function calc(str)
n=0
while true
n+=1
push!(st[1],n)
for (j,s) in enumerate(str)
if '2'<= s && s<='9'
t[j]+=1
if t[j]==parse(Int,s)
shift!(st[j])
t[j]=0
break
else
push!(st[j+1],shift!(st[j]))
end
elseif s=='h'
if t[j]<100
t[j]+=1
shift!(st[j])
break
else
push!(st[j+1],shift!(st[j]))
end
elseif s=='C' || s=='S'
while pow(s,t[j])<st[j][end]
t[j]+=1
end
if length(st[j])==1 #実は length 関係ない
if pow(s,t[j])==st[j][1]
break
else
push!(st[j+1],shift!(st[j]))
end
else
if pow(s,t[j])==st[j][end]
break
else
push!(st[j+1],st[j][1])
st[j]=[]
end
end
elseif s=='c' || s=='s'
if length(st[j])==2
while pow(s,t[j])<st[j][2]
t[j]+=1
end
if pow(s,t[j])==st[j][2]
shift!(st[j])
break
else
push!(st[j+1],shift!(st[j]))
end
else
break
end
end
end
if length(st[end])>9
break
end
end
return st[end]
end
t=Array{Int,1}(20)
str1=split(str,"\n")
res=[]
st=[]
for s in str1
res=[]
s=replace(s, r"\t", s" ")
s1=split(s,r"\s+")
st=[[]]
for (i,v) in enumerate(s1[2])
push!(st,[])
t[i]=0
end
ans1=calc(s1[2])
ans=join(ans1,",")
if ans==strip(s1[3])
sel="pass"
else
sel="fail"
end
print(sel," ",ans[1:end],"\n")
end
Prologでは、再帰でnを増やし、リストの長さが10を終了条件としている以外同様です。
%swi-Prolog version 7.4.2
%start.
%:-initialization(start). % ideone
pow(S,N,M,N,X):-((S=='S';S=='s')->X is N^2;X is N^3),X>=M,!.
pow(S,N,M,R,X):-N1 is N+1,pow(S,N1,M,R,X).
calc1('h',N,[P2,P3],R1,R2):- % ikkai no sousa
!,N<100->(N1 is N+1,R1=N1,R2=[[],P3]);(R1=N,append(P3,P2,P31),R2=[[],P31]).
calc1(S,N,[P2,P3],R1,R2):-
(S=='C';S=='S'),!,last(P2,M),pow(S,N,M,N1,X),R1=N1,
(X=:=M->R2=[P2,P3];(P2=[H|_],append(P3,[H],P31),R2=[[],P31])).
calc1(S,N,[P2,P3],R1,R2):-
(S=='c';S=='s'),!,length(P2,K),(K=\=2->(R1=N,R2=[P2,P3]);
(last(P2,M),pow(S,N,M,N1,X),R1=N1,P2=[P21|P22],
(X=:=M->R2=[P22,P3];(append(P3,[P21],P31),R2=[P22,P31])))).
calc1(S,N,[P2,P3],R1,R2):-
atom_number(S,M),N1 is N+1,(N1=:=M->(R1=0,R2=[[],P3]);
(R1=N1,append(P3,P2,P31),R2=[[],P31])).
calc([],_,[X],L,R1,L,R):- % itijun
append(R1,[X],R),!.
calc(_,L2,[[]|T2],L0,R0,L,R):-
append(L0,L2,L),append(R0,[[]|T2],R),!. %N->V?,P2,P3->progression
calc([H1|T1],[N|T2],[P2,P3|T],L0,R0,L,R):-
calc1(H1,N,[P2,P3],R1,[R2,R3]),append(L0,[R1],L4),append(R0,[R2],R4),
calc(T1,T2,[R3|T],L4,R4,L,R).
solve(_,_,_,L,R):- % zentai no kurikaesi
last(L,L1),length(L1,10),R=L1,!.
solve(N,L,NL,[H|T],R):- %N->V?
append(H,[N],H1),calc(L,NL,[H1|T],[],[],NL1,RL1),
N1 is N+1,solve(N1,L,NL1,RL1,R).
solve(L,R):- %NL->VL?
length(L,N),length(NL,N),maplist(=(0),NL),
N1 is N+1,length(RL,N1),maplist(=([]),RL),solve(1,L,NL,RL,R),!.
start:-str(S),split_string(S,"\s\n","\s",L),pre(L),!.
pre([]):-!.
pre([_,B,C|T]):-
atom_chars(B,L),solve(L,R),atomics_to_string(R,",",S),disp(S,C),pre(T).
disp(R,C):-(R==C->Str=" yes ";Str=" no "),write(Str),writeln(R).
str("0 ss6cc24S 1,9,21,30,33,37,42,44,49,56
1 h 101,102,103,104,105,106,107,108,109,110
2 hh 201,202,203,204,205,206,207,208,209,210
3 hhh 301,302,303,304,305,306,307,308,309,310
4 2 1,3,5,7,9,11,13,15,17,19
5 22 1,5,9,13,17,21,25,29,33,37
6 222 1,9,17,25,33,41,49,57,65,73
7 3 1,2,4,5,7,8,10,11,13,14
8 33 1,2,5,7,10,11,14,16,19,20
9 333 1,2,7,10,14,16,20,23,28,29
10 s 1,2,4,5,6,7,9,10,11,12
11 ss 1,4,5,6,9,10,11,12,13,16
12 sss 4,5,9,10,11,12,16,17,18,19
13 S 1,3,4,6,7,8,9,11,12,13
14 SS 1,4,7,8,9,12,13,14,15,16
15 SSS 1,8,9,13,14,15,16,20,21,22
16 c 1,2,3,4,5,6,8,9,10,11
17 cc 1,2,3,4,5,8,9,10,11,12
18 ccc 1,2,3,4,8,9,10,11,12,13
19 C 1,3,4,5,6,7,8,10,11,12
20 CC 1,4,5,6,7,8,11,12,13,14
21 CCC 1,5,6,7,8,12,13,14,15,16
22 23 1,3,7,9,13,15,19,21,25,27
23 32 1,4,7,10,13,16,19,22,25,28
24 2h 201,203,205,207,209,211,213,215,217,219
25 h2 101,103,105,107,109,111,113,115,117,119
26 sC 1,4,5,6,7,9,10,11,12,13
27 Cs 1,4,5,6,7,8,10,11,12,13
28 s468 1,2,4,6,7,11,12,16,17,20
29 S468 1,3,4,7,8,12,13,16,18,21
30 cc579 1,2,3,4,8,9,11,13,15,16
31 CC579 1,4,5,6,8,11,13,15,17,18
32 85 1,2,3,4,6,7,9,10,12,13
33 sh 110,111,112,113,114,115,116,117,118,119
34 94h 150,151,154,155,156,158,159,160,163,164
35 h9c8 101,102,103,104,105,106,107,110,111,112
36 Cc3s 1,3,5,6,10,11,13,16,17,19
37 cs4h6 149,150,152,153,154,157,158,160,161,162
38 84523c 1,3,11,15,23,26,34,38,46,49
39 54C78hS 228,231,232,233,236,241,242,243,246,247
40 65h7ccs 151,152,153,154,157,158,160,163,164,165
41 c95hSc2C 145,147,151,153,156,159,162,164,168,171
42 c5h3Ss794 130,131,133,137,138,142,148,150,152,157
43 7ShscC846 129,130,131,134,135,139,141,142,146,148
44 cshSCCS7ch 253,254,256,259,260,261,263,264,265,266
45 hhC7849Ss6C 201,202,203,205,206,211,212,216,220,225
46 hhsc3C987Ccs 201,202,204,205,207,208,214,217,218,220
47 SC7S8hc59ss2 162,169,174,178,182,185,188,194,199,203
48 s7S6c35C9CShc 367,371,377,379,380,385,387,388,392,395
49 4scC3hh982Cc5s 422,426,430,434,447,451,459,463,471,479
50 23h465Ssc9CchC 1027,1033,1045,1047,1057,1069,1071,1075,1081,1093").
撤去作業の果てに現れる数列
http://nabetani.hatenablog.com/
https://sw-logic.com/Portfolio/Programing/CodeIQ/3011.php 問題と解答例
前問の作者が、CodeIQに出題されことについて書かれていましたので、読んでいましたら、
上記の問題とよく似た問題がありましたので解いてみました。
COdeIQの問題は、過去問を解いてもテストケースが少なくて自信がないのですが、
この問題は基本的には前問と同じですの大丈夫でしょう。
（どう書くの作者の方が、毎回多くのテストケースを作ってくださるのは有り難いです。）
素数のn個前の数を除去するには、連続するn+1個の数をリストに貯めて、
最後の数が素数なら最初の数を捨てて、次の段階にはなにも送らない。
最後の数が素数でなければ最初の数を次の段階に移す。
リストの要素がn+1より少なければ、何もせず次の段階に進む。
最後の段階で集まった数が10未満ならx->x+1にして最初に戻る。
pri(2):-!.
pri(X):-not(syn(X)).
syn(X):-floor(sqrt(X),Y),between(2,Y,N),X mod N =:=0,!.
calc1(N,[P2,P3],R2):-
length(P2,K),(K=\=N->(R2=[P2,P3]);
(P2=[H|T],last(P2,M),(pri(M)->R2=[T,P3];(append(P3,[H],P31),R2=[T,P31])))).
calc([],[X],R1,R):- % itijun
append(R1,[X],R),!.
calc(_,[[]|T2],R0,R):-
append(R0,[[]|T2],R),!. %P2,P3->progression
calc([H1|T1],[P2,P3|T],R0,R):-
calc1(H1,[P2,P3],[R2,R3]),append(R0,[R2],R4),
calc(T1,[R3|T],R4,R).
solve(_,_,L,R):- % zentai no kurikaesi
last(L,L1),length(L1,10),R=L1,!.
solve(N,L,[H|T],R):-
append(H,[N],H1),calc(L,[H1|T],[],RL1),
N1 is N+1,solve(N1,L,RL1,R).
solve(L,R):-
length(L,N),N1 is N+1,length(RL,N1),maplist(=([]),RL),
maplist(plus(1),L,L1),solve(0,L1,RL,R),!.
start:-case(L,A),solve(L,R),disp(R,A),fail.
start.
disp(R,C):-(R==C->Str=" yes ";Str=" no "),write(Str),writeln(R).
case([3,2,3],[3,6,9,15,19,22,23,27,30,31]).
case([2,3],[4,6,7,10,12,13,16,18,20,22]).
タクシー数
タクシー数とは、二つの正の三乗数の和として二通りに書ける最小の自然数ですが、
今回はタクシー数とその同型（「同型」と表示）を探します。
nを増やしつつnが「同型」の数かどうか調べるコードは、
advent calendar の導入部だけ読んで急遽考えました。
x=n div 2を求め、x以下の数の三乗根とxより大きくn以下の数の三乗根の組み合わせから、
各々の要素の三乗根の和がnになる二組があるか調べます。
%solve(4,R),write(R).
%:-initialization(main).
lim(N,R):-between(1,N,X),X^3>N,!,R is X-1.
taxi(N,R):-
N1 is N div 2,lim(N1,LN),lim(N,HN),N4 is LN+1,findall(X:Y,(between(1,LN,X),
between(N4,HN,Y),X^3+Y^3=:=N),R),length(R,M),M>=2,!.
solve(_,N,L,R):-length(L,N),reverse(L,R),!.
solve(M,N,L,R):-(taxi(M,L1)->L2=[L1|L];L2=L),M1 is M+1,solve(M1,N,L2,R).
solve(N,R):-solve(4,N,[],R).
main:-solve(4,R),write(R).
advent calendarの記事
https://qiita.com/sym_num/items/e618d36f482d0226b5db
を読み、また
https://math-jp.net/2017/03/26/taxi-number-2/
でエクセルで多くの「同型」を求めているのを見て、
上記のコード得られるのは妥当な時間内にせいぜい数個、一応メモ化でしたコードでも倍くらいでしたので、
4数から「同型」を求めるコードを書いてみる気になりました。
エレガントとはかけ離れていますが、
between(1,?,X),between(1,X-1,Y)のような感じで表の対角線より上を求め、表を大きくしていきます。
X,Yの三乗とその和を一組にしてリストに入れるとともに、そのリストに同じ和の組があれば、
その2組が求めるものです。
taxi/6の中にwritelnがあるのは、私の環境でデータが多いとき一括して表示できなかったからです。
%solve(100,N).
%:-initialization(main).
taxi(M,M,L,R,L,R).
taxi(M,N,L,R,FL,FR):-
V is M^3+N^3,E=N:M:V,(member(X:Y:V,L)->
(writeln([N^3+M^3:X^3+Y^3=V]),R1=[[N,M,X,Y,V]|R]);R1=R),
L1=[E|L],N1 is N+1,taxi(M,N1,L1,R1,FL,FR).
solve(X,R):-solve(X,1,[],[],L),reverse(L,R),!. %N ko mituikeru
solve(X,_,_,R,R):-length(R,X).
solve(X,M,L,R,FR):-taxi(M,1,L,R,L1,R1),M1 is M+1,solve(X,M1,L1,R1,FR).
main:-solve(100,R).
2019.2.24追加
オフラインリアルタイムどう書くE30の問題をerlangのプロセス間通信を使って解いてみたら、
https://qiita.com/smallbigcats/items/f78fca99796cf160ef39
速さもまあまあで面白かったので、「多段階選抜」と「撤去作業の果てに現れる数列」
にも応用してみました。
多段階選抜
solve/2から各段の操作の情報を持たせてプロセスcalc/2を作ると、
calcが逐次的に下の段の情報を持った子のプロセス(calc)を作ります。
最後に情報を持たないプロセスができたら、
数字を求めるメッセージ（req）を親のプロセスに送ります。
親のプロセスは、reqが来たらその親にreqを送ります。
親から{data,N}が送られてきたら、calc1/5で子に渡す数字があるか調べ、
あればPid! {data,N}で子に送り、なければ親にreqを送ります。
これを繰り返します。
最下段のプロセスは、数字が10個になったら親に{ans,Nl}を送ります。
他のプロセスは{ans,Nl}メッセージが来たら、親に同じメッセージを送ります。
solveのループではreqが来たら次の数字を送り、
{ans,Nl}が来たら、Nlを戻り値とします。
その数値をsolve内で答え合わせして終わりです。
コードを短くするために、C,c,S,sをまとめましたので、
0の代わりに二乗でも三乗でも元の数字と同じにならない数字として-2を使っています。
%Erlang/OTP 21,Eshell V10.1
% erl -> c(n24). ->n24:start().
-module(n24).
-export([calc/2,calc1/5,loop1/2,loop/2,solve/2,pow/3,str/0,start/0]).
pow(S,N,M)->
if
S =:=83 ; S =:=115->X = N*N;
true->X = N*N*N
end,
if
X>=M->{N,X};
true->N1 = N+1,pow(S,N1,M)
end.
calc1($h,Tn,On,Pid,Up)->
receive
{data,N}->
if
Tn<100->Tn1 = Tn+1,Up! req,calc1($h,Tn1,On,Pid,Up);
true->Pid! {data,N},calc1($h,Tn,On,Pid,Up)
end;
req->
Up! req,calc1($h,Tn,On,Pid,Up);
{ans,Nl}->
Up! {ans,Nl}
end;
calc1(S,Tn,On,Pid,Up) when S=:=99;S=:=115;S=:=67;S=:=83->
receive
{data,N}->
if
On==-2,S=/=67,S=/=83->Up! req,calc1(S,Tn,N,Pid,Up);
true->
if
S=:=99;S=:=115->Y=N,Z=On,{Tn1,X}=pow(S,Tn,Y);
S=:=67;S=:=83->Y=On,Z=N,{Tn1,X}=pow(S,Tn,Y)
end,
if
X=:=Y->Up! req,calc1(S,Tn1,N,Pid,Up);
true->Pid! {data,Z},calc1(S,Tn1,N,Pid,Up)
end
end;
req->
Up! req,calc1(S,Tn,On,Pid,Up);
{ans,Nl}->
Up! {ans,Nl}
end;
calc1(S,Tn,On,Pid,Up)->
receive
{data,N}->
Tn1 = Tn+1,
if
Tn1==S-48->Up! req,calc1(S,0,On,Pid,Up);
true->Pid! {data,N},calc1(S,Tn1,On,Pid,Up)
end;
req->
Up! req,calc1(S,Tn,On,Pid,Up);
{ans,Nl}->
Up! {ans,Nl}
end.
loop(Nl,Up)->
Up! req,
receive
{data,N}->
Nl1=Nl++[N],Ln=length(Nl1),
if
Ln<10->loop(Nl1,Up);
true->Nl1
end
end.
calc([],Up)->
Nl=loop([],Up),Up! {ans,Nl};
calc([S|T],Up)->
Pid=spawn(n24,calc,[T,self()]),calc1(S,0,-2,Pid,Up).
loop1(N,Pid)->
receive
req->
Pid! {data,N},N1 = N+1,loop1(N1,Pid);
{ans,Nl}->Nl
end.
solve(L,A)->
Pid=spawn(n24,calc,[L,self()]),Nl=loop1(1,Pid),
Sl=string:join(lists:map(fun(X)->integer_to_list(X) end,Nl),","),
if
Sl==A->Str="pass ";
true->Str="fail "
end,
io:fwrite("~s~s~n",[Str,Sl]).
start()->
S=str(),Str=string:tokens(S,"\n"),pre(Str).
pre([])-> ok;
pre([H|T])->
[_,LS,AS]=string:tokens(H," \t"),
solve(LS,AS),
pre(T).
str()->
"0 ss6cc24S 1,9,21,30,33,37,42,44,49,56
1 h 101,102,103,104,105,106,107,108,109,110
2 hh 201,202,203,204,205,206,207,208,209,210
3 hhh 301,302,303,304,305,306,307,308,309,310
4 2 1,3,5,7,9,11,13,15,17,19
5 22 1,5,9,13,17,21,25,29,33,37
6 222 1,9,17,25,33,41,49,57,65,73
7 3 1,2,4,5,7,8,10,11,13,14
8 33 1,2,5,7,10,11,14,16,19,20
9 333 1,2,7,10,14,16,20,23,28,29
10 s 1,2,4,5,6,7,9,10,11,12
11 ss 1,4,5,6,9,10,11,12,13,16
12 sss 4,5,9,10,11,12,16,17,18,19
13 S 1,3,4,6,7,8,9,11,12,13
14 SS 1,4,7,8,9,12,13,14,15,16
15 SSS 1,8,9,13,14,15,16,20,21,22
16 c 1,2,3,4,5,6,8,9,10,11
17 cc 1,2,3,4,5,8,9,10,11,12
18 ccc 1,2,3,4,8,9,10,11,12,13
19 C 1,3,4,5,6,7,8,10,11,12
20 CC 1,4,5,6,7,8,11,12,13,14
21 CCC 1,5,6,7,8,12,13,14,15,16
22 23 1,3,7,9,13,15,19,21,25,27
23 32 1,4,7,10,13,16,19,22,25,28
24 2h 201,203,205,207,209,211,213,215,217,219
25 h2 101,103,105,107,109,111,113,115,117,119
26 sC 1,4,5,6,7,9,10,11,12,13
27 Cs 1,4,5,6,7,8,10,11,12,13
28 s468 1,2,4,6,7,11,12,16,17,20
29 S468 1,3,4,7,8,12,13,16,18,21
30 cc579 1,2,3,4,8,9,11,13,15,16
31 CC579 1,4,5,6,8,11,13,15,17,18
32 85 1,2,3,4,6,7,9,10,12,13
33 sh 110,111,112,113,114,115,116,117,118,119
34 94h 150,151,154,155,156,158,159,160,163,164
35 h9c8 101,102,103,104,105,106,107,110,111,112
36 Cc3s 1,3,5,6,10,11,13,16,17,19
37 cs4h6 149,150,152,153,154,157,158,160,161,162
38 84523c 1,3,11,15,23,26,34,38,46,49
39 54C78hS 228,231,232,233,236,241,242,243,246,247
40 65h7ccs 151,152,153,154,157,158,160,163,164,165
41 c95hSc2C 145,147,151,153,156,159,162,164,168,171
42 c5h3Ss794 130,131,133,137,138,142,148,150,152,157
43 7ShscC846 129,130,131,134,135,139,141,142,146,148
44 cshSCCS7ch 253,254,256,259,260,261,263,264,265,266
45 hhC7849Ss6C 201,202,203,205,206,211,212,216,220,225
46 hhsc3C987Ccs 201,202,204,205,207,208,214,217,218,220
47 SC7S8hc59ss2 162,169,174,178,182,185,188,194,199,203
48 s7S6c35C9CShc 367,371,377,379,380,385,387,388,392,395
49 4scC3hh982Cc5s 422,426,430,434,447,451,459,463,471,479
50 23h465Ssc9CchC 1027,1033,1045,1047,1057,1069,1071,1075,1081,1093".
撤去作業の果てに現れる数列
http://nabetani.hatenablog.com/entry/2018/10/03/221322
https://blog.goo.ne.jp/r-de-/a4cf8c21b28069ac8cb7cd0002e4576a?fm=entry_awc
テストケースは上記より拝借しました。
（先に投稿したprologのプログラムも改めて検証してみましたがすべてpassしました。）
%Erlang/OTP 21,Eshell V10.1
% erl -> c(c50). ->c50:start().
-module(c50).
-export([pri/1,pri/2,f/2,start/0,take/2,loop2/4,loop1/2,loop/2]).
pri(X) when X<2->false;
pri(2)->true;
pri(X)->Y=trunc(math:floor(math:sqrt(X+1))),pri(Y,X).
pri(1,_)->true;
pri(Y,X)->
if
X rem Y =/=0->pri(Y-1,X);
true->false
end.
take([],Up)->
Nl=loop([],Up),Up! {ans,Nl};
take([S|T],Up)->
Pid=spawn(c50,take,[T,self()]), % Pid iranai?
loop2(S,[],Pid,Up).
loop(Nl,Up)->
Up! req,
receive
{data,N}->
Nl1=Nl++[N],Ln=length(Nl1),
if
Ln<10->loop(Nl1,Up);
true->Nl1
end
end.
loop2(S,Dl,Pid,Up)->
receive
{ans,Nl}->
Up! {ans,Nl};
{data,X}->
if
length(Dl)<S->Dl1=Dl++[X],Up! req,loop2(S,Dl1,Pid,Up);
true->[H|T]=Dl,Dl1=T++[X],
case pri(X) of
true->Up! req;
false->Pid! {data,H}
end,
loop2(S,Dl1,Pid,Up)
end;
req->
Up! req,loop2(S,Dl,Pid,Up)
end.
loop1(Fr,Pid)->
receive
req->
Pid! {data,Fr},
Fr1 = Fr+1,
loop1(Fr1,Pid);
{ans,Nl}->
Nl
end.
f(L,A)->
Pid=spawn(c50,take,[L,self()]),
Nl=loop1(0,Pid),
if
Nl==A->Str="pass ";
true->Str="fail "
end,
io:format("~s~p~n",[Str,Nl]).
start()->
f([3,2,3],[3,6,9,15,19,22,23,27,30,31]),
f([2,3],[4,6,7,10,12,13,16,18,20,22]),
f([1,4,2,2,2,4,2,1,3,3,1,1,2,2,2,1,3,4,3,2],[0,1260,1327,1328,1329,1330,1331,1332,1333,1339]),
f([3,3,6,4,3,2,3,1,1,2,2,3,6,5,4,3,3,3,4,3],[1,1307,1313,1327,1328,1329,1330,1331,1332,1333]),
f([2,1,1,2,1,2,2,3,2,1,2,2,1,1,1,2,1,1,2,2],[2,1129,1130,1131,1134,1327,1328,1329,1330,1331]),
f([1,3,2,1,1,2,5,4,3,5,4,4,4,3,2,2,2,5,3,3],[3,61,1123,1328,1330,1916,2287,2470,2477,2480]),
f([1,4,2,1,1,3,2,1,3,4,1,1,3,1,4,2,2,2,4,2],[892,1262,1327,1332,1381,2447,2477,2478,2971,3023]),
f([5,2,2,1,3,4,2,4,4,1,5,2,5,2,2,5,5,3,4,1],[1669,2166,2557,2971,2973,3271,3739,3745,3787,3953]),
f([5,2,2,1,1,4,2,4,6,5,7,7,3,2,3,2,4,2,1,3],[513,1327,1329,1381,1382,1385,1631,1675,2171,3271]),
f([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1129,1130,1327,1328,1329,1330,1331,1332,1333,1334]),
f([1,100,1,100,1,100,1,100,1,100,1,100,1,100,1,100,1,100,1,100],[169,200,204,209,214,354,356,701,702,763]),
f([100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100],[2,28,41,94,145,166,167,184,187,209]),
f([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20],[327,480,711,993,1263,1382,1735,2477,2499,3313]),
f([20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1],[85,224,271,272,274,275,292,294,295,296]).