Box2DのポリゴンをC++から使うときの注意点
こんばんはおはようございますこんにちは。
今回は、実験の自由課題でBox2Dを使って物理シミュレーションをしたのですが、そのときにちょっとハマった点を書きます。
Box2Dとは
ハマったところを書く前に、とりあえずBox2Dの簡単な紹介です。
Box2D（http://box2d.org/）は、2次元平面上での物理シミュレーションをするためのライブラリです。zlibライセンスで配布されています。
2013/12/02現在の最新版はBox2D 2.3.0です。
もともとはC++用のライブラリですが、JavaとかActionScriptとか.NETとか向けに有志によって移植されたものもあるようです。
ポリゴンの座標系
さてここがハマったところです。
ちなみに、コーディング中はずっと、Box2Dを公式サイトから落としてくるときについてくるドキュメントはもちろんのことながら、それに加えてnitoyon氏のてっく煮ブログの記事を参考にしてました（情報が古いししかもC++じゃなくてActionScriptですが）。
ポリゴンを生成するとき、次のようなコードを書いたとします。
b2Vec2 grabity(0.0f, 9.8f); // 重力加速度9.8 b2World world(grabity); b2BodyDef polygonDef; polygonDef.type = b2_dynamicBody; polygonDef->positon.Set(0.0f, 0.0f); // 位置を原点にセット auto polygonBody = world.CreateBody(&polygonDef); const int verticesCount = 5; // 頂点数 b2Vec2 vertices[verticesCount]; vertices[0].Set(1.0f, 1.0f); vertices[1].Set(2.0f, 1.0f); vertices[2].Set(3.0f, 2.0f); vertices[3].Set(2.0f, 3.0f); vertices[4].Set(1.0f, 2.0f); b2PolygonShape polygonShape; polygonShape.Set(vertices, verticesCount); b2MassData polygonMassData; polygonShape.ComputeMass(&polygonMassData, 1.0f); // 密度は1.0 b2FixtureDef polygonFixture; polygonFixture.friction = 0.3f; // 摩擦係数0.3 polygonFixture.restitution = 0.7; // 反発係数0.7 polygonFixture.density = 1.0f; // 密度1.0 上で設定してるから多分書かなくていい polygonFixture.shape = &polygonShape; polygonBody->CreateFixture(&polygonFixture); polygonBody->SetMassData(&polygonMassData);
これでworldにポリゴンを設定できたと思います（実際に実験課題で書いたソースコードは該当部分が都合上断片化してたりしてもしかすると少し足りなかったりコンパイル通らなかったりするかもしれませんが、ご容赦ください）。
さて、参考にしたと上で書いたブログ（上のリンクとは同じブログ内の別のページだったかもしれませんが）には、「polygonBody->GetPositon()して得られるのは重心の座標」みたいなこと書いてあったように思います（書いてなかったらすみません）。
しかし実際に動かしてみると、次のようになりました。
polygonBody->SetPosition()したときに設定する座標は、そのポリゴンの位置を参照するときに使う基準の座標- 当たり判定は普通に、
polygonShape.Setで設定した座標を基準として行う polygonBody->GetPosition()で返ってくる座標は、polygonShape.Setで設定したポリゴンの重心の座標が平行移動したぶんだけ、polygonBody->SetPosition()で設定した座標を平行移動させたもの
要するに、polygonBody->SetPosition()だとかpolygonBody->GetPosition()だとかは重心云々とはそんなに関係ないようです。
実験課題ではこれまわりのデバッグに一番時間をとられました。似たものがたくさんでてきて非常にややこしい。
ポリゴンの頂点数
Box2Dの公式ドキュメントには「ポリゴンの頂点数はb2_maxPolygonVertices（デフォルトでは8）以下じゃないとダメ」とか書いてありますが、高精度なポリゴン計算をしようとしてこの値を動的に書き換えようとしても、b2_maxPolygonVerticesはなんと次のように定義されてるので動的には書き換えられません。
#define b2_maxPolygonVertices 8
また、余裕をもって大きな値にしようとしてもメモリ制限か何かでそれはできないようです。
1つの物体に対して複数の図形を登録して、登録した図形があわさった形を作ることはできるようなので、頂点数が多い図形やそもそも凸でない図形を扱いたいときはおとなしくポリゴンの三角形分割とかを考えましょう（上のてっく煮ブログの記事に、八角形に分割するActionScriptのコードが載っているので、それを真似してC++で書けばできるんじゃないかなあと思います）。
その他
この記事を書いてて気づいたんですが、Box2D 2.3.0から、ポリゴンの頂点を指定するときに反時計回りの凸包じゃないといけない云々は考えなくてもよくなったようですね。頂点を指定するときに自動的に凸包を計算して反時計回りに頂点が並ぶよう修正してくれるようです。それ以前のバージョンでは凸包を計算する（座標直打ちのときはその頂点が本当に凸包になっているかどうか計算する）必要があって、また時計回りには頂点が並ばないよう注意する必要があったので、かなり楽になったようですね。
また、ある程度以上近いポリゴンの頂点は併合されてしまうようになったらしいので、あまりに小さいポリゴンを作りたいときなどには注意が必要です。
最後に
実験課題ではそんなに重くなるような計算をさせたわけではないので、計算が高速かどうかはよくわかりませんが、2Dシミュレーション向けには結構使えそうですね。
Web上に日本語資料があまりないのが難点ですが。
C#からC++/CLIのdllを呼び出すときのIntelliSenseの挙動がひどい
みなさんお久しぶりです。2ヶ月半ぶりくらいですね。
今回は小ネタで、大学の実験課題をやってて気になったことです。
C#はVisual Studioでの開発との親和性がとても高く、そのキモになってるのがIntelliSenseでもあるわけです。
しかし、OpenCVとかみたいにどうしてもC++で書かれたライブラリを使わないといけない場合もあります（OpenCVの場合はOpenCVSharpという素晴らしいラッパライブラリがありますが）。
C++で開発するよりもC#で開発するほうが圧倒的に楽なので、大きなアプリケーションはできればC#で開発したいわけです。
ということで、C++/CLIでC++で書かれたライブラリをラップしてdll化し、それをC#で参照して使うと、既存のライブラリを楽に使えますし、また時間のかかる処理をC++で書いてdll化して高速化、みたいなことも考えられます。
しかし、このときのIntelliSenseの挙動がちょっとひどい。
同じソリューション内に
があって、後者は前者のプロジェクトを参照設定しているとします。このとき、dllを作る方のプロジェクトをまずコンパイルしないと、使う方のプロジェクトでは、そのdll内にある名前空間とかはIntelliSenseの中ではなかったことにされます。いちいちコンパイルするのめんどくせぇ。
まあこれは同じソリューションの中のプロジェクトから作られるdllでないdllを参照するときと同じ仕様にしてるんだろうなぁということでまだ納得できます（やっぱりいちいちコンパイルするのめんどくさいけど）。
しかし、休憩するだとかで開発中を一旦中断してVisual Studioを閉じてもう一回開くと、dllを使う側の方のdllを参照しているところについては、やはりそのdll内にある名前空間とかはIntelliSenseの中ではなかったことにされます。回復方法は今のところ不明。
なんなんだこれは。IntelliSenseの意味ほとんどないじゃん。C++単体より便利さ下がってるじゃん。死んでくれ。
イラついて一気に書いたのでぐちゃぐちゃな文章ですが、最後までお付き合いいただきありがとうございました。
C#でJSONのパース
こんばんはおはようございますこんにちは
今回はC#でJSONのパースをしてみたいと思います。
neueccさんの作られたDynamicJsonという素晴らしいライブラリもありますが、ここでは標準ライブラリを使うことにします。
標準ライブラリでJSONのパースをするには、DataContractJsonSerializerクラスを使います。
なお、.NET Framework 4.0以上が必須です。
まずは使ってみる
使い方はとても簡単で、取得したいオブジェクトの型でDataContractJsonSerializerのインスタンスを初期化して、文字列をMemoryStream経由で読み込ませるだけです。
using System; using System.Collections.Generic; using System.Globalization; using System.IO; using System.Runtime.Serialization; using System.Runtime.Serialization.Json; using System.Text; [DataContract] class Data { [DataMember] public int a; [DataMember] public double d; [DataMember] public string s; } class Program { static void Main() { var json = @"{""a"":123, ""s"":""test!"", ""pi"":3.14}"; var serializer = new DataContractJsonSerializer(typeof(Data)); using (var ms = new MemoryStream(Encoding.UTF8.GetBytes(json))) { var data = (Data)serializer.ReadObject(ms); Console.WriteLine(data.a); Console.WriteLine(data.d); Console.WriteLine(data.s); } } }
このように、JSONデータの中に存在しないフィールド・プロパティがあるなどJSONデータとオブジェクトが完全には一致していなくても、デフォルト値を入れるなど適当に処理してくれます。
また、読み込ませたいオブジェクトにはDataContractAttributeを、読み込むフィールド・プロパティにはDataMemberAttributeをつけないといけないことに注意しましょう。DataMemberAttributeをつけていないフィールドやプロパティはJSONから読み込まれません。
DataMemberAttributeさえつけていれば、publicだけではなく例えばprivateなフィールド・プロパティでも読み込んでくれます。
Dictionaryの読み込み
このDataContractJsonSerializerは、組み込み型でもユーザ定義型でもだいたい読み込んでくれます。
ただし、データをDictionaryとして読み込みたいときは少しコードを変えないといけません。
具体的に何をするかというと、DataContractJsonSerializerSettingsのインスタンスを作って、UseSimpleDictionaryFormatプロパティをtrueにして、DataContractJsonSerializerのインスタンスを作ります。
using System; using System.Collections.Generic; using System.Globalization; using System.IO; using System.Runtime.Serialization; using System.Runtime.Serialization.Json; using System.Text; [DataContract] class Data { [DataMember] public Dictionary<string, double> xs; } class Program { static void Main() { var json = @"{""xs"":{""1"":1, ""e"":2.718, ""pi"":3.14}}"; var settings = new DataContractJsonSerializerSettings(); settings.UseSimpleDictionaryFormat = true; var serializer = new DataContractJsonSerializer(typeof(Data), settings); using (var ms = new MemoryStream(Encoding.UTF8.GetBytes(json))) { var data = (Data)serializer.ReadObject(ms); foreach (var x in data.xs) { Console.WriteLine("{0}\t{1}", x.Key, x.Value); } } } }
読み込み時に自動的にデータを変換する
TwitterAPIを叩いたときに返ってくるJSONデータの中には、created_atプロパティのように「中身は実質的にDateTimeだけど、JSONに載せる都合上stringで送られてくる」ものも存在します（JSONに載せられるデータ型は実質的に、数値と文字列とそれらの配列だけです）。
中身は実質的にDateTimeなので、JSONを読み込むと自動的にstringからDateTimeに変換してほしいものですが、実際にはそんなに簡単にはいきません。
というのも、Twitterから送られてくるcreated_atプロパティの中のフォーマットがDateTimeのデフォルトの文字列解釈のフォーマットと異なるため、そのままではちゃんと読み込んでくれないのですね。
そこで、DataMemberAttributeをつけたものしか読み込まないという仕様をうまく使って、データ読み込み時に自動的にデータ変換するようにします。
using System; using System.Collections.Generic; using System.Globalization; using System.IO; using System.Runtime.Serialization; using System.Runtime.Serialization.Json; using System.Text; [DataContract] class Data { [DataMember(Name = "created_at")] private string created_at_str_prop { get { return created_at_str_field; } set { created_at_field = DateTime.ParseExact(value, "ddd MMM dd HH:mm:ss zzz yyyy", DateTimeFormatInfo.InvariantInfo, DateTimeStyles.None); created_at_str_field = value; } } private string created_at_str_field; public DateTime created_at { get { return created_at_field; } set { created_at_str_field = value.ToString("ddd MMM dd HH:mm:ss zzz yyyy", DateTimeFormatInfo.InvariantInfo); created_at_field = value; } } private DateTime created_at_field; } class Program { static void Main() { var json = @"{""created_at"":""Wed Sep 11 20:01:35 +0000 2013""}"; var serializer = new DataContractJsonSerializer(typeof(Data)); using (var ms = new MemoryStream(Encoding.UTF8.GetBytes(json))) { var data = (Data)serializer.ReadObject(ms); Console.WriteLine(data.created_at); } } }
JSONデータを読み込むときに、DataMemberAttiributeがついているcreated_at_str_propプロパティのsetterが呼び出されるので、その中でデータを変換しているわけです。
Data.created_atプロパティ以外はクラスの外からは見えないので、あたかもJSONを読み込むと自動的にstringをDateTimeに変換しているように見えるわけですね。
また、今まで特に触れていませんでしたが、DataMemberAttributeをつけるときに、Name = "hogehoge"と指定することで、JSONデータ中のフィールド名を指定できます。
最後に
これでDataContractJsonSerializerを使ってJSON形式のデータを読み込む方法の紹介がざっと終わったわけですが、書き込むときもReadObjectメソッドではなくWriteObjectメソッドを使って同じようにすればできるみたいです。
LinkedListとArrayの速度が全く違う件
今回の内容は軽めです。
前回の多項式の因数分解プログラムのリファクタリング中に気づいたのですが、約数の一覧を配列で持たせるかLinkedListで持たせるかで実行速度が数倍違うような気がしました（どうも勘違いで、実際にはほとんど変わってなかったみたいです）。
実験
本当にLinkedListで持たせてるのが遅くなっている原因なのか調べるために、次のような簡単なC#のコードを書いて実験してみました。単に1からnまでの整数の和を求めるだけのコードです。
using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; class Program { static void Main() { int n = 10000000; // テストするデータ数 var sw = new Stopwatch(); long res; Console.WriteLine("----- LinkedList"); sw.Reset(); sw.Start(); var ll1 = new LinkedList<int>(); for (int i = 0; i < n; ++i) { ll1.AddLast(i); } sw.Stop(); Console.WriteLine("Generate: {0:e6}[ms]", sw.Elapsed.TotalMilliseconds); sw.Reset(); sw.Start(); res = 0; foreach (var x in ll1) { res += x; } sw.Stop(); Console.WriteLine("Compute : {0:e6}[ms]", sw.Elapsed.TotalMilliseconds); Console.WriteLine(); Console.WriteLine("----- Array"); sw.Reset(); sw.Start(); var a1 = new int[n]; for (int i = 0; i < n; ++i) { a1[i] = i; } sw.Stop(); Console.WriteLine("Generate: {0:e6}[ms]", sw.Elapsed.TotalMilliseconds); sw.Reset(); sw.Start(); res = 0; foreach (var x in a1) { res += x; } sw.Stop(); Console.WriteLine("Compute : {0:e6}[ms]", sw.Elapsed.TotalMilliseconds); Console.WriteLine(); Console.WriteLine("----- LinkedList -> Array"); sw.Reset(); sw.Start(); var ll2 = new LinkedList<int>(); for (int i = 0; i < n; ++i) { ll2.AddLast(i); } sw.Stop(); Console.WriteLine("Generate: {0:e6}[ms]", sw.Elapsed.TotalMilliseconds); sw.Reset(); sw.Start(); var a2 = ll2.ToArray(); sw.Stop(); Console.WriteLine("ToArray : {0:e6}[ms]", sw.Elapsed.TotalMilliseconds); sw.Reset(); sw.Start(); res = 0; foreach (var x in a2) { res += x; } sw.Stop(); Console.WriteLine("Compute : {0:e6}[ms]", sw.Elapsed.TotalMilliseconds); } }
手元のPCで実行した結果は下のとおりです。
----- LinkedList Generate: 1.343535e+003[ms] Compute : 8.357720e+001[ms] ----- Array Generate: 2.087620e+001[ms] Compute : 1.494910e+001[ms] ----- LinkedList -> Array Generate: 1.392360e+003[ms] ToArray : 5.870290e+001[ms] Compute : 1.685090e+001[ms]
生成時間が2桁も違うのはアレですが、和の計算時間もおよそ5.6倍も開きがあります。
さらに驚きなのは、LinkedListのまま先頭から末尾まで走査して和を計算するより、一旦配列に変換してから先頭から末尾まで走査して和を計算するほうが、配列変換にかかる時間を考えても短いことですね。
理由
LinkedListは遅いと断定できたところで私は思い出したんですが、みなさんご存知の通り、線形リストの動作は一般に非常に遅いです。
これはコンピュータのしくみとも関係があるのですが、配列の場合はデータを記憶するために必要なデータ量が必要最小限で済んでしかもデータがメモリ上に連続的に配置されるのでデータが高速なキャッシュメモリに乗りやすく、そのお陰で動作も高速です。
一方線形リストの場合は、データを記憶するために必要なデータ量が多く（LinkedListの場合は双方向リストなので、64bit環境でint型のデータを格納する場合は、配列に比べておよそ5倍のデータ量が必要です）、データもメモリ上に連続的に配置されるとは限らないのでキャッシュミスが必然的に多くなり、動作が遅くなってしまうわけです。
となると、「なんでLinkedListそのままで全部の数の和を計算するよりもToArrayしてから全部の数の和を計算するほうが速いのか。LinkedListのままで和を計算するのもToArrayするのもどうせデータの先頭から末尾まで操作するんだから時間は後者のほうが長くなるはずなのに」という疑問が湧いてくるわけですが、さっきのテストプログラムを逆アセンブル（ILのコードを人間が読みやすいように変換）して実行可能ファイルを見てみると、どうやらToArrayはCLRの内部関数に投げちゃってるらしいです。
CLRの内部関数なんだから恐らく僕達が適当に書くより速く動作するんでしょう。知らないけど。
ということで（アセンブラあまり読めないし）こういうことで適当に納得することにしました。
結論
ここまで書くと、なんで線形リストなんか存在するんだっていう感じですが、ちゃんと存在理由はあります。
線形リストの最大の利点は、「要素の追加・削除・挿入がとても簡単にできる」ということです。配列の場合はサイズ変更が必要になったときにデータの移動が必要ですが、線形リストはそんなの全く必要ないですからね。
また、LinkedListは単なる双方向線形リストですが、線形リストクラスを自分で作るなどすれば、ノードのつなぎかたによっては循環リストだとかそういうのも作ることができて応用範囲が非常に広いです。
ということでLinkedListと配列の使いどころのまとめ。
LinkedList
- いくつ入るかわからないデータの格納に使う
- データの追加・挿入・削除が簡単
- LinkedListに持たせたデータの処理は、ToArrayでLinkedListを配列に変換してからやるほうが速そう。何回もそのデータを使うような場面なら効果絶大
- 参照型とかintみたいな単純な値型ならToArrayする方が速いけど、フィールドがたくさんある複雑な値型ならToArrayが遅そうな気がする（だからLinkedListのままデータ処理する方がよさそう）
そもそも大量のデータ持ってるときにさらにToArrayしたら使うメモリががが
配列
- 最初からいくつ入るかわかってるデータの格納に使うといい
- データの参照とかが高速
- 使うメモリが必要最小限
というかパフォーマンス気にしなきゃいけないような段階にきたらまずは使うアルゴリズム変えるのを検討しろよって僕は思うので、普段のコーディングではLinkedListでも配列でも使いやすい方を使いましょう。
以上、おしまい。
多項式の因数分解
因数分解にも（本当は）いろいろあるのですが、今回は1変数整数係数多項式を、定数でない1変数整数係数多項式の積で書くことを考えます。若干表現が遠回りかもしれませんが、いわゆる普通の因数分解です。
さて、コンピュータで因数分解をするにはどうすればいいでしょうか。
直接因数分解するのは難しそうなので、因子の候補をすべて挙げて、その中から適しているものを選べばよさそうです。
問題はその因子の候補の選び方ですね。因子の候補はモレがあってはいけませんし、できることなら候補の数は減らしたいわけです（候補の数が多いと、適しているかどうかのチェックに時間がかかってしまいます）。
効率のいいアルゴリズムとかだと環論とかの知識を使うらしいんですが、残念ながらそういう抽象代数学の知識がないので、今回は頭の悪い方法で計算量的にはかなり効率が悪いのですが、単純な方法で因数分解してみたいと思います。
アルゴリズムの主要部分
今回紹介するのはKroneckerの方法（Wikipedia(英語)）です。原理はわりと単純なので理解しやすいと思います。
英語版wikipediaを読むのが一番手っ取り早いと思いますが、英語なんて読めねぇぜって人もいると思うので要点だけかいつまんで説明すると、因数分解したい多項式の整数での値の約数を調べて、約数の全組み合わせに対して多項式を調べて因子を決定する、というものです。
ところがこの方法、たった5次の多項式を因数分解するのにも、128通り（英語版wikipediaには実質64通りって書いてありますが組み合わせだけからどうやって高速に見分けるんでしょうねぇ）調べなければならず、結構大変です。
みたいなわりと単純な多項式を因数分解する場合でも、約100兆通りも調べなければならなくて、こんなのは現代のPCではめちゃくちゃ計算時間がかかってやってられないわけです。
そこでいろいろ工夫をして処理量を減らすわけですね。
工夫その1
Kroneckerのアルゴリズムの欠点は、因数分解したあとの因数の数（重複度も含めて考えます）が増えると、約数の数も当然増えて、組み合わせが膨大になってしまう点です。
そこで、Kroneckerのアルゴリズムに頼らなくても（完全なとはいわないけど）因数分解できるところについては分解してしまえば、因数分解する多項式の数は増えますがそれよりも組み合わせ爆発を抑える効果のほうが圧倒的に大きくなり、因数分解が高速化されます。
ここで登場するのが無平方分解です。
無平方分解というのは、多項式を因数分解したときにの部分が現れないようにすることです。
一見実行が難しそうですが、かなり単純なアルゴリズムで計算できます。
多項式を微分したものと元の多項式の最大公約数（最大公約多項式といったほうがわかりやすいかも）をとると、多項式を因数分解したときのの部分が
になって出てきます。
従って
を計算すれば、重複度がちょうどの因子が出てくるわけです。
多項式の微分は普通に各項ごとに微分すればいいですし、多項式の最大公約数はユークリッドの互除法と同じアルゴリズムで計算できます。
これにより、因子の数を減らして計算を高速化できるようになるばかりか、最終的に出てきた候補のうち次数が小さいものから順に割っていって割り切れたら商をもとの多項式として試行除算を繰り返す、という操作だけで因子の規約性も保証されながらすべて求められるというオマケ付きです。
工夫その2
先のような工夫は平方因子を持つ多項式に対しては非常に有効なのですが、先ほどののように平方因子をもたない多項式に対しては完全に無力です。
では、平方因子を持たない多項式に対して打つ手はないのでしょうか？
いいえ、あります。うまく枝刈りをすればいいわけです。
合同式の性質として、任意の整数係数多項式に対して、ならば
が成り立つというものがありましたね（合同式の法はなんでもいいです）。つまり、整数係数多項式なら
は
で割りきれます。ということは、
が
の倍数でないような
が存在するなら、その約数の組み合わせは整数係数多項式を生成しないので不適ということがわかります。
これは整数列が整数係数多項式を生成するための必要十分条件ではない（例えば～
がそれぞれ1,1,1,1,13のとき、
は整数係数じゃないのに
は
で割りきれる）ですが、反例となる多項式の数はかなり少なく、また整数列の途中までしか見なくても整数係数多項式にはならないということがわかるので非常に有効な枝刈り法です。
Befungeで遊ぶ
今回は難解プログラミング言語の1つ、Befungeで遊んでみようと思います。
Befungeの言語仕様はwikipediaを見てもらえばいいと思いますが、大きな特徴はプログラムポインタがソースコード中を2次元的に動きまわることと、プログラム内の命令によって自分自身を書き換えられることでしょう。
ソースコードの大きさが無制限の場合はチューリング完全でC言語とかと同等のプログラミング能力を（理論上）持ちますが、今回は80桁25行に限定したのでチューリング完全というわけではありません。しかし、これだけでも結構書けるものです。
処理系
とりあえずまずは処理系を作ってみることにします。
命令の数が多くないので、そこまで大変ではありません（といっても4時間くらいかかりましたが）。
適当にJavaScriptで書いてみました。JSはあまり得意じゃないので汚いかもです。
var code = new Array(25); var stack = new Array(); var x = 0; var y = 0; var direction = [[1, 0], [0, -1], [-1, 0], [0, 1]]; var dir = 0; var skip = false; var string = false; var interval = 100; var quit = false; function escape(letter) { if (letter < 32 || letter >= 127) { return ' '; } switch (letter) { case '<'.charCodeAt(0): return '<'; case '>'.charCodeAt(0): return '>'; case '&'.charCodeAt(0): return '&'; case ' '.charCodeAt(0): return ' '; default: return String.fromCharCode(letter); } } // (x, y)がハイライトされた状態でソースコード表示 function show_code(source_code, x, y) { var rows = "ABCDEFGHIJKLMNOPQRSTUVWXY"; var digit = "0123456789ABCDEF" var i, j; // 1行目の記述 var text = " | "; for (i = 0; i < Math.floor(x / 16); ++i) { text += i + " "; } if (x % 16 == 0) { text += "<div>" + Math.floor(x / 16) + "</div> "; } else { text += i; for (j = 1; i * 16 + j < x; ++j) { text += " "; } text += "<div> </div>"; for (++j; j < 16; ++j) { text += " " } } for (++i; i < 5; ++i) { text += i + " "; } text += "<br />"; // 2行目の記述 text += " | "; for (i = 0; i < x; ++i) { text += digit[i % 16]; } text += "<div>" + digit[i % 16] + "</div>"; for (++i; i < 80; ++i) { text += digit[i % 16]; } text += "<br />"; // 3行目の記述 text += "-+-"; for (i = 0; i < x; ++i) { text += "-"; } text += "<div>-</div>"; for (++i; i < 80; ++i) { text += "-"; } text += "<br />"; // 4行目以降 for (i = 0; i < y; ++i) { text += rows[i] + "| "; for (j = 0; j < x; ++j) { text += escape(source_code[i][j]); } text += "<div>" + escape(source_code[i][j]) + "</div>"; for (++j; j < 80; ++j) { text += escape(source_code[i][j]); } text += "<br />"; } text += "<div>" + rows[i] + "| "; for (j = 0; j < x; ++j) { text += escape(source_code[i][j]); } text += "</div><div id='pointer'>" + escape(source_code[i][j]) + "</div><div>"; for (++j; j < 80; ++j) { text += escape(source_code[i][j]); } text += "</div><br />"; for (++i; i < 25; ++i) { text += rows[i] + "| "; for (j = 0; j < x; ++j) { text += escape(source_code[i][j]); } text += "<div>" + escape(source_code[i][j]) + "</div>"; for (++j; j < 80; ++j) { text += escape(source_code[i][j]); } text += "<br />"; } document.getElementById('source').innerHTML = text; } // 初期位置ハイライトでソースコード表示 function show_code_init(source_code) { var rows = "ABCDEFGHIJKLMNOPQRSTUVWXY"; var digit = "0123456789ABCDEF" var i, j; // 1行目の記述 var text = " |<div> </div>"; for (i = 0; i < 5 ; ++i) { text += i + " "; } text += "<br />"; // 2行目の記述 text += " |<div> </div>0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF<br />"; // 3行目の記述 text += "-+<div>-</div>--------------------------------------------------------------------------------<br />"; // 4行目の記述 text += "<div>A|</div><div id='pointer'> </div><div>"; for (j = 0; j < 80; ++j) { text += escape(source_code[0][j]); } text += "</div><br />"; // 5行目以降 for (i = 1; i < 25; ++i) { text += rows[i] + "|<div> </div>"; for (j = 0; j < 80; ++j) { text += escape(source_code[i][j]); } text += "<br />"; } document.getElementById('source').innerHTML = text; } // 逐次解釈・実行 function interpret() { var xx, yy, vv; show_code(code, x, y); document.getElementById('stack').innerHTML = stack.join(" "); if (string) { if (code[y][x] == '"'.charCodeAt(0)) { string = false; } else { stack.push(code[y][x]); } } else if (!skip) { switch (code[y][x]) { case '<'.charCodeAt(0): dir = 2; break; case '>'.charCodeAt(0): dir = 0; break; case '^'.charCodeAt(0): dir = 1; break; case 'v'.charCodeAt(0): dir = 3; break; case '_'.charCodeAt(0): xx = stack.pop(); if (xx == 0) { dir = 0; } else { dir = 2; } break; case '|'.charCodeAt(0): xx = stack.pop(); if (xx == 0) { dir = 3; } else { dir = 1; } break; case '?'.charCodeAt(0): dir = Math.floor(Math.random() * 4); break; case '#'.charCodeAt(0): skip = true; break; case '@'.charCodeAt(0): return 0; // プログラム停止のサイン case '0'.charCodeAt(0): stack.push(0); break; case '1'.charCodeAt(0): stack.push(1); break; case '2'.charCodeAt(0): stack.push(2); break; case '3'.charCodeAt(0): stack.push(3); break; case '4'.charCodeAt(0): stack.push(4); break; case '5'.charCodeAt(0): stack.push(5); break; case '6'.charCodeAt(0): stack.push(6); break; case '7'.charCodeAt(0): stack.push(7); break; case '8'.charCodeAt(0): stack.push(8); break; case '9'.charCodeAt(0): stack.push(9); break; case '"'.charCodeAt(0): string = true; break; case '&'.charCodeAt(0): stack.push(parseInt(prompt("value?"))); break; case '~'.charCodeAt(0): do { xx = prompt("value?"); } while (xx.length > 0); stack.push(xx.charCodeAt(0)); break; case '.'.charCodeAt(0): document.getElementById('output').innerHTML += stack.pop() + " "; break; case ','.charCodeAt(0): document.getElementById('output').innerHTML += escape(stack.pop()); break; case '+'.charCodeAt(0): yy = stack.pop(); xx = stack.pop(); stack.push(xx + yy); break; case '-'.charCodeAt(0): yy = stack.pop(); xx = stack.pop(); stack.push(xx - yy); break; case '*'.charCodeAt(0): yy = stack.pop(); xx = stack.pop(); stack.push(xx * yy); break; case '/'.charCodeAt(0): yy = stack.pop(); xx = stack.pop(); stack.push(Math.floor(xx / yy)); break; case '%'.charCodeAt(0): yy = stack.pop(); xx = stack.pop(); stack.push(xx % yy); break; case '`'.charCodeAt(0): yy = stack.pop(); xx = stack.pop(); if (xx > yy) { stack.push(1); } else { stack.push(0); } break; case '!'.charCodeAt(0): xx = stack.pop(); if (xx == 0) { stack.push(1); } else { stack.push(0); } break; case ':'.charCodeAt(0): xx = stack.pop(); stack.push(xx); stack.push(xx); break; case '\\'.charCodeAt(0): yy = stack.pop(); xx = stack.pop(); stack.push(yy); stack.push(xx); break; case '$'.charCodeAt(0): stack.pop(); break; case 'g'.charCodeAt(0): yy = stack.pop(); xx = stack.pop(); stack.push(code[yy][xx]); break; case 'p'.charCodeAt(0): yy = stack.pop(); xx = stack.pop(); vv = stack.pop(); code[yy][xx] = vv; break; default: break; } } else { skip = false; } x += direction[dir][0]; y += direction[dir][1]; if (x < 0) { x = 79; } else if (x >= 80) { x = 0; } if (y < 0) { y = 24; } else if (y >= 25) { y = 0; } return 1; } // 一定間隔で実行するための関数 function run_int() { var ret = interpret(); if (ret != 0 && !quit) { setTimeout("run_int()", interval); } else { document.getElementById('exe').innerText = '実行'; document.getElementById('exe').onclick = run; document.getElementById('clear').disabled = false; } } // 実行関数 function run() { document.getElementById('exe').innerText = '停止'; document.getElementById('exe').onclick = stop; document.getElementById('clear').disabled = true; document.getElementById('output').innerHTML = ''; x = y = 0; quit = false; stack = new Array(); dir = 0; skip = string = false; interval = parseInt(document.getElementById('interval').value); // ソースコードの設定 var txt = document.getElementById('befunge').value.split("\n"); var i; for (i = 0; i < Math.min(25, txt.length) ; ++i) { code[i] = new Array(80); for (j = 0; j < Math.min(80, txt[i].length) ; ++j) { code[i][j] = txt[i].charCodeAt(j); } for (; j < 80; ++j) { code[i][j] = 0; } } for (; i < 25; ++i) { code[i] = new Array(80); for (var j = 0; j < 80; ++j) { code[i][j] = 0; } } show_code_init(code); if (interval > 0) { setTimeout("run_int()", interval); } else { while (interpret() != 0); document.getElementById('exe').innerText = '実行'; document.getElementById('exe').onclick = run; document.getElementById('clear').disabled = false; } } // 停止用 function stop() { document.getElementById('exe').innerText = '実行'; document.getElementById('exe').onclick = run; document.getElementById('clear').disabled = false; quit = true; } // 内容の全消去 function my_clear() { stack = new Array(); document.getElementById('output').innerHTML = ''; document.getElementById('stack').innerHTML = stack.join(" "); show_code_init(code); } // 初期化 for (var i = 0; i < 25; ++i) { code[i] = new Array(80); for (var j = 0; j < 80; ++j) { code[i][j] = 0; } } show_code_init(code);
だいぶダラダラと長くなってますが、3/8くらいがソースコードをキレイに表示するための関数で、処理本体は半分弱くらいです。残りは実行用のエントリポイントだとか初期化処理だとかその類のやつです。
HTMLの方もかなり適当で、
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta content="text/html; charset=utf-8" http-equiv="Content-Type" /> <title>Befunge</title> <style type="text/css"> div div { background-color:aqua; display:inline-block; } div div#pointer { background-color:lime; display:inline-block; } div.tt, div#source { display:inline-block; font-family:"ＭＳ ゴシック"; } </style> </head> <body> <form> <textarea cols="80" rows="25" id="befunge"></textarea><br /> <input type="text" size="5" id="interval" value="100" />ms <button type="button" onclick="run()" id="exe">実行</button> <button type="button" onclick="my_clear()" id="clear">クリア</button> </form> <div class="tt">出力: </div><div class="tt" id="output" style="background-color:yellow"></div><br /> <div class="tt">スタック: </div><div class="tt" id="stack" style="background-color:yellow"></div><br /> <br /> <div class="tt">ソースコード</div><br /> <div style="display:inline-block;font-family:'ＭＳ ゴシック'" id="source"> </div> <script language="javascript" type="text/javascript" src="befung.js"></script> </body> </html>
みたいな感じで適当にちゃちゃーっと作っちゃいましょう。
これでBefungeで遊ぶ準備ができました（ようやく）。
なお、プログラムサイズは80桁25行以下限定です。
また、本当はデバッグ用にステップ実行機能をつけたかったのですが、めんどくさかったのと時間があまりなかったので省略。つけたい場合はお好みでどうぞ。プログラムの実行速度は制御できるようにしてあります。
まずはHello world
定番のプログラムですね。まずはこれで遊びましょう。
wikipediaに載ってるコードをそのままコピペしちゃいましょう。
v @_ v >0"!dlroW"v v :# < >" ,olleH" v ^ <
これだけ見るとなんのこっちゃって感じなんですが、実際に動かしてみると動作の様子がよくわかると思います。
,とか!を表示させる文字列と命令記号と兼用させているところがちょっと工夫されているところでしょうか。
ぶっちゃけ、こんなややこしいことしなくても、単純にこれで十分だと思いますが。
v >,v |:<"Hello, World!"0< @
もしくはこんな感じ。
0"!dlroW ,olleH">:v
^,_@どのプログラムも、数字の0に続いて、Hello, World!の文字をスタックに積んで、それを順に出力しているわけですね。
この時点で書字方向が左右逆だったり変な記号ばっかりで気持ち悪いんですが、とりあえずそこには目をつぶって先に進みましょう。
もう少し進んだプログラム
Hello worldしただけでは面白くないので、もう少し複雑なプログラムを書いてみましょう。
プログラミングの入門書によくある、「1からnまでの整数の和を求める」プログラムを書いてみましょう。公式を使うと面白くないので、for文を回して（？）求めたいと思います。
こんな感じで書けばいいですね。
0&>:!v v+ < @.-#\_:00p^ ^1 g0<
やっぱりこれだけ見てもなんのこっちゃなので、プログラムの構成法を書いておきます。
まず、今までに足した数の和と、足す数の上限を記録しておかないといけないので、0と、&でユーザが入力した数をスタックに積みます。問題はそのあとですね。
スタックの状態が
[sum][counter]
の状態から
[sum+counter][counter-1]
にしたいわけです。
どうすればいいかというと、もっていきたい状態の方から逆順に考えればよくて、(x, y)をソースコード中の適当な場所として
[sum+counter][counter-1] --[counter] [sum+counter][counter][1] --[counter] [sum+counter][counter] --[counter] [sum+counter][x][y] --[counter] [sum+counter][x] --[counter] [sum+counter] --[counter] [sum][counter] --[counter] [sum][coutner][counter][x][y] --[???] [sum][counter][counter][x] --[???] [sum][counter][counter] --[???] [sum][counter] --[???]
という感じで考えれば、やり方がわかりますね。--[counter]みたいなのは(x, y)に記録されているデータとします。
counterが非0であれば、
:xyp+xyg1-
という処理をすればいいわけです（xやyは適当な数字に置き換えましょう）。
counterが0のときはsumの値を表示してプログラムを終了するだけなので、
\.@
という処理をすればいいというのはすぐわかると思います。
あとはまあなんというか試行錯誤というか、ソースコードをいかに圧縮するかの戦いみたいな感じでしょうか。
もちろんいろんな実装方法があるので、例えばこんなのも考えられるでしょう。
v v>#<:00pv 0 -^_ \.@ + >&>:^^1g00<
これの面白いところは、#の部分を左右にいったりきたりするところでしょうか。
もっと複雑なプログラム
FizzBuzzでもやってみることにしましょう。
&00p1>:00g`!v v < >%\52*v v*86<
>,v + v`1:_@v *#< / +>\`|
|:<", "0_v # # ^2 5:<: ,*
1 >:3%!10p:5%!20p10g20g*v^"Buzz"0_:52*\^_$v^2<
> $ ^ v!:<"Fizz Buzz"0_10gv # >:5^
^ <_, ^ "Fizz"0_20g ^ ^ < こんな感じでいいと思います。これをもっと短くするとかいうのはちょっとやりたくないですね（これでもちょっとはやりました）。
一番苦労したのは数字を表示する部分です。
普通なら.で簡単に出力できるんですが、数字の直後はスペースじゃなくてカンマにしたかったのでわざわざ自分で処理を書きました。
FizzBuzzの難しいところは、条件分岐がたくさんあるので、さっきのnまでの和を求めるプログラムみたいになってほしい状態が複雑なことですね。
そのまま考えるはちょっと難しいので、C言語で書いたソースコードをもとに考えてみます。
#include <stdio.h> int main(void) { int n; int i = 1; int mod3, mod5; scanf("%d", &n); while (i <= n) { if (i > 1) { printf(", "); } mod3 = !(i % 3); mod5 = !(i % 5); if (mod3 && mod5) { printf("Fizz Buzz"); } else if (mod3) { printf("Fizz"); } else if (mod5) { printf("Buzz"); } else { printf("%d", i); } } return 0; }
C言語ならみなさん慣れ親しんでいる（はず）なので、これが正しくFizzBuzzを表示することはまあわかると思います。
それでは部分ごとに分けて考えてみます。
初期化
&でとってきた入力とi=1をスタックもしくはソースコードのどこかに保存します。どこに保存するのが適切かはこの段階ではまだよくわかりません。
", "の出力
iと1を比較してiの方が大きかったら", "を出力するので、この段階でiがスタックの先頭に来てないといけないですね。あとでiは頻繁に参照・更新することを考えると、iはスタックに置くほうがよさそうですね。
v_, v →1`v ^!:<", "_$>→ > ^
という雛形ができます（→はここから入る、←はここから出る印とします）。
条件振り分け
3とか5で割った余りをとりあえず変数に保存します（解説書いてて思った
のですが、ちょっと無駄かもしれません）。
最終的に
[i] --[!(i%3)][!(i%5)]
とかいう感じになっていてほしいので、さっきのプログラムと同じ要領で考えると、(A, B), (C, D)をそれぞれ適当な場所として
:3%!ABq:5%!CDq
とすると、結果が保存できますね。
肝心の条件分岐ですが、Befungには、&&みたいな演算子がないので、掛け算で対応です。
→:3%!ABq:5%!CDqABgCDg*v
イ←_ABgv
ロ←_CDgv
ハ←_→ニイはFizz Buzzを表示するブロック、ロはFizzを表示するブロック、ハはBuzzを表示するブロックで、それぞれ抜けると最初のループ条件のところに戻ります。ニは次で説明する十進数表示ルーチンです。
十進数表示
残念ながらBefungeの.での数値表示は、C言語の
printf("%d ", number);
というのに相当し、数値の後ろにスペースが入ってしまいます。今はそれでは困るので、自分の手で1桁ずつ表示します。
1番下の桁の数は表示したい数を10で割った余りで、それより上の桁の数は表示したい数を10で割った商です。ということは、10で割った余りをスタックに積んでいって、商が0になった段階でASCIIコードで48足しながらスタックの先頭から表示していくと、ちょうどいい感じに表示されそうです。
10で割った余りをスタックに積んでいくには
→:52*\>:52*%\52*/v
^ _$→でいいですね。あとは48を足しつつ表示していくので、
→>:52*\`v ^ ,+*86_$→
みたいな感じになります。なお、終了判定のためにスタックの底（から1つ上）に10を積んでいます（スタックから取り出した値が10以上ならループ脱出）。
初期化処理をもう一度
&で最初に拾ってきた値をスタックの底に積むと終了判定がうまく書けなかったので、ソースコードの適当な場所に値を記憶させることにします。
(E, F)に値を記憶させるとして、
→&EFp1 :00g`v
@_→という部品が出来上がりますね。
ループから戻ってくるときはカウンタに1を足して、上の:の直前の空白のところに戻ってくればいいわけです。
まとめ
こんな感じで出来上がった部品を組み合わせて、あとはいろいろ配置とかをいじくると完成すると思います。
感想
めんどくさい。二度と触りたくないけど、しばらくしたらまた触りたくなってそう。
あと、記事の面積の2/3くらいが自作処理系のソースコードになっちゃってる事実に触れてはいけない。
おまけ
JavaScript触りながら、「なんで文字定数ないねん！」とかいっぱいツッコミ入れながら書いてました。JSも触りたくない。
追記
記事書いた3時間後くらいにFizzBuzz見返してたら、なんじゃこのコードはわけわからんわーとなったので、いろいろ解説を追加しました。
配列の要素の和
何か配列を用意したとき、その配列の要素すべての和を求めたいことはよくありますね。
そのとき、すべての要素が数値型（intとかfloatとか）なら特に問題はないんですが、stringの配列だったりだとか、2次元配列だったりとかすると事態は複雑です。スクリプト言語とかで配列の要素の型が1種類じゃない場合はもっと複雑ですね。
そこで、私の独断と偏見で選んだ代表的なスクリプト言語4つの「配列の要素の和を求める標準関数」を使って、下の4つの配列の要素の和をそれぞれ求めてみました。
a = [1, 2, 3, 4, 5, 6] b = [1, "2", 3, 4, 5, 6] c = [1, 2, 3, 4, [5, 6]] d = [1, "2", 3, 4, [5, 6]]
Ideone上でためしに実行するとこんな感じになります。スクリプト言語はあまり好きではないのでよく知らないのですが、変な書き方などしているところがあったらご指摘ください。
Perl
use strict; use List::Util qw(sum); my @a = (1, 2, 3, 4, 5, 6); my @b = (1, "2", 3, 4, 5, 6); my @c = (1, 2, 3, 4, (5, 6)); my @d = (1, "2", 3, 4, (5, 6)); print List::Util::sum(@a), "\n"; # => 21 print List::Util::sum(@b), "\n"; # => 21 print List::Util::sum(@c), "\n"; # => 21 print List::Util::sum(@d), "\n"; # => 21
Perlは入れ子になった配列でも再帰的に和を計算してくれるらしいです。
文字列も数値に変換した上で合計を計算してくれています。
PHP
<?php $a = array(1, 2, 3, 4, 5, 6); $b = array(1, "2", 3, 4, 5, 6); $c = array(1, 2, 3, 4, array(5, 6)); $d = array(1, "2", 3, 4, array(5, 6)); echo array_sum($a) . "\n"; # => 21 echo array_sum($b) . "\n"; # => 21 echo array_sum($c) . "\n"; # => 10 echo array_sum($d) . "\n"; # => 10 ?>
こちらはPerlと違って入れ子の配列は再帰的に和を計算するとかはせず、単に0扱い（or 単に足さないだけ）らしいです。
Python
a = [1, 2, 3, 4, 5, 6] b = [1, "2", 3, 4, 5, 6] c = [1, 2, 3, 4, [5, 6]] d = [1, "2", 3, 4, [5, 6]] print sum(a), "\n" # => 21 # print sum(b), "\n" # => error # print sum(c), "\n" # => error # print sum(d), "\n" # => error
お行儀がいいと言いましょうか、最初の数字だけの配列以外はすべてREになりました。
Ruby
a = [1, 2, 3, 4, 5, 6] b = [1, "2", 3, 4, 5, 6] c = [1, 2, 3, 4, [5, 6]] d = [1, "2", 3, 4, [5, 6]] puts a.inject(:+) # => 21 # puts b.inject(:+) # => error # puts c.inject(:+) # => error # puts d.inject(:+) # => error
Pythonと同じ結果です。
まとめ
ということで適当にアルファベット順に実行してみたわけですが、PythonやRubyは配列に「変なもの」が入っていても型付けの強さのおかげですぐREを出してくれます。
Perlの仕様は1次元配列だけではなくて多次元配列の全要素の和を求めたいときなどにはとても楽に書けるようになっているんじゃないかと思います。しかし、下手に無理やり答えを計算しようとしちゃっているので、「一応エラーは出ないけど答えが正しくない」とかいう一番厄介なパターンのバグを含みやすそうな気がします。
PHPの仕様は誰得なんでしょうね。数値型じゃない要素は足さないという仕様ならまだしも、文字列型のものは数値型に変換して足しちゃってるので、便利になりそうなケースも思い浮かばないですし、Perlでの一番厄介なバグも含みやすそうです。数値型にできないものは足さないというのは内部の実装としてはわりと簡単そうですが。
まあそもそも配列にぐちゃぐちゃいろんな型の値を突っ込むのが間違いだと思うので、スパゲティコードを書きたくない人は素直に、配列に入れるのは1種類の型（もしくはintとfloatみたいに1種類の型とみなしても差し支えない範囲の複数の型）だけにしましょうｗ
