Problem 67 「最大経路の和 その2」 †

以下の三角形の頂点から下まで移動するとき, その数値の合計の最大値は23になる.

3
7 4
2 4 6
8 5 9 3

この例では 3 + 7 + 4 + 9 = 23

100列の三角形を含んでいる15Kのテキストファイル triangle.txt (右クリックして, 『名前をつけてリンク先を保存』)の上から下まで最大合計を見つけてください.

注：これは, Problem 18のずっと難しいバージョンです.
全部で299 通りの組み合わせがあるので, この問題を解決するためにすべてのルートをためすことは可能でありません！
あなたが毎秒1兆本の(1012)ルートをチェックすることができたとしても, 全てをチェックするために200億年以上かかるでしょう.
解決するための効率的なアルゴリズムがあります. ;o)

解法

一段ずつの動的計画法で解けます。

max(X1,X2,X2):-X1<X2,!.
max(X1,_,X1):-!.

next_calc([X],[Y],[Z]):-
      !,
      Z is X+Y.
next_calc([X1,X2|Rest],[Y|Rest1],[Z|Result]):-
      !,
      max(X1,X2,X3),
      Z is X3+Y,
      next_calc([X2|Rest],Rest1,Result).

calc([],List):-
      !,
      msort(List,List1),
      reverse(List1,[Ans|_]),
      write(Ans).

calc([NowRow|Datas],OldRow):-
      !,
      [NowLeft|NowRow1]=NowRow,
      next_calc(OldRow,NowRow1,NowRow2),
      [OldLeft|_]=OldRow,
      NowLeft1 is NowLeft+OldLeft,
      calc(Datas,[NowLeft1|NowRow2]).

main67:-
      open('pe67.txt',read,IS),
      read_term(IS,[Top|Datas],[]),
      close(IS),
      calc(Datas,Top).

プロジェクトオイラー Problem 59 「XOR暗号解読」 †

Problem 59 「XOR暗号解読」 †

(訳者注: 文字コードの説明は適当です) 各文字はそれぞれ一意のコードに割り当てられている. よく使われる標準としてASCII (American Standard Code for Information Interchange) がある. ASCIIでは, 大文字A = 65, アスタリスク (*) = 42, 小文字k = 107というふうに割り当てられている.

モダンな暗号化の方法として, テキストファイルの各バイトをASCIIに変換し, 秘密鍵から計算された値とXORを取るという手法がある. XOR関数の良い点は, 暗号化に用いたのと同じ暗号化鍵でXORを取ると平文を復号できる点である. 65 XOR 42 = 107であり, 107 XOR 42 = 65である.

破られない暗号化のためには, 鍵は平文と同じ長さのランダムなバイト列でなければならない. ユーザーは暗号文と暗号化鍵を別々の場所に保存する必要がある. また, もし一方が失われると, 暗号文を復号することは不可能になる.

悲しいかな, この手法はほとんどのユーザーにとって非現実的である. そこで, 鍵の変わりにパスワードを用いる手法が用いられる. パスワードが平文より短ければ (よくあることだが), パスワードは鍵として繰り返し用いられる. この手法では, 安全性を保つために十分長いパスワードを用いる必要があるが, 記憶するためにはある程度短くないといけない.

この問題での課題は簡単になっている. 暗号化鍵は3文字の小文字である. cipher1.txtは暗号化されたASCIIのコードを含んでいる. また, 平文はよく用いられる英単語を含んでいる. この暗号文を復号し, 平文のASCIIでの値の和を求めよ.

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2059




解法
eが一番多いのでeへ多く変換できる数字。
これを
1,4,7、、、
2,5,8、、、
3,6,9、、
文字目でそれぞれ個別に求めて計算。
何か楽しみ方を見いだせない問題なのでコードも適当。


is_ok1(X,1):-atom_codes('the',X),!.
is_ok1(_,0):-!.
is_ok2(X,2):-atom_codes('this',X),!.
is_ok2(_,0):-!.

