2011-04-07

マラソンマッチ68 美しいクロスワード

TopCoder Marathon Match 68 BeautifulCrosswordの意訳です。
翻訳間違ってる箇所があったら、ごめんなさい。
　
原文は、下記になります。
http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14495&pm=11353

問題の概要

ここにN×Nマスの板と、単語リストがある。
これらの単語のみを使って、板の上に、より美しいクロスワードを作ることが、あなたの使命だ。

注意点

・　マス上に２つ以上の文字が連続する時、それが垂直（上から下）であっても水平（左から右）であっても、単語と見なされる。単語は単語リストにあるものしか存在してはならない。
・　マス上におかれたアルファベットは、少なくとも１つの単語の一部である必要がある。
・　各単語は、１回きりしか使えない。

クロスワードの美しさの基準……４つの部分スコア

充填率スコア：　アルファベットが埋まっているマス数　／　全マス数
　
行列使用率スコア：　使われている列数×使われている行数　／　（全行数＋全列数）
　
※　使われている＝列または行に属するマスのうち、１つ以上にアルファベットが刻まれている。
　
対称スコア：
【上下反転／左右反転／９０度ずつの回転】を行った時に、各点が移動する８カ所を同一グループと見なす。
　
・　この８カ所全てがアルファベット、または全て空白なら、１。
・　８カ所中７カ所がアルファベットまたは、１カ所だけがアルファベットなら、０．５。
・　８カ所中６カ所がアルファベットまたは、１カ所だけがアルファベットなら、０．１。
　
のそれぞれでグループを点数付けし、それらを平均したものが、対称スコアとなる。
　
なお、角の対角線上や、Nが奇数の場合の中央列／中央行では、８カ所ではなく４カ所１グループとなる。
また、Nが奇数の場合の中心点では１カ所１グループとなる。
この場合、アルファベット数を２倍または８倍することになる。
（つまり、Nが奇数の場合の中心点は、常に、全てアルファベットまたは全て空白となり、ポイント１となる）
　
交差スコア：　交差セル数　／　アルファベットが埋まっているセル数
交差セルとは、垂直と水平の両方で、単語のアルファベットとして使われているセル。

テストケースごとの最終スコア

