オフラインどう書く第11回参考問題解答

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

最初はPrologで解きました。
数える数列の開始点を1ずつ後ろにずらしながら以下の処理をします。(for/3)
　　　　(N:最後の数字、H:最初の数、T:残りの数列)
　数える数列の間隔を1ずつ増やしながら以下の処理をします。(for0/4)
　　　　　(D:間隔)
　　　連続する(等間隔の)数列の数を数え最長の数を得ます。 (cal0/6)
　　　　　　(X:等差数列の数字)
　　　間隔ごとの長さを比較します。(for0/4)
　開始点ごとの長さを比較します。(for/3)

```Prolog
%swi-Prolog  version 7.4.2
%start.
%:- initialization(start). %ideone

for(_,[],0).                                      
for(N,[H|T],R):-for(N,T,R1),for0(N,H,T,R2),R is max(R1,R2).
for0(_,_,[],0).                                  
for0(N,H0,[H|T],R):-for0(N,H0,T,R1),D is H-H0,cal0(N,D,H,T,2,R2),R is max(R1,R2).
cal0(N,D,X,L,R1,R):-X1 is X+D,X1=<N,member(X1,L),!,R2 is R1+1,cal0(N,D,X1,L,R2,R).
cal0(_,_,_,_,R,R).                                 

solve([_],1):-!.
solve(L,R):-last(L,N),for(N,L,R),!.

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

        %split_string(S,"\n","",L) demo yoi
pre([]).
pre([_,B,C,_|T]):-atom_chars(B,L1),maplist(ston,L1,L),solve(L,R),disp(R,C),pre(T).

disp(R,C):-number_chars(C1,C),(R=:=C1->S1="pass  ";S1="fail  "),
            write(S1),writeln(R).
            
ston(S,N):-string_codes(S,[X]),(X>96->N is X-87;N is X -48).

str("0  12345abcz       5       12345
1       012abku         4       0aku
2       01245689cdeghik         6       048cgk
3       0       1       0
4       m       1       m
5       01      2       01
6       az      2       az
7       0az     2       0a
8       0ak     3       0ak
9       05ak    3       05a
10      01349acdrsuv    2       01
11      01245789efgipqstux      3       012
12      0123456789abcdefghijklmnopqrstuvwxyz    36      0123456789abcdefghijklmnopqrstuvwxyz
13      02468acegikmoqsuwy      18      02468acegikmoqsuwy
14      0369cfilorux    12      0369cfilorux
15      048cgkosw       9       048cgkosw
16      05afkpuz        8       05afkpuz
17      0123456789abcdefghjklmnopqrstuvwxyz     18      0123456789abcdefgh
18      0123456789bcdefghijklmopqrstuvwxyz      12      0369cfilorux
19      0156abfgklpquv  7       05afkpu
20      0167cdijopuv    6       06ciou
21      0178eflmst      5       07els
22      0189ghopwx      5       08gow
23      019aijrs        4       09ir
24      012567abcfghklmpqruvw   7       05afkpu
25      012678cdeijkopquvw      6       06ciou
26      012789efglmnstu         5       07els
27      01289aghiopqwxy         5       08gow
28      0129abijkrst    4       09ir
29      01235678abcdfghiklmnpqrsuvwx    7       05afkpu
30      01236789cdefijklopqruvwx        12      0369cfilorux
31      0123789aefghlmnostuv    5       07els
32      012389abghijopqrwxyz    5       08gow
33      01239abcijklrstu        4       0123
34      368acdknouvz    4       68ac
35      369chikmnopqruwx        6       mnopqr
36      05689cdefghijklmnopqrstvwy      18      cdefghijklmnopqrst
37      2489abdeiklrsuvwz       4       28ek
38      678bhijklnpqrsuvwxyz    6       hjlnpr
39      1246cfjkopquxz  5       fkpuz
40      123459abcefhilmotuvx    6       9cfilo
41      02578acdefikmopqsuvwxz  8       05afkpuz
42      135abdefghijlopstuwz    7       defghij
43      0126789fgjnotuvxy       5       29gnu
44      2345678defjkmnoqrtvwxy  7       2345678
45      02568bdemnostw  5       258be
46      145689bdfhilnqrstvwxz   6       159dhl
47      4aghjrtuvwxyz   7       tuvwxyz
48      158achklmqstwy  3       5ht
49      012346abceghjknortv     5       01234  ").
```
等差数列の要素を除いていく方法でも解いてみました。
間隔別に分けます。(solve4/3)　
　　(第一引数:間隔のリスト、第二引数:数列)
最初から該当する数がある間は長さを1ずつ増やして進みます。
その間使わなかった数はメモリ(M)にれます。(solve4/6の二節目)
なくなったら、その等差数列の長さとそれ以前の最大値(Vに保存)の大きいほうをV1に入れ、
残りの数列とメモリの数列を合わせた数列を調べます。(solve4/6の三節目)
数字が一個になったら、その時の等差数列の長さと保持した数の大きいほうを
その間隔の最長値とします。(solve4/6の一節目)
　　(第一引数：間隔のリスト、第二引数:数列、第四引数:現在の等差数列の長さ)
間隔ごとに同じ操作をして長さを比較し大きいほうを選びます。(solve4/3)
速さは同じくらいです。

