円周率おぼえ歌 in Ruby - d.y.d.
21:26 15/12/11 円周率おぼえ歌 in Ruby 円周率 π = 3.14159265... を語呂合わせで 「産医師異国に向こう…」 として覚えるみたいなのありますよね。 英語では Piphilology と言って、たとえば、こんなの。 How I wish I could recollect pi easily today... 長さ 3 の単語 (How)、長さ 1 の単語 (I)、長さ 4 の単語 (wish)、… という列で数字の列を覚えたりするそうです。 この方式だとゼロの桁の表現に困りそうですが、ゼロの所には巧みに句読点などの記号を配したり、 あるいはもう少し単純に、長さ 10 の単語を当てて表すのだそうな。 と、いうわけで。 in Ruby 長さ 3 のトークン、長さ 1 のトークン、長さ 4 のトークン、 長さ 5 のトークン、長さ 9 のトークン、長さ 2
d.y.d. - シミュレーション問題について
20:43 13/12/31 本 今年読んで面白かった本ベスト20。 自分が今年読んだ基準なので遙か昔に出版された本も多数含みます。 しかもジャンル分けもせず適当に混ざっています。 ここ数年読書メーターでまとめてたんですけど今年ないみたいだし、 本棚機能もログインしていないと見られないようになってしまったみたいだし、 こちらで。 カクリヨの短い歌 和歌を詠むとその歌に応じた異能が発動するという能力バトルもの…というと情緒が飛んでしまいますかね。 読み終わったときはそうでもなかったのだけど、後からじわじわ来て、気づいたらこの話のことばかり考えるようになっていました。なんというか、歌を、この歌に込められた思いはこう…等々ロジカルな解題として語ってしまうのは勿体ないと思うんですよ。たとえば一面の桜吹雪、たとえば夜咲く紫陽花の花、その景色をただ再現するだけ、その具象が聴き手に何かを感じさせたならそ
ICFPコンテストでした - d.y.d.
17:55 13/08/12 ICFPコンテストでした ICFP プログラミングコンテスト が終わりました。 今年は @nya3jp @phoenixstarhiro @dmikurube @kinaba の 4 人チームで参戦していました。 C++ で計算バックエンド、 Python でサーバーとのやりとりと計算モジュールをつないで答えを送りまくる最上位のロジックとフロントエンド、 という構成でした。 簡単なまとめ 今年の問題は、 『サーバーに1400個くらいプログラムが置いてあります。 プログラムは 64bit 整数を 1 個受け取って、 何か計算して 64bit 整数を 1 個返す関数です。 サーバーは、プログラムの番号と引数を指定すると実行して結果を返してくれます。 どういうプログラムが置いてあるのか、できるだけ沢山当ててみなさい！』 という問題。 当てた個数が多ければ多いほど好ス
クイックソート殺し - d.y.d.
19:39 12/09/01 クイックソート殺し こういう系統の話。 Quicksort Killer (kazoo04さん) qsortを撃墜し(最悪ケースを与え)てみた。 (qnighyさん) A Killer Adversary for Quicksort (shinhさんの解説) Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 (徳丸さんの解説) ただのクイックソートは要素数 N の配列をソートするのに最悪 N2 オーダの時間がかかってしまう、 そしてそれは pivot を偏って選びまくってしまった時に発生する、というのはよく知られた話だと思います。 といっても、広く使われている言語／ライブラリのソート関数はその辺り気をつけられていて、最悪時も O(N log N) になるアルゴリズムで実装されている…と思い込んでいたのですが（例えば C++ の
d.y.d.
23:04 12/07/16 ICFP Contest 2012 この連休は、毎年恒例 ICFP Programming Contest に出ていました。 ソースコード置き場。 今回のお題は Boulder Dash っぽいゲームのAI書けというものでした。ただしダイヤモンドではなく「λ」を回収します。 見た瞬間に、えっ無理だろそんなの、と思って思わず旅に出たくなってしまったりしていましたが、 やってみるとそれなりに手はあって、結局３日間ちまちまと改善を続けていました。 と言っても結局パッと思いつくことしかできていない…。 基本的に貪欲アルゴリズム。（幅優先探索で）一番近いλに向かって直行、を繰り返す。 ただし岩の下にあるものを取ると盤面を崩壊させる恐れがあるので、そこだけ微妙に距離をおく たどり着けるλも出口もなくなったら、土をどけたり岩を押したり色々してみる。 が基本方針で、ただしこれ
ICFPC 2011 - d.y.d.
22:15 11/06/27 ICFPC 2011 ここ 8 年くらいほぼ毎年参加していた ICFP Programming Contest ですが、今年は出題者側に回ってみました。 問題の原型決定の議論、画像に変なネタを仕込む、Windows版バイナリのビルドをする、対戦サーバの中身を突貫でどうにかする、 などなどをしていました。 ゲームのバランス調整が非常によくできていたとの評価を頂いているのですが、 肝心のその辺りは、出題チーム内の熟練者達の高度な議論に既についていけなくなっており、 私は全然貢献できていないという…。 詳しいことは 9 月の ICFP で発表があると思いますので、ここでは今年のテーマの紹介だけ。 公式の問題文はこちら です。 一言でいうと、関数を呪文に変えて撃ち合う、プログラミング魔法バトル。 Lambda: the Gathering L:tG という２人対戦ゲー
正規表現しちへんげ！ 第二夜
09:25 10/12/31 年末まとめ 今年何やったっけ、と日記を読み返していました。何もやってないな…。 Polemy 作りました、くらい。 言語処理系作るのはやっぱり楽しいですね。 汎用言語として使う本格的なものを作ろうとすると懲りすぎて一歩も進まなくなってしまう自分が見えるので、 来年は、そうだなあ、TopCoder/ICPC風コンテストに特化した言語というかC++へのトランスレータ、 くらいに絞って作ってみようかなあ。 書いた記事だと 最短性チェックの話 が自分では割と気に入っています。 これのもっとバグを許容するバージョン作れないか。 読んだ論文で面白かったのは "A Pearl on SAT Solving in Prolog" と "When Simulation Meets Antichains" (PDF) など。 あとは、今年読んで面白かった本ベスト５（順不同）： 『
階乗を求める - d.y.d.
22:56 10/09/04 階乗を求める 去年聞いた中で、私が一番感動した式の話。 k! = limn→∞ nk / nCk kの階乗は、「nのk乗 ÷ n個のものからk個選ぶ組み合わせの数」という式で n を無限に大きくしていったときの収束先、である。 特に難しい証明が要るとかではなくて、nCk = n(n-1)(n-2)...(n-k+1) / k! であることを使うと、 limn→∞ nk / nCk = limn→∞ nk k! / n(n-1)(n-2)...(n-k+1) で、n が k に比べて十分大きければ n も n-k+1 もほとんど同じ値なので、 分子も分母もだいたい n を k 個かけているわけでして、 その部分が相殺して、k! が残るという寸法。 （厳密な表現ではないので、気になる人は厳密に証明してください。） 実装 と、この式自体はそんなに不思議ではないのです
行列と項書換 - d.y.d.
21:54 10/06/30 行列と項書換 "Termination of String Rewriting with Matrix Interpretations" という論文を読みました。 これは何かというとつまり、 ICFPコンテストの元ネタとして 紹介 されていた論文です。 れ い 年、 冗談９割で、主催者の専門分野にちなんだ問題が出るに違いない！と叫んでいるのですが、 本当に来るとは思わなかった…。 さて。項書き換え (term rewriting) と呼ばれる研究分野がありまして、 例えばこんな問題を調べています。 文字列に対して、「以下の操作のどれかを好きに選ぶ ＆ 実行する」を繰り返します。 abc という部分文字列を de に書き換える （abc ⇒ de と書きます） ef ⇒ g fgh ⇒ ij どんな文字列からスタートしても、最後には、どの規則も使えない状態 （つ
Here a Const, There a Const - プログラミング言語 D 2.0
Here A Const, There A Const by Walter Bright ちょっとしたプログラムを書くなら、柔軟で寛大で、 そんなに杓子定規でないようなプログラミングシステムが便利です。 しかしプログラムの複雑さが増すにつれて、 コード中の宣言の意味をコードそのものできっちり記述することに利点が出てきます。 プログラマは、巨大なアプリケーションを部分部分に区切って、 特定の状態変化の影響を狭い範囲に限ることができるようにすべきです。 そうすることで、遠く離れた位置にあるコードが同じデータを書き換えるという結合を避けることができます。 コードではなくドキュメントに書くという方法ではどうしても、間違った、ミスリーディングな、 不完全で古い、そもそも記述されないドキュメントしか残らない危険があります。 このような場面が、"const性" の重要な使い道です。 C や C++ には
アルゴリズムコンテストの挑み方 (3) - d.y.d.
17:19 08/11/27 TopCoder Code Jam の練習に……と思ってしばらく前から TopCoder のSRMに参加してたのですが、 せっかくなので cafelier@SRM に記録をつけることにしました。 どういう試行錯誤をしながら提出した時のコードにいたったのかを、 できるだけ詳細にメモろうと思っています。 426以前のは記憶から掘り起こして書いたのでちょい大ざっぱですが。 これまで何回かここで書いたような整然とした考え方を本当に自分がしているかいうと、 してないよなー、と薄々思ってしまっているので、じゃあどういう風にやっているんだろうかと。 自分のふり見て我がふり直す。 20:26 08/11/24 論文 PLAN-X 2009 通ったみたいです。ばんざい。 ただでさえD論まったく間に合う気がしないのに、camera ready版なんて作ってる時間が… オートマトン
アルゴリズムコンテストの挑み方 (2) - d.y.d.
21:25 08/10/27 論文 の締め切り終わったら頑張った自分へのご褒美（笑）であれとこれとそれをやる時間をとるぞー！ ……みたいなことを思っていたはずなのに、いざ提出し終わると気が抜けて何一つやる気がでない問題。 困った困った。 ナイチル たくさん人がいらしてる今のうちに 「ナイトメア☆チルドレン」新装版 面白いよみんな買おうぜ！ などと書いてみる。 自分のマンガの趣味はわりと平凡だと思ってて、 流行ってるマンガは大抵好きだし自分の好きなのはだいたい流行ってるし。 なのになぜだか藤野もやむ作品だけは唯一の例外で、とっても不思議でならない。 100回くらいアニメ化されてて然るべきだと思う。 何回か書いてますがとにかく最終話が好きで、 そこまでのシナリオが一気に集まって一つ一つのセリフが３倍の重みを持つように収斂していく幕引き。 あれは良い。 17:12 08/10/24 アルゴリズム
ICFP プログラミングコンテスト - d.y.d.
19:01 09/06/30 ICFPCまとめ やったことをまとめておきます。 まあ問題の意図を盛大に勘違いして別のゲームを遊んでいた （与えられたシナリオファイルを最適に解くだけじゃなくて、 もっとジェネラルな自動ソルバを作らなければいけなかったらしいorz） のでスコアは問題外な感じですが、 面白かったのでよしとしよう。 今回は、地球の周りを飛んでる人工衛星に命令を送って他の人工衛星やデブリと接触できたらスコア＋＋、 という、(仮想の)人工衛星制御プログラムを作るコンテストでした。 → shinhさん にならって自前ビジュアライザを 動画にするとこんな感じ。 2003年 や 2008年 の問題に結構近いものがありますが、 今回はとにかく、燃料の許す限り速度変化 ΔV を自由に与えられるという仕様が （自動でやるにしろ手動でやるにしろ） 素晴らしかった。 例えば「隣を飛んでる別の衛星と同
d.y.d.
23:11 07/08/29 アスカ見参 定期的に俺内アスカブームがやって来ます。さっきやっと一致団結クリアー！あと残るは万歩だけ。 いわゆる"もっと不思議"を仲間４人引き連れて降りるダンジョンで、ただし１人でもやられるとゲームオーバー。 ５人で戦力５倍！とはならずに、むしろ５人な分危険が５倍という全然一致団結してないっぷりが 素晴らしい感じです。攻略サイトであまり強調されていない気がするのですけど、[不]印 が便利すぎた。 バネと虎と龍を完封できるのは強い。便利度は 水がめ ＞ [識] ＞ [不] ＞＞＞＞＞越えられない壁＞＞＞＞＞ [仏] ＞ [祭] ＞ 遠投、くらいじゃなかろうか。 23:48 07/08/23 ラーミア "Decisions Volta Masters Remix" って曲を教えてもらって聴きまくっている今日この頃です。 Twin Primes Twin Prime
d.y.d. DanoMoi と Haskell
17:24 06/09/27 XP theme 昨日 OSXP というビジュアルスタイルを知りました。 完全にMacOS化してない辺りがかなり好みです。しばらく使ってみよう。 ただ日本語のせいかスタートメニュー周りがずれるので、TClockで調整したりユーザーの 表示名をスタイルに合わせて変えたりと適当に酷い合わせ方をしてます。 マジメに直そうよ＞自分。 LCSD LCSD '06 (Library-Centric Software Design) のプログラムが出てました。 "ライブラリ" そのものを対象にしてその設計や実装について議論する学会…ということで 特に言語について限定されてはいません。が、実際中身を覗いてみると、 基調講演や Program commitee の面々の名前を見る人が見ればすぐわかるように、 えらく濃いC++使いが集結する感じの学会です。 （や、必ずしも皆が皆C
アルゴリズムコンテストの挑み方 - d.y.d.
17:29 08/09/30 クロスワード 暇つぶしに "Clueless Crossword" という冊子を買ってみて意外とハマっています。 クロスワードパズルなんだけど、単語のヒントの代わりに、 各マスに1～26の数字が振ってあって同じ数字のマスには同じA～Zが入るように埋めるというもの。 「母音っぽくて二連続して語尾にも出てくるのは多分 E だろう、もしかしたら O の可能性はなくもないけど」 みたいに埋めていく。 ちょっと違うけど フラッシュであった。 20:15 08/09/28 だいちのよろい そろそろ日本に戻る前に観光するぞ月間、ということにして、ウルル（エアーズロック）に行ってきました。 もっとワイルドな感じかと思ったら、完全にリゾートのリゾートによるリゾートのための地帯になってました。 まあそんなもんか。 本日は強風のため登るの禁止とのことだったので、周りから見るだけ。
d.y.d.構文解析の話をしよう
16:46 08/03/30 YZ1.DLL 0.30 リリース しました。 具体的には、ヘッダの格納ファイル数フィールドに実際より大きい値が入ってると変なとこ読もうとして落ちるバグ修正。 GreenPad の修正は来週くらいには…。 Booooooost Boost 1.35.0 来てました。 Asio と Fusion と GIL の三枚看板がでかいですが、Bimap が地味に便利だ。 あと、mbさんのEgg のレビューが明日からでしょうか。（また スケジュール から消えてますが…Protoが入る前までロールバックしてる？） 他人事ながらドキドキ。 17:36 08/03/28 ケース 十年来の疑問なんですが、"case" に単独で対応する日本語ってなんになるんですかね。 "case-insensitive" や "lowercase" の "case"。単に "case-insens
d.y.d. 正規表現にマッチする例をランダム生成
15:43 07/05/17 正規表現にマッチする例 soutaroさんの 正規表現にマッチする例をランダム生成 する話を見てたら、 自分でも書きたくなってきました。というわけでソース。 正規表現を構文解析してオートマトンに コンパイルしてから、その上を似非ランダムウォークしてます。対応してる正規表現は ?と+と*と|と.と[…]だけです。[…]の中の-とか^とかにも反応しません。あと IE と Rhino でしかチェックしてないので他の環境で動かなかったらゴメンナサイ。 きっともっとマトモなのをsoutaroさんが公開されるはずです。 ボタンを押したらこの上↑に10個例が生成されるはず。 で、動かしてみて思ったのは、当たり前だけど繰り返しが長続きしないなー、と。 確かに、ループをちゃんと意識しないと面白い結果にならないかもしれないですね。 なるほど。 追記12:15 07/05/18 ぎ
λx.(x+1) - d.y.d.
19:52 06/03/30 反応とか Schemeのマクロは 自分も好きなので、人間コンパイラコンパイラ的に楽しいっていうのは同意です。 ただ、マクロはともかく言語自体が、「なんでもS式」と「型宣言がない」のコンボのおかげな 気がするのですが、Schemeで書いてるとどうもコードが10KB越える辺りで自分の頭の把握能力が 追っつかなくなってしまうもので、最近は敬遠してました。 これは経験と修行でなんとかなるような気がするのでなんとかしたいなーと思い中です。 頑張るます。 テンプレートの型検査は、最低限、実行される可能性のあるinstanceにはコンパイル時にC++の型検査が入るので、 まあなんとか…。そもそもマクロやアセンブリではせいぜいパラメタ多相もどき までしかできなくて別の意味で困るような。module typeもどきになるとPOPL06のアレや例によってそのテンプレートでの実現（
d.y.d. 文字コード＆ベイズ推定
12:21 06/05/28 うたひめ 先日の記事に書いたように KOKIA にハマりまして、 とりあえず片っ端から聴いてみることにしました。まずは 1st アルバムの 『songbird』 から … …４曲目の "白い雪" ヤバい。超ヤバい。なんだこれ。ツボすぎる。 ベスト盤を聴いたとき感じた揺らぎなく落ち着いた歌唱力的な曲を期待して聴きはじめたら、 予想外の声質の歌が飛び込んできてびっくりしました。もちろん抜群に巧いのに かわりはないんですが、ずっと儚げな、ガラス細工みたいなイメージの、ああ、その、 つまり白い雪みたいな雰囲気の綺麗な声で。その声と奇跡的にマッチしたメロディ。 すごいなあ。９曲目の "ありがとう…" もベスト盤でのリテイクと比べて同じ印象で、 Amazonのreview で TenderBerry さんという方が近いことを書いておられました。 しかし書いてて自分の語彙の
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
