ICFPC 2014 参戦記

ICFP Programming Contest 2014 に @cos65535 さん, @qwerty__ さん, @seikichi さんとチームを組んで参加した。

25日(金)

  • 21:00 コンテスト開始。問題を読み始める。
    • パックマンみたいなゲームの AI を書け、という問題。
    • ただしゲームの AI は GCC という謎の LISP マシンの上で動く。(それ専用の機械語が定義されているので、それを使って AI を書かないといけない)
    • また、ゴーストの AI も書く必要がある。ゴーストの方は GHC というわりと普通な感じの機械語の上で動くが、メモリが 256 バイトしか使用できず、また、プログラムも 1024 命令しか実行できない。
  • 21:30 夕食を食べに行く。
  • 23:40 seikichi さんが到着。

26日(土)

  • 0:00 方針を決める。
    • AI を直接 GCC (与えられた Lisp マシンにおける機械語) で書くのはかなりキツい。高級言語からコンパイルしたい。
    • 機械語Lisp っぽいので Lisp からコンパイルするのが自然なのではないか。Lisp なら構文解析が楽そうだし。ということで、Lisp から GCC へのコンパイラを作ることに。
    • また、与えられた機械語で配列(定数時間で任意のインデックスに読み書きもの)が実現できないことが判明する。2分木を使った配列もどきライブラリを作らないといけないという話になる。
    • ということで、以下の4つの作業を分担してやることになった。
      • Lisp から GCC へのコンパイラの作成
      • GCC のシミュレータの作成
      • ゲームのシミュレータの作成
      • Lisp 用のライブラリの作成
    • 自分はコンパイラを作ることになった。
  • 2:00 GCC の仕様書を読みながら幾つかのプログラムを手コンパイルしてみる。
    • DUM と RAP の意味がいまいちわからないが、一応コンパイラはなんとか作れそうな気分になる。
    • 実装言語を決める。速度はどうでも良さそうなので Python にした。
  • 5:00 構文解析まで実装終了。寝る。
  • 11:00 起きる。
  • 13:00 (+ 1 1)コンパイルできるようになる。
  • 15:00 define の実装でつまる。
    • 以下のコードをどうやってコンパイルしたらいいかわからない。
      ;; カリー化された add
      (define add (lambda (x) (lambda (y) (+ x y))))
      ; 部分適用
      (define inc (add 1))
      ;; 42 が返る。
      (inc 41)
      
  • 16:00 DUM で予め領域を確保しておき、後から ST でクロージャを入れていけば define が実装できることに気付く。
    • lambda の中で define してもちゃんとレキシカルスコープ的に正しく動作する。
  • 17:00 lambdaの実装が完了。
  • 17:20 ifの実装が完了。
  • 17:30 ラベルをアドレスに変換する部分を実装し、Lisp コンパイラが完成。
  • 20:30 seikichi さんが Lisp でそれっぽい AI を実装し、ライトニングラウンドにサブミット。

27日(日)

土曜日の反動でだらだらしてしまった日。

  • 0:00 seikichi 先生が Gauche の macroexpand を使ってマクロを展開してからコンパイラに投げるプログラムを書く。
    • これにより、define-macroで簡単に構文を拡張できるようになる。
    • let, and, begin, cond などのおなじみのマクロが自由に使えるようになる。
    • さすが Lisp …。
  • 1:30 末尾関数呼び出しの最適化を実装。
  • 2:00 寝る。
  • 10:00 起きる。
  • 14:00 コンパイラデバッグ + (define (foo x y) ...) のような構文の実装。
    • かなり普通の Scheme っぽく書けるようになってきた。ぱっと見では見分けがつかない。
  • 15:00 コンパイラでやることがなくなってきたので、GCC のシミュレータのデバッグを手伝う。
  • 18:00 GCC のシミュレータが動くようになる。
    • cos さんが作ったゲームのシミュレータと合わせると、Lambda Man の AI を動作させる環境が完全に揃ったことになる。
  • 20:00 再びやることがなくなってたので AI の作成を始める。
  • 21:30 BFS をする AI を書いた。が、バグっていて動かない。
  • 22:30 Scheme の関数の引数の数を間違っているところがあったのを修正。
  • 22:30 ゴーストが弱い場合はマップをクリアできるようになった。
    • AI は動くようになったがやけに重い。最初はシミュレータのパフォーマンスが悪いのかと疑ったが、実はそうではなく、BFS の実行に時間がかかりすぎているようだった。
    • 32x32 程度のマップを BFS するのに 170 万命令かかっていた。AI の 1 ステップの命令数の上限が 300 万命令程度なので、これはかなり危ない (というか 256x256 のマップが来たら即死する)状況だということを認識する。
    • とりあえず、適当に最適化をしてみたが、ほとんど改善しなかったので、qwerty さんにプロファイラの実装をお願いする。

