オフラインリアルタイムどう書く(E31)

問題はこちら->http://nabetani.sakura.ne.jp/hena/orde31rotnum/
for loop で解くつもりだったのとb進数の扱いが便利そうでしたのでJuliaで書きました。
解き方の見当がつかないという問題ではありませんでしたが、
どう解けば、スタックオーバや計算量の過剰らが無く書きやすいかを考えたり、
ちょっとした勘違いがあったりして結構時間がかかりました。
結局わかりやすい再帰で書き、いちいち上限を超えていないか確認しましたが、
上記に関しては杞憂でした。
結果は二数のぐるぐる数の差で求めています。
b進数の桁の小さい部分のぐるぐる数の数は、(b-1)*(1+2+2^2+2^3+...)=(b-1)*(2^m-1)となり、
最大桁の部分は,最上位桁をxとすると、1からxについて、再帰でぐるぐる数を作り、
上限値を越えなければ、ぐるぐる数の個数に加えます。
(1からx-1までを(x-1)*2^m)とすることも可能ですが、速さは変わりません)
Prologでも書くかどうかは未定です。

```Julia
#julia 0.6,0.52

str="0 4,1313,3012  12
1 10,100,110  0
2 36,zoo,zyz  0
3 4,1300000,2222221  0
4 2,1,1  1
5 2,1000,1110  7
6 4,21,132  8
7 10,28,79  10
8 36,q,1r  12
9 28,bjb,g9a  16
10 20,2i9d,5id4  24
11 5,12000,24141  24
12 6,1245,5145  28
13 36,1,z  35
14 14,277,dc1  42
15 35,9iy,l5p  44
16 17,7be,19b1  44
17 18,96f,236g  52
18 23,b1f,1k81  56
19 6,143424,353115  64
20 5,3401,40123  67
21 4,321,123022  102
22 13,1b0,8a72  108
23 20,62,339f  124
24 24,f8h,bcn0  124
25 31,do3,78no  124
26 17,727,ced4  136
27 5,14,222243  154
28 16,3c5,100bb  168
29 9,353,80016  200
30 21,h7d,34504  220
31 11,20a,78926  224
32 12,b0,77996  238
33 3,212,11112012  254
34 22,6f2,789hd  340
35 36,5l6,tvmw  352
36 25,db8,99b08  376
37 32,hpi,556a7  376
38 29,1cl,456d2  396
39 34,dli,455u7  404
40 15,ced,3345c1  424
41 30,601,7780o  428
42 3,22,22000021  445
43 5,440,4012303  446
44 27,hg,aaamk  480
45 33,suv,defn7  480
46 2,11,111101110  492
47 35,60e,9aamd  528
48 7,33,3445635  542
49 4,120,22330013  550
50 23,8fk,lm066  564
51 6,142,5001252  568
52 8,111,3344567  572
53 26,4na,klmib  600
54 19,32a,6678g3  672
55 7,605,6011223  680
56 6,15,11235050  692
57 9,664,5567833  746
58 10,909,4556846  746
59 10,991,5555766  769
60 8,757,7700001  812
61 36,6pku,27wr28  856
62 35,6n89a,j1dlik  1024
63 34,7gehm,m0anuo  1088
64 10,3268665,134217728  1856
65 11,571016a,47352388a  2624
66 4,10030022033,10203020123103  21504
67 3,22111101011101,11021122211120221  100352
68 2,101001011010110000110101,110101110001110110110101  3240321"

function calc(k,n,x,y,b)
   if k==-1
     return 1
   else
     y1=y+x*b^k
     if y1<=n
        res1=calc(k-1,n,x,y1,b)
    else
        res1=0
    end
     x1=rem(x+1,b)
     y2=y+x1*b^k  
     if y2<=n
        res2=calc(k-1,n,x1,y2,b)
     else
        res2=0
     end
     return res1+res2
   end
end

function solve(s2,s1,b)
  m=length(s1)-1
  k1=(b-1)*(2^m-1)
  h1=0
  n=parse(Int32,s1,b)
  for i in 1:parse(Int32,s1[1],b)
     h1+=calc(m-1,n,i,i*b^m,b)
  end
  n=parse(Int32,s2,b)-1
  s2=base(b,n)
  m=length(s2)-1
  k2=(b-1)*(2^m-1)
  h2=0
  for i in 1:parse(Int32,s2[1],b)
     h2+=calc(m-1,n,i,i*b^m,b)
  end
  return h1-h2+k1-k2
end

function main()
  str1=split(str,"\n")
  for s in str1
    s=replace(s, r"\t", s" ")
    s1=split(s,r"\s+")
    s2=split(s1[2],",")
    b=parse(Int32,s2[1])
    ans=solve(s2[2],s2[3],b)
    if ans==parse(Int32,s1[3])
        sel="pass"
    else
        sel="fail"
    end
    print(sel," ",ans,"\n")
  end
end

main()
```
2019.3.11追加
結局Prologで書きましたので追加します。
最大桁の数をx1とすると(x1-1)*b^m+(b-1)b^(m-1)+...の部分までを、前の投稿時述べましたように
(b-1)*(1+2+2^2+2^3+...)+(x1-1)*2^m=(b+x1-2)*2^m-(b-1)で計算し、
残り(x1*b^m からx1*b^m+x2*b^(m-1)+...まで)も一列ずつ右にずらしながら同様に処理する方法で、
最初に考えた時の最有力候補でした。
ただ一部で書き方が全く浮かんでこなかったのでいったんあきらめたのですが、
もう一度見直したところ、結構簡単に書けることが分かりました。
この方法だと各処理の部分は2^kか2^(k+1)になります。

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