search([X1,X2,X3],[A1,A2,A3],Sum,3,Sum1,[]):-!,
      Sum1 is Sum+(A1 xor X1)+(A2 xor X2)+(A3 xor X3).

search([X1,X2,X3],[A1,A2,A3,A4|Rest],Sum,IsOK,Result,[A11|ReText]):-
      A11 is A1 xor X1,
      A22 is A2 xor X2,
      A33 is A3 xor X3,
      A44 is A4 xor X1,
      is_ok1([A11,A22,A33],Add1),
      is_ok2([A11,A22,A33,A44],Add2),
      IsOK1 is IsOK \/ Add1 \/ Add2,
      !,
      Sum1 is Sum+A11,
      search([X2,X3,X1],[A2,A3,A4|Rest],Sum1,IsOK1,Result,ReText)
      .
search([X1,X2,X3],[A1|Rest],Sum,IsOK,Result,[A11|ReText]):-
      !,
      A11 is A1 xor X1,
      Sum1 is Sum+(A1 xor X1),
      search([X2,X3,X1],Rest,Sum1,IsOK,Result,ReText).



change(N,N1):-!,
      char_code('e',E),
      N1 is N xor E.


count([],[Count,X],[[Count,X1]]):-!,
      change(X,X1).
count([X|Xs],[Count,X],Result):-
      !,
      Count1 is Count+1,
      count(Xs,[Count1,X],Result).
count([X1|Xs],[Count,X],[[Count,X2]|Result]):-
      change(X,X2),
      !,
      count(Xs,[1,X1],Result).

count_w(Text,[X1,X2,X3,X4,X5,X6]):-
      msort(Text,[Top|Text1]),
      count(Text1,[1,Top],Count),
      msort(Count,Count1),
      reverse(Count1,[X1,X2,X3,X4,X5,X6|_]).


split3([],[],[],[]):-!.
split3([X|Text],[X|Text0],Text1,Text2):-
      !,
      split3(Text,Text1,Text2,Text0).

main59:-
      open('pe59.txt',read,IS),
      read_term(IS,Text,[]),
      close(IS),
      split3(Text,Text0,Text1,Text2),
      count_w(Text0,XORs0),
      count_w(Text1,XORs1),
      count_w(Text2,XORs2),
      member([_,A0],XORs0),
      member([_,A1],XORs1),
      member([_,A2],XORs2),
      search([A0,A1,A2],Text,0,0,Ans,ReText),
      atom_codes(AnsText,ReText),
      write(AnsText),nl,
      write(Ans).

プロジェクトオイラー Problem 64 「奇数周期の平方根」 †

Problem 64 「奇数周期の平方根」 †

平方根は連分数の形で表したときに周期的であり, 以下の形で書ける:

√N = a0 + 1 / (a1 + 1 / (a2 + 1 / (a3 + ...)))

例えば, √23を考えよう.

√23 = 4 + √23 - 4 = 4 + 1 / (1 / (√23 - 4)) = 4 + 1 / (1 + (√23 - 3) / 7)

となる.

この操作を続けていくと,

√23 = 4 + 1 / (1 + 1 / (3 + 1 / (1 + 1 / (8 + ...))))

を得る.

操作を纏めると以下になる:

• a0 = 4, 1/(√23-4) = (√23+4)/7 = 1 + (√23-3)/7
• a1 = 1, 7/(√23-3) = 7(√23+3)/14 = 3 + (√23-3)/2
• a2 = 3, 2/(√23-3) = 2(√23+3)/14 = 1 + (√23-4)/7
• a3 = 1, 7/(√23-4) = 7(√23+4)/7 = 8 + (√23-4)
• a4 = 8, 1/(√23-4) = (√23+4)/7 = 1 + (√23-3)/7
• a5 = 1, 7/(√23-3) = 7(√23+3)/14 = 3 + (√23-3)/2
• a6 = 3, 2/(√23-3) = 2(√23+3)/14 = 1 + (√23-4)/7
• a7 = 1, 7/(√23-4) = 7(√23+4)/7 = 8 + (√23-4)