28日(月)

  • 2:00 プロファイラのおかげで組み込み関数の呼び出しに時間がかかっていることが判明したので、コンパイラを改造して最適化。
    • この改修で 170 万命令 → 140 万命令。
    • 次のボトルネックvector-refだが、作者が寝てしまっていたので、放置して寝ることにした。
  • 8:30 起きる。
  • 10:30 seikichi 先生がひたすら関数をマクロでインライン展開する。
    • 140 万命令 → 40 万命令。
  • 11:00 移動
  • 13:30 BFS AI のループ回数に上限をつけた。これで 256x256 のマップでも一応動作するようになった。
  • 14:00 近くにゴーストがいるときはゴーストからに逃げるようにした。
    • これで結構 AI っぽくなった。
  • 14:30 ゴーストを殺せるときは殺しに行くようにした。
  • 18:40 方向にスコア付けして一番高いスコアの方向に行くようにした。
    • 複数のゴーストに同時に襲われたときに逃げられる確率が上がった。たぶん。
    • Lambda-Man Hall of Fame の ghostbusters でランクインした。
  • 19:00 cos さんがいつの間にか DFS をするゴーストの AI を書いていた。
  • 19:45 フルーツを食べに行くようにした。(by seikichi 先生)
  • 20:30 パラメータの調整など
  • 20:50 AI 提出!!

まとめ

  • 最初はどうなることかと思ったが、意外とまともな AI を書けたような気がする。
    • やはり高級言語は偉大。
    • あと macroexpand 偉い。
  • プロファイル大事。
  • コンパイラのエラーチェックを真面目に作っておいたおかげでデバッグコストが結構低かった。
  • qwerty さんの予約してくれたホテルが快適だった。環境大事。

VirtualBoxにArch Linuxをインストールしたときのメモ

VirtualBoxにInstall media 2012.08.04 を使用してArch Linuxをインストールしたときのメモ.VMのディスクサイズは40GB,メモリは4GB.メモリサイズが1GB以上あるときはswap作らないほうがパフォーマンスがでるらしいのでswapなし.

いつの間にかインストーラが削除されていてArch Linuxのインストールが面倒になってました.

# loadkeys jp106
# parted
(parted) unit MiB
(parted) mklabel msdos
(parted) mkpart primary 1 10241
(parted) mkpart primary 10241 20481
(parted) mkpart primary 20481 20581
(parted) mkpart extended 20581 40959
(parted) mkpart logical 20582 40959
(parted) quit
# mkfs -t ext4 /dev/sda1
# mkfs -t reiserfs /dev/sda2
# mkfs -t ext2 /dev/sda3
# mkfs -t ext4 /dev/sda5
# mount -t ext4 /dev/sda1 /mnt
# mkdir /mnt/{var,boot,home}
# mount -t reiserfs /dev/sda2 /mnt/var
# mount -t ext2 /dev/sda3 /mnt/boot
# mount -t ext4 /dev/sda5 /mnt/home
# vi /etc/pacman.d/mirrorlist
日本のサーバをリストの一番上に持ってくる
# pacstrap /mnt base base-devel
# pacstrap /mnt grub-bios
# genfstab -p /mnt >> /mnt/etc/fstab
# arch-chroot /mnt
# vi /etc/hostname
arch-vm
# ln -s /usr/share/zoneinfo/Asia/Tokyo /etc/localtime
# vi /etc/locale.conf
LANG="en_US.UTF-8"
LC_COLLATE="C"
LC_TIME="en_DK.UTF-8"
# vi /etc/locale.gen
以下の3行のコメントアウトを解除
en_DK.UTF-8 UTF-8
en_US.UTF-8 UTF-8
ja_JP.UTF-8 UTF-8
# locale-gen
# mkinitcpio -p linux
# mv /boot/grub /boot/grub-legacy
# mkdir /backup
# dd if=/dev/sda of=/backup/mbr-backup bs=512 count=1
# modprobe dm-mod
# grub-install --target=i386-pc --recheck --debug /dev/sda
# mkdir -p /boot/grub/locale
# cp /usr/share/locale/en\@quot/LC_MESSAGES/grub.mo /boot/grub/locale/en.mo
# grub-mkconfig -o /boot/grub/grub.cfg
# vi /etc/rc.conf
次の行を追加
KEYMAP=jp106
# passwd
rootパスワードを設定
# exit
# umount /mnt/{var,boot,home,}
# reboot
# pacman -S zsh vim tmux git openssh sudo
# pacman -S virtualbox-archlinux-additions
# modprobe -a vboxguest vboxsf vboxvideo
# vim /etc/modules-load.d/vbox.conf
vboxguest
vboxsf
vboxvideo
# pacman -S dbus
# vim /etc/rc.conf
DAEMONSにdbusを加える
# rc.d start dbus
# pacman -S xorg
# pacman -S gnome
# pacman -S gdm
# pacman -S xorg-xinit xterm
# vim /etc/inittab
id3:initdefault: をコメントアウトして
id5:initdefault: のコメントアウトを解除
x:5:respawn:/usr/bin/xdm -nodaemon をコメントアウトして
x:5:respawn:/usr/bin/gdm -nodaemon のコメントアウトを解除
# vim /etc/skel/.xinitrc
VBoxClient-all &
exec ck-launch-session gnome-session
# adduser
普段使い用ユーザを追加
# visudo
今追加したユーザをsudoerにする