テストケースごとに4つの値からなる配列weightsが与えられ、それを用いて以下の様に最終スコアを計算する。
　
最終スコアの計算式：
A*weights[0] + B*weights[1] + C*weights[2] + D*weights[3]) / (weights[0] + weights[1] + weights[2] + weights[3]
A: 充填率スコア
B: 行列使用率スコア
C: 対称スコア
D: 交差スコア
　
なお、無効な回答は０点となる。

総合スコア

総合スコアは、各テストケースの最終スコアの合計となる。
（試合中のランキングでのテストケースは１００問、試合終了後のシステムテストでのテストケースは１０００問でした）

実装すべきメソッドの引数と戻り値

vector generateCrossword(int N, vector words, vector weights);
　
戻り値は、完成したクロスワードの各行を文字列として入れた配列。
　
Nは20〜100の整数。（ただし、テストケース０のみ、Nは11。
weightsは（前述の通り）４つの要素からなり、各要素の値は1〜10の整数。
　
wordsの各単語は、全て大文字アルファベット。
なお、wordsに使われる可能性のある単語は、あらかじめ公開されている。
http://www.topcoder.com/contest/problem/BeautifulCrossword/words.zip

補足

ローカル環境にてテスト可能なテスターが、与えられる。
http://www.topcoder.com/contest/problem/BeautifulCrossword/manual.html
　
スコアリングの詳細について上記であいまいな場合は、テスターのソースコードを読めば一意に分かる。
また、メモリやソースの長さ等は得に制限ない。（ただし、動かすテストサーバー自体のメモリは有限である）
ただし処理時間は１問につきサーバー時間で１０秒で、それ以上かかると処理が打ち切られ、無効な回答（０点）となる。

例題

原文をお読み下さい。

2011-02-28

囲碁パターンマッチング範囲のメモ書き

現在趣味で作っている囲碁AIですが、着手優先度用のマッチングには、以下の３段階でzobrist hashingを用いる予定。

□□□□□□□
□□□■□□□
□□■■■□□
□■■☆■■□
□□■■■□□
□□□■□□□
□□□□□□□

□□□□□□□
□□■■■□□
□■■■■■□
□■■☆■■□
□■■■■■□
□□■■■□□
□□□□□□□

□□■■■□□
□■■■■■□
■■■■■■■
■■■☆■■■
■■■■■■■
□■■■■■□
□□■■■□□

2011-02-03

cssコンパイラを自作してみた

サイトデザインの技術的な部分について、ようやく取りかかることにしました。
要は、htmlとかcssとか、その辺の上手な活用法についてです。
　
普段、基本的には、なるべくIDとクラスに対してスタイル指定する様にしています。
　
クラスがIDと異なる特徴として、以下の２つがあります。
　
・同じクラスの要素が複数存在可能。（同じIDの要素は、複数存在は推奨されない）
・１つの要素に複数のクラスを指定可能。
　
こんな特徴があるものだから、クラスは以下の様な使い方をします。
　
A. ２個以上登場しうる同じ意味を持つDOMの、デザイン指定
B. 動的に意味が変化するDOMの、デザイン指定（addClassやremoveClassでON/OFFする）
C. 頻度の高い部分デザインの指定を、DOMに対して補助的に行う
　
AとBは正しい使い方だと思うのですけれども、
Cの用途で使おうとすると、html側にデザインを持っていることになります。
　
もう何年も前から、この辺が気に入りませんでした。
　
しかし、CにはCの需要があるというか。
同じことを２度書くべきではないという意味において、Cにも正当性があります。
　
たとえばヘッダ領域／サイドメニュー領域／ボディ領域／フッタ領域がそれぞれID指定divタグで定義されている時、このうちのサイドメニュー領域とフッタ領域のみ、角を丸くしたいとします。
　

border-radius:5px;

　
このとき、上記の指定をcss側に対して、サイドメニューとフッタのIDに対して追加したとします。
　
しばらくして、5pxではなく7pxに変更したくなったとします……ここで２箇所変更するのが、私は嫌です。
　
しかしながら、角丸のクラスを定義して、html側でサイドメニュー領域とフッタ領域に角丸クラスの指定を書くのも、デザインをhtml側に書くことになるので、嫌です。
　
じゃあ、どうすれば嫌じゃないかというと、css側の各スタイル指定が、mixinなり多重継承なりを指定可能であれば、これらの問題は解決します。
　
そこでちゃちゃっと、css コンパイラを作りました。
　
たとえば以下の様なcssもどきを用意します。
　

@charset "utf-8";

$aa {
　　bb: cc;
　　dd: ee;
}

$ff {
　　dd: gg;
　　hh: ii;
}

#jj {
　　$import: aa, ff;
　　kk: ll;
}

　
このcssもどきをcss コンパイラに通すと、以下の様なcssを吐き出してくれます。
　

@charset "utf-8";

#jj {
　　bb: cc;
　　dd: gg;
　　hh: ii;
　　kk: ll;
}

　
ほんのひと手間、こういうものを作っておくことで、色々と楽になるんじゃないかなぁと思いました。

2011-01-16

PHPExcelのキャッシュ機能について

PHP上でExcelを使えるPHPExcelというライブラリについて勉強中。
　
PHPExcel
http://phpexcel.codeplex.com/
　
これを使って、以下の様なプログラムを書く。
　

<?php
set_include_path(get_include_path() . PATH_SEPARATOR . './PHPExcel-1.7.5/Classes/');

include 'PHPExcel.php';
include 'PHPExcel/IOFactory.php';

$objReader = PHPExcel_IOFactory::createReader('Excel5');
$objPHPExcel = $objReader->load('sum.xls');

$sheet = $objPHPExcel->getActiveSheet();
$a1 = $sheet->getCell('A1');
$b1 = $sheet->getCell('B1');
$c1 = $sheet->getCell('C1');

echo "A1: " . $a1->getCalculatedValue() . "\n";
echo "B1: " . $b1->getCalculatedValue() . "\n";
echo "C1: " . $c1->getCalculatedValue() . "\n";

$b1->setValue(7);

echo "A1: " . $a1->getCalculatedValue() . "\n";
echo "B1: " . $b1->getCalculatedValue() . "\n";
echo "C1: " . $c1->getCalculatedValue() . "\n";

　
A1=1, B1=3, C1=A1+B1のような内容のsum.xlsを用意して、このプログラムを動かすと、次の様な結果になる。
　

A1: 1
B1: 3
C1: 4
A1: 1
B1: 7
C1: 4

　
なんで？　２回目のC1は8になって欲しいのに。
キャッシュが効いてるんかな？　と思ってデバッグモードで１行ずつ動かしていくと、不思議と２回目のC1は8という結果が出る。
　
ん？？　動作時間でキャッシュがクリアされる設計？
……とりあえず、１プロセス内で人間との対話をすることが少ないPHP専用のライブラリで、時間依存でキャッシュクリアされる設計には正直納得がいかないけれども、B1に7をセットした後に以下の行を付け足すことで、キャッシュクリアできることが分かりました。
　

