オフラインリアルタイムどう書く E22 の問題

問題はこちら->http://nabetani.sakura.ne.jp/hena/orde22numord/
1億という数にビビッて計算で解いてみました。
数の列の中にどうしても小さい数や大きい数が混ざってしまいますので、
いわゆる漸近法をつかってみました。
数の列の中の位置を求めるのに、最小値の桁未満で足切りしていますので、
条件の設定が簡単になっています。
このプログラムでは、位置を直接は使わず、1からX番目を求めて、
その中の、最小値未満で同じ桁の数の個数を足し、
大きい数は、求めた位置の数を最大値と同じ桁にしたものと最大値を比較して、
その差を足して新しい位置を求めることを繰り返すことで、目的の位置に達します。
私は、論理を厳密に突き詰められず、試行錯誤に頼る癖があり、
この問題はなかなかバグな取れずに難渋しました。
後から出された3月7日の問題のほうが先にできてしまいました。
足切りをしないプログラムも作ろうと思ったのですが成功しませんでした。
ptol->数の列での位置からD進数を表すリストを求める。
ltop->D進数を表すリストからを求める>数の列での位置をもとめる。

```Prolog
tenton(0,_,L,L):-!.
tenton(X,B,L,RL):-X1 is X div B,R1 is X mod 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).

ptol(_,_,_,0,R,R):-!.
ptol(0,D,K,X,L,R):-
      Y is (D^K-1) div (D-1),N is X div Y,M is X mod Y,K1 is K-1,
      (M=:=0->(X1 is Y-1,(L==[]->N1=N;N1 is N-1));
      ((L==[]->N1 is N+1;N1=N),X1 is M-1)),append(L,[N1],L1),ptol(0,D,K1,X1,L1,R).
ptol(I,D,K,X,L,R):-
      Y is D^I*(D^K-1) div (D-1),N is X div Y,M is X mod Y,I1 is I-1,
      (M=:=0->(X1 is Y,(L==[]->N1=N;N1 is N-1));
      ((L==[]->N1 is N+1;N1=N),X1 is M)),append(L,[N1],L1),ptol(I1,D,K,X1,L1,R).

ptol0(K1,D,K2,X,R):-I is K1-1,K is K2-K1+1,ptol(I,D,K,X,[],R),!.

ltop(_,_,_,_,[],N,N):-!.
ltop(0,_,_,1,[X],_,X):-!.
ltop(F,0,D,K,[H|T],N,R):-
      (F=:=0->H1 is H-1;H1=H),X is H1*(D^K-1) div (D-1),
      K1 is K-1,N1 is N+X+1,F1 is F+1,ltop(F1,_,D,K1,T,N1,R).
ltop(F,I,D,K,[H|T],N,R):-
      (F=:=0->H1 is H-1;H1=H),X is H1*D^I*(D^K-1) div (D-1),
      N1 is N+X,I1 is I-1,F1 is F+1,ltop(F1,I1,D,K,T,N1,R).

ltop0(K1,D,K2,L,FN):-I is K1-1,K is K2-K1+1,ltop(0,I,D,K,L,0,FN),!.

dec(0,L,L):-!.
dec(K,L,RL):-K1 is K-1,dec(K1,L,L1),reverse(L1,[_|T]),reverse(T,RL).

solve(F,T,D,X,R):-
      tenton(F,D,[],FL),tenton(T,D,[],TL),length(FL,K1),length(TL,K2),
      asy(FL,F,FN,K1,TL,T,TN,K2,X,X,D,R1),ntoten(D,R1,0,R),!.

asy(FL,F,FN,K1,TL,T,TN,K2,X,TX,D,R):-
      ptol0(K1,D,K2,TX,RL),length(RL,LN),
      (LN>K1->(W is LN-K1,dec(W,RL,RL1),ltop0(K1,D,K1,RL1,N));ltop0(K1,D,K1,RL,N)),
      ltop0(K1,D,K1,FL,FN1),(N<FN1->V is N;V is FN1-1),
      length(RL,K3),(K3=K2->ntoten(D,RL,0,Y);(K4 is K2-K3,con(D,K4,RL,Y))),
      (Y<T->Y1=T;Y1=Y),
      (TX-X<Y1-T+V->(X1 is X+Y1-T+V,asy(FL,F,FN,K1,TL,T,TN,K2,X,X1,D,R));R=RL).

con(D,K,L,Y):-conv(K,L,L2),ntoten(D,L2,0,Y1),Y is Y1-1.

conv(K,L,L2):-length(L1,K),maplist(=(0),L1),append(L,L1,L2).

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

pre([]):-!.
pre([_,B,C,D,E,F|T]):-
      maplist(atom_number,[B,C,D,E,F],[B1,C1,D1,E1,F1]),E2 is E1,solve(B1,C1,D1,E2,R),
      (R=:=F1->Str=" pass";Str=" fail"),write(Str),write(" "),writeln(R->F),pre(T).

myatom_char(X,Y):-atom_chars(Y,X).

str("0       2,15,3,8        14
1       6,8,8,1         8
2       6,6,5,1         6
3       4,11,5,2        6
4       9,17,8,2        10
5       73,82,18,5      77
6       70,149,2,48     95
7       82,119,15,26    107
8       40,127,26,47    86
9       851,950,31,89   939
10      660,807,34,143  802
11      962,1227,34,186         1075
12      544,1258,25,245         869
13      1208,7380,2,803         4630
14      2,100000000,10,1        10
15      1642,6626,3,4354        2029
16      8623,15873,2,4188       12810
17      7013,16409,17,3919      10931
18      7222,13243,19,3623      10844
19      4421,87412,5,62080      60697
20      51812,61593,22,2957     54768
21      44260,67742,17,15128    59387
22      90929,696974,36,84356   175284
23      1,100000000,2,50000000  92108858
24      101262,924931,7,341846  358105
25      211114,675661,33,312769         523882
26      1,100000000,36,50000000         11855060
27      1,100000000,10,100000000        99999999
28      826566,1444644,36,186226        1012791
29      6687091,6985458,4,251580        6938670
30      4219082,6179401,12,538113       4757194
31      7781931,8634872,23,217457       7999387
32      818218,64845924,12,57752258     30039084
33      4987258,11760092,32,6741567     11728824
34      7075964,28431054,22,11548591    18624554
35      26065964,66252692,18,29196596   63208819
36      66097362,104618756,16,32740764  98838125").
```
2018.3.14追加
上の記事の
ltop->D進数を表すリストからを求める>数の列での位置をもとめる。
は
ltop->D進数を表すリストから数の列での位置をもとめる。
の間違いです。
また上のコードでも間違いではありませんが、asyのltop0(K1,D,K1,FL,FN1)は、
solve中にあるのがより正しいコードです。
その他の部分も整理して該当部分のみ再掲載します。

```Prolog
small(D,K1,RL,FN,V):-
      length(RL,LN),(LN>K1->(W is LN-K1,dec(W,RL,RL1),ltop0(K1,D,K1,RL1,N));
      ltop0(K1,D,K1,RL,N)),(N<FN->V is N;V is FN-1).

big(D,K2,T,RL,V):-
      length(RL,K3),(K3=K2->ntoten(D,RL,0,Y1);(K4 is K2-K3,con(D,K4,RL,Y1))),
      (Y1=<T->V=0;V is Y1-T).

solve(F,T,D,X,R):-
      tenton(F,D,[],FL),tenton(T,D,[],TL),length(FL,K1),length(TL,K2),
      ltop0(K1,D,K1,FL,FN),asy(FL,F,FN,K1,TL,T,K2,X,X,D,R1),ntoten(D,R1,0,R),!.

asy(FL,F,FN,K1,TL,T,K2,X,TX,D,R):-
      ptol0(K1,D,K2,TX,RL),small(D,K1,RL,FN,VS),big(D,K2,T,RL,VB),
      (TX-X<VS+VB->(X1 is X+VS+VB,asy(FL,F,FN,K1,TL,T,K2,X,X1,D,R));R=RL).
```