Category Archives: 制約論理プログラミング

Project Euler Problem 59

全体の文字数 – 「何文字がA-Z a-zの範囲だったか」　の数値をコストとして計算し、一番コストが小さくなるものをbb_minで調べました。
あんまり効率よくないプログラムで、1900秒くらいかかりました…遅いな…
あとテキストの文字数が3の倍数というところは前もって調べてて、それをあてにしたプログラムになってます（文字数が3の倍数でないとdecryptでこける）

ソース

:-lib(ic).
:-lib(ic_sets).
:-lib(propia).
:-lib(branch_and_bound).
:-lib(csv).

go(Str,Cost,Sum) :-
	csv:(csv_read("p059_cipher.txt", [InLst], Option)),
	char_code('a',AscA),
	char_code('z',AscZ),
	[Key1,Key2,Key3]#::AscA..AscZ,
	decrypt(InLst,OutLst,[Key1,Key2,Key3]),
	OutLst#::0..127,
	OutLst#::0..127,
	letter_count(OutLst,Cnt),
	length(OutLst,Len),
	Cost #= Len - Cnt, 
	flatten([Key1,Key2,Key3,OutLst],AllVals),
	labeling(AllVals),
	iso_light:(atom_codes(Str,OutLst)),
	mysum(OutLst,Sum).

decrypt([],[],_).
decrypt([N1,N2,N3|NRest],[D1,D2,D3|DRest],[K1,K2,K3]):-
	xor(N1,K1,D1) infers most,
	xor(N2,K2,D2) infers most,
	xor(N3,K3,D3) infers most,
	decrypt(NRest,DRest,[K1,K2,K3]).

letter_count([],0).
letter_count([First|Rest],Cnt):-
	letter_count(Rest,Cnt1),
	#::(First, [65..90, 97..122],Hit),
	Cnt #= Cnt1+Hit.

mysum([],0).
mysum([First|Rest],Sum):-
	mysum(Rest,Sum1),
	Sum is Sum1 + First.

:-lib(ic).

:-lib(ic_sets).

:-lib(propia).

:-lib(branch_and_bound).

:-lib(csv).

go(Str,Cost,Sum) :-

csv:(csv_read("p059_cipher.txt", [InLst], Option)),

char_code('a',AscA),

char_code('z',AscZ),

[Key1,Key2,Key3]#::AscA..AscZ,

decrypt(InLst,OutLst,[Key1,Key2,Key3]),

OutLst#::0..127,

letter_count(OutLst,Cnt),

length(OutLst,Len),

Cost #= Len - Cnt,

flatten([Key1,Key2,Key3,OutLst],AllVals),

labeling(AllVals),

iso_light:(atom_codes(Str,OutLst)),

mysum(OutLst,Sum).

decrypt([],[],_).

decrypt([N1,N2,N3|NRest],[D1,D2,D3|DRest],[K1,K2,K3]):-

xor(N1,K1,D1) infers most,

xor(N2,K2,D2) infers most,

xor(N3,K3,D3) infers most,

decrypt(NRest,DRest,[K1,K2,K3]).

letter_count([],0).

letter_count([First|Rest],Cnt):-

letter_count(Rest,Cnt1),

#::(First, [65..90, 97..122],Hit),

Cnt #= Cnt1+Hit.

mysum([],0).

mysum([First|Rest],Sum):-

mysum(Rest,Sum1),

Sum is Sum1 + First.

実行結果

?- bb_min(go(A, Cost, Sum), Cost, _223).
A = 復号化した文字列（伏せます）
Cost = 伏せます
Sum = 伏せます
Yes (1893.05s cpu)

?- bb_min(go(A, Cost, Sum), Cost, _223).

A = 復号化した文字列（伏せます）

Cost = 伏せます

Sum = 伏せます

Yes (1893.05s cpu)

Project Euler Problem 52

Leave a reply

Problem52

ECLiPSeで解きました。
処理時間は自分のマシン(Intel(R) Core(TM) i5-3340M CPU @ 270GHz)で6.5秒くらい。
見どころ？はECLiPSeのlogical-loopで書いた順列permutationと、propiaで数値を入れ替えた制約を作っているところ
logical loop はループ用のサブ述語みたいなアホっぽい定義がなくなってコードがエレガントになるのでSWI-Prologでもぜひ正式採用してほしい。
桁のところは一般化してなく、1桁、2桁、3桁…　と手入力で増やしながら確認しました
（bb_minでそれぞれの桁での最小の数値が取れるようにしてます）。