ノートPCのVirtualBox上にDebian環境を作る

やりたいこと

  • ホストOSはWindows,ゲストOSはDebian,仮想化にはVirtualBoxを使用
  • インターネットにはNATで接続
  • DebianにはGUI環境をインストールせず,常にPuTTYを通じて使用する
  • DebianのファイルをSambaを使ってWindowsと共有する

やったこと

  1. VMのネットワークの設定
    インターネットにはNATで接続したいので,アダプタ 1 にはNATを割り当てます.さらに,ポートフォワーディングの設定でホストポート2222からゲストポート22へのポートフォワードの設定を追加します (IPの欄は空).また,ホスト-ゲスト間の通信のためにアダプタ 2 にホストオンリーアダプタを割り当てます.
  2. Debianのインストール
    普通にインストールします.途中にどのアダプタでインターネットに接続するかを聞かれるので,最初のアダプタを選びます.
  3. IPアドレスの設定など
    /etc/network/interfaces を以下のように編集します.
    # The loopback network interface
    auto lo
    iface lo inet loopback
    
    # The primary network interface (NAT)
    auto eth0
    allow-hotplug eth0
    iface eth0 inet dhcp
    
    # The secondary network interface (Host-only)
    auto eth1
    iface eth1 inet static
    address 192.168.56.102
    netmask 255.255.255.0
    
    次にネットワークを再起動します.
    sudo /etc/init.d/networking restart
  4. Samba の設定
    まず apt で Samba をインストールします.インストール中にWORKGROUPを聞かれるので,WindowsのWORKGROUPと同じものを指定します.
    sudo apt-get install samba
    /etc/samba/smb.conf を編集します.diff はこんなかんじ.
    --- a/samba/smb.conf
    +++ b/samba/smb.conf
    @@ -114,7 +114,7 @@
     # This boolean parameter controls whether Samba attempts to sync the Unix
     # password with the SMB password when the encrypted SMB password in the
     # passdb is changed.
    -   unix password sync = yes
    +   unix password sync = no
    
     # For Unix password sync to work on a Debian GNU/Linux system, the following
     # parameters must be set (thanks to Ian Kahan < for
    @@ -239,15 +239,15 @@
    
     # By default, the home directories are exported read-only. Change the
     # next parameter to 'no' if you want to be able to write to them.
    -   read only = yes
    +   read only = no
    
     # File creation mask is set to 0700 for security reasons. If you want to
     # create files with group=rw permissions, set next parameter to 0775.
    -   create mask = 0700
    +   create mask = 0644
    
     # Directory creation mask is set to 0700 for security reasons. If you want to
     # create dirs. with group=rw permissions, set next parameter to 0775.
    -   directory mask = 0700
    +   directory mask = 0755
    
     # By default, \\server\username shares can be connected to by anyone
     # with access to the samba server.
    
    Samba のアカウントを作ります.
    sudo smbpasswd -a nojima
    最後に Samba を再起動します.
    sudo /etc/init.d/samba restart
    Windows側のエクスプローラのアドレス欄に
    \\192.168.56.102
    と打ち込んでアクセスできれば成功です.
  5. Windows の hosts ファイルの書き換え
    毎回VMのIPアドレスを打ち込むのは面倒なので,hostsに名前を登録しておきます. C:\Windows\System32\drivers\etc\hosts に以下の行を追加します.(debian-vmのところはVMの名前)
    192.168.56.102    debian-vm
    書き換えに管理者権限が必要だったりするので,管理者権限でメモ帳などを実行し,そこから編集するとよいです.

