ドーナツを穴だけ残して食べる方法


4872594703大阪大学ショセキカプロジェクト『ドーナツを穴だけ残して食べる方法』(大阪大学出版会, 2014)(各章に参考文献リストあり・索引なし)

第1部全5章では、教員5名がドーナツの穴だけ残して食べる方法を、第2部の全7章では、教員7名がドーナツの穴に学ぶことを論じている。

私にとってのベストは大久保邦彦教授の「法律家は黒を白と言いくるめる?」で、末弘厳太郎「嘘の効用」(青空文庫にある)などの参考文献もちゃんと読みたいと思う。その一方で、ドーナツの穴とはあまり関係なさそうな話もいくつかあった。

本書は、学生が中心となって大阪大学の知を書籍化するというプロジェクトの成果物だという。書籍自体は学際的だが、個々のソリューションはそうではない。次は、各分野の英知を集めなければ解けない問題に取り組んでみてほしい。

さて、肝心のドーナツを穴だけ残して食べる方法だが、小さい虫数十匹を、ドーナツの表面を這って食べ、食べ終わったらそこにとどまるように調教すれば、その様子を見た人の中には「穴だけ残った」と思ってくれる人がいるのではないだろうか。

Adobe-Japan1-6のすべてのグリフを1ページで


この記事で作るもの:Adobe-Japan1-6の全23058グリフを1ページで (PDF, 5MB)

Unicodeの文字の一覧を作ったのに続いて、Adobe-Japan1-6のグリフの一覧を作ります。自分で作らなくてもAdobe-Japan1のグリフ一覧は、

しかし、自分で作れるようになっていれば、全グリフを1ページにといった、自分の好きなレイアウトの一覧表が作れます。

改訂版が出るたびに買っている奥村晴彦, 黒木裕介『LaTeX2ε美文書作成入門』(技術評論社, 第6版, 2013)にも、判型が変わった頃から“Adobe-Japan1全グリフ”が掲載されているのですが、書体が小塚明朝ではなくヒラギノ明朝なので、ここでの目的には適しません。以前書いたように、小塚明朝では区別され、ヒラギノ明朝では区別されない漢字のペアがあるので、ヒラギノ明朝では全グリフにはならないのです。『基本日本語活字見本集成』の著者の一人である小形克宏さんも、ブログで次のように書いています。

このページをより一般的なヒラギノ明朝で組むという話が出たとき、ぼくはかなり強く小塚明朝でなければ信頼性を担保できないことを主張しました。仮にヒラギノ明朝でAdobe-Japan1-5を表しても、それはヒラギノとしての実装解釈を示したにすぎず、仕様制定者の本来の意図が見えなくなってしまいます。Adobe-Japan1は文字コード規格ではなく、あくまでも「グリフ」セットなのですから、小塚明朝のタイプフェイス・デザインを前提とするのは自明の理であり、その意味で小塚明朝で掲載されたことは至極当然と言えるでしょう。『基本日本語活字見本集成本OpenType版』のこと (1)

というわけで、小塚明朝で作ります。

小塚明朝とTeXLiveがインストールされた環境で、「kanji-config-updmap kozuka-pr6n」として小塚明朝を埋め込めるようにします。Adobe-Japan1-6のCIDは、0から23057まで、間を空けずに使われているようなので、単純な繰り返しをするTeXファイルで一覧を作れます。こうして作った一覧表が冒頭のPDFファイルです(改行の制御に不満があります@doraTeXさんのコードを参考に修正しました)。

Unicodeのすべての文字を1ページで


この記事で作るもの:Unicode 6.0のすべての文字を1ページで (PDF, 23MB)