よって, この操作は繰り返しになることが分かる. 表記を簡潔にするために, √23 = [4;(1,3,1,8)]と表す. (1,3,1,8)のブロックは無限に繰り返される項を表している.

最初の10個の無理数である平方根を連分数で表すと以下になる.

• √2=[1;(2)], period=1
• √3=[1;(1,2)], period=2
• √5=[2;(4)], period=1
• √6=[2;(2,4)], period=2
• √7=[2;(1,1,1,4)], period=4
• √8=[2;(1,4)], period=2
• √10=[3;(6)], period=1
• √11=[3;(3,6)], period=2
• √12= [3;(2,6)], period=2
• √13=[3;(1,1,1,1,6)], period=5

N ≤ 13で奇数の周期をもつ平方根は丁度4つある.

N ≤ 10000 について奇数の周期をもつ平方根が何個あるか答えよ.

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2064




解法
連分数について人生で一度も教育を受けたことがないので
数列を眺めて直感で無理矢理漸化式を立てて計算した。
出鱈目だな俺。
とりあえず答えはあった。

gcd(0, B, G) :- G is abs(B).
gcd(A, B, G) :- A =\= 0, R is B mod A, gcd(R, A, G).

calc_next(N,Up,Dell,D2,NextDell,[Add,NextDell,D2]):-
!,
D1 is N-Dell*Dell,
gcd(Up,D1,G1),
NextUp is Up//G1,
D2  is D1//G1,
Add is ((floor(sqrt(N))+Dell)*NextUp)//D2,
NextDell is Add*D2-Dell.

calc(N,Up,Dell,List):-
calc_next(N,Up,Dell,NextUp,NextDell,E),
(member(E,List) ->
!,length(List,Len),
Len mod 2=:=1;
append(List,[E],List1),
calc(N,NextUp,NextDell,List1)).



search(1):-
between(1,10000,N),
N1 is sqrt(N),
not(N1=    

プロジェクトオイラー Problem 65 「e の近似分数」 †

Problem 65 「e の近似分数」 †

2の平方根は無限連分数として書くことができる.

無限連分数である √2 = [1;(2)] と書くことができるが, (2) は2が無限に繰り返されることを示す. 同様に, √23 = [4;(1,3,1,8)].

平方根の部分的な連分数の数列から良い有理近似が得られることが分かる.√2の近似分数について考えよう.

従って, √2の近似分数からなる数列の最初の10項は：

1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, ...

もっとも驚くべきことに, 数学的に重要な定数,
e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...].

e の近似分数からなる数列の最初の10項は：

2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, ...

10項目の近似分数の分子の桁を合計すると1+4+5+7=17である.

e についての連分数である近似分数の100項目の分子の桁の合計を求めよ.

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2065



解法
上から計算すると考えると難しいので分数を下から計算していくだけです。


gcd(0, B, G) :- G is abs(B).
gcd(A, B, G) :- A =\= 0, R is B mod A, gcd(R, A, G).

sum([],0):-!.
sum([X|Xs],Result):-
      !,
      sum(Xs,Re),
      Result is Re+X-48.

d(Deep,N1):-
      Deep mod 3=:=0,
      !,
      N1 is Deep//3*2.

d(_,1):-!.

calc(1,U,D):-
      !,
      U1 is U+D*2,
      D1 is D,
      gcd(U1,D1,G1),
      U2 is U1//G1,
      number_codes(U2,List2),
      sum(List2,Ans),
      write(Ans).
calc(Deep,U,D):-
      !,
      d(Deep,N),
      U1 is D*N+U,
      D1 is D,
      gcd(U1,D1,G1),
      U2 is U1//G1,
      D2 is D1//G1,
      Deep1 is Deep-1,
      calc(Deep1,D2,U2).

main65:-
      d(100,D),
      calc(99,1,D).

プロジェクトオイラー Problem 63 「べき乗の桁の個数」 †

Problem 63 「べき乗の桁の個数」 †

