名古屋で数学するプログラマ(仮)

@antimon2 が趣味兼一部本職の数学で何かするときのブログ。

「充足可能性問題(3-SAT)を解く乱択アルゴリズム」 by Haxe

初雪です。さっき吹雪いてました。てか3か月ほどブログ更新滞ってました(>_<)
統計とか機械学習の勉強も進んでないのですが、今日はリハビリに、また例の 3-SAT ネタでも投下しときます。

半年以上前に『Rで「充足可能性問題(3-SAT)を解く乱択アルゴリズム」』て記事でこんなこと書いています:

新しい言語を覚えるときに、数学ガール 乱択アルゴリズムの「充足可能性問題(3-SAT)を解く乱択アルゴリズム」(p.353)を実装するという癖がついてしましました。

また新しい言語で書いてみました。
今仕事で使っている、Haxewikipedia:Haxe)で。

Haxeというのが元々ActionScriptから派生した言語で、基本構文もECMAScriptにほぼ準拠してるので、結局以前に書いた JavaScript 版とかなり近い実装になっちゃいました。今回も焼き直し感が否めないです。

ただ、今までの言語と違う点が1点。
今までの言語(最期の一覧します)は、所謂「スクリプト言語」だったのですが、今回は一応分類上は「コンパイル言語」。今までは言語の動的な性質を利用(eval 関数またはそれに相当するものを利用して文字列を解析・実行等)してきたのですが、今回はそれが使えない*1
で。
今回は、「クローズ(Clause)を表す文字列を自前で解析」しています。parseClause 関数参照。
てかこの方法は他の言語でも応用できますね。しかも、今までは言語の癖に合わせて入力を少しずつ変えてきたけど、入力形式を統一することも可能ですね。

ちなみに動作は、JavaScriptC++Java*2 の各プラットフォームで確認しています。

最後に、今までの Rw3sat の実装を一覧列挙。

*1:一応、Haxe のコンパイル先を JavaScript にすれば、条件コンパイルや untyped コードを組み合わせて JavaScript のコードも書ける、つまり eval も使えるのですが、クロスプラットフォームで動くものにしたかったので今回は使用していません。

*2:日本語が文字化けしますが、一応動作します。