λx. x K S K ＠はてな

このブログ内に記載された文章およびコードの著作権は，すべて Keisuke Nakano に帰属します．

一筆書きできる括弧の組

問題

一昨年，昨年に続き，とある研究室合宿でのプログラミングコンテストで出題するために作成した問題を（一部編集して）公開します． 解答は後日ここで発表します．

n (≧1) を自然数とする． s，tはそれぞれ 2n+1 文字，2n 文字からなる文字列で以下の全ての条件を満たしている．

  • s の中の文字は，ハイフン '-'，左括弧 '(' ，右括弧 ')' のいずれかであり，ハイフンはちょうど1回だけ現れる．
  • t の中の文字は，左括弧 '('，右括弧 ')' のいずれかである．
  • s，t の中のどの括弧も正しく対応づけられている．ハイフンの位置は問題にしない．
  • 文字 s[i] (1≦i≦2n) がハイフンであるとき，文字 t[i] から始めて，以下の手順で移動を繰り返すことにより，s と t の中の全ての括弧を 1 回ずつ辿ることができる．
    • その文字が s の中の括弧のとき，対応する括弧 s[j] を辿り，t[j] に移動する．
    • その文字が t の中の括弧のとき，対応する括弧 t[j] を辿り，s[j] に移動する．
ここで，x[i] は文字列 x の i 番めの文字を表すものとする．たとえば，n=2 のとき， <s, t> = <"(()-)", "()()"> や <s, t> = <"()(-)", "(())"> は条件を満たすが， <s, t> = <"(-())", "()()"> や <s, t> = <"(()-)", "(())"> は条件を満たさない． 与えられた自然数 n (≦10) に対し， 条件を満たす <s, t> の組の数を出力するプログラムを書け．

ICFP PC Lightning Division

OCaml

結果が出てますね． 残念ながら6回戦で脱落． というか，よくそこまで残ったなと見るのが正しいか． 角度の単位とか間違えてたりクレーターが近すぎるとむしろ突進したりするようなひどいプログラムだったし…，

OCaml では (大抵の言語でもそうだけど) 度もラジアンもどっちも float なのでこれが誤りの原因でした． 単位も型検査でチェックしてくれればいいのになぁ． その昔，こんな研究がありましたが， 角度も三角比も無次元なので関係ないですね．

6年がかりと7年ぶりなこと

研究 OCaml

2002年に提出した論文がようやく受理されました． 長かった…．Editorのおかげで提出したときよりだいぶ進化しています． 一方，全く毛色の違う論文の方もとある会議に受理されたようです．

そして，久しぶりにICFPのプログラミングコンテストに参加しました(7年ぶり3回め…数えてみて愕然)． 前回 (第4回) はXMLもどきをいじる問題， その前に参加したのは記念すべき第1回で対戦ゲームの問題でした． ゴルフをするならRubyだけども，やっぱりこういう問題を解くにはOCamlが自分に合ってるなあと実感しました． まあ，迷路みたいなものを解くこととは考えずに結局障害物を避けつつ只管ゴールに向かうだけでしたが． ちなみに，TCP_NODELAYはOCaml 3.10.2 (最新のリリース) では設定できなかったという． そして，今調べてみたら，コンテストと関連しているか否かは謎ですが，最新のOCamlのCVSでは 実装されているという． といっても，これを使ったからといって性能が上がるようなコードは書いていませんでした． 問題としては，最近の傾向だった変な方向に凝った問題よりは面白かったと思います．

あけましておめでとうございます