PHPExcel_Calculation::getInstance()->clearCalculationCache();

　
これで動かすと、次の通り、成功。
　

A1: 1
B1: 3
C1: 4
A1: 1
B1: 7
C1: 8

　
なお、clearCalculationCacheを使う代わりに、include等が全部終わった後の初期化フェーズに以下の行を入れることでも、正しい結果が得られました。
　

PHPExcel_Calculation::getInstance()->setCalculationCacheEnabled(false);

　
setCalculationCacheEnabled(false)は、キャッシュクリアじゃなくて、キャッシュ機能ごと無効にしてしまう機能ですね。
キャッシュ自体は諸々の理由により必要な機能だと思うので、clearCalculationCacheを使うことをオススメ致します。

2011-01-10

SPOJ-PRIC 素数判定１位奪還！

やりました。
SPOJ-PRICの１位を、取りました。
2009年8月にハンガリーのRobert Gerbiczさんが１位を取ってから１年と５ヶ月ぶりに、日本が奪還したことになります。
アルゴリズム的には、前回の日記の時から何も変わっていません。
　
SPOJ PRIC Ranking
http://www.spoj.pl/ranks/PRIC/
　
あの後、各小素数ごとにD^{-1}をかけて現在位置を求める処理をmulなしで実装することに成功しましたが、速度が一切改善しなかったため、実はボトルネックが別の場所にあったことに気が付きます。
（私がボトルネックの箇所を間違えるのは稀です）
　
33Mの結果表に直接エラトステネスを適用すると、ページフォルトが起きまくって使い物にならないのは誰もが真っ先に気付くことで、そのため、一旦作業領域上でエラトステネスの篩を実行し、一区切りついた所で結果を転写しております。
　
ここでボトルネックになっていたのは、以下の２点でした。
　
・小さな素数（３とか）の倍数の塗り潰し
・作業領域から結果領域への転写
　
そのため、小さな素数である3と7について、特別な対策を取りました。（5は、X法に使われているXの素因数であったため、まとめ試し割りで除外されています）
　
3と7の合成数は21周期なので、21個まとめて転写するようにしました。
この21個のうち9個は、3の倍数または7の倍数であるため、最初から転写を免れます。
そのため、エラトステネスの篩を行う際、3と7については篩を行わなくて良いことになりました。
これら２つの事柄の両方が速度アップに結びついたことと、まとめforループが若干速度アップに繋がり、１位に浮上しました。
　
とりあえず嬉しいんですけど、１位が取れたそのこと自体よりも、生活に集中できることが一番嬉しいです。
　
今回素数判定に着手した大晦日から現在までだと、１０日間。
最初にSPOJ-PRIC(素数判定)に取り組んだ2008年1月7日からだと、実に３年間かけての１位です。
その３年間、素数判定のことが頭の片隅から消えない日はありませんでした。
これで今日からは新しいことに取り組めるというものです。
　
p.s.
そういえば、素数のことを【塗り残したタイル】と表現しているのは、Googleで検索した範囲だと、日本中では私一人の様です。
これは、エラトステネスの篩プログラムの動く様子が、タイルを塗っている様に見えて、塗らなかったタイルが素数となることに由来します。
　
Wikipediaのエラトステネスの篩の右側の動画のイメージです。
http://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
　
いやまぁ、なんというか。
フェルマーテストを使っていた時も、試し割りしている時も、X法上のエラトステネスの篩を使ってる時も、
脳内では常にタイルが塗られ、何が塗り残されるのかを考えながらだったので、
【塗り残したタイル】という表現は、非常にしっくり来るし、気に入っております。

2011-01-04

素数のまとめとか