ポートフォワードについて

PuTTYでVMにアクセスする際にはポートフォワードを用いてアクセスする方が便利です.(つまり localhost の 2222 番ポートにアクセスする) 直接VMにアクセスすると,ノートPCをスリープさせた時に接続が切れてしまいますが,何故かポートフォワードを使ってアクセスすると接続が切れません.どうして接続が切れないのかよくわかりませんが,とりあえず便利です.

アプリケーションのメモ

OSの再インストールに備えてリストアップ.

Windowsで快適なLaTeX環境を構築する

Windowsで快適にLaTeXで論文を書くためのメモ.

LaTeXで論文を書いているときは,
 テキストエディタで.texを編集する → platexでコンパイル → Adobe Readerでプレビュー → 最初にもどる
という流れで論文を書いていくことになるのですが,いちいちコンパイルしたり,Adobe Readerで開いたりするのは面倒なので,.texを変更したら自動的に変更を検出してコンパイルし自動的にプレビューに反映する環境を構築しました.

使用したソフトは

  • w32tex.これがなくては始まらない.abtexinst を使えば何も考えなくてもインストールできます.
  • OMake.いわゆるビルドツール.コンパイルの自動化に使用します.
  • SumatraPDF.PDFビューワ.PDFを変更すると自動的にリロードしてくれます.

です.

以下では書いているTeXファイルを document.tex とし,BibTeXファイルを refs.bib としています.違う名前を使う場合はこれらの名前を置換してください.また,platexやomakeの存在するディレクトリにはパスが通っているものとします.

まず,document.tex や refs.bib が存在しているディレクトリで omake --install を実行して OMakefile と OMakeroot を生成します.Windows 7だといちいちコマンドプロンプトを開かなくても,エクスプローラーのアドレスバーに「omake --install」と打てばそのディレクトリでomakeを実行することができます.

次に,OMakefileの内容を全て消去して以下のように編集します.

LATEX = platex
TETEX2_ENABLED = false
LATEXFLAGS = -interaction=nonstopmode
BIBTEX = pbibtex
DVIPDFM = dvipdfmx
DVIPDFMFLAGS = -p a4

TEXDEPS[] = refs.bib

LaTeXDocument(document, document)

.DEFAULT: document.pdf document.dvi

次に,omake -P --verbose を実行します.このコマンドは,omake を監視モードで起動し,ファイルに変更があった場合は自動的にコンパイルするコマンドです.

次に,document.pdf を SumatraPDF で開いておきます.

後は,document.texテキストエディタで編集して保存する度に,omake が自動的にコンパイルを行い,SumatraPDF が自動的にプレビューに反映してくれます.手動でコンパイルするのと比べて,かなり楽にプレビューを見ることができるようになります.デュアルディスプレイだと,片方のディスプレイで PDF を常に表示しておくと,プレビューを見ながら TeX を編集できて,楽しいです.

ただし,TeXでエラーが出てしまうと,platexモードがデバッガモードに入ってしまって自動ビルドが止まってしまうことがあります.こういうときは,コマンドプロンプトの画面で Enter を押すとたいてい動いてくれます.それでもうまくいかないときは omake をいったん終了させてもう一度起動しましょう.ここらへんがもうちょっと何とかなればもっと楽なのですが,解決策がわからない…… -interaction=nonstopmode を LaTeX の引数に与えればエラー時にデバッグモードに入らないようです.

「サマーインターン2011問題 : Preferred Research」について考えてみる

今更ながら,「サマーインターン2011問題 : Preferred Research」について考えたので,ここにメモ.

問題の概要を箇条書きにすると

  • 長さ n の文字列 s が与えられる
  • s に含まれる文字の中で,出現回数が最も大きい文字を出力せよ
  • ただし,出現回数が最大の文字の出現回数は n/2 より大きい
  • 計算時間は O(n) でなければならない
  • 空間使用量は s を格納するバッファを除いて O(1) でなければならない
  • s を格納するバッファは書き換えてよい