雑記 アンビグラム
って，もうすぐ3月ですが…． 左のは昨年末に作成したアンビグラムで今年の年賀状に使用したものです．*1
いろいろ立て込んでいたので更新していませんでしたが，今年のこれまでのまとめは以下の通り：
桑港に出向いてPLAN-Xで発表，PEPM, Coq Tutorial, POPLに参加．
個人的にはCoq Tutorialが面白かった．最初の方は退屈だったが，後半はいろいろ勉強になった．
POPLの「各発表20分，各セッション3発表」は非常に聴きやすかった．
他の会議でも採用してもよいかも（但し，発表者が周到な準備をしている場合に限る）．
会議やらワークショップやら雑誌やらの査読がいろいろ．
日程がかぶりまくる上にやたら多い．
//golf.shinh.org/p.rb?Palindromic+Quine#OCaml">Palindromic Quineに挑戦．:行コメントのないOCamlでは非常に面倒．
最初は無理な気がしたためkinaba氏に振ってみたら，あっさりできたみたいだったのでチャレンジ．
ついでにcaml-listでも宣伝．最終的に以下のコードで最短（199B）をゲット．
"k\"",let rec(!)n?(q=String.make 1(Char.chr 34))s
k=print_char(q^s^q^q^k^q).[abs n];!(n-1)s k
in!99"99!ni
k s)1-n(!;]n sba[.)q^k^q^q^s^q(rahc_tnirp=k
s))43 rhc.rahC(1 ekam.gnirtS=q(?n)!(cer tel,""\k"
今年度でプロジェクトが終了するので総仕上げをいろいろ．
まだまだ仕事が残っています．
前項と関連して，次期ポスト探しの就職活動．
なんとか決まりました．急ですが3月から所属が変わります．

*1:アンビグラムは，主にigatoxinさんの影響です．

PLAN-X 2008

研究

めでたく２本とも採択されました． 一方はXMLのストリーム処理の話，もう一方はXML変換としての型検証の話です．

XML Stream Processing Using a Lazy Concurrent Language
XMLストリーム処理のメモリ効率をあげるには，ただ単にXMLパーサとXML木処理を融合しただけでは十分ではなく，値呼出しでも必要呼出しでもない評価戦略が必要である．この研究では，それを特殊なデータ型と並行処理による実装で表現している．
XML Type Checking for Macro Tree Transducers with Holes
名前付の穴と穴適用をマクロ木トランスデューサ（MTT）に導入することで，２つの決定性MTTの合成が表現できて，その型検証もナイーブな実装よりも効率的な方法が存在するという内容．この穴付MTTはマクロ森トランスデューサの自然な拡張になっている．
と書いてみたところで説明になっているかどうか…．

[追記（12/27）] 前者は共著者が，後者は私が発表することになっています． プログラムも決まったようでトップバッターになってしまいました． 他の発表で先にMTTについて説明してもらえるとありがたかったのですが．

caml-listにて

OCaml golf

caml-listにてgolfの話題が…．*1 といっても，segmation faultを起こす最短のコードを見つけようという問題だったので， 開発者の逆鱗に触れてあっという間に鎮火． 普通の(?)golfの話題ならどういう反応があるかなぁ．

*1:ただし，golfという単語が直接出ているわけではありません．

Timeout.ml

OCaml golf

無限ループでも重い処理でもよいので3秒間実行し続ければOKという問題． OCamlだとwhileを使うものが最短のようですが， 考えられる解をいくつか記録しておきます．

まず，最短であると思われるwhile版 (17B)．

while 0=0do()done
とか
while-7<7do-7done
とかいろいろあります． 次に，再帰を使うとこんな感じ (19B).
let rec(!)_= !0;;!0
let recを使わない「再帰」では，短くするのが難しいようです (28B)．
let f(`f f)=f(`f f);;f(`f f)

ついでに失敗例もいくつか挙げておきます．（疑似）無限リストを使って (19B)

let rec r=0::r;;r@r
とすると（ゴルフサーバでは）スタックオーバーフローで3秒以内で止まってしまうのでダメです． ちなみに，このコードはスタックオーバーフローで止まってしまう最短のものではなく，18B の
at_exit do_at_exit
という解もあります．終了処理関数を終了処理関数として登録するという荒技です． do_at_exitなんていうマニュアルにない関数を使ってしまってるのがアレですが．

あと，「ゴルフサーバでは test.ml というファイル名で実行される」ということを利用して 13B の

#use"test.ml"
も考えましたが，残念ながら Too many open files ですぐに止まってしまいました． 以上，途轍もなくどうでもいい考察でした．