数独+IP+GLPK
某友人がCPLEXで数独を解いてみたと聞いて、自分でもやってみた。
01変数を9*9*9=729個使った定式化。たぶん某友人と同じ。
モデリングにはGNU MathProgを使い、ソルバはGLPKを使った。
以下のファイルを書いてから
glpsol -m sudoku.mod -d instance.dat -w result.txt
で最適化実行。
結果をawkで整形すればできあがり。
tail -n 729 result.txt | gawk '{c += $0*++i;};NR%9==0{printf("%d",c);c=0;i=0};NR%81==0{printf("\n")}'
インスタンスの出展はwikipedia:数独。
計算が重ければソルバにCPLEXを使うこともできるけど、
CPLEXに比べて遅いGLPKでも一瞬で解けた。
# sudoku.mod set I := 0..8; set J := 0..8; set K := 1..9; set B := 0..8; set Bs{b in B} := setof{y in 0..2, x in 0..2}(y+3*(b div 3),x+3*(b mod 3)); var X{I,J,K} binary; param known{I,J}, integer; minimize dummy: sum{i in I,j in J,k in K}X[i,j,k]; s.t. Row{i in I,k in K}: sum{j in J}X[i,j,k] = 1; Col{j in J,k in K}: sum{i in I}X[i,j,k] = 1; Cell{i in I,j in J}: sum{k in K}X[i,j,k] = 1; Block{b in B,k in K}: sum{(i,j) in Bs[b]}X[i,j,k] = 1; Known{i in I,j in J,k in K: known[i,j]==k}: X[i,j,k]=1;
# instance.dat param known : 0 1 2 3 4 5 6 7 8 := 0 5 3 0 0 7 0 0 0 0 1 6 0 0 1 9 5 0 0 0 2 0 9 8 0 0 0 0 6 0 3 8 0 0 0 6 0 0 0 3 4 4 0 0 8 0 3 0 0 1 5 7 0 0 0 2 0 0 0 6 6 0 6 0 0 0 0 2 8 0 7 0 0 0 4 1 9 0 0 5 8 0 0 0 0 8 0 0 7 9;
# 出力 534678912 672195348 198342567 859761423 426853791 713924856 961537284 287419635 345286179
■
昔作った「シャノンのスイッチングゲーム」を作り直した。
http://www.misojiro.t.u-tokyo.ac.jp/~tzik/shannon/index.xhtml
前々回の五月祭で、室田教授の助言のもと id:yambi、id:jeneshicc と一緒に作ったものだ。
以前作ったものは、中核の計算部分はC++で書いてサーバ上で動かし、
インターフェイス部分はJavascriptとSVGで書いて、firefoxから使うものだった。
ライブラリは標準のもの以外は特に使わず、ブラウザごとの挙動の違いは無視して
五月祭当日の環境での動作だけを考慮していた。
今回のものは計算部分をJavascriptで書き直して、ブラウザ側だけで完結させ、
外部ライブラリとしてjqueryとraphaelを使った。
例のごとくInternet Explorerは未対応。
raphaelでの描画とcssでのスタイル付けを併用しているのが原因。
cssを使っている部分を手動でエミュレートすればIEでも動くかもしれないが、きれいな解法じゃない。
なんとかならないかな…
# id:yambi に先に紹介されてしまった。
Interactive SVG
ふと思いたってsvgでボール遊びなどしてみる。IEは非対応。
次期Firefox (Gecko 1.9.3)ではsvgのanimationモジュールが実装されるらしい。
現状ではsetIntervalとかのタイマーを使って絵を少しずつ更新して
動いているように見せているけど、
補間をブラウザに任せて、タイマー無しで作れるようになるかも。
追記:
衝突処理を修正。
割と楽しい動きをするようになったけど、これって物理的に正しいのかなあ…
追記:
Google Chrome (WebKit 532.6)ではanimateタグは認識して、
変数を線形に補間するアニメーションは作れた。
スプライン補間はしてくれないらしい。
Opera (Presto 2.2.15)ではスプライン補間までしてくれた。
SVG 1.1 Support in Firefox - SVG: Scalable Vector Graphics | MDN
Webkit SVG status
How can we help you? - Opera Help
Javascriptは関数型言語
最近jquery.js, raphael.jsを使ってjavascriptでゲームを作った。
javascriptの扱いにもだいぶ慣れてきた。
だんだんjavascriptは関数型言語だと思えてきた。
ConTeXt+TeXLive2009
今日はレポート提出日。
でも、いざコンパイルして印刷しようとしたらコンパイルエラーが出た。
\usemodule[japanese] で参照している font-jap.tex が見つからないらしい。
http://wiki.contextgarden.net/Context_2009.08.19 によると、
TeXLive2008から2009へのアップデートで
font-jap.tex は font-jap.mkii にリネームされたようだ。
http://en.wikipedia.org/wiki/ConTeXt によると、
mkii は Mark II のことで、機能追加の行われない安定版。
TeX のエンジンとして pdfTeX や XeTeX を使っているらしい。
一方、ConTeXtには開発版の Mark IV (MKIV)というのがあり、
こちらは LuaTeX を TeX のエンジンとしているとのこと。
Mark IV で日本語を使うにはどうすればいいんだろう…？
ともかく、今回は急いでコンパイルを通す必要があるので応急措置。
# cd /usr/share/texmf-dist/tex/context/base # ln -s font-jap.mkii font-jap.tex # ln -s font-chi.mkii font-chi.tex # mktexlsr
と、リネームを戻したら無事コンパイルを通った。
ConTeXtでレポート
とりあえず書いてみた。提出前だし、回答は割愛。
記号類にunicode文字を使っても大丈夫みたい。
agdaのunicode入力が便利。
フォントの指定方法があっているのか不明。
ConTeXtではMathMLの数式を扱えるらしい、後で使ってみよう。
Mathematicaとかと連携させると色々楽になるかな。
\enableregime[utf-8] \mainlanguage[ja] \usemodule[japanese] \definefontsynonym[Japanese][ipag] \definefontsynonym[ipagRegular][ipag] \definefontsynonym[ipagBold][ipag] \noheaderandfooterlines \defineenumeration[Problem][text=問題] \defineenumeration[Answer][text=回答] \defineenumeration[Note][text=Note] \starttext {\tfa % タイトル } \rightaligned{% % 所属とか } \Problem $\{X_i\}_{i ∈ ℕ}$は独立に同一の分布に従う確率変数列， $M_n := \max\{x_i\}_{i=1}^n$とする． $G(x)$を$X_i$の確率分布の分布関数として， $$\lim_{x→∞}{\rm e}^x\{1-G(x)\} = c,\quad c>0$$ が成立するとき， $$\lim_{n→∞}P[M_n-\log(cn) ≤ x] = {\rm e}^{-{\rm e}^{-x}}$$ となることを示せ． \Problem Cauchy分布は，密度関数が， $$f(x) = {1\over π}{c \over x^2 + c^2},\quad (c>0)$$ で与えられる確率分布である． Cauchy分布の特性関数が， $$φ(λ) = {\rm e}^{-c|λ|}$$ となることを示せ． \Problem Cauchy分布の場合，Lamperti p.89 Lemma 1 にある， 分布の裾に対する特性関数を用いた上限がどのくらいゆるいかを確認せよ． J. Lamperti. {\it Probability: A survey of the mathematical theory}, page 89. John Wiley \& Sons Inc, 1996. {\it Lemma 1.\quad Let $X$ be a random variable with characteristic function $ψ$. Then for any $u>0$, $$P\left[|X|>{2\over u}\right] ≤ {1\over u}∫_{-u}^u \{1-ψ(λ)\}{\rm d}λ.$$ } \Problem $\{X_k\}_{k ∈ ℕ}$を独立同一な$[-1,1]$の一様乱数列とし， $$Y_n = ??_{k=1}^n {\rm sign}(X_k){1\over |X_k|^{1/2}}$$ とおく． $\sqrt{n \log n}$で基準化すれば$Y_n$は正規分布に分布収束することを示せ． \stoptext % Local Variables: % compile-command: "texexec --batchmode report-2.tex" % after-save-hook: (lambda () (compile compile-command)) % End:
