「prolog勉強プロジェクトオイラー31～40」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
プロジェクトオイラーの問題をＰｒｏlogで解くページ。
作者 堀江 伸一
*問い 31 Coin sums
（以下の文章は学者の書き方を真似した遊び文章です）
この問題は難しい。
ただ解くだけならループでも書けば簡単だ,
速度もこのサイズの問題ならループを回してもそんなに時間がかからないだろう。
問題はコインが増えたり作るべき金額が大きくなると、ループでは計算が終わらなくなるだろうというところにある。
動的計画法が必要となるがこの手法は破壊的代入があると非常に便利なのだが、Ｐｒｏｌｏｇには破壊的代入がないために簡便な実装が出来ない。
この問題を解くには一工夫が必要となる。
ピュアＰｒｏｌｏｇには破壊的代入もない、配列もないのないないづくし、不便であり、Ｐｒｏｌｏｇが廃れたのもうなづける。
無いと言っても始まらない、まあなにか工夫してみよう。
導入
Ｐｒｏｌｏｇには基本的に線形リストしかないので、リストの先頭を取り出すリストの先頭に追加する以外の処理は非効率といえる。
これに注意しながら実装する。
この問題をＰｒｏｌｏｇを知らない人向けに翻訳すると、スタックだけを使って動的計画法を実装せよ。
スタックから取り出した中身は他の変数に入れない限り変更することは禁止する。
というちょっと意地悪な問題と同値になります。
-解説
今回はこの問題を題材にprologによる動的計画法の実装をおこなった。
0～200にその金額を作れる組み合わせ数をいれこれをとりあえずＬｉｓｔとする。
価値5の通貨を足す場合
Ｌｉｓｔの0～4まではそのまま。
0～4までの値にＬｉｓｔの5～9までの値を足すと価値5の通貨を足した場合の5～9までの組み合わせ数が出る。
5～9までの結果を使って10～14までの組み合わせ数をもとめ、10～14までの結果を使い15～19までの組み合わせ数をもとめていく、、、。
これを続けるとListの終端に行きつき計算が停止する。
最後に計算結果のリストを平坦化してリバースすれば通貨5を追加した場合の組み合わせ数がでてくる。
他の通貨でも同じ作業を続ける。
これにより効率よく動的計画法がPrologで実装できる。
余りが出る場合は
12を作る場合、５～9とＬistからよめるのは10～1２の組となるが、余分な8 9をリストから取り除いて計算すれば良い。
5 6 7と10 11 12だけを計算すれば良くこれは簡単に実装できる。
この発想にたいするご近所の創価学会員森本さんの評価。
「ぷぷぷ、堀江伸一のコード”馬鹿でも思いつく、ぷははは」
というのを窓全開きこえよがしな大きな声で隣家の森本さんに言われてしまいました。
後藤村さんからは「笑うやろひたすら堀江の奴」
森本さんは私を馬鹿にすることを遊びにしてるだけだけど、藤村さんは私のことを何段も下等な生物か猿について語るように語るんだよね。
藤村さんはむかつくほうだけど、森本さんはまだまし。
彼のながした噂のなかでは私は勉強はしたことなく小学校の算数をギリギリ出来る人間ということになっている。
藤村さんと違い森本さんはまだ算数という範囲で私を人間扱いしてくれている、この差は個人的に大きいです。
思い起こせば私の人生馬鹿にされるか笑い物にされるかの二択しかなかったな。
まあ、森本さんは、
「ネットの奴ら相手にしてるけどひたすら気持ち割いいｗｗｗｗ」：
「ニコ動やってるやつってヒモテで哀れだよな」
「このサイト気持ちわり」とか結構はっきり通る声でたまに言ってる人なので。
声が遠くまでよく通る人なんですよね森本さんて、だから夏なんか家越しに森本さんの声が聞こえちゃうわけです。
森本さんを分類すると、少し貧乏なさわやかリア充実系差別主義者といったところか？
森本さんは人格はいい人なのですが、でも差別やいじめや笑い物にして楽しむことは娯楽は娯楽として楽しむタイプに見えます。
ちょっと思いますが。
差別してる時の人間てすごく楽しそうですよね。
ネットでも差別で盛り上がってる場所では文章の端々から私達は差別話で盛り上がって今とても楽しいですという気分が伝わるし。
差別を娯楽や熱狂にまで盛り上げる仕掛け人も世の中にはいる。
差別の進化系は娯楽を多分に含むのだと私は思ったりします。
差別根絶に従事してる人は大変な仕事だろう思います、なにせ娯楽の１ジャンルを撲滅するようなものですから、そういう人たちの困難さを考えると頭が下がります。
とこんなことを書きましたが、こんな文章は世の99.99999％の人にとってどうでもいい話ですね、私個人の人生にすぎませんし上記は全部主観的意見にすぎません。
誰にとってもどうでもいい話です。
これは私から見た彼らにすぎません。
ここで勘違いしてはいけないのは周囲や世間から見たら、彼らは普通のしっかりしたリア充人間なのです。
彼らと付き合ったら、いい人たちだと思うだろうことは保証します。
多分彼らにとって私はテレビの中おバカ芸人見たいな役割になっていて馬鹿にして楽しむ存在、日常生活や友達づきあいはまた別なのだと思います。
つまり、犬以下の扱いをしていい相手（私）、人間（世間様）という分類になってるのかもしれません。
肝心のプログラムは以下の通り。
Hide Code
fast_reverse(List1,List2):-fr(List1,[],List2).
fr([Head|Tail],SoFar,Result):-fr(Tail,[Head|SoFar],Result).
fr([],SoFar,SoFar).
drop_w(Xs,Ys,Result):-length(Xs,Len1),length(Ys,Len2),Len3 is Len1-Len2,
drop(Xs,Len3,Result).
drop(Xs, 0, Xs).
drop([], N, []) :- N > 0.
drop([_ | Xs], N, Ys) :-
N > 0, N1 is N - 1, drop(Xs, N1, Ys).
add([],[],[]):-!.
add([Z1|Zs1],[Y|Ys],[Z2|Sum]):-Z2 is Z1+Y,add(Zs1,Ys,Sum).
setY([],Zs1,Ys1,Ans,_,_,Coins):-
drop_w(Zs1,Ys1,Zs2),
add(Zs2,Ys1,Zs3),
!,
NextZ=[Zs3|Ans],
flatten(NextZ,NextZ1),
fast_reverse(NextZ1,NextZ2),
(Coins==[]->write(NextZ2);
[Coin|Coins1]=Coins,
first_set(NextZ2,[],Zs4,Coin,NextZ3),
setY(NextZ3,Zs4,[],Zs4,0,Coin,Coins1)).
setY(Xs,Zs1,Ys1,Ans,N,N,Coins):-!,
add(Zs1,Ys1,NextZs),
setY(Xs,NextZs,[],[NextZs|Ans],0,N,Coins).
setY([X|Xs],Zs1,Ys1,Ans,Count,N,Coins):-!,
Count1 is Count+1,
setY(Xs,Zs1,[X|Ys1],Ans,Count1,N,Coins).
first_set(List,Zs,Zs,0,List):-!.
first_set([X|List],Zs,Result,N,Result2):-
N1 is N-1,
first_set(List,[X|Zs],Result,N1,Result2).
main_31_3:-
[C|Coins]=[1,2,5,10,20,50,100,200],
findall(0,between(0,199,_),List),
List1 = [1|List],
first_set(List1,[],Zs,C,List2),
setY(List2,Zs,[],Zs,0,C,Coins).
*問い32
うーん？
ヒュースティリックに解いてしまった。
コードはむやみに長いし、自動的に解の探索範囲がもとまらず探索範囲を人手で指定しているし。
これっていいコードなんだろうか？
sets([_],[_,_,_,_]).
sets([_,_],[_,_,_]).
selects([],Rest,Rest).
selects([X|Rest],Nums,Result):-select(X,Nums,NumRest),selects(Rest,NumRest,Result).
toNum([],C1,C1).
toNum([X|Rest],C1,Result):-
C2 is C1*10+X,toNum(Rest,C2,Result).
calc(Z):-
sets(Xs,Ys),
selects(Xs,[1,2,3,4,5,6,7,8,9],Rest1),
toNum(Xs,0,X),
selects(Ys,Rest1,Rest2),
toNum(Ys,0,Y),
Z is X*Y,
Z<10000,
Z1 is Z mod 10,
Z2 is (Z//10) mod 10,
Z3 is (Z//100) mod 10,
Z4 is (Z//1000) mod 10,
selects([Z1,Z2,Z3,Z4],Rest2,_).
sum([],Sum,Sum).
sum([X|Rest],Sum,Result):-Sum1 is Sum+X,sum(Rest,Sum1,Result).
main32:-
findall(Z,calc(Z),List),sort(List,List1),
sum(List1,0,Ans),write(Ans).
*問い34
問い30のコードをそのまま流用。
特に書くことなし。
check([_|_],0):-!,fail.
check([],0):-!.
check(Nums,Sum):-
T is Sum mod 10,
select(T,Nums,Rest),!,
Sum1 is Sum//10,
check(Rest,Sum1).
search(Nums,_,_,Sum,Sum):-
check(Nums,Sum).
search(_,_,7,_,_):-!,fail.
search(Nums,P,Deep,Sum,Result):-
between(P,9,N),
nth0(N,[1,1,2,6,24,120,720,5040,40320,362880],N1),
Sum1 is Sum+N1,
Deep1 is Deep+1,
search([N|Nums],N,Deep1,Sum1,Result).
sum([],Sum,Sum):-!.
sum([X|Rest],Sum,Result):-
Sum1 is Sum+X,sum(Rest,Sum1,Result).
main34:-findall(Re,search([],0,0,0,Re),List),
sum(List,0,Ans),Ans1 is Ans-3,write(Ans1).
*問い35
計算量低減テクニックで書いたコードといっても。
どの桁も奇数であるというものだけを探索して検討するようにしただけ。
２は探索では検討せず最後に足している。
テクニックがみについたら無意味に使いたがる、そういうコードかもしれない。
テクニックで遊ぶのも技術習得には必要な気もするのでこれもありかと。
round_list([],[],_).
round_list([X|L],R,Result):-round_list(L,[X|R],Result).
round_list([X|L],R,[X|Result]):-
reverse(R,R1),
append(L,R1,Result).
not_prime(N):-N<2,!.
not_prime(N):-
sqrt(N,N1),
N2 is floor(N1),
between(2,N2,N3),
N4 is N mod N3,
N4=:=0,!.
to_num([],Result,Result):-!.
to_num([X|List],Num,Result):-Num1 is Num*10+X,to_num(List,Num1,Result).
check_exe(List,Ans):-
round_list(List,[],Perm),
to_num(Perm,0,Num),
(member(Num,Ans)->!,true;true),
(not_prime(Num)->
true,!;fail).
result_list(List,_,_,List).
result_list(List,Deep,Ans,Result):-
create_perm(List,Deep,Ans,Result).
check_perm(List,Deep,Ans,Result):-
not(check_exe(List,Ans)),!,
to_num(List,0,Num),
result_list(List,Deep,[Num|Ans],Result).
check_perm(List,Deep,Ans,Result):-
create_perm(List,Deep,Ans,Result).
create_perm(_,6,_,_):-!,fail.
create_perm(List,Deep,Ans,Result):-
Deep<6,
between(1,9,N),
T1 is N mod 2,
T1\==0,
Deep1 is Deep+1,
check_perm([N|List],Deep1,Ans,Result).
main35:-findall(L,create_perm([],0,[],L),List),write(List),
length(List,Len),Len1 is Len+1,write(Len1).
*問い36 Double-base palindromes
http://projecteuler.net/problem=36
Prolog的コードで書いたつもり。
set([_],[]).
set([X1],[X1]).
set([X1,_],[X1]).
set([X2,X1],[X1,X2]).
set([X2,X1,_],[X1,X2]).
set([X2,X1,X0],[X0,X1,X2]).
num_perm([]).
num_perm([X|Rest]):-member(X,[0,1,2,3,4,5,6,7,8,9]),num_perm(Rest).
to_num([],Sum,Sum).
to_num([X|Rest],Sum,Result):-Sum1 is Sum*10+X,to_num(Rest,Sum1,Result).
to_bit2(0,[]):-!.
to_bit2(Y,[B|Result]):-Y1 is Y//2,B is Y mod 2,to_bit2(Y1,Result).
calc(Y):-
set(A,B),
num_perm(A),
num_perm(B),
[Top|_]=A,
0<Top,
to_num(A,0,X),
to_num(B,X,Y),
to_bit2(Y,Re),
reverse(Re,Re).
sum([],Sum,Sum).
sum([X|Rest],Sum,Result):-Sum1 is X+Sum,sum(Rest,Sum1,Result).
main36:-
findall(Y,calc(Y),List),write(List),
sum(List,0,Ans),write(Ans).
*問い37
ちょっとコードが冗長かもしれない。
速度はそれなり。
短い方から左へ数字列を伸ばしてそれが条件を満たす限りのばす単純な探索で作成。
右側を消したとき素数でなくなる数でも左側へ無限に数字を加えたらどこかで素数になるものがあるかもしれないので。
素数が１１個という情報がなかったらこの問題は恐ろしい難問となるはず。
探索は深さ制限で実行。
not_prime(N):-N<2,!.
not_prime(N):-
sqrt(N,N1),
N2 is floor(N1),
between(2,N2,N3),
N4 is N mod N3,
N4=:=0,!.
is_prime(N):-not(not_prime(N)).
to_num([],Sum,Sum).
to_num([X|Rest],Sum,Result):-Sum1 is Sum*10+X,to_num(Rest,Sum1,Result).
check_exe_R(0):-!.
check_exe_R(Num):-
Num1 is Num//10,
is_prime(Num),
check_exe_R(Num1).
search(List,List,_):-
to_num(List,0,Num),
10<Num,
check_exe_R(Num).
search(List,Ans,Deep):-
Deep>0,
Deep1 is Deep-1,
member(N,[1,2,3,5,7,9]),
to_num([N|List],0,Num),
is_prime(Num),
search([N|List],Ans,Deep1).
sum([],Sum,Sum).
sum([X|Rest],Sum,Result):-to_num(X,0,Num),Sum1 is Sum+Num,sum(Rest,Sum1,Result).
main37:-between(2,10,N),
findall(Ans,search([],Ans,N),List),length(List,11),
!,write(List),sum(List,0,Ans),write(Ans).
*問い38
探索するだけの問題です。
最後に出てきた数字の並びが答えとなります。
num_add(0,List,List):-!.
num_add(Num,List,[X|Result]):-
X is Num mod 10,
Num1 is Num//10,
num_add(Num1,List,Result),
X>0,
not(member(X,Result)).
search(_,_,List,_):-
length(List,Len),9<Len,!,fail.
search(_,_,List,List1):-
length(List,9),reverse(List,List1),!.
search(N,P,List,Result):-
N1 is N*P,
P1 is P+1,
num_add(N1,List,NextList),
search(N,P1,NextList,Result).
search_start(Re):-
between(1,9999,N),
search(N,1,[],Re).
main38:-
findall(Re,search_start(Re),List),
sort(List,List1),write(List1).
プロジェクトオイラーの問題をＰｒｏlogで解くページ。
作者 堀江 伸一
*問い 31 Coin sums
（以下の文章は学者の書き方を真似した遊び文章です）
この問題は難しい。
ただ解くだけならループでも書けば簡単だ,
速度もこのサイズの問題ならループを回してもそんなに時間がかからないだろう。
問題はコインが増えたり作るべき金額が大きくなると、ループでは計算が終わらなくなるだろうというところにある。
動的計画法が必要となるがこの手法は破壊的代入があると非常に便利なのだが、Ｐｒｏｌｏｇには破壊的代入がないために簡便な実装が出来ない。
この問題を解くには一工夫が必要となる。
ピュアＰｒｏｌｏｇには破壊的代入もない、配列もないのないないづくし、不便であり、Ｐｒｏｌｏｇが廃れたのもうなづける。
無いと言っても始まらない、まあなにか工夫してみよう。
導入
Ｐｒｏｌｏｇには基本的に線形リストしかないので、リストの先頭を取り出すリストの先頭に追加する以外の処理は非効率といえる。
これに注意しながら実装する。
この問題をＰｒｏｌｏｇを知らない人向けに翻訳すると、スタックだけを使って動的計画法を実装せよ。
スタックから取り出した中身は他の変数に入れない限り変更することは禁止する。
というちょっと意地悪な問題と同値になります。
-解説
今回はこの問題を題材にprologによる動的計画法の実装をおこなった。
0～200にその金額を作れる組み合わせ数をいれこれをとりあえずＬｉｓｔとする。
価値5の通貨を足す場合
Ｌｉｓｔの0～4まではそのまま。
0～4までの値にＬｉｓｔの5～9までの値を足すと価値5の通貨を足した場合の5～9までの組み合わせ数が出る。
5～9までの結果を使って10～14までの組み合わせ数をもとめ、10～14までの結果を使い15～19までの組み合わせ数をもとめていく、、、。
これを続けるとListの終端に行きつき計算が停止する。
最後に計算結果のリストを平坦化してリバースすれば通貨5を追加した場合の組み合わせ数がでてくる。
他の通貨でも同じ作業を続ける。
これにより効率よく動的計画法がPrologで実装できる。
余りが出る場合は
12を作る場合、５～9とＬistからよめるのは10～1２の組となるが、余分な8 9をリストから取り除いて計算すれば良い。
5 6 7と10 11 12だけを計算すれば良くこれは簡単に実装できる。
この発想にたいするご近所の創価学会員森本さんの評価。
「ぷぷぷ、堀江伸一のコード”馬鹿でも思いつく、ぷははは」
というのを窓全開きこえよがしな大きな声で隣家の森本さんに言われてしまいました。
後藤村さんからは「笑うやろひたすら堀江の奴」
森本さんは私を馬鹿にすることを遊びにしてるだけだけど、藤村さんは私のことを何段も下等な生物か猿について語るように語るんだよね。
藤村さんはむかつくほうだけど、森本さんはまだまし。
彼のながした噂のなかでは私は勉強はしたことなく小学校の算数をギリギリ出来る人間ということになっている。
藤村さんと違い森本さんはまだ算数という範囲で私を人間扱いしてくれている、この差は個人的に大きいです。
思い起こせば私の人生馬鹿にされるか笑い物にされるかの二択しかなかったな。
まあ、森本さんは、
「ネットの奴ら相手にしてるけどひたすら気持ち割いいｗｗｗｗ」：
「ニコ動やってるやつってヒモテで哀れだよな」
「このサイト気持ちわり」とか結構はっきり通る声でたまに言ってる人なので。
声が遠くまでよく通る人なんですよね森本さんて、だから夏なんか家越しに森本さんの声が聞こえちゃうわけです。
森本さんを分類すると、少し貧乏なさわやかリア充実系差別主義者といったところか？
森本さんは人格はいい人なのですが、でも差別やいじめや笑い物にして楽しむことは娯楽は娯楽として楽しむタイプに見えます。
ちょっと思いますが。
差別してる時の人間てすごく楽しそうですよね。
ネットでも差別で盛り上がってる場所では文章の端々から私達は差別話で盛り上がって今とても楽しいですという気分が伝わるし。
差別を娯楽や熱狂にまで盛り上げる仕掛け人も世の中にはいる。
差別の進化系は娯楽を多分に含むのだと私は思ったりします。
差別根絶に従事してる人は大変な仕事だろう思います、なにせ娯楽の１ジャンルを撲滅するようなものですから、そういう人たちの困難さを考えると頭が下がります。
とこんなことを書きましたが、こんな文章は世の99.99999％の人にとってどうでもいい話ですね、私個人の人生にすぎませんし上記は全部主観的意見にすぎません。
誰にとってもどうでもいい話です。
これは私から見た彼らにすぎません。
ここで勘違いしてはいけないのは周囲や世間から見たら、彼らは普通のしっかりしたリア充人間なのです。
彼らと付き合ったら、いい人たちだと思うだろうことは保証します。
多分彼らにとって私はテレビの中おバカ芸人見たいな役割になっていて馬鹿にして楽しむ存在、日常生活や友達づきあいはまた別なのだと思います。
つまり、犬以下の扱いをしていい相手（私や２ちゃんねらやニコ動ユーザ）、人間（世間様）という分類になってるのかもしれません。
肝心のプログラムは以下の通り。
Hide Code
fast_reverse(List1,List2):-fr(List1,[],List2).
fr([Head|Tail],SoFar,Result):-fr(Tail,[Head|SoFar],Result).
fr([],SoFar,SoFar).
drop_w(Xs,Ys,Result):-length(Xs,Len1),length(Ys,Len2),Len3 is Len1-Len2,
drop(Xs,Len3,Result).
drop(Xs, 0, Xs).
drop([], N, []) :- N > 0.
drop([_ | Xs], N, Ys) :-
N > 0, N1 is N - 1, drop(Xs, N1, Ys).
add([],[],[]):-!.
add([Z1|Zs1],[Y|Ys],[Z2|Sum]):-Z2 is Z1+Y,add(Zs1,Ys,Sum).
setY([],Zs1,Ys1,Ans,_,_,Coins):-
drop_w(Zs1,Ys1,Zs2),
add(Zs2,Ys1,Zs3),
!,
NextZ=[Zs3|Ans],
flatten(NextZ,NextZ1),
fast_reverse(NextZ1,NextZ2),
(Coins==[]->write(NextZ2);
[Coin|Coins1]=Coins,
first_set(NextZ2,[],Zs4,Coin,NextZ3),
setY(NextZ3,Zs4,[],Zs4,0,Coin,Coins1)).
setY(Xs,Zs1,Ys1,Ans,N,N,Coins):-!,
add(Zs1,Ys1,NextZs),
setY(Xs,NextZs,[],[NextZs|Ans],0,N,Coins).
setY([X|Xs],Zs1,Ys1,Ans,Count,N,Coins):-!,
Count1 is Count+1,
setY(Xs,Zs1,[X|Ys1],Ans,Count1,N,Coins).
first_set(List,Zs,Zs,0,List):-!.
first_set([X|List],Zs,Result,N,Result2):-
N1 is N-1,
first_set(List,[X|Zs],Result,N1,Result2).
main_31_3:-
[C|Coins]=[1,2,5,10,20,50,100,200],
findall(0,between(0,199,_),List),
List1 = [1|List],
first_set(List1,[],Zs,C,List2),
setY(List2,Zs,[],Zs,0,C,Coins).
*問い32
うーん？
ヒュースティリックに解いてしまった。
コードはむやみに長いし、自動的に解の探索範囲がもとまらず探索範囲を人手で指定しているし。
これっていいコードなんだろうか？
sets([_],[_,_,_,_]).
sets([_,_],[_,_,_]).
selects([],Rest,Rest).
selects([X|Rest],Nums,Result):-select(X,Nums,NumRest),selects(Rest,NumRest,Result).
toNum([],C1,C1).
toNum([X|Rest],C1,Result):-
C2 is C1*10+X,toNum(Rest,C2,Result).
calc(Z):-
sets(Xs,Ys),
selects(Xs,[1,2,3,4,5,6,7,8,9],Rest1),
toNum(Xs,0,X),
selects(Ys,Rest1,Rest2),
toNum(Ys,0,Y),
Z is X*Y,
Z<10000,
Z1 is Z mod 10,
Z2 is (Z//10) mod 10,
Z3 is (Z//100) mod 10,
Z4 is (Z//1000) mod 10,
selects([Z1,Z2,Z3,Z4],Rest2,_).
sum([],Sum,Sum).
sum([X|Rest],Sum,Result):-Sum1 is Sum+X,sum(Rest,Sum1,Result).
main32:-
findall(Z,calc(Z),List),sort(List,List1),
sum(List1,0,Ans),write(Ans).
*問い34
問い30のコードをそのまま流用。
特に書くことなし。
check([_|_],0):-!,fail.
check([],0):-!.
check(Nums,Sum):-
T is Sum mod 10,
select(T,Nums,Rest),!,
Sum1 is Sum//10,
check(Rest,Sum1).
search(Nums,_,_,Sum,Sum):-
check(Nums,Sum).
search(_,_,7,_,_):-!,fail.
search(Nums,P,Deep,Sum,Result):-
between(P,9,N),
nth0(N,[1,1,2,6,24,120,720,5040,40320,362880],N1),
Sum1 is Sum+N1,
Deep1 is Deep+1,
search([N|Nums],N,Deep1,Sum1,Result).
sum([],Sum,Sum):-!.
sum([X|Rest],Sum,Result):-
Sum1 is Sum+X,sum(Rest,Sum1,Result).
main34:-findall(Re,search([],0,0,0,Re),List),
sum(List,0,Ans),Ans1 is Ans-3,write(Ans1).
*問い35
計算量低減テクニックで書いたコードといっても。
どの桁も奇数であるというものだけを探索して検討するようにしただけ。
２は探索では検討せず最後に足している。
テクニックがみについたら無意味に使いたがる、そういうコードかもしれない。
テクニックで遊ぶのも技術習得には必要な気もするのでこれもありかと。
round_list([],[],_).
round_list([X|L],R,Result):-round_list(L,[X|R],Result).
round_list([X|L],R,[X|Result]):-
reverse(R,R1),
append(L,R1,Result).
not_prime(N):-N<2,!.
not_prime(N):-
sqrt(N,N1),
N2 is floor(N1),
between(2,N2,N3),
N4 is N mod N3,
N4=:=0,!.
to_num([],Result,Result):-!.
to_num([X|List],Num,Result):-Num1 is Num*10+X,to_num(List,Num1,Result).
check_exe(List,Ans):-
round_list(List,[],Perm),
to_num(Perm,0,Num),
(member(Num,Ans)->!,true;true),
(not_prime(Num)->
true,!;fail).
result_list(List,_,_,List).
result_list(List,Deep,Ans,Result):-
create_perm(List,Deep,Ans,Result).
check_perm(List,Deep,Ans,Result):-
not(check_exe(List,Ans)),!,
to_num(List,0,Num),
result_list(List,Deep,[Num|Ans],Result).
check_perm(List,Deep,Ans,Result):-
create_perm(List,Deep,Ans,Result).
create_perm(_,6,_,_):-!,fail.
create_perm(List,Deep,Ans,Result):-
Deep<6,
between(1,9,N),
T1 is N mod 2,
T1\==0,
Deep1 is Deep+1,
check_perm([N|List],Deep1,Ans,Result).
main35:-findall(L,create_perm([],0,[],L),List),write(List),
length(List,Len),Len1 is Len+1,write(Len1).
*問い36 Double-base palindromes
http://projecteuler.net/problem=36
Prolog的コードで書いたつもり。
set([_],[]).
set([X1],[X1]).
set([X1,_],[X1]).
set([X2,X1],[X1,X2]).
set([X2,X1,_],[X1,X2]).
set([X2,X1,X0],[X0,X1,X2]).
num_perm([]).
num_perm([X|Rest]):-member(X,[0,1,2,3,4,5,6,7,8,9]),num_perm(Rest).
to_num([],Sum,Sum).
to_num([X|Rest],Sum,Result):-Sum1 is Sum*10+X,to_num(Rest,Sum1,Result).
to_bit2(0,[]):-!.
to_bit2(Y,[B|Result]):-Y1 is Y//2,B is Y mod 2,to_bit2(Y1,Result).
calc(Y):-
set(A,B),
num_perm(A),
num_perm(B),
[Top|_]=A,
0<Top,
to_num(A,0,X),
to_num(B,X,Y),
to_bit2(Y,Re),
reverse(Re,Re).
sum([],Sum,Sum).
sum([X|Rest],Sum,Result):-Sum1 is X+Sum,sum(Rest,Sum1,Result).
main36:-
findall(Y,calc(Y),List),write(List),
sum(List,0,Ans),write(Ans).
*問い37
ちょっとコードが冗長かもしれない。
速度はそれなり。
短い方から左へ数字列を伸ばしてそれが条件を満たす限りのばす単純な探索で作成。
右側を消したとき素数でなくなる数でも左側へ無限に数字を加えたらどこかで素数になるものがあるかもしれないので。
素数が１１個という情報がなかったらこの問題は恐ろしい難問となるはず。
探索は深さ制限で実行。
not_prime(N):-N<2,!.
not_prime(N):-
sqrt(N,N1),
N2 is floor(N1),
between(2,N2,N3),
N4 is N mod N3,
N4=:=0,!.
is_prime(N):-not(not_prime(N)).
to_num([],Sum,Sum).
to_num([X|Rest],Sum,Result):-Sum1 is Sum*10+X,to_num(Rest,Sum1,Result).
check_exe_R(0):-!.
check_exe_R(Num):-
Num1 is Num//10,
is_prime(Num),
check_exe_R(Num1).
search(List,List,_):-
to_num(List,0,Num),
10<Num,
check_exe_R(Num).
search(List,Ans,Deep):-
Deep>0,
Deep1 is Deep-1,
member(N,[1,2,3,5,7,9]),
to_num([N|List],0,Num),
is_prime(Num),
search([N|List],Ans,Deep1).
sum([],Sum,Sum).
sum([X|Rest],Sum,Result):-to_num(X,0,Num),Sum1 is Sum+Num,sum(Rest,Sum1,Result).
main37:-between(2,10,N),
findall(Ans,search([],Ans,N),List),length(List,11),
!,write(List),sum(List,0,Ans),write(Ans).
*問い38
探索するだけの問題です。
最後に出てきた数字の並びが答えとなります。
num_add(0,List,List):-!.
num_add(Num,List,[X|Result]):-
X is Num mod 10,
Num1 is Num//10,
num_add(Num1,List,Result),
X>0,
not(member(X,Result)).
search(_,_,List,_):-
length(List,Len),9<Len,!,fail.
search(_,_,List,List1):-
length(List,9),reverse(List,List1),!.
search(N,P,List,Result):-
N1 is N*P,
P1 is P+1,
num_add(N1,List,NextList),
search(N,P1,NextList,Result).
search_start(Re):-
between(1,9999,N),
search(N,1,[],Re).
main38:-
findall(Re,search_start(Re),List),
sort(List,List1),write(List1).