4327377368ヨハネス・ベルガーハウゼン, シリ・ポアランガン『世界の文字と記号の大図鑑 ー Unicode 6.0の全グリフ』(研究社, 2014)の著者はUnicode 6.0の全109242文字2時間30分かけて見るビデオの作者ですか。今度は1024ページの書籍。「Decodeunicode」で画像検索すると原著が出てきますが、楽しみですね。(追記:世界の文字と記号の大図鑑

「Unicodeのすべての文字を印刷した本って、前にもなかったっけ?」と思って本棚を探したのですが、勘違いでした。

0321480910頭に浮かんだのはThe Unicode Consortium『The Unicode Standard, Version 5.0』(Addison-Wesley Professional, 2006)(文献リストあり、索引なし)だったのですが、この本は、(1) The Unicode Standard、(2) Code Charts (PDF)から漢字を除いたもの、(3) Han Radical-Stroke Index (PDF)という構成でした。つまり、漢字はコードポイント順に一つずつではなく、Han Radical-Stroke Indexという形で掲載されているだけでした。

Unicode 5.0より後は、紙媒体ではないようですが、たとえば6.0について同じことをするなら、 (1) The Unicode Standard (PDF)、(2) Code Charts (PDF)、(3) Han Radical-Stroke Index (PDF)を使うことになるのでしょう。(Code Chartsには漢字も含まれているので、「文字の一覧(番号順)」が欲しいだけならCode Chartsだけで十分です。)

これらの資料もいいのですが、こういうのは、自分でもちょっとやってみたいところです。例えば、Unicodeの全文字を1ページに、なんてことも、自分で作れるようになればできます。

というわけで、必要なデータをEnumerated Versions of The Unicode Standardから探して作ろうとしたら、これがなかなか面倒でした。

Unicode 6.0の全文字は、UnicodeData.txtに載っているはずですが、この第1列をHTMLの数値文字参照に置き換えるだけでは終わりません。

UnicodeData.txtには、CJK統合漢字など、1行1文字になっていない部分があります。それを補うのは面倒なので、Unicode 5.1以降で導入されたUnicode Character
Database in XML
を使うことにします。このXMLファイルは、char要素1個が1文字に対応します。

XMLファイルには、印刷できない文字?も含まれているので、それを除外しなければなりません。Unicode 6.0のコードポイントは109449個ありますが、そのうちGraphic Characterは109242個です(参照)。『世界の文字と記号の大図鑑』の109242文字というのはこれのことなのでしょう。Graphic Characterの定義General_Category ValuesThe Unicode Standard Chapter 2 General Structureの「Table 2-3. Types of Code Points」を見ると、char要素のgc属性値がCから始まるものとZl, Zpになっているものは除外しなければならないことがわかります。(異体字セレクタのような、明らかに印刷不能な文字が残るのですが、とりあえずはそのままにします。それを使う異体字もここでは数えません。)

というわけで、ちょっとスクリプトを書いて、Unicode 6.0の文字の一覧を作ります。

こんなHTMLファイルです。このファイルは、Unicodeの文字を数値文字参照で書いてあるだけのものなので、文字を実際に表示できるかどうかは環境によります。Noto花園明朝などを入れた環境で、Firefox 31とChrome 36を試したところ、FirefoxはUnicode 6.0のすべての字形を表示できたようですが、Chromeはぜんぜんだめでした(目視以外の確認法がわかりません)。

Windows上のFirefoxでAdobe PDFに印刷した結果が冒頭のPDFファイルです。

完成に必要な無料フォントを列挙する(あるいはもっとよい方法の提案)という自由研究を、どこかの小学生がやってくれることを期待します。

関連:Unicodeのすべての文字を1回ずつ使って絵を描く

魔方陣の解の数を一瞬で求めるプログラム


以前、「スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す(C++)」という記事を書きましたが、解を列挙するのではなく、解の数を数えるだけなら一瞬で終わらせるプログラムがあります。

4×4の魔方陣の場合

clang++ -O3 -std=c++11 magicsquare4.cc」などとしてコンパイルしてから実行します。実行時間は一瞬です。

このプログラムの欠点は、コンパイルにかなりの時間がかかることです(TANSTAAFL)。手元の環境では、コンパイルに4分くらいかかりました(説明するのは野暮ですが、これはネタです)。

C++のconstexprを使っています。複数のコンパイラがconstexprをサポートしていますが、このコードをコンパイルできるのは、私が試したところではClang 3.3のみです(Ubuntuでは「sudo apt-get install clang-3.3」などとしてインストールできます)。ステップ数に上限が導入されたClang 3.4以降や、途中経過を記憶してメモリを圧迫するgccではコンパイルできません。

Clang 3.3でサポートされるconstexprの関数には、大ざっぱに言えばreturn文しか書けないので、マスに数が入るかどうかをチェックする関数を作り、「数がすでに使われていなければ次のマスを試し、使われていれば1だけ大きい数を再帰的に試す」ということを、return文の条件演算子で実現しています。

このコードは私が直接書いたものではなく、私が書いたプログラムが生成したものです(手で直接書くのは大変です)。同じプログラムで5×5の場合も生成しましたが、試すのはやめた方がいいでしょう(constexprを消してコンパイル・実行すれば、正しいことは確認できます)。

スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す(C++)


追記:対称性の活用法をコメントで教えていただきました。それを採用すると本稿の結果よりもかなり高速になります(10分→6分)。(コード

筑波大学のスパコン「T2K-Tsukuba」で約2時間36分かけて5×5の魔方陣(≠魔法陣)の全解を求めたというニュースがありました。

「スパコン」ではなく「パソコン」だったらどうなのだろう、と思って試してみたら、10分でした(Core i7 4930K)。

解の「数」がわかればいいだけ、つまり全解をディスクに書き出さなくてももいいならもう少し早くなります。

コードはこちら(最初のバージョン)。頭の悪そうなコードですが、スクリプトで生成した枠組みを手直しして作れば、そんなに大変ではないかと。理想は全自動生成ですが。Visual Studio 2013 ExpressとICC 14.0.2、GCC 4.6.3、Clang 3.4で動作を確認しています。ClangはOpenMPに対応させるのが面倒なうえに、ちょっと試したところでは、GCCより遅かったです。(実際に試す場合は、OpenMPを有効にしてください。計算中のCPU使用率は100%になるはずです。)

多重for文(笑)ですべての場合を探索するというのが基本方針ですが、それではさすがに終わらないので、次のような工夫をします(工夫というほどのものではありませんが)。

  • 各行・各列・対角線の和は65。(1から25までの和 / 5)
  • (カンで)効率が良くなりそうなところから順番に埋めていく(下図の番号順)。
  • 回転と裏返しで同一になるものを重複して数えないように、下図の緑部分に、「左上<右上<左下」かつ「左上<右下」のような制約を入れる。左上は22以下としてよい。
  • a+b+c+d+eのうち、a,b,c,dが決まったら、e=65-a-b-c-dになる(下図の紫部分)。
  • a+b+c+d+eのうち、a,b,cが決まったら、dはmax(1,65-a-b-c-25)からmin(25,65-a-b-c-1)の範囲で調べればよい。max(un,65-a-b-c-ux)からmin(ux,65-a-b-c-un)にするとさらに速くなる(unは未使用の最小数,uxは未使用の最大数。これを調べるのに時間をかけると効果はなくなる)。

この方針の場合、ループを関数で表現したり、盤面をコンテナで表現したりすると遅くなります。

数を埋める順番
6 10 11 12 8
20 1 18 2 21
22 13 5 16 23
24 3 19 4 25
9 14 17 15 7

魔方陣の解の列挙は並列化しやすそうな問題ですが、ここでの方針では、探索効率を上げるためには条件分岐が不可欠なので、(「数」を求めるだけだとしても)GPGPUでうまくやる方法がわかりません。そこで、CPUに載っているコアのみで並列化します(Xeon Phiなら簡単なのでしょうか→追記参照)。

一番外側の、0から(1<<25)-1まで変化する変数iのループをOpenMPで並列化します。変数iは上の図の緑の部分(カンで5個にしました)を各数5ビットで表現し、つなげたものです。マスに入りうる数は1から25までなので、5ビットというのはちょっと冗長ですが、とりあえずはよしとしましょう。

一番外側の、0から(N – 3) * N * N * N * NN^4 + N^3 + 2N^2 + 3N + 4から(N – 4)N^4 + (N – 1)N^3 + (N – 2)N^2 + (N – 3)N + (N – 4)まで変化する変数iのループをOpenMPで並列化します(schedule(guided)では遅くなります。schedule(auto)はVisual C++でサポートされたら試します)。変数iは上の図の緑の部分(カンで5個にしました)を掛けたものです。

出力はバイナリ形式で、1つの解に25バイト使います(1つのマスに入る数を1バイトで表現する)。これはちょっと冗長ですが、テキスト形式よりは小さくて速いはずなので、とりあえずはよしとしましょう。

解は全部で2億7530万5224個、1つの解を25バイトで表現するので、(スレッド数と同数できる)出力ファイルのサイズの合計は275305224 x 25 = 6882630600バイト(約6.4GB)になります。

最初のバージョンの実行時間は以下の通りです。最終的には、先述の通り、もう少し速くなります。

Core i7 4930K(12スレッド・出力先はRAMディスク)
  • Windows 7 64 bit, Visual Studio 2013 Express, 593秒(約10分)(ターゲットはx64。/openmp /Ox /arch:AVX
  • Fedora 20 64 bit, Intel C++ Compiler 14.0.2, 471秒(約8分)-fopenmp -O3 -xHost
  • Fedora 20 64 bit, GCC 4.8.2, 583秒(約10分)-fopenmp -O3 -march=native
Core i7 4700MQ(8スレッド・出力先はSSD)
  • Windows 7 64 bit, Visual Studio 2013 Express, 1156秒(約20分)/openmp /Ox /arch:AVX

4535786569大森清美『魔方陣の世界』(日本評論社, 2013)(参考文献リストあり・索引あり)を見たら、a+b+c+d+e=65のとき、(26-a)+(26-b)+(26-c)+(26-d)+(26-e)=65なので、解の、すべての数xを(26-x)に置き換えたものもやはり解になるということが載っていました。変数x7を13以下に限定して、「x17 < 13 && x19 < 13」のときのcountsの増分を2にすれば、私のコードでもこの知識を活用できますが、やっても速くはなりませんでした。この知識を使えばもっと速くなるでしょう(ここでは試しませんが)。コメントでご指摘いただいたように、この知識を使って、真ん中のセルに入る数字を1から13までに限定し、そこが13ではない解が見つかったら、すべての数xを(26-x)に置き換えたものも解として出力するようにするとさらに速くなります(同条件でちょうど6分)。

『魔方陣の世界』では、この問題のためのコードも紹介されていますが、並列化されていないこともあって、解の「数」を調べる場合は約5000秒(確認済み)、全解を出力する場合は約3日(未確認)と、あまりふるいません。

この問題は、パソコン・プログラミングに最適の題材である。(p.111)

今日では、5次方陣の総数検索問題は、パソコンに最適な題材となった。(p.124)

パソコンに最適とも、スパコンに不適とも思いませんが、興味深い題材であることは確かです。

追記

  • 正解の数(2億7530万5224個)を知っているから速いのか? 正解の数は1981年にはすでに知られていましたが、ここで試した方法では、その知識は使っていません。ディスクの空き容量は小さくてよいことがわかっているとか、下に書くような理由で、正解が既知だと試すのが気楽だということはあります。
  • 結果の正しさをどうやって確認したのか? 確認していません。解の数は既知なので、それと同じ数が出てくればまあいいかなと。正しさを確認するためには、(1)得られたものが本当に解であること、(2)結果に重複がないこと、(3)すべての場合を調べていること、の確認が必要です。(1)はループの最も内側で解になっているかどうかをチェックすることによって、(2)は得られた解をハッシュテーブル等に格納することによって確認できますが、ある程度のメモリと時間(上のマシンだと約200秒)が余分に必要です(コード)。(3)はここでは難しいですね。
  • アルゴリズム? 穴埋め問題の穴を多重for文(笑)で埋めているだけなので、アルゴリズムというほどのものはありません。(参考:Puzzles for Hackers
  • 10分くらいならやってみようかなという人が、きれいな書き方やGPUで解く方法、効率的な方法を見つけてくれればと思います。(参考:Toy problemsは役立たずか
  • Xeon Phiなら(ほぼ)そのままのコードが動いて、計算は5分で終わるそうです。(スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙をXeon Phiで試す - パラレルに恋して