プログラム：

:-lib(ic).
:-lib(propia).
:-lib(branch_and_bound).

go(Digits,[X1num,X2num,X3num,X4num,X5num,X6num]) :-
	length(X1Lst,Digits),
	X1Lst#::[0..9],
	lst2num(X1Lst,X1num),
	X1num #> 10 ^ (Digits-1),
	X2num #= X1num * 2,
	X3num #= X1num * 3,
	X4num #= X1num * 4,
	X5num #= X1num * 5,
	X6num #= X1num * 6,
	permutation(X1Lst,X2Lst) infers most,
	lst2num(X2Lst,X2num),
	permutation(X1Lst,X3Lst) infers most,
	lst2num(X3Lst,X3num),
	permutation(X1Lst,X4Lst) infers most,
	lst2num(X4Lst,X4num),
	permutation(X1Lst,X5Lst) infers most,
	lst2num(X5Lst,X5num),
	permutation(X1Lst,X6Lst) infers most,
	lst2num(X6Lst,X6num),
	labeling([X1num,X2num,X3num,X4num,X5num,X6num]).
	
lst2num(L,N):-
	(foreach(Num,L),fromto(0,In,Out,N),count(I,0,_)
		do
		Out #= In + 10^I * Num
	).

permutation(A,B):-
	(fromto(A,AIn,AOut,[]),fromto(B,[BFirst|BRest],BRest,[])
		do
		select(BFirst,AIn,AOut)
	).

:-lib(ic).

:-lib(propia).

:-lib(branch_and_bound).

go(Digits,[X1num,X2num,X3num,X4num,X5num,X6num]) :-

length(X1Lst,Digits),

X1Lst#::[0..9],

lst2num(X1Lst,X1num),

X1num #> 10 ^ (Digits-1),

X2num #= X1num * 2,

X3num #= X1num * 3,

X4num #= X1num * 4,

X5num #= X1num * 5,

X6num #= X1num * 6,

permutation(X1Lst,X2Lst) infers most,

lst2num(X2Lst,X2num),

permutation(X1Lst,X3Lst) infers most,

lst2num(X3Lst,X3num),

permutation(X1Lst,X4Lst) infers most,

lst2num(X4Lst,X4num),

permutation(X1Lst,X5Lst) infers most,

lst2num(X5Lst,X5num),

permutation(X1Lst,X6Lst) infers most,

lst2num(X6Lst,X6num),

labeling([X1num,X2num,X3num,X4num,X5num,X6num]).

lst2num(L,N):-