SPOJのPRICにて２位取りました。
　
SPOJ - Prime Checker - Ranking
https://www.spoj.pl/ranks/PRIC/
　
が……１位が取れませんので、日本勢頑張ってねということで、一旦バトンタッチします。
（ネタバレが嫌いな人は、読まないでください）
　
また４月ぐらいになったら時間取れるので、それまでに他の方々にアイデアを出しておいて欲しかったりとか、あるいは２位の僕だけでなく、１位も抜いちゃって欲しいですとの願いをこめて、日記にまとめておきます。
　
■主だったアイデア
　
僕の２位実装は、独自のアイデアは何一つありません。
ネットに出回ってるアイデアを繋ぎ合わせただけです。
　
一番大切な記事は、以下の２つ。
　
PRoxy Diary - 2007-12-27 [ICPC] Prime Checker
http://mono.kmc.gr.jp/~oxy/d/?date=20071227
　
に出てくる26418法と、
　
菊やんの雑記帳 - 2010-02-28 ヒープソートによる素数判定？
http://d.hatena.ne.jp/kikx/20100228
　
に出てくる等差数列上でもエラストテネスのふるいが使えるという事実。
（ヒープソートは重要じゃないので割愛）
　
それから、そこまで大切じゃないけど参考にした記事として、sheさんの以下のMontgomery Reductionの記事。
　
兼雑記 - 2007-12-29 [Program] PRIC 21:20
http://d.hatena.ne.jp/shinichiro_h/20071229
　
■26418法の亜種
　
26418法は亜種が沢山存在しており、oxyさんの132090法より良いものも、探せば見つかります。
　
2008年9月21日に8.35秒を出した時は、26418法（亜種）＋フェルマーテスト（＋Montgomery Reduction）の組み合わせを最適にチューニングしたものでした。（別途、試し割も使ってますが、これは基本技なので割愛）
このときの26418法亜種には、6515670法（＝2*3*5*7*19*23*71）を用いています。
　
菊やんさんの等差数列上のエラストテネスのふるいを使うにあたっては、310270法（＝2*5*19*23*71）を使っています。
　
ちなみに、26418法の超亜種として2法が存在していて、こいつはpricで問題となる数列の逆関数化として使います。
　
■26418法の最適亜種の求め方
　
iを1から65536ぐらいまで変化させつつ、(i*1234567890) mod Rの値をしらみつぶしに見ていきます。（ただし、R=2^{31}）
単純に試し割り目的で使う場合は、小さな素数を沢山約数として持っている方が有利（3の倍数であることはほぼ必須）で、結果として6515670法（＝2*3*5*7*19*23*71）が最も有利という結論でした。
しかし、等差数列上のエラストテネスのふるいでは、等差数列がいかに長続きするかが重要（33,333,333個の制限と、2^31の制限の２つがある）なので、必ずしも沢山の素数を含んでいなくても良いわけです。
でも幸運なことに、そうやって見つけた一番良い条件のものが、5と19と23と71の倍数だったので、これらについては26418法の、まとめて試し割り的な恩恵を受けております。
　
■等差数列上のエラストテネスのふるい
　
考え方は菊やんさんのサイトに書かれているので割愛します。
公差をDとしたときの、各素数を法とする公差の逆数（D^{-1} mod p)は、拡張ユークリッドの互除法を使って求めます。
このD^{-1}をかけることで、現在の位置が求まり、そこから次の倍数地点が分かります。
　
ここまでの実装で、だいたい４秒前後が目安です。
　
■D^{-1}とRとR^{-1}
　
Montgomery Reductionの処理自体でR^{-1} mod pがかかってしまうので、これにR mod pをかける処理を加えなきゃいけません。
なので、(D^{-1}・R) mod pを、前処理時点で求めておけばokです。
　
これで3.2秒前後になると思います。
　
■その他の工夫
　
・３３Ｍの出力を高速化する試み
・作業メモリを効率的に使う試み（ページ切り替えのコスト削減）
　
やってない・できなかった試み
　
・mmap　（stdoutに対して適用できなかった…適用する方法を知ってる人は情報下さい）
・前処理のプリプロセッサ化　（0.1秒切ってるので、後回しにしてます）
・Barrett Reduction
・SSEとMMXによる高速化　（spojサイトはSSE2に対応していません。SSE1とMMXになら対応しているので、この辺を使って高速化できないかなぁと……思ったのですが、思いつかないので、まだ試してません。ちなみにSSE2にさえ対応してもらえたら、フェルマーテストが２倍早くなる実装を既に作ってあったりします……もうフェルマーテストはしてないので、何の意味もないですが）
　
■spojのcpuid
　
pricでは、１回のプログラム実行につき0〜33,333,333の値を返し、その結果を見ることができます。
（全ての答えを求めておいて、最後に出力する文字数を変える）
私は利便上、0〜65535の値を返す様にして、１回の実行につき16bitの情報をサーバーから抜き出す様にして、内部情報を得る様にしています。
　
と言っても、spojから抜くべき情報はcpuidぐらいですね。
　
2011年元旦時点のspojのcpuidの結果を、以下にまとめます。
　
eax=0でcpuidを呼び出した時の結果：

	上位	下位
eax	0	2
ebx	30062	25927
ecx	27749	29806
edx	18789	28265

　
ebx->edx->ecxの順に下位からASCIIコードとして読んでいくと、GenuineIntelと読めます。
　
eax=1でcpuidを呼び出した時の結果：

	上位	下位