解法1

よく考えると,s をソートしたときに n/2 番目に来る要素は,出現回数が最大の文字であることがわかります.「ソートしたときに k 番目に来る要素」というのは,実際にソートをしなくても O(n) で求めることができ,問題の条件を満たします.C++ の標準ライブラリには nth_element という関数が用意されており,これを使うと簡単に「ソートしたときに k 番目に来る要素」を計算できます.

解法2

次のアルゴリズムを考えます.

for (;;) {
  添字 i を [0, n) からランダムに選ぶ;
  文字 s[i] の出現回数をリニアにカウントする;
  if (s[i] の出現回数 > n/2) return s[i];
}

1回の反復で答えが求まる確率は少なくとも1/2あるので,平均計算時間は

(1 + 1/2 + 1/4 + ...) O(n) = O(n)

となり問題の条件を満たします.

[論文紹介] GConnect: A Connectivity Index for Massive Disk-Resident Graphs

授業で論文紹介したので,ここにメモ.

GConnect: A Connectivity Index for Massive Disk-Resident Graphs』は,巨大なグラフに対してインデックスを作って,辺連結度クエリに高速に答える手法について議論した論文です.以下のような問題を考えます.

巨大なグラフGが与えられる.(例えば,頂点数10万,辺数100万とか)
G内の任意の2点s, tが与えられたとき,sとtの辺連結度を高速に計算せよ.

2頂点の辺連結度というのは,グラフから最小で何本辺を取り除けば,その2頂点を非連結にできるかで定義される量です. 

計算時間を気にしなければ,最大 s-t フローを求めるアルゴリズム(Dinic や Goldberg-Tarjan など)で連結度を計算することができます.しかし,これらのアルゴリズムは記憶領域へのランダムアクセスを要求するため,メモリに格納できないサイズのグラフに対しては非常に遅くなり得ます.情報検索への応用を考えると,(s, t)が与えられたときに,数秒で答えを返さなければなりません.そこで,厳密解を求めることを諦め,近似解を求めることにし,事前に巨大なグラフをメモリに収まるサイズまで圧縮しておくことを考えます.

グラフの圧縮は,辺サンプリングに基づいて行います.下図(論文中の図から引用)のように,グラフ内の各辺に対して,一定の確率 f でその辺をサンプルします.そして,サンプルされた辺による連結成分を縮約します.結果として,頂点数と辺数が小さくなったグラフができます.

20111210154539

なぜこれで辺連結度の近似ができるのでしょうか?まず,辺連結度というのは,グラフの中の辺が比較的疎な部分で決まりやすいという性質を持っています.さらに,グラフの辺サンプリングは,辺が密な部分は,多くの辺がサンプルされ,一つの頂点に縮約されやすく,また,辺が疎な部分は,余り辺がサンプリングされず,縮約もされにくいという性質を持っています.よって,グラフの辺が疎な部分の構造が辺サンプリングによって保存されやすいため,辺連結度を概ね保存したまま,グラフを圧縮できるというわけです.

頂点対(s, t)に対応する,圧縮されたグラフの頂点対が(s', t')であったとします.ここで,s' ≠ t' とします.真のs-t辺連結度が C であるとすると,辺サンプリングによって正しくs-t辺連結度が求まる確率は少なくとも (1 - f)^C あります.(最小 s-t カットに含まれる辺がいずれも辺サンプリングによって選ばれない確率が (1 - f)^C です)

より高い確率で正しく辺連結度を求めるため,圧縮されたグラフを k 個作成し,それぞれの圧縮されたグラフで辺連結度を計算し,それらの最小値を答えとして返すことにします.(圧縮によって辺連結度が大きくなる場合は存在するが,逆の場合は存在しないので,最小値をとるのが良い)

圧縮されたグラフにおいて,s' = t' になってしまった場合は,辺連結度を計算できません.このような場合に対処するために,論文では,頂点サンプリングを使って圧縮したグラフを導入しています.詳しくは論文を読んでください.

現実のグラフを使った実験結果によると,圧縮によりグラフのサイズを 93% ~ 99% 程度減らすことができ,それによるエラーは6%以下にとどまっています.クエリの計算時間は,ナイーブな場合にくらべて 500倍程度速くなったようです.