tenton(B,X,R):-X==0->R=[0];tenton(X,B,[],R).
tenton(0,_,L,L):-!.
tenton(X,B,L,RL):-X1 is X div B,R1 is X-(X1*B),tenton(X1,B,[R1|L],RL).
ntoten(_,[],XR,XR):-!.
ntoten(B,[H|T],X,XR):-X1 is X*B+H,ntoten(B,T,X1,XR).

calc(B,[H|T],R):-
     calc(B,T,H,R1),length(T,N),R2 is (H+B-2)*2^N-(B-1),R is R1+R2.

calc(_,[],_,1).
calc(B,[H|T],C,R):-H==0,
     (C==0;(C+1) mod B==0),calc(B,T,0,R).
calc(B,[H|T],C,R):-
     C1 is (C+1) mod B,findall(X,(member(X,[C,C1]),X<H),XL),
     length(XL,N1),(N1>0->(length(T,N2),R1=N1*2^N2);R1=0),
     (member(H,[C,C1])->calc(B,T,H,R2);R2=0),R is R1+R2.
     
solve(B,NL,NL2,R):-
     ntoten(B,NL,0,X),X1 is X-1,tenton(B,X1,NL1),
     calc(B,NL1,R1),calc(B,NL2,R2),R is R2-R1,!.

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

pre([]):-!.
pre([_,B,C|T]):-
     atomics_to_string(L,",",B),L=[S1,S2,S3],atom_number(S1,N1),
     atom_codes(S2,A2),atom_codes(S3,A3),maplist(aton,A2,N2),
     maplist(aton,A3,N3),solve(N1,N2,N3,R),disp(R,C),pre(T).

disp(R,C):-
     number_string(R,S),(S==C->write("pass ");write(" fail ")),
     writeln(S),!.

aton(N,R):-N<60->R is N-48;R is N-87.

str("0 4,1313,3012  12
1 10,100,110  0
2 36,zoo,zyz  0
3 4,1300000,2222221  0
4 2,1,1  1
5 2,1000,1110  7
6 4,21,132  8
7 10,28,79  10
8 36,q,1r  12
9 28,bjb,g9a  16
10 20,2i9d,5id4  24
11 5,12000,24141  24
12 6,1245,5145  28
13 36,1,z  35
14 14,277,dc1  42
15 35,9iy,l5p  44
16 17,7be,19b1  44
17 18,96f,236g  52
18 23,b1f,1k81  56
19 6,143424,353115  64
20 5,3401,40123  67
21 4,321,123022  102
22 13,1b0,8a72  108
23 20,62,339f  124
24 24,f8h,bcn0  124
25 31,do3,78no  124
26 17,727,ced4  136
27 5,14,222243  154
28 16,3c5,100bb  168
29 9,353,80016  200
30 21,h7d,34504  220
31 11,20a,78926  224
32 12,b0,77996  238
33 3,212,11112012  254
34 22,6f2,789hd  340
35 36,5l6,tvmw  352
36 25,db8,99b08  376
37 32,hpi,556a7  376
38 29,1cl,456d2  396
39 34,dli,455u7  404
40 15,ced,3345c1  424
41 30,601,7780o  428
42 3,22,22000021  445
43 5,440,4012303  446
44 27,hg,aaamk  480
45 33,suv,defn7  480
46 2,11,111101110  492
47 35,60e,9aamd  528
48 7,33,3445635  542
49 4,120,22330013  550
50 23,8fk,lm066  564
51 6,142,5001252  568
52 8,111,3344567  572
53 26,4na,klmib  600
54 19,32a,6678g3  672
55 7,605,6011223  680
56 6,15,11235050  692
57 9,664,5567833  746
58 10,909,4556846  746
59 10,991,5555766  769
60 8,757,7700001  812
61 36,6pku,27wr28  856
62 35,6n89a,j1dlik  1024
63 34,7gehm,m0anuo  1088
64 10,3268665,134217728  1856
65 11,571016a,47352388a  2624
66 4,10030022033,10203020123103  21504
67 3,22111101011101,11021122211120221  100352
68 2,101001011010110000110101,110101110001110110110101  3240321").

```
2019.3.12追加
ちょっと説明を端折った感がありますので、
出題者の@Nabetaniさんの
https://qiita.com/Nabetani/items/d45273ca8e629d3a1a66
に同じ考え方の解説がありますので、ご覧になったら分かりやすいかもしれません。
少し補足しますと、x1と(x1+1) rem bのうちx2より小さいものの個数をnとしますと、
n*2^(m-1)がx1*b^m+x2*b^(m-1)-1までのぐるぐる数の数、
更にx2がx1と(x1+1) rem bのいずれかと等しければ再帰で下位の桁の値を求めます。