```Prolog

solve(L,R):-length(L,N),(N=:=1->R=1;(last(L,X),numlist(1,X,L2),solve4(L2,L,R))).

solve4([_],[_],_,R1,R2,R):-R is max(R1,R2),!.
solve4([H1],[H|T],M,R0,V,R):-
      X is H+H1,member(X,T),!,R1 is R0+1,append(M1,[X|TX],T),
      append(M,M1,M2),solve4([H1],[X|TX],M2,R1,V,R).
solve4([H1],[_|T],M,R0,V,R):-
     V1 is max(R0,V),append(M,T,L),solve4([H1],L,[],1,V1,R),!.
solve4([],_,0):-!.
solve4([H1|T1],[H|T],R):-solve4([H1],[H|T],[],1,0,R11),
     solve4(T1,[H|T],R2),max_list([R11,R2],R),!.

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

split(S,L):-atomics_to_string(L,",",S).

pre([]).
pre([_,B,C,_|T]):-atom_chars(B,L1),maplist(ston,L1,L),solve(L,R),disp(R,C),pre(T).

disp(R,C):-number_chars(C1,C),(R=:=C1->S1="pass  ";S1="fail  "),
            write(S1),writeln(R).

ston(S,N):-string_codes(S,[X]),(X>96->N is X-87;N is X -48).

```
 
juliaで別解を試みました。
ar[1:36]の、添字が数列の数字+1番目の要素を1,他を0とします。
dp[1:36,1:36]（dp[arの添え字,等差j]）を0で初期化します。
ar[i]が1ならdp[i,j]=1とし、更にar[i-j]=1ならdp[i,j]+=dp[i-j,j]とします。

```Julia
#julia v 0.6,1.3

str="0  12345abcz       5       12345
1       012abku         4       0aku
2       01245689cdeghik         6       048cgk
3       0       1       0
4       m       1       m
5       01      2       01
6       az      2       az
7       0az     2       0a
8       0ak     3       0ak
9       05ak    3       05a
10      01349acdrsuv    2       01
11      01245789efgipqstux      3       012
12      0123456789abcdefghijklmnopqrstuvwxyz    36      0123456789abcdefghijklmnopqrstuvwxyz
13      02468acegikmoqsuwy      18      02468acegikmoqsuwy
14      0369cfilorux    12      0369cfilorux
15      048cgkosw       9       048cgkosw
16      05afkpuz        8       05afkpuz
17      0123456789abcdefghjklmnopqrstuvwxyz     18      0123456789abcdefgh
18      0123456789bcdefghijklmopqrstuvwxyz      12      0369cfilorux
19      0156abfgklpquv  7       05afkpu
20      0167cdijopuv    6       06ciou
21      0178eflmst      5       07els
22      0189ghopwx      5       08gow
23      019aijrs        4       09ir
24      012567abcfghklmpqruvw   7       05afkpu
25      012678cdeijkopquvw      6       06ciou
26      012789efglmnstu         5       07els
27      01289aghiopqwxy         5       08gow
28      0129abijkrst    4       09ir
29      01235678abcdfghiklmnpqrsuvwx    7       05afkpu
30      01236789cdefijklopqruvwx        12      0369cfilorux
31      0123789aefghlmnostuv    5       07els
32      012389abghijopqrwxyz    5       08gow
33      01239abcijklrstu        4       0123
34      368acdknouvz    4       68ac
35      369chikmnopqruwx        6       mnopqr
36      05689cdefghijklmnopqrstvwy      18      cdefghijklmnopqrst
37      2489abdeiklrsuvwz       4       28ek
38      678bhijklnpqrsuvwxyz    6       hjlnpr
39      1246cfjkopquxz  5       fkpuz
40      123459abcefhilmotuvx    6       9cfilo
41      02578acdefikmopqsuvwxz  8       05afkpuz
42      135abdefghijlopstuwz    7       defghij
43      0126789fgjnotuvxy       5       29gnu
44      2345678defjkmnoqrtvwxy  7       2345678
45      02568bdemnostw  5       258be
46      145689bdfhilnqrstvwxz   6       159dhl
47      4aghjrtuvwxyz   7       tuvwxyz
48      158achklmqstwy  3       5ht
49      012346abceghjknortv     5       01234  "

function solve(s)
  ar=zeros(Int,36)
  for c in s
    if c<='9'
      ar[Int(c)-47]=1
    else
      ar[Int(c)-86]=1
    end
  end
  dp=zeros(Int,36,36)
  max=0
  for i in 1:36,j in 1:36
    if ar[i]==1
        dp[i,j]=1
        if i-j>=1 && ar[i-j]==1
           dp[i,j]+=dp[i-j,j]
       end
       if dp[i,j]>max
           max=dp[i,j]
       end
    end
  end
  return max
end
function main()
  for s in split(str,"\n")
    s1=replace(s, r"\t"=>s" ")
    s2=split(s1,r"\s+")
    ans=solve(s2[2])
    if ans==parse(Int,s2[3])
        sel="pass"
    else
        sel="fail"
    end
    print(sel," ",ans,"\n")
end
end

main()

```