(foreach(Num,L),fromto(0,In,Out,N),count(I,0,_)

Out #= In + 10^I * Num

permutation(A,B):-

(fromto(A,AIn,AOut,[]),fromto(B,[BFirst|BRest],BRest,[])

select(BFirst,AIn,AOut)

実行結果（解答伏せます）：

?- bb_min(go(XXXXXXX, [N1, N2, N3, N4, N5, N6]), N1, Option).
N1 = XXXXXXXX
N2 = XXXXXXXX
N3 = XXXXXXXX
N4 = XXXXXXXX
N5 = XXXXXXXX
N6 = XXXXXXXX
Option = bb_options(continue, -1.0Inf, 1.0Inf, 1, 1, 0, 0, one, _466, _467, _468)
Yes (6.59s cpu)

?- bb_min(go(XXXXXXX, [N1, N2, N3, N4, N5, N6]), N1, Option).

N1 = XXXXXXXX

N2 = XXXXXXXX

N3 = XXXXXXXX

N4 = XXXXXXXX

N5 = XXXXXXXX

N6 = XXXXXXXX

Option = bb_options(continue, -1.0Inf, 1.0Inf, 1, 1, 0, 0, one, _466, _467, _468)

Yes (6.59s cpu)

[Prolog]最近の勉強

Leave a reply

最近あんまりPrologのブログ書いてませんが、ずっと研究してます(具体的にブログに書けるような結果が出てない）現在はECLiPse（IDEのほうじゃなくて制約プログラミングのほう）の勉強してます。

書くネタないので今までのPrologの勉強の流れを説明すると以下のような感じで進んできました(スパンは数年単位）

広井さんのページでPrologの基礎を把握しいくつかのパズルのソルバーを作る（20年近く前に大学の授業で受けていたがあまり深いところまで理解していなかった）

↓

SWI-Prologのマニュアル読み込むうちCLPFDを発見し衝撃を受け、勉強開始

↓

ProjectEulerでPrologで問題を解くうち、正答者スレでECLiPseを用いてSWIの自分のプログラムよりはるかに速いスピード(数十倍）で結果を出している人を発見して衝撃を受ける。プログラムの内容自体はCLPFDを使用した自分のとそんなに変わらなかった。

↓

ECLiPseの勉強を始める。だんだんSWI-PrologのCLPFDがSicstusやECLiPseの制約ソルバーに比べると「オモチャ」レベルだったということがわかってくる。また、SWI-PrologのCLPFD開発者のmarkus triskaさんは開発の継続をsicstusで行うみたいな記述を最新のSWIのマニュアルで見つけた。

また、ECLiPse は node.jsを使用してjavascriptで呼び出せるらしく、ECLiPseの勉強はWeb系の仕事でのちのち面白い威力を発揮するかもしれないと期待を抱く。

↓

ECLiPseには、自分がSWIのCLPFDでどうしてもできなかった自作制約の作成がPropiaとCHRの2種類の方法で可能なことを知り、そちらの勉強を開始。SWIのCLPFDの自作制約の作成方法はマニュアルが意味不明だった（まだ完成してないとも書いてある）

↓

Propiaのほうは大体の概要を把握。任意の述語をそのまま制約にできて、Propagationの厳密さをinferという述語の引数でコントロールするという仕組みらしい

↓

CHRの勉強に移る。ルール自体は少ないが結構難しくてどのように作ればよいかなかなか理解できない。CHRはHaskellやJavaなどでも使用できるようだ。

↓

CHRが並列計算に向いていると知り、ハードウェアで実行したりGPUを使用したりして解くといった論文をネットで見つけて読み始め、少しECLiPseの勉強から浮気する。

↓

「CHRをGPUを用いて計算する｣方法を記載した論文を見つけるが実際にやった時の速度比較が載ったものを見つけることができなかったので、そういう論文が出ないかを定期的にウォッチすることに決め、とりあえず論文リサーチはやめる。CHRをハードウェアでやった論文では数万倍とかのスピードで解いてるの見つけたが良く読むとCHRの機構だけではなくプログラムのほうもハードウェア化していてちょっとちがうだろという感じだった（論文で使用している最大公約数求めるみたいな単純なロジックしかハードウェア化できなくて現実的ではないし、そもそもそれってCHR自体の速さではない）

↓

またECLiPseのCHRの勉強に戻る

△いまここです。

まあ日本語の情報がないです。
ずーーっと英語読んでます。ECLiPse、日本で使ってる人100人もいないんじゃなかろうか。日本のECLiPse界では望まずして第一人者になりそうです。もしそういう人たちいれば仲間に入れてほしい。誰か一緒に勉強しませんか？情報交換して一緒に研究の成果を教えあいましょう

CHRはルール自体は3種類しかなくて単純なんだけど以下が良くわかってなくてまだ自作の制約を作るまで至ってない

・labelingの振る舞い
・制約の述語の変数に「値を設定した時？」と「新しい制約がセットされたとき？」に再度bodyがfireされるらしいがそこらへんの振る舞い

多分CHRの制約の形が｢自分がCLPFDを勉強してきた上で持っている制約のイメージ」とかなりずれているのが理解が滞ってる理由だと思います。

自分の数年の目標であるTantrixというパズルのソルバーをECLiPseの自作制約でいつか作れれば良いなあ。手続き型だと現在のスキルで多分作れるが制約プログラミングで作るという目標がありわざとそういう手法では作ってない

…………………………うーん。

この記事書いてるうちになんで自分がCHRを必死に勉強してるのか分かんなくなってきた…
Propiaで間に合ってるような気がしてきたので、そっちでやるかな…。CHRは「つかうとすごいスピードが出るケースが見つかる(並列処理とかで）」とか「CHRで書かれためちゃくちゃエレガントなコードを見つける」みたいな状況になってから改めて勉強しようかな。
CHRの良さをご存じの方いらっしゃればぜひ koyahata*koyahatataku.com(*を@に変更) にメール下さい。そうでなくてもProlog関連で勉強中の人はぜひ連絡取り合って一緒に勉強しましょう

ブログまとめるのも自分の行動を見直す良い機会になりますね

よし方向転換