SAT ソルバで数独を解く方法 - まめめも
数独は非常に SAT に変換しやすい問題です。全部参考文献 *1 に載っている内容ですが、なるべくわかりやすく説明してみます。ちょっと長いです。 SAT とは まず SAT をごく簡単に説明します。すでに SAT を知っている人はここは読み飛ばしてください。 命題論理式の形の一つに乗法標準形のというのがあります。変数か変数の否定 (リテラルと言います) を or だけでつないだ式 (節と言います) を and だけでつないだ論理式のことを言います。つまり以下みたいな形です。 ( a1 or !a2 or ... or an) and ( b1 or !b2 or ... or !bn) and ... and (!z1 or z2 or ... or !zn)SAT は「a1 や zn などの変数にうまく true か false を代入して、上の式全体を true にできるか」という問題
ruby 0.62 のソースコードを復活させた - まめめも
RubyKaigi の後夜祭で、akr さんが「327 種類の Ruby をビルドする方法 〜0.49 から 2.6.0-preview2 まで〜」という発表をされていました。 RubyKaigi 2018 After Party で話したスライドです: 「327 種類の Ruby をビルドする方法 ~0.49 から 2.6.0-preview2 まで ~」https://t.co/J5MXgM2PNN— Tanaka Akira (@tanaka_akr) 2018年6月4日 その中で、ruby-0.62.tar.gz と ruby-0.63.tar.gz のファイルは「gzip 形式じゃないといわれて展開できない」ということで、ビルド対象から外されていました。 いろいろやって、めでたくこの 2 ファイルを復活させることに成功しました。そのプロセスを書きます。 なお、壊れていたファイルも
『オブジェクト指向設計実践ガイド』を読んで - まめめも
オブジェクト指向設計実践ガイド ~Rubyでわかる 進化しつづける柔軟なアプリケーションの育て方posted with amazlet at 16.09.01Sandi Metz 技術評論社 売り上げランキング: 20,383 Amazon.co.jpで詳細を見る 自著を書いたご縁で、技術評論社さまから贈本いただきました。ありがとうございます。 本書は明日 9/2 (金) に発売らしいですが、発売前に読み終わったので書評など書きます。（書評アフィリエイトブログみたい） 概要 一言で言えば、「仕様変更に強い Ruby プログラムを設計する方法」というテーマの本です。 2 つのクラスにまたがる関心事を実装するとき、どっちのクラスにどんなメソッドを持たせるべきか、ということは誰でも悩んだことがあると思います。正解があるわけではないので、自分で基準を選んで決定するしかないわけですが、この本は「将来
ハッシュは頻繁に参照する値を最後に入れると高速 - まめめも
明日から RubyKaigi なので、ちょっとした小ネタを一つ。 例えば、0 から 9999 までをハッシュに順に入れます。 h = {} 10000.times do |n| h[n] = true end このとき、h[9998] や h[9999] は、h[0] や h[1] より高速です。 どのくらい高速かというと、 1_000_000_000.times { h } # 40.8 sec (ループ自体の速度) 1_000_000_000.times { h[9999] } # 57.2 sec 1_000_000_000.times { h[0] } # 89.1 sech[0] は 89.1 - 40.8 = 48.3 nsec 、h[9999] は 57.2 - 40.8 = 16.4 nsec ということになります。なんと 3 倍も速い。*1 なぜこんなことが起きるのか ハ
クリーネの再帰定理＋ Quine が書けることの証明 - まめめも
クリーネの再帰定理のプログラマ向け説明（＋証明）を書いてみました。何か間違ってたら教えて！ 前提 すべてのプログラムは文字列を 1 つ入力して文字列を 1 つ出力する、という世界を考えます。なお、プログラム自体も当然文字列です。 プログラムは eval っぽい命令を使っていいことにします。つまり、プログラムpと、pへの入力文字列sを受け取って、pを実行した結果の出力文字列を返す関数 E(p, s) が利用可能です。*1 二つのプログラム p と q が完全に同じように振る舞うとき、p 〜 q と書くことにします*2。これは明らかに推移的。 定理 任意のプログラム f に対し、p 〜 E(f, p) となるようなプログラム文字列 p が存在する。*3 定理の証明 以下のような 3 つの文字列を考えます。 h: 入力文字列 x に対し、E(x, x) の結果を出力するプログラム*4 e: 入力
contributor を大切に - まめめも
「htmlspecialcharsのパッチ私案」に書いた件、バグレポートを出してみましたが、「すでに同じバグレポートがあるだろ」という理由により、あえなく却下されました。 htmlspecialcharsに関する残念なお知らせ - 岩本隆史の日記帳 これ関係のいろいろを見て思ったこと。どうでもいい長文です。結論はありません。 信用のない人のパッチが通るかどうかは運 が大きいと思います。パッチの出し方は無関係ではないですが (信用度が大きく変わる) 、勘違いされたり見過ごされたりはどうしてもあると思います。 今回は変な人に当たっちゃったみたいですね。残念！ 問題の説明について日本語の URL を貼るだけというのはさすがにきついとは思いましたが、「わかんないから却下」という返答ではないので今回はそれは関係ないのでしょう。 パッチを送るときはいろいろと期待とか気負いとかあるのはわかる (ぼくもあ
放射線耐性 Quine (1 文字消しても動く Quine) - まめめも
ref: https://github.com/mame/radiation-hardened-quine 放射線はメモリエラーを引き起こすらしいです。そんな放射線が飛び交う過酷な環境でも、できることなら Quine したい。 ということで、プログラム内の 1 文字をランダムに消しても元のプログラムを出力する、なんともロバストな Quine を書きました。*1 何を言っているかわからないと思いますが、こんなふうに動くものです。 # ランダムに 1 文字消すスクリプト $ cat mutate.rb src = $<.read src[rand(src.size), 1] = "" print src # rrquine.rb からランダムに 1 文字消したプログラムを生成する $ ruby mutate.rb rrquine.rb > broken.rb # 壊れたプログラムを実行する (
回文や XML にマッチする鬼車の正規表現 - まめめも
ref: 鬼車 正規表現 Version 5.9.1 ref: Ruby Freaks Lounge: 第6回 Ruby M17N 事始め:正規表現編 \g と \k について今までちゃんとわかってなかったけれど、少しわかったような気になったのでメモ。Ruby というより鬼車の話なので、PHP でも使えるかもしれない。試してないけど。 田中哲スペシャル \g の基本 \g で参照される括弧の中身がそこにそのまま書かれたと思えばいい。 re = /\A(?<foo>abc...def)\g<foo>\z/ # \g<foo> を展開して考える # /\A(?<foo>abc...def)abc...def\z/ と同じ意味 p "abc123defabc123def".match(re) # マッチ p "abc123defabc456def".match(re) # マッチ p "abc1
gcov の使い方 - まめめも
concov のドキュメントを書こうと思ったけれど、何から書くか困ったので、とりあえずその前に gcov の使い方とはまりどころを書いてみます。 gcov とは C 言語で書かれたプログラムのカバレッジを測定するツールです。gcc に付属しています。 基本的な使い方 こういうコードがあるとする。 /* test.c */ #include <stdio.h> int foo(int x, int y) { return x + y; } int bar(int x, int y) { return x - y; } int main(void) { printf("%d\n", foo(2, 3)); printf("%d\n", foo(3, 4)); return 0; } コンパイルする。-coverage をつけると gcov 用のオブジェクトファイルが生成される *1 。 $ g
Quine リレー - まめめも
ref: https://github.com/mame/quine-relay/ 以下は、自分自身を出力する REXX プログラムを出力する Python プログラムを出力する R プログラムを出力する (...略...) を出力する Scala プログラムを出力する Ruby プログラムです。合計 50 言語を使います。 eval$s=%q(eval(%w(B=92.chr;N=10.chr;n=0;e=->(s){s.gsub(/[#{B+B+N}"]/){B+(N==$&??n:$&)}};E=->(s){'("'+e[s]+'")'} ;d=->(s,t=?"){s.gsub(t){t+t}};D=->(s,t=?@){s.gsub(B){t}};Q=->(s,t=?$){s.gsub(t){B+$&}};puts(eval(%q("objectXQRX extendsXApp{
in 中置演算子 - まめめも
「func() の帰り値が 1 または 2 または 3 のとき」みたいなことを書きたいことはよくあります。 r = func() if r == 1 || r == 2 || r == 3 p "hit" end しかし、いちいち変数に代入しないといけないのが気に入りません。とくに変数名を考えるのが面倒くさい。あと、r == を何回も書くのも気に食わない。 そこで、Array#include? を使う人もいます。 if [1, 2, 3].include?(func()) p "hit" end しかしこれは、1 、2 、3 、func() の語順が直感に合いません。この処理の主体は func() の帰り値なので、最初に func() を書きたいのです。「ary が x を含むかどうか」と「x が ary に含まれるかどうか」は意味は同じですが、ニュアンスが違うのです。*1 *2 *3 そ
Merry Quine-mas 2012 - まめめも
今夜は、年に一度の W. V. Quine の命日イブです。(もう日が変わってますが) %;';;eval$s=%q{eval(%w~i=1;T="$)*L)L)))0)E(E(0(7(>'>'7&E&0&7&>%L%)%0%E*)$L$)* L)L)))0 )E(E(0(7(>' >'7&E&0&7&>%L%)%0%E5&$L%#8C5G7/530L2B1*/'19-D03 #E*&,1). *G'6#3*>5 &'F'#)E(L)0*)'L'?(#)#)7(E'0&E&#(0%0&L%7&0':+)%E# {"4F"*18} 3F4F5F4 F4@493@1@5@7@6@692@2939325952425+4+3+3F4$5F4F".by tes.each_s lice( 2).map{|s,c|[s*3-99,c/7*3-13-i=-i,c%7+41]};$><<"'# {e=27.
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
