オフラインどう書くE16・CodeIQ:単調増加連数の解答

オフラインリアルタイムどう書くE16の問題と同じ出題者のCodeIQの類題です。
勘違いしていなければこれで「どう書く」の問題すべて投稿したことになります。

どう書くE16の問題
問題はこちら->http://nabetani.sakura.ne.jp/hena/orde16nontri/

入力データn0に1を足します。n=n0+1
nとm=2^(k-1)との論理積をとることによってnのkけた目の数を判定しています。
k桁目で三連数になるとき、(n div m)*m+mでk-1桁以下を0にしてk桁目に1をたして、
最初から調べます。非三連数になるまで繰り返します。
単純な方法で効率が悪いかもしれませんが、テストケースの桁数が少ないので問題ありません。

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

tri(R,0,_,_,R).
tri(N,N1,B,T,R):-0 =:= N /\ N1->tri0(N,N1,B,T,R);tri1(N,N1,B,T,R).
tri0(N,N1,B,T,R):-B=:=0->tri3(N,N1,B,T,R);(N2 is N1 >> 1,tri(N,N2,0,1,R)).
tri1(N,N1,B,T,R):-B=:=1->tri3(N,N1,B,T,R);(N2 is N1 >> 1,tri(N,N2,1,1,R)).
tri3(N,N1,B,2,R):-N2 is (N div N1)*N1,N3 is N2+N1,pow(N3,N4),tri(N3,N4,1,1,R).
tri3(N,N1,B,T,R):-T1 is T+1,N5 is N1 >> 1,tri(N,N5,B,T1,R).

pow(N,R):-pow1(N,R1),R is  R1 >>1.
pow1(1,1):-!.
pow1(N1,R):-N2 is N1 >> 1,pow1(N2,R1),R is R1*2.

solve(N,R):-N1 is N+1,pow(N1,N2),tri(N1,N2,1,1,R).

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

pre([]):-!.
pre([_,B,C,_|T]):-
     number_chars(BN,B), solve(BN,R),number_chars(CN,C),
     (R=:=CN->Str=" pass";Str=" fail"),write(Str),write(" "),writeln(R),pre(T).

str("0       1441    1444    10110100100
1       1       2       10
2       2       3       11
3       3       4       100
4       7       9       1001
5       43690   43691   1010101010101011
6       349525  349526  1010101010101010110
7       209715  209716  110011001100110100
8       209919  210066  110011010010010010
9       209664  209700  110011001100100100
10      65536   74898   10010010010010010
11      1048575         1198372         100100100100100100100
12      14      18      10010
13      13      18      10010
14      27      36      100100
15      44      45      101101
16      136     146     10010010
17      383     402     110010010
18      649     658     1010010010
19      1227    1228    10011001100
20      2693    2706    101010010010
21      4943    4946    1001101010010
22      9152    9362    10010010010010
23      8336    9362    10010010010010
24      36993   37449   1001001001001001
25      81868   84260   10100100100100100
26      73287   74898   10010010010010010
27      305901  305956  1001010101100100100
28      555516  599186  10010010010010010010
29      691590  692809  10101001001001001001
30      3112217         3295524         1100100100100100100100
31      5235890         5392676         10100100100100100100100
32      6804756         6890642         11010010010010010010010
33      13653246        13781284        110100100100100100100100
34      20099429        20099657        1001100101011001001001001
35      107304545       107304548       110011001010101011001100100
36      227978622       227978642       1101100101101010110110010010
37      380810157       380810386       10110101100101011010010010010
38      268435455       306783378       10010010010010010010010010010
39      536870912       613566756       100100100100100100100100100100
40      1072693248      1227133513      1001001001001001001001001001001").

```
CodeIQ:単調増加連数
問題とテストケースはこちらのお世話になりました。解答もあります。
->https://blog.goo.ne.jp/r-de-r/e/b5549572e33f631900b64ea38d02c7f5

入力に1を足して2進数のリストに直した後、
arr72(下位桁,継続中の連数,既存の最長連数(直前の連数),確定した桁,戻り値)
で上位桁から調べていき連数が途切れた時
1:最長連数より1の連数が短いとき
　①1が最下位のときは、最長連数の最下位を1にして最初から始めます。
　（上位の桁に影響があるかもしれないから）
　②それ以外はすぐ下の0を1にそれより下位は0にして続けます。
2:0の連数が短いときは、0の一番上の位を1としそれより下を0として続けます。

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

tenton(0,_,L,L):-!.　　　　%10進数をB進数のリストに
tenton(X,B,L,RL):-X1 is X div B,R1 is X mod B,
       tenton(X1,B,[R1|L],RL).
       
ntoten(_,[],XR,XR):-!.　　%B進数のリストを10進数に
ntoten(B,[H|T],X,XR):-X1 is X*B+H,ntoten(B,T,X1,XR).

longer(L1,L2):-length(L1,N1),length(L2,N2),N1>N2.　　%長さの比較

makel(N,X,L):-length(L,N),maplist(=(X),L). %要素XのN桁のリストを作る

arr72([],[],L,R,FR):-!, %リストがない
     append(L,R,R1),reverse(R1,FR).
arr72([H|T],[],[],R,FR):-!,  %上位桁がない(開始)
     arr72(T,[H],[],R,FR).
arr72([X|T],[X|T1],TL2,R,FR):-!,  %下位桁の先頭と上位桁の最後の数が同じ->継続
     arr72(T,[X,X|T1],TL2,R,FR).
arr72([X|T],[Y|T1],TL2,R,FR):-  %上位桁の最後の連数が最長連数->既存の最長連数を確定した桁のリストに追加
     X\=Y,longer([Y|T1],TL2),!,append(TL2,R,R1),arr72(T,[X],[Y|T1],R1,FR).
arr72([1|T],[0|T1],TL2,R,FR):-  %数字が0から1に変化->方針2
     length(T,N),makel(N,0,L1),!,append([0|L1],T1,L2),arr72([],L2,[1|TL2],R,FR).
arr72([0|T],L,T2,R,FR):-!,  %数字が1から0に変化->方針1:②
     length(T,N),makel(N,0,L1),arr72(L1,[1|L],T2,R,FR).
arr72([],[X|T1],[Y|T2],R,FR):-  %最長連数で終わる
     longer(T1,T2),!,append([Y|T2],R,R1),arr72([],[],[X|T1],R1,FR).
arr72([],[1|T1],[0|T2],R,FR):-!,  %最長連数でない1で終わる->方針1:①
     append([1|T1],[1|T2],L1),append(L1,R,R1),reverse(R1,R2),arr72(R2,[],[],[],FR).
arr72([],[0|T1],L,R,FR):-  %最長連数でない0で終わる->方針2　　
     arr72([],T1,[1|L],R,FR).

solv72([]).
solv72([f72(X,Q)|T]):-
     X1 is X+1,tenton(X1,2,[],RL),arr72(RL,[],[],[],R1),ntoten(2,R1,0,R),disp72(R,Q),solv72(T).

start:-ar(L),solv72(L),!.

disp72(R,A):-(A=:=R->Str=" pass ";Str=" fail "),write(Str),writeln(R).

ar([f72(77,79),
f72(79,96),
f72(57,63),
f72(1,3),
f72(3,4),
f72(10^10+1,10468982784),
f72(1228,1248),
f72(160199,161792),
f72(5368709119,6442450944),
f72(29614080,29614207),
f72(575,624),
f72(19968,19999),
f72(1278987,1279936),
f72(163831842,163831935),
f72(587776,588800)]).
```