ICFP Programming Contest 2010 終了 - まめめも
ref: http://icfpcontest.org/ 今回の課題は近年稀に見る面白さでした。要約するとこんな課題。 車とその燃料を開発して、市場に投入せよ。 市場に投入された車の設計書は参加者全員に公開される。燃料の設計書は公開されない。 他社の車の設計書を解析して、他社の車用の燃料を開発し市場に投入することもできる。売上はほぼ折半 *1 。 燃料の売上を競う。 以上より目的は、「解析が難しい車を設計して投入し、燃料の売上を寡占する」かつ「他人の車を解析して燃料を作り、売上を奪う」ということになります。すばらしい皮肉的な設定。 さらに ICFPC らしさとして、 車や燃料の設計書は trit 文字列 (0 と 1 と 2 のみからなる文字列) で書かれる。trit 文字列の仕様は非公開。適当に作った設計書を投入してみて、パースエラーのメッセージを元に、トライアンドエラーでフォーマットを
Ruby でパターンマッチ - まめめも
ref: 未来の国のアリス - d.y.d. で紹介されている implicit future が Ruby に欲しい！ # promise を作る x = Promise.new a = [1, x, 2, x, 3, x] # 今はまだ値になっていない p a #=> [1, _promise_, 2, _promise_, 3, _promise_] # この promise は 42 に決めた！ (代入ではないよ) x === 42 # x の箇所は勝手に 42 になっている p a #=> [1, 42, 2, 42, 3, 42] というのも、これがあれば Ruby でパターンマッチができる気がするんですよね。こんな感じに。 # 何にでもマッチする箇所には _ と書く (実体は Promise.new) def _ Promise.new end # + と定数だけからなる抽象
山手 quine - まめめも
t="+,m-n./mAm0o1p23a4q56r7sBt89u-t-1:v;A<w4x=y1z>[?]A^@CD_ CD_EsF`GHmIJbKa*l";eval$s=%w{F=%q{ceY8#<DvO1=x&t9CSOqMYkzH U.kCpz+Vo8hB.1AF&tq21+$/IrMY]U.aDd!-1y!4MMGQm6m?bYh($QMYpX s4g,x1UlbNKH?>NzbisMn?sT@m3,F.Abb`xW!r%'%Ybee>xkUfjf[(*^Nd Xo_"@hQh%Fx*q[iB7EM"suSG8GVOIzceg/O=4CL,d[-k]twgVP`&wcfaT` 2M)j8sFY?(HKzOrVCHO_694[Uq8g @i/i;tMBG#;-;B]rV[])`3'<os^. OV(SA<=ok%m[iV#qt[&dJ7SIdB;/ VUnVIrH;hEJ*QWD"E+
2 進数のふしぎ - まめめも
"%b" % -1 #=> "..1" "%b" % -2 #=> "..10" "%b" % -3 #=> "..101" "%b" % -4 #=> "..100" を見て思ったんですが、ビット長に制限が無ければ、負の整数の 2 進数表記はある桁以上が全部 1 と考えられるんですね。逆に正の整数はある桁以上が 0 と考えられる。 じゃあ、..010101 みたいに、ある桁以上が 0 と 1 を交互に繰り返す数字って考えられるのかなと思ったんですが。 a = ..010101 a*2 = ..101010 a*2 + a = ..101010 + ..010101 = ..111111 = -1 a = -1/3あれ？
Q(uine)R(uby) code - まめめも
RubyKaigi でこっそり (?) 発表したものを再掲。 読み込んでみる *1 。 $ java -classpath classes example.QRCodeDecoderCUIExample quine-ruby-code.png > quine-ruby-code.rb [Success] quine-ruby-code.png Processed 1 images in 1050ms (1050 images/sec) OK: 1 NG: 0quine-ruby-code.rb はこんなの。 #!ruby # Q(uine)R(uby)code (C) Y.Endoh 2009 eval s=%q(X=(0..7).map{|i|1<<i};W=116;m=(1..w=117).map{[]};B=999.times{|i|X<<( X[-4]^X[-5]^X[-6]^X[
勉強帳 (2) - まめめも
Scala By Example を読みます。 資料: http://www.scala-lang.org/docu/files/ScalaByExample.pdf 1. Introduction いんとろだくしょん 2. A First Example imperative に書いたクイックソートの例。 def sort(xs: Array[Int]) { def swap(i: Int, j: Int) { val t = xs(i); xs(i) = xs(j); xs(j) = t } def sort1(l: Int, r: Int) { val pivot = xs((l + r) / 2) var i = l; var j = r while (i <= j) { while (xs(i) < pivot) i += 1 while (xs(j) > pivot) j -=
Ruby の例外クラスは分類が粗すぎる or 細かすぎる - まめめも
と思いません？ def foo(x) end foo(1, 2) #=> wrong number of arguments (2 for 1) (ArgumentError) 1.step(10, 0) { } #=> step can't be 0 (ArgumentError) a = []; a << a a.flatten #=> tried to flatten recursive array (ArgumentError) 確かにどれも Argument に関する Error ではあるんだけど *1 、全部同じ例外クラスというのは粗すぎですよね。メッセージ読めば意味はわかるからデバッグには困りませんが、ArgumentError の中の特定の例外だけ拾いたいときに困ります。 具体的には、テストです *2 。例えば foo(1, 2) で wrong number of arg
15quzzle.rb - まめめも
15 パズルを quine で作ってみました。 eval((%w[a=0;loop{a=(0..15).sort_by{rand};b=a.reverse;b=a[0,4]+b[8,4]+a [8,4]+b[0,4];n=0;16.times{|i|b[i]>0&&(0..i).map{|j|b[j]>b[i]&&n+=1}};n% 2>0&&break;};eval$s="b=0x#{a.map{|n|"%x"%n}.join}"+%w[;i=(m=0..15).find {|i|1>b&m=15<<4*i};t=m|n=m<<4*o=("AdABrBlBAuA"=~/(.)#{ARGV*''}\1/||04|| 0)-4;( n<1 ||n>1<<64||[255<<12]&[t>>040||0,t>>16, t]!=[])?t=0:i +=o;; ## s ####### ="eva
あけましておめでとうございます - まめめも
1 時間くらいで書いた年賀状。 require"zlib";r=Zlib::Inflate.inflate(%w(eJylk 1FywzAIRK+0CBWR6xRb9z9CF6Q4mU4+0kaZ2BjxDFrwOKE TMh3jxLU UEq/stQzi6Qd CoeLikdYz7 Q9bX9POm/CBo MEfAN2K92jviAaj40E j7Im2lzS9giz aLMunvzVMYHj RLKvzUdEDjb9xYxUu5 6bp1YtGJtAmB xWISsfqu9x4j YwznBNjuH77oqOzeMG mS/KTscJtzW1 1ChKa75c82kh X3uf0OpzGuNOlk2n JtOjhjLBFe9/ N4ZEWnTnY5U1 XV41Y0kK7d/ek61B +b+3Yqom3i to0rOjpOmf5r R8s8 lRLO i56bjqjskJ0o6RV
unicode の大文字小文字は大変だなあ - まめめも
ちょっと調べただけですが、面白かったのでメモ。世界は広いですね。バベルの塔ですね。 ß ドイツ語では、ß (U+00DF 、エスツェット) を大文字にすると SS になるらしい。 鬼車 (Ruby や PHP で使われている正規表現エンジン) はこれに対応していて、ignore case にすると、一文字が複数の文字にマッチして驚く。 # coding: UTF-8 p "-SS-"[/-\u00DF-/i] #=> "-SS-" p "-\u00DF-"[/-SS-/i] #=> "-\u00DF-" こういう関係の字は他にもあるみたい。 ref: ftp://ftp.unicode.org/Public/UNIDATA/SpecialCasing.txt İ と ı トルコ語やアゼルバイジャン語では i と I が別の字らしい。i の大文字は İ (U+0130 、点つきの I) で、
Ruby に callcc を公式にサポートさせよう - まめめも
Ruby の callcc というと、 現在の Ruby の Continuation は欠陥品で、まともに利用できないシロモノです。具体的には、dynamic-wind 相当の機能がありません。 (略) ちなみに、dynamic-wind 相当の機能を入れるのは、拡張ライブラリを全部 callcc safe にする作業に相当しますので、現実的じゃないんじゃないかなぁ、と思っています。 ruby-dev:30988 という話があって、「そっかー欠陥品なのかー」「直すのも難しいのかー」と悲しんでいました。 が、dynamic-wind を実装するだけなら広範囲の修正は不要なことに気がつきました。つまり直すのは簡単。というエントリ。 その前に: dynamic-wind とは dynamic-wind とは、継続呼び出しで指定した範囲に突入したり脱出したりするときに起動するハンドラを設定する関
Seven Trees - まめめも
id:bonotake さんに教えてもらった問題。すごく面白い。 ref: http://d.hatena.ne.jp/m-hiyama/20081022/1224640248 この問題を Haskell で言うと、 data Tree = Leaf | Node Tree Tree deriving Eq type Tree7 = (Tree, Tree, Tree, Tree, Tree, Tree, Tree) で定義される普通の二分木と、二分木の 7 つ組を考える。このとき f :: Tree7 -> Tree g :: Tree -> Tree7 の型になる 2 つの関数 f と g を定義せよ。ただし以下の 3 つの条件が満たされるものとする。 Tree 型の任意の値 x に対して x == f (g x) Tree7 型の任意の値 x に対して x == g (f x) f
スタックオーバーフローの仕様の続き - まめめも
いろいろコメントをいただきました。ありがとうございます。 問題点を整理すると、 1. 「無限に再帰呼び出しをする」という意味は、リソースが有限な現実のコンピュータでは実現不可能である (末尾再帰だけとか特殊な例はできるけど、一般的には無理だと思う) 。 2. C 言語の規格を流し読みする限り、くだんのプログラムは「無限に再帰呼び出しをする」という意味になりそう。そうならない理由が見つからない。 3. 1 と 2 より、現実のコンピュータで C 言語の規格に完全に準拠することは不可能である。 で、それはなんか変な気がしたので、2 が間違ってるかと思って聞いてみたのでした。 具体的に何を心配しているかというと、例えば、ものすごくスタックが短くて main 関数の呼び出しすら失敗するような環境 *1 でも、「C 言語の規格に準拠しています」と言っていいんでしょうか。別にいいのか。 ちなみにこの問
brainfuck interpreter in Coq - まめめも
Haskell 、Erlang の次のブームは Coq に違いありません。とりあえず基本ということで、Coq でひねりのない brainfuck インタプリタを書いてみました。動作例。Coq のコードが色づけできないとは何事か。 Eval compute in (finite_execute " +++++++++[>++++++++>+++++++++++>+++++<<< -]>.>++.+++++++..+++.>-.------------.<++ ++++++.--------.+++.------.--------.>+. " "" 500). = "Hello, world!"%string : string 残念ながら (?) Coq では停止性が保障された関数しか定義できません。ここでは最大評価ステップを指定しないといけないという仕様にしてごまかしています (引数の 50
Grass で quine - まめめも
この記事は Quine Advent Calender 2014 の 102 日目になりました。ref: http://d.hatena.ne.jp/shinichiro_h/20080910#1220988953 やろうやろうと思って放置してたら先にやられてしまったー。一念発起して完成させて、がんばって縮めて見ました。 $ time ruby grass.rb quine.www > quine2.www real 0m21.830s user 0m20.440s sys 0m1.390s $ diff quine.www quine2.www $ wc -c quine.www 9787 quine.wwwでも試しに golf 鯖に投稿してみたら、over 10K って言われた。なぜー。 あとは菊さんの 100B が楽しみですね。 以下どーんとソース。 どーん。 wWwwwwWWWwv
カッコとキーボード - まめめも
多くのプログラミング言語ではカッコが重要な意味を持ちますが、ASCII で書けるカッコは 丸カッコ '(' ')' カギカッコ '[' ']' 中カッコ '{' '}' 大なり小なり '<' '>' しかありません。 特にこの中で、シフトキーを押さずに打てるカッコはカギカッコだけです。純粋な打鍵数で見ると、カギカッコ以外は実は 2 ストロークなわけです。つまりカギカッコは「打ちやすいカッコ」という意味でとても貴重です。 それにもかかわらず C 言語では、貴重な貴重なカギカッコを配列のインデックスというしょうもないところにしか使ってません。もったいない。 一方 Ruby はカギカッコがメソッド呼び出しで使え、Proc#[ ] や Struct#[ ] などがあってすばらしい。 というネタをたまに考える。Ruby 書いてるとなぜか「class 定義したら負け」という気分になるけど、最近は「メソ
braingrass - まめめも
brainfuck から Grass への変換器を書いてみました。brainfuck はできるけど、Grass はちょっと……という人向け。 # brainfuck のプログラム $ cat hello.bf +++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-. ------------.<++++++++.--------.+++.------.--------.>+. # grass のプログラムに変換 $ ruby19 braingrass.rb hello.bf > hello.www # 実行 $ ruby19 yagi.rb hello.www; echo Hello, world!ソースはこちら。 http://github.com/mame/grass-misc/tree/master/braing
関数ポインタのキャストと gcc - まめめも
C の関数呼び出しは、関数定義の型と互換性のない型として呼び出したら未定義動作です。例えば以下のコードの動作は未定義です。 #include <stdio.h> int main(void) { ((int (*)(char *, ...)) &printf)("Hello, world!\n"); } printf は int printf(const char *, ...) なので、const が無くなってるのが間違ってます。未定義のプログラムはどのような実行結果になろうとも、C の規格には違反しません。 でも、現実問題としてこのコードは期待通りに動くだろー、と高をくくってました。しかし最近の gcc (3.4 以降くらい) では、このコードは落ちます。 $ gcc --version gcc (GCC) 4.3.1 Copyright (C) 2008 Free Software
Grass 処理系 - まめめも
プログラミング言語 Grass の Ruby 1.9 による処理系です。 # parse A, L = Struct.new(:m, :n), Struct.new(:code) code = File.read(ARGV[0]) code = code.gsub("\uFF37", "W").gsub("\uFF57", "w").gsub("\uFF56", "v") code = code.gsub(/[^wWv]/, "") code = code[/w.*\z/m].split(/v/).map do |sub| sub = sub.scan(/w+|W+/) arity = sub.first[0] == "w" ? sub.shift.size : 0 sub = sub.each_slice(2).map {|n, m| A[n.size - 1, m.size - 1]
coverity やばい - まめめも
PPL サマースクール 2008が告知されています。内容はおおいわさんのFail-Safe Cと、coverity 社の人による Thread Analyzer for Java とかいうツールの紹介だそうです。 それとは関係ないんですが、coverity 社がやってる Coverity Scan というサービスがあります。coverity 社の製品の Prevent という静的解析ツールのデモみたいなもので、Apache とか OpenSSL とかのオープンソースプロジェクトに対して Prevent で検査した結果を無償提供してくれています (参考) 。ただし脆弱性のヒントになる可能性があるので、各プロジェクトの開発者のみに公開。 ここぞとばかり Ruby のコミッタ権限を活用して Ruby の結果を見せてもらったんですが、これ、かなりすごいです。 鬼車が /x{1,1}/ でメモリリー
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