eax	0	1697
ebx	0	3
ecx	0	0
edx	899	64511

　
eax=1の時のedxの値から、SSE1とMMXは使えます。SSE2は使えません。
おそらくPentium3です。
　
（なお、2008年9月にやってみた時も、ほぼ同じ結果だったと記憶しています）

2010-12-03

uupaa.jsの不具合報告

Twitterの@uupaaさんのメールアドレスが分からないので、
日記で不具合報告を書くことにします。
　
まぁ、ずっと更新されてない日記なので、こんな使い方でも良いでしょう。
　

<table>
<tr id='xx'><td>C</td><td>D</td></tr>
</table>

　
以上のようなHTMLがあって、スクリプト内にて、以下の様な処理を行います。
　

uu('#xx').add('<tr><td>A</td><td>B</td></tr>', 'prev');

　
すると、OperaとSafari以外のブラウザ（IE, firefox, Chrome）にて、
予想と異なる結果になりました。
（各ブラウザでどうなるかは、各自やってみてください）
　
それで、少しソースコードを変えて、以下の様にしてやると、
失敗していたブラウザでも、予想と同じ結果になりました。
　

uu('#xx').add(uu.node.bulk('<tr><td>A</td><td>B</td></tr>'), 'prev');

　
で、uupaa.js初心者な私としては、
これはこういうものだと最初のうちは思ったのですが、
どうやら違うことに気が付きます。
　
これはバグだ――そんな予感がして、ちょいと調べてみました。
バグな気がしたのは、addのみの処理の場合でも、その中では
uu.node.bulkを呼び出していたからです。
　
addの第二引数は、内部関数のuunodeaddの中では
positionという変数に収納されます。
　
そして以下の様な処理で、指定した場所に追加する処理が書かれています。
　

        switch (uunodeadd.pos[position] || 8) {
        case 1: reference = context[_parentNode][_firstChild];
        case 2: reference || (reference = context);
        case 3: reference || (reference = context[_nextSibling]);
        case 4: context[_parentNode].insertBefore(node, reference); break;
        case 5: reference = context[_firstChild];
        case 8: context.insertBefore(node, reference);
        }

uunodeadd.pos = { first: 1, prev: 2, next: 3, last: 4, "./first": 5, "./last": 8 };

　
uu.node.bulkが内部的に呼ばれているのは、その少し前……
下記の場所のuunodebulkが、それにあたります。
　

    var nodes = !source ? [newNode()]        // [1] uu.node.add()
              : isArray(source) ? source     // [4] uu.node.add([<div>, <div>])
              : source[_nodeType] ? [source] // [3][6] uu.node.add(Node or DocumentFragment)
              : !source[_indexOf]("<") ? [uunodebulk(source, context)]
                                             // [5] uu.node.add(HTMLFragmentString)
              : [newNode(source)],           // [2] uu.node.add("p")
        reference = null, i = 0, iz = nodes.length, node, rv;

　
uu.node.bulkを予め呼び出しておいた場合と、
ほとんど同じ扱いをされていることになるのですが、
唯一違うのはcontext、こいつの中身が、結果を変えていると言えます。
　
で……contextが何者なのか、調べました。
　
uu.node.bulkを直接呼び出した場合、
contextは'div'と同じものとして動作します。
そしてadd経由で呼び出されていた時は、'TR'になっていました。
　
uunodebulk内の大まかな流れとしては、以下の様な感じです。
　
1. contextをdoc.createElementする。
2. 1で作ったノードのinnerHTMLに、作りたいhtmlテキストを流し込んでやる。
3. ノードから、子要素を全て抜き出す。
　
つまり、具体例で言うと'<tr><td>A</td><td>B</td></tr>'の親ノードとして、
contextを使ってノードを作っている、ということです。
　
divの時にうまく行って、TRのときにうまくいかないのは、
trタグの中にtrタグを生成するのがDOM的に不正だからでしょう。
　
そう、本当にあるべきcontextは、TRではなく、TABLEなわけです。
　
もうお分かりでしょうか。
positionによって処理分岐が発生するのは、要素を収納する時だけでなく、
context（文脈）を特定する時にも、positionによる分岐が必要なのです。
　
ここまで書けば、あとはこれだけ立派なjsライブラリを作った@uupaa氏が、
良い感じに修正してくれることだと思います。
　
それにしても、Javascriptド素人の私が、
ちょっと読んだだけで原因を特定できるぐらい読みやすいコードを書くuupaa氏、
流石ですね。
　
ということで、原因だけ特定しておいて、この日記を終えます。
アデュー。