λx. x K S K ＠はてな

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

今年もゴルフコンペします

OCaml golf

来る8月30日の「OCaml Meeting 2010 in Nagoya」にて， 今年もゴルフコンペを開催することになりました．与えられた問題に対して OCaml で解いてもらい，最も少ないバイト数で記述できた方が優勝となります．

ゴルフ場については，今年も shinhさんのご好意により，あなごるサーバをお借り致します．

  • OCaml で投稿してサーバに受理されていること
  • 当日会場にいること
を満たす人の中で最高位の方には，賞品が提供される予定です． 参加を希望される方には，今のうちにあなごるのサーバの振る舞いに慣れておくことをお勧め致します． あなごるサーバでは，締切の過ぎている問題については投稿されたコードが公開されているので， 覗いておくとよいかもしれません． OCaml で既に投稿があった問題については， こちらが参考になると思います． このページでは，これまで出題された問題とそれを解いた人のランキングがあり， post mortem と書かれた問題については，解いた人の名前からリンクが張られているので，その人のプログラムを覗くことができます．

なお，この記事は 昨年の記事 をコピペして，「今年も」を追加しただけの記事です． いくつかの OCaml ゴルフのテクニックについては，昨年の講演でお話しした内容をこのブログにでも連載していく予定ですので参考にしてください．

間違い探し

OCaml

クイズ (?) です． 以下のOCamlで定義されている関数は 「数値を表す文字列を受け取って次の数値を表す文字列を返す」関数です．

let string_succ str = try
  string_of_int (succ (int_of_string str))
with Failure "int_of_string" ->
  invalid_arg "string_succ: "^str^" cannot be converted into int."

実は，この関数定義は型検査は通るのですが， プログラマが意図していないと思われるバグがあります． さて，どこでしょう？
実行してしまうとすぐにわかるので，なるべく実行せずに考えてみましょう．

Parsing Expression Grammar

研究

以前どこかで「 X\to aXa/\varepsilon という規則が 2^n\quad(n\geq 0) 個の a を受理する」というような記述を見かけた気がして， 確認してみたのですがなかなかうまくいきません． 偶数個の a を受理してしまうという勘違いはなくなったのですが，どう確認しても 2^n-2\quad(n\geq 1) 個 (つまり，0, 2, 6, ... ) の a しか受理しません． X\to aXa/aa なら手許でも 2^n\quad(n\geq 1) 個 (つまり，2, 4, 8, ... ) の a を受理することが確認できました．

その記述を見たのが記憶違いなのか，手許の計算がどこか間違っているのか…．

Helloworld-less Helloworld

OCaml golf

最近，仕事の方がバタバタしていましたが， ようやく一段落しました．

先日の OCaml Meeting で解けないとか言ってしまった Helloworld-less Helloworld でしたが，
xsd さんによって解かれました．そのアイデアをもとに縮めると，

Obj.magic(+)242(^^)"\072\101\108\108\111\044\032\119\111\114\108\100\033"
という73Bのコードが得られます．

ちなみに， find anagrams の締切まであと4日です． わりと考えさせられる問題だったので，現実逃避や気分転換に是非どうぞ．

コンペ終了

OCaml golf

参加された方お疲れさまでした．
始まる前までは「ゴルフの参加者が 3 人くらいだったらどうしよう」とか思っていましたが，
予想以上に参加してくれてよかったです．
今後も OCaml Golf を続けてくれると，あなごるでの OCaml の順位が上がってなおうれしいですね．
解いてない問題を解けばスコアが上がりますが，解かれている問題でも 1 位のコードを上回れば，
それでもスコアは上がりますので，是非チャレンジしてください．

ルールは急いで書き上げたものですが*1， 問題の方は 8 月の初めくらいから練っていたものです．
あなごるの Performance Checker で実行時間を入念にテストした結果，
あの大きさの入力になりました．

自分としては 1 位のコードが書けなかったのが悔やまれますが，
ゴルフを知らない方にも興味を持ってもらえたのはとてもよかったです．
ただ，あんな小手先の役に立たないテクニックばかり紹介してしまったので，
あまり OCaml でプログラムを書いたことのない人があらぬ誤解をしていないとよいのですが…．

*1:不備があったようですみません．

コンペ途中経過

OCaml golf

3人が100byteを切ったようです．

ところで，出題時にexec deniedを忘れるというミスをしてしまいました*1．すみません．
(POSTするときにdexecを"1"とすべきところを"deny"としてしまったという…． 素直にブラウザから出題すればよかった．)

それから，exec関係の変更以外についても，以下の点を補足させていただきます．

  • Lightning Talkの終了に合わせて，締切が16:20になりました
  • タイムアウトは3秒と書きましたが，正確には1入力につき1秒です

*1:今は修正されています．shinhさん，ありがとうございました．