5桁の数 16807 = 75は自然数を5乗した数である. 同様に9桁の数 134217728 = 89も自然数を9乗した数である.

自然数を n 乗して得られる n 桁の正整数は何個あるか?

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2063

解法
10以上の数は桁の増加がｎの増加より大きくなります。
10以下の数はいつかは桁の増加にｎの増加が追い付かれます。
ｌog計算すればすぐに答えが出ます。

sum([],0):-!.
sum([X|Xs],Result):-sum(Xs,Re),Result is Re+X.

search(B):-
      between(1,9,A),
      B is floor(1/(1-log10(A))).
main63:-
      findall(N,search(N),AnsList),
      sum(AnsList,Ans),

      write(Ans).

プロジェクトオイラー Problem 60 「素数ペア集合」 †

Problem 60 「素数ペア集合」 †

素数3, 7, 109, 673は非凡な性質を持っている. 任意の2つの素数を任意の順で繋げると, また素数になっている. 例えば, 7と109を用いると, 7109と1097の両方が素数である. これら4つの素数の和は792である. これは, このような性質をもつ4つの素数の集合の和の中で最小である.

任意の2つの素数を繋げたときに別の素数が生成される, 5つの素数の集合の和の中で最小のものを求めよ.

解法
とりあえず上限を定めて全探索した結果暫定的な答えを得ました。
暫定解よりも大きな素数が答えの5つの数字に入らないことは明白なので。
その上限で全探索して答えを確認すればよいですが。
高速化の方法がわかりません。




#include<stdio.h>
#include<vector>
#include<map>
#include<set>
#include<string.h>
#include<iostream>

const int PRIME_LIMIT=100000;
const int SEARCH_LIMIT=27000;

std::map<__int64,std::set<__int64> > cons;
std::vector<__int64> primes,set5;
__int64 ans=-1;



bool isConnectOK(__int64 a,__int64 b){
      __int64 mult=1,c,d;
      while(mult<=b)mult*=10;
      c=a*mult+b;
      for(int i=0;i<primes.size();i++){
            d=primes[i];
            if(c<d*d)break;
            if(c%d==0)return false;
      }
      return true;
}

void search5(std::set<__int64>::iterator &it,std::set<__int64>::iterator &eIt,__int64 sum){
      if(ans!=-1&&(ans<sum||SEARCH_LIMIT<sum))return ;
      if(set5.size()==5){
            if(ans==-1||sum<ans)ans=sum;
            for(int i=0;i<5;i++){
                  std::cout<<set5[i]<<" ";
            }
            std::cout<<sum<<"\n";
      }else if(it==eIt){
            return ;
      }else{
            it++;
            search5(it,eIt,sum);
            it--;
            __int64 p1=(*it);
            bool insertOK=true;
            for(int i=0;i<set5.size();i++){
                  if(cons[p1].find(set5[i])==cons[p1].end()){
                        insertOK=false;
                  }
            }
            if(insertOK==true){
                  set5.push_back((*it));
                  it++;
                  search5(it,eIt,sum+p1);
                  it--;
                  set5.pop_back();
            }
      }
}


int main(){
      bool is_prime[PRIME_LIMIT];
      memset(is_prime,true,sizeof(is_prime));
      is_prime[0]=is_prime[1]=false;    

      std::set<__int64> setE;
   
   
      for(int i=2;i*i<PRIME_LIMIT;i+=1+(i%2)){
            if(is_prime[i]==false)continue;
            int start=4;
            int add=2;
         
            if(i%2==1){
                  start=i*i;
                  add=i*2;
            }
            for(int j=start;j<PRIME_LIMIT;j+=add){
                  is_prime[j]=false;
            }
      }
      for(int i=2;i<PRIME_LIMIT;i++){
            if(is_prime[i]==false)continue;
            if(i<SEARCH_LIMIT)cons[i]=setE;    
            primes.push_back(i);
      }
      __int64 a,b;
      int search_size=cons.size();
      for(int i=0;i<search_size;i++){
            __int64 p1=primes[i];
            for(int j=i+1;j<search_size;j++){
                  if(i==j)continue;
                  __int64 p2=primes[j];
                  if(p1+p2>SEARCH_LIMIT)break;
                  if(isConnectOK(p1,p2)&&isConnectOK(p2,p1)){
                        cons[p1].insert(p2);
                        cons[p2].insert(p1);
                  }
            }
      }
      std::map<__int64,std::set<__int64> >::iterator mIt;
      std::set<__int64>::iterator sIt,eIt;
      for(mIt=cons.begin();mIt!=cons.end();mIt++){
            set5.push_back((*mIt).first);
            sIt=(*mIt).second.upper_bound((*mIt).first);
            eIt=(*mIt).second.end();
            search5(sIt,eIt,(*mIt).first);
            set5.pop_back();
      }
      std::cout<<ans<<"\n";
}

プロジェクトオイラー Problem 61 「巡回図形数」 †

Problem 61 「巡回図形数」 †

三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される.

三角数	P3,n=n(n+1)/2	1, 3, 6, 10, 15, ...
四角数	P4,n=n2	1, 4, 9, 16, 25, ...
五角数	P5,n=n(3n-1)/2	1, 5, 12, 22, 35, ...
六角数	P6,n=n(2n-1)	1, 6, 15, 28, 45, ...
七角数	P7,n=n(5n-3)/2	1, 7, 18, 34, 55, ...
八角数	P8,n=n(3n-2)	1, 8, 21, 40, 65, ...

3つの4桁の数の順番付きの集合 (8128, 2882, 8281) は以下の面白い性質を持つ.

1. この集合は巡回的である. 最後の数も含めて, 各数の後半2桁は次の数の前半2桁と一致する
2. それぞれ多角数である: 三角数 (P3,127=8128), 四角数 (P4,91=8281), 五角数 (P5,44=2882) がそれぞれ別の数字で集合に含まれている
3. 4桁の数の組で上の2つの性質をもつはこの組だけである.

三角数, 四角数, 五角数, 六角数, 七角数, 八角数が全て表れる6つの巡回する4桁の数からなる唯一の順序集合の和を求めよ.

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2061





解法
循環するのでどこから初めてもよく3角数から探索を始めます。
後は全探索するだけです。
探索が進むとリストが短くなるシンプルイズベストなコード。
比較的綺麗にかけたと思う。

今回は全探索してますが。
この問題、動的計画法を使えば計算量を下げる遊びができるのでそれもおすすめです。

初めに選んだ数の上2桁と、今まで使ったｎ角数をビットで管理最後に選んだ数の末尾2桁で管理し、解が一つしかないというヒントを使えば動的計画法の計算中にかなりの枝刈りを行えます。




f3(N,N1):-!,N1 is (N*(N+1))//2.
f4(N,N1):-!,N1 is N*N.
f5(N,N1):-!,N1 is (N*(N*3-1))//2.
f6(N,N1):-!,N1 is N*(2*N-1).
f7(N,N1):-!,N1 is (N*(5*N-3))//2.
f8(N,N1):-!,N1 is N*(3*N-2).

calc2(Siki,[Head,Tail]):-
      between(20,500,N),
      call(Siki,N,E),
      1000=<E,
      E=<9999,
      Head is E//100,
      Tail is E mod 100.

calc(List):-
      member(Siki,[f3,f4,f5,f6,f7,f8]),
      findall(E,calc2(Siki,E),List).

search([],Tail,Sum,Tail):-!,write(Sum).
search(Lists,Tail,Sum,FirstTop):-
      !,
      select(List,Lists,Lists1),
      member([Tail,Tail1],List),
      Sum1 is Sum+Tail*100+Tail1,
      search(Lists1,Tail1,Sum1,FirstTop).

main61:-
      findall(L,calc(L),[List3|Lists]),
      member([FirstTop,Tail],List3),
      Sum is FirstTop*100+Tail,
      search(Lists,Tail,Sum,FirstTop).