2012/09/06にくいなちゃんさん主催で開催された6さいカンファレンスのまとめ。 第3回は「アルゴリズムを自力で生み出すプログラムを作ろう！」です。 勝手にまとめてしまったので、何か問題があれば@shogo82148まで。 WELCOME TO HEAVEN!! くいなちゃん: ところでみなさん、次の( ) に入る数を当ててください 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ( ) くいなちゃん: はい、正解です！ これは、フィボナッチ数列と呼ばれ、 前の2つの値の和が、次の値になっているという数列です くいなちゃん: これを、f(0) = 0, f(1) = 1, f(2) = 1, f(3) = 2, f(4) = 3, f(5) = 5, … と書いていくことにしましょう。　f(10) = 55　ですね！ くいなちゃん: もっと汎用的に考えて、f(x) の x を与えると、フィボナッチ数が返ってくることを考えましょう。 x = 10 のとき、f(x) が 55 になる、といった感じです くいなちゃん: ではみなさん、この f(x) を、プログラムで書くことはできますでしょうか。 言語は何でも構いません。 くいなちゃん: やり方は、いくつかあります。 x = 100 と与えられれば、0, 1, 1, 2, 3, 5, …　と 約100回繰り返して、x = 100 の値を求めるというものです。

昨日，Twitterで猫型さんのアイコンのテンションが上がっている話をしていたら， こんな無茶ぶりをされたんですよ． 明日には、いっちーがWebRTCでリアルタイムテンション上がってきたサービス作ってくれるだろうし、猫型さんがアプリの申請出してるだろう — Takashi Sasakiさん (@civic) 10月 2, 2012 いいだろう，その挑戦受けてやる！ WebRTCって？ WebRTCというのはブラウザ上で Real Time Communication を行うAPI群のことことです． ローカルデバイス(Webカメラとかマイクとか)へのアクセス ブラウザ同士が(サーバを介さずに)直接通信 なんてことができるようになるらしいです． つまり WebRTCを使えば Skype っぽいものをプラグインのインストールなしにブラウザ上で実現できるってわけですね． Chrome の最新安定版で、ウェブの最先端に触れてみようから いろいろなWebRTCを使ったデモを見ることができます． 僕も似顔絵描いてもらったりしてみました． getUserMedia API を使ってみる まだまだ仕様策定中で対応ブラウザがほとんどない状況ですが， 2012年10月現在，最新版の Chrome 21 で前者のローカルデバイスへアクセスするAPIである getUserMedia API が使えるようです． 早速遊んでみましょう． navigator.getUserMedia( {video: true}, // constrains: 接続先のデバイス function successCallback(stream) { // アクセス成功 // stream に LocalMediaStream オブジェクトが入ってる // <video id="video"></video> 要素を取ってくる var video = document.getElementById('video'); // BlobURLに変換してsrcに入れる video.src = URL.createObjectURL(stream); // 再生 video.

2012/09/13にくいなちゃんさん主催で開催された6さいカンファレンスのまとめ。 第2回は「数学の定理を自動で発見するAI を Haskellで作ろう！」です。 勝手にまとめてしまったので、何か問題があれば@shogo82148まで。 WELCOME TO HELL!! くいなちゃん: それでは、まず、数学の「定理」とは何か、について説明したいと思います。 みなさん、日常的に「定理」という言葉を使っていると思いますが、「定理」とは何か、説明できますか くいなちゃん: 「教科書に載っている公式が、定理だ！」と思うかもしれませんね。 確かに、教科書にも定理は載っています。 くいなちゃん: では、曖昧な理解の方のために、厳密かつ ゆるふわに説明しましょう。 くいなちゃん: 定理とは、次のように定義できます。 公理であるならば、定理である。 定理を推論規則によって推論したものは、定理である。 以上。 くいなちゃん: はい、みなさんこれで定理が何かを理解したと思いますので、数学の定理を自動で発見するAIを作ろうと思います。 くいなちゃん: Haskellで。 Haskell! くいなちゃん: そもそも、Haskellって何？ という方もおられるかと思いますので、まずは Haskell について簡単に説明しておきたいと思います。 くいなちゃん: Haskell は、関数型言語です。 宣言的プログラミングによって、プログラムしていくプログラミング言語です。「○○は××である！」というのを繰り返してプログラミングする感じですね。　「まずは○○して、次に××しろ！」という C言語(手続き型言語)とはかなり異なります。 くいなちゃん: では具体的に、今回定理を発見するための数学の体系を説明しながら、同時に Haskell で実装してみることにしましょう。 くいなちゃん: 最終的には 大規模な数学体系の定理を発見するとしても、まずは試しに小さな体系で定理を発見してみることを考えます。 今回は、命題論理を対象としてみます。 定義 くいなちゃん: では、今回対象とする命題論理を、厳密に定義していきましょう。 まず、この体系で用いられる記号は、P　Q　R　￢　⇒　の5種類です。 この5種類をうまく並べると、この数学体系でのあらゆる式や命題が記述できます。 くいなちゃん: まあ、たとえば、　P⇒P　(PならばPである)　といった感じですん。 わかりますね。 くいなちゃん: ￢　は数学における否定によく使われる記号ですが、いまのところ、単なる記号にすぎず、意味は定義されていません くいなちゃん: ちなみに、くいなちゃんはポーランド記法が好きなので、　P⇒P　を、　⇒PP　と書くことにしましょう

だいぶ時間がたってしまったけど、2012/09/06にくいなちゃんさん主催で開催された6さいカンファレンスのまとめ。 第1回は「C言語で作る、はじめてのDAWソフト制作」です。 勝手にまとめてしまったので、何か問題があれば@shogo82148まで。 BATTLE START!! くいなちゃん: みなさんは、既にC言語の基本的なところはマスターしていると思いますが、念のために軽く復習しておきましょう。　まずは、このソースコードをご覧ください。 http://kuina.tes.so/6saiconf/a.png(魚拓) #include <stdio.h> #include <math.h> int main(void) { return 0; } くいなちゃん: 右下の100% は気にしなくてOKです。　このプログラムは、「何もせず終了するだけ」のプログラムとなっています。　ソースコードを順に解説しましょう。 くいなちゃん: まず、1行目と2行目に書かれている #include ですが、これはおまじないです。　プログラムの本質は、4行目からとなります。 くいなちゃん: int main(void) { } が、プログラムの本質となります。　コンピュータがこのプログラムを起動すると、int main(void) { } の { と } に囲まれた部分を上から順に実行していきます。 } に辿り着いたら終了です。 くいなちゃん: よって、このプログラムは、 return 0; を実行するだけのプログラムとなります。　return 0; とは、おまじないです。　えへへ☆ DAWを作ってみる くいなちゃん: はい、もう、C言語の基本的なところは全てマスターできましたね。　では、早速 DAWソフトを作ってみましょう。 くいなちゃん: DAWとは、簡単にいいますと、曲を作るソフトです。　それでは、int main(void) { } の中に、DAWっぽいプログラムを書いていきましょう。　とりあえず、int i, j; を書きます。

先週土曜日は第28回NDS(長岡技術者勉強会)でした。 スーツ vs ギーク Togetterのまとめを見ながら、内容を頑張って思い出してみる。 (せっかくローカルでブログ書ける環境作ったんだから、ちゃんとメモっとくべきですね・・・と思いつつ毎回できない) プログラマは誰でもいい？ 人に依存しないことはいいこと でも、本当にそれでいいの？ 能力があれば誰もいいのかも 社長の方が誰でもいい (自称)ギークなスーツ 「これからはHadoopらしいよ」 ギークにもユーザの対応して欲しい 「技術的な制限で無理」なことを説明するときとか 浅い知識だけでは矛盾点を突かれて、Yesと言わざる負えない時も 「ときどき行く→ギーク行くといいじゃんってなる→ときどきが毎回になる」と困るよね 判断を全部ギークに丸投げしないで！ 例えば、初期コストを取るか、拡張性を取るか、とか 技術的な利点・欠点は説明するけど、実際どっち使うかの判断はスーツな人にお願いしたい スーツを手玉に取るコミュ力 コミュ力の低いギークは技術力を生かせなくてもったいない！ ギークもコミュ力を身につけるべき 名選手と名監督は両立しない 技術者からの叩き上げでマネージメントする側になった人は他人を上手く使えない マネージメント系は手足のように他人を使えなければならない 社会は怖いところです。 通常セッション マッチョ見積もり by @hiro55bsさん 「つまり、見積りは予想ではなく、帳尻をあわせるものなんだよ！」 見積もりはリスク管理、プロジェクト初期だけでなく随時やっていくもの プロジェクト初期では見積もりに幅があって当然 もる いろんな統計データからざっくり見積もれるんですね。勉強になります。 ワンライナーでノイズミュージック by @neko_gata_sさん Experimental music from very short C programsに触発されたというお話 RIFFヘッダつけるとこは Perl でやってます！ 波といえば正弦波の組み合わせで・・・と思っていたので、ビット演算で音を出してみるというのはおもしろいです。ぜひやってみたいです。 LT SIの現場から感じた未来 by @nemuzukaさん 現在の契約形態に対する問題提起 皆さんで考えて行きましょう RubyMotionでiOSゲームを作るっきゃない by @jewel_x12さん Pythonが主人公のゲーム Android版はまだですか？ Echigo Network Operators’ Group について by @yyasuyukiさん コイントスで決めよう お姉さんのコンピュータを高速化したお話 補足とか スライド上げようと思ったんですけど、よく考えたら半分他人さまの画像使ってるのであまりよろしくないですね。 検索アルゴリズムの紹介などは「おねえさんのコンピュータを作ってみた」を ご覧ください。

まだやってたのか、と言われてしまいそうですが、おねえさんが計算にかけた時間と比べればまだまだです。 『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！ この動画で出てくるおねえさんのコンピュータを作ってみた、というお話。 おねえさんのコンピュータからアクセスできます。 検索アルゴリズム HTML+CSSでコンピュータの画面を再現してみました。Javascriptを組むより、そっちの方に時間がかかった気がする。 経路の描画にはCanvasを使ってます。 この問題は自己回避歩行(Self-avoiding walk)と呼ばれるものらしいです。 単にグラフ上を移動するだけなので、小さいなサイズなら単純な深さ優先検索(DFS)で解けます(大きなサイズで何が起こるのか・・・それは動画で)。 実装では、DFSによる検索プログラムをWeb Workerを使って走らせ、スタートとゴールを結ぶ経路を見つけたらメッセージを飛ばしてます。 さすがに全部は表示できないので、実際に表示するのは50ms秒程度の間隔。 4×4以下ではそれだと速すぎて何が何だかわからないので、待ち時間を入れてある。 さあ、君も10×10にチャレンジだ！！ おねえさんに教えて上げよう！ しかしながらDFSだけだとなんだか負けた気がして悔しいので、高速化したアルゴリズムも試してみた。 「おねえさんに教えてあげる」のチェックボックスにチェックを入れると高速化したアルゴリズムで問題を解きます。 ゼロサプレス型二分決定グラフ 自分が色々試行錯誤している間に他の人が解いてしまった(「フカシギの数え方」の問題を解いてみた) ので、それを参考に実装してみた。 今回の問題は「グラフ上の経路問題」ですが、どの枝を通ってどの枝を通らないかという「枝の選択問題」として考えることができます。 その組み合わせを効率良く表すための方法が、ゼロサプレス型二分決定グラフ(ZDD; Zero-Suppressed Binary Decision Diagram)。 ZDDは数学の組み合わせでよく使う樹形図の一種で、 同じ結果になる枝を集めることで樹形図を効率良く表したものです。 概要はBDD/ZDDを基盤とする離散構造と処理演算系の最近の展望 を参照。 もっと詳しい説明はThe Art of Computer Programmingに書いてあるらしい(まだ読んでない)。 ZDDを考えた湊先生は最初の動画の企画・監修も努めている方なので、 動画中の数値もZDDを使って求めたものと思われます。 Simpath ZDDは単なる組み合わせの表現方法なので、別途グラフからZDDを求める手法が必要になります。 これに関する簡単な解説がZDDを用いたパスの列挙と索引生成 から見られます。 上のセミナー資料ではZDDの基本演算を使った列挙の方法が紹介されているけど、 今回はクヌース先生のSimpathを採用。 Simpathでは(既約でない)ZDDを作ることができます。 経路の両端にのみ着目し、この情報をmateという配列で管理。 frontierと呼ばれる頂点のmateを用いてZDD上のノードを共有することで簡略化を行います。 実際使ったアルゴリズム セミナー資料では幅優先でノードを作ってみるように見えるけど、今回の実装では深さ優先で経路数だけカウント。 ZDDのノードを作るのが面倒だったんです。 しかし、覚えなければならないmateが大量になってしまいメモリがああああ！！ すべて覚えるのは諦め、一部のmateだけ覚えるようにしました。 「おねえさんに教えてあげる」のチェックを入れると、適当実装のSimpathで計算します。 計算中一部の枝が灰色になるのは、ZDD上でノードの共有化が行われたため、実際には枝が処理されなかったためです。 格子上の点に丸がついているのはfrontier。 この点の継続情報を用いて共有化を行います。 まとめ おねえさんのコンピュータの実装と高速化を行いました。 高速化の結果、処理に数分かかっていた6×6の計算が200msで終わるようになりました。 10×10も1分程度で終わります。 ただ、表示のためのオーバーヘッドがあるとはいえ、他の人と比べると少し遅いような。 なにか実装間違っているかも。 The Art of Computer Programmingを読んで勉強しないとかな。

Vagrant VagrantはコマンドラインからVirtualBoxを扱えるようにするツール。 仮想マシンの起動・再起動をコマンドライン上から行えるのはもちろん、Chefや Puppet と連携することで必要なソフトウェアのインストールを行なってくれます。 Vagrantを使うには仮想マシンのひな形であるBase Boxが必要です。 Vagrantbox.esにいろんなOSのBoxがあるけど、 インストールされているOSのバージョンが古かったり、タイムゾーンがUTCになっていたりして 不具合発生。 そこでBoxを自分で作ってみようと思い立ち、やってみたのでそのメモ。 作ったBoxは GitHub にあげておいたので使いたい方はどうぞ。 Ubuntu 12.04.2 Server + VirtualBox 4.2.10 で作ってあります。 vagrant box add myubuntu https://shogo82148.github.io/boxes/ubuntu-12.04.2-amd64.box VeeWee VeeWeeはBoxの作成を自動化してくれるツール。 OSのインストール、不要なパッケージの削除、Box化なんかを自動でやってくれるらしい。 VagrantとVeeWeeのインストール Rubyの実行環境とVirtualBoxのインストールを済ませたら、 gemを使ってVagrantとVeeWeeをインストール。 gem install vagrant gem install veewee 使ってみる vagrant basebox templates と打つとテンプレートの一覧が出てくる。 現時点でのUbuntu最新版であるUbuntu 12.04をテンプレートとして使ってみる。 vagrant basebox define myubuntu ubuntu-12.04-server-amd64 これでdefinitions/myubuntuの中に設定ファイルができる。 そのままだとisoのダウンロードで404が帰ってくるので設定ファイルを書き換え。 加えて日本語が使えるようにLocaleをja_JPに、タイムゾーンをAsia/Tokyoにしておく。 --- templates/ubuntu-12.04-server-amd64/definition.rb 2012-08-31 18:23:28.000000000 +0900 +++ definitions/myubuntu/definition.rb 2012-08-31 21:17:52.000000000 +0900 @@ -6,8 +6,8 @@ :hostiocache => 'off', :os_type_id => 'Ubuntu_64', :iso_file => "ubuntu-12.

Octopressでツイートを引用しようと思ったけど 使えそうなプラグインがなかったので作ってみた。 ツイートに限らずいろんなものを挿入できるよ！ OEmbed 調べてみるとツイートの表示はOEmbedというのを使うとできるらしい。 これはURLを埋め込み適した形に変換してくれるプロトコル。 ツイートのURLから引用のためのHTMLを作ったり、YouTubeのURLから動画再生用のHTMLを作ることができる。 せっかくだからOEmbedに対応してしまえばいろんなものを埋め込めて便利だよね！ってことでやってみた。 インストール ruby-oembedをインストール。 gem install ruby-oembed ruby-oembedは名前から想像できる通り、RubyでOEmbedプロトコルを扱うためのライブラリ。 Provider(OEmbedの提供者)を自分で追加したり、Discovery(HTMLドキュメントにProviderの情報を入れる)にも対応している。 しかし、プロキシ環境下で動かなかったり、文字コードのエラーを吐いて死んだりしたので、 フォークして改造版ruby-oembedを作った。 もしオリジナルで不具合が出るようなら、こちらもどうぞ。 oembed_tagからoembed_tag.rbをダウンロードして、pluginsフォルダに置く。 Gemfileを適当なテキストエディタで開き、「gem ‘ruby-oembed’」の行を追加 source "http://rubygems.org" group :development do gem 'rake' gem 'rack' gem 'jekyll' gem 'rdiscount' gem 'pygments.rb' gem 'RedCloth' gem 'haml', '>= 3.1' gem 'compass', '>= 0.11' gem 'rubypants' gem 'rb-fsevent' gem 'stringex' gem 'liquid', '2.2.2' gem 'ruby-oembed' #追加 end gem 'sinatra', '1.2.6' これでとりあえずは動くはず。 以上の作業に加えて、キャッシュファイルがリポジトリに含まれないよう.gitignoreに.oembed-cacheを追加しておく。 使い方 以下の様に書くと、適切な埋め込み方法をWebから取得して変換してくれる。 &#123;% oembed URL %&#125; 例 Twitter &#123;% oembed https://twitter.

久しぶりにOMakeを使おうと思ったら、使い方を忘れてしまったので復習。 基本的な流れ 初期化 OMakeのインストールはaptitudeやyumやDownload OMakeあたりで頑張る。 OMakeがインストールできたら、まずは初期化のおまじない。 omake --install カレントディレクトリにOmakefileとOmakerootが作られる。 自分のプロジェクト内容に合わせてOmakefileを編集。 具体的な例は後述。 ビルドする 単に「omake」と打つとビルド omake 継続監視ビルド 「-P」オプションで継続監視ビルド omake -P 関連するファイルを監視して、変更があれば自動的にビルドしてくれる。 キャッシュの削除 OMakeでビルドすると環境依存なパスの設定とかを書き込んだファイルが作成される。 Dropboxなどの同期ソフトはこれらの設定ファイルも同期してしまうので、 別環境で作業しようとするとエラーを吐いて止まってしまう。 次のコマンドでキャッシュファイルを無視すれば大丈夫。 omake --flush-includes Omakefileの例 TeXの文章をビルドするOMakefileの例。 LinuxとWindowsでデフォルトの文字コードが違って面倒なので、文字コードはutf-8に統一。 PDF出力はA3サイズ。 {% gist 3300749 OMakefile %} prosperを使ってプレゼン資料を作った時のOMakefile。 dvipdfmでは処理できない場合があるので、一度PostScriptにしてからPDFに変換するようにルールを上書き。 数式を多用するようなプレゼン資料だと便利。 {% gist 3300749 OMakefile-slide %} 参考 OMake つかったらC言語でプログラム書く手間がバカみたいに減った OMake つかって LaTeX コンパイルしたら簡単すぎて身長が5cm伸びた OMake マニュアル日本語訳 omakeが動かない …. 動いた [卒論] LaTeXのビルドにOMakeを使ってみた おまけ Dropboxと連携するとこんなことも。 Dropboxで同期しているフォルダで、「omake -P」を実行して自動コンパイルする設定のまま放置してきちゃった。別のPCでソース書き換えると、Dropboxが同期→リモートのomakeが自動コンパイル→Dropbox経由でコンパイル結果が帰ってきた。 — Ichinose Shogoさん (@shogo82148) 9月 27, 2011

さあ、皆さん！今年も長岡の大花火大会の季節がやって参りました！ 花火大会といえば、 光と音の速度差を体感できる絶好の機会です。 というわけで、去年もこんなアプリを作って遊んでました。 このアプリを頑張って改良したので、改めて紹介したいと思います。 アプリをダウンロード 使い方 起動すると、こんな画面が表示されます。 花火が開いたら画面をタップ！ そして、花火が画面中央に来るよう素早く端末を動かします。 (※画像ははめ込み合成です) 花火の音がしたら、目標をセンターに入れてタップ！ タップの間隔から花火までの距離を計算し表示してくれます。 さらに、加速度センサの値から端末の仰角を読み取り、花火の高さや水平距離などを算出してくれるという機能もついてます。 去年からの変更点 と、ここまでは、去年と一緒。 今年はさらにパワーアップしました。 地図へのマッピング スマートフォンには磁気センサがついており、方位が分かります。 加えて、GPSもついているので、スマートフォンの現在位置も分かります。 これだけの情報が揃えば、地図にプロットできるはず！ 結果表示の画面で「地図を表示」を選ぶとマッピングしてくれます。 この画面でメニューキーを押すと、TwitterやGoogle+などで、花火の位置をみんなに知らせることもできます。 GPS測位ができない場合は、デフォルトの位置を使用します。 この位置は設定画面で変更できます。 自動花火検出 去年からの課題であった、花火の自動検出も試みてみました。 初期画面でメニューキーを押すと設定画面へ飛べます。 ここで「花火を自動的に検出する」「花火の音を検出する」を選択すると、自動検出してくれるはずです(※理論値)。 花火が開いたことは、画面が明るくなったことで検出します。 明るさの検出は初期画面中央の四角の中が使われます。 設定画面でこの四角の大きさを変えることができます。 明るさの変化が閾値を超えたら測定開始です。 音は音量で検出します。 音声にDFTをかけて、周波数フィルタリングをかけてあります。 これで人ごみにまぎれても花火の音が検出できる・・・はず。 周波数0Hzにすると、周波数フィルタを通さずに振幅のみで判定します。 検出した値は、画面の右上に表示しているので、設定の時の参考にしてください。 ダウンロード アプリをダウンロード 野良アプリなので、「設定→アプリケーション→提供元不明のアプリ」をチェックする必要があります。 スマートフォンの機能をフル活用するので権限をたくさん要求してきますが、きっとだいじょうぶ。 そろそろマーケットでの公開も試してみたいですね。 ** Google Play にリリースしました！ ** Google Play からアプリをダウンロード まとめ それでは、大幅に機能UPしたアプリと一緒に、長岡の大花火大会をお楽しみください。 打ち上げはこのあたりらしいです。 ちゃんとマッピングできますかね？