2011年10月19日

Anarchy Golfにハマり中

Twitterのタイムライン上でFibBuzzBuzzFibが流行っていたのをきっかけに、私もAnarchy Golfにハマってしまいました。

Anarchy Golfは、いわゆるCode Golfという競技で、与えられたお題に対するプログラムをできるだけ短いコードで記述するという遊びです。現時点で83種類ものプログラミング言語が使用できますが、私は主にPythonで参加しています。

コードを1バイトでも短くするために色々なアルゴリズムを考えたり、同じ処理を短く書くために様々なパターンを試行錯誤するのは、数独に似た感覚を覚えます。

最適解が何バイトになるのか分からないゴールの見えない戦いで、すでに限界まで絞り込んだコードから更に縮む可能性を模索するのは、色々な方向から考える必要があって、かなり頭を使います。

上位勢が同じバイト数で並んでいて「これが理論上限界だろう」と検討を終了した問題が、しばらく経ってから1位の記録が更新されたときは、悔しさと同時に「まだ削れるか!」という喜びも感じます。そしてまた苦悩の日々を過ごすことに…

Code Golfでは短く書くことが正義なので、きちんと問題を解かずに答えそのものをコード内に埋め込んでしまうことも多いです。答えを埋め込む方が短くなるというのは、問題としては残念ですが、いかに少ない文字数で答えを埋め込むかという戦いも面白かったりします。さすがに、外部プログラムを呼び出したり、ソースをzlibで圧縮して実行時に展開するようなのは、逸脱してる感じがして私は好きではないですが。

Anarchy Golfでは制限時間付きの問題と無期限の問題があり、制限時間付きの問題は時間切れ後にソースコードを見ることができます。最初のうちは、開示されたコードを見てノウハウを勉強していくといいでしょう。Pythonのコードは、Code Golfでも読みやすい傾向にあります。逆にPerlは、書いた本人でもよく分からない難解なものになるので、パズル的な要素ではPerlの方が面白いかもしれません。

コード例

tennisという問題を検討中に、なんだかロジックが美しいコードが出来たので晒しておきます。

s=[0]*3
while 1:
 s[input()]+=1
 w=cmp(*s[1:])
 p=s[w]
 print('Set is tied at '+`s[1]`,'Player%d %s %d - %d'%(1-w/2,p/7*'wins the set'or'leads',p,s[-w]))[w]

1行目は各プレイヤーのスコアの初期化です。入力値が’1’か’2’なので、値を補正せずに使えるように長さ3のリストになっています。先頭のs[0]は使いません。[0,0,0]ではなく[0]*3と書くことで文字数を節約しています。

4行目は、プレイヤー1と2のどちらが勝っているか調べています。cmpは引数2の関数ですが、必要な引数の数と同じ長さのシーケンス型に*を付けて関数を呼ぶ構文を利用しています。

5行目は勝っている方の得点を取得しています。wはcmpの結果なので値は1,0,-1になりますが、Pythonでは配列の添え字が負の値の場合は後ろから数えるので、長さ3の配列の場合は-1は2と等しくなります。ここで配列の長さが3なのが活きてきます。

6行目は結果の出力です。同点の場合と点差がある場合の出力をtupleにして、wで選択しています。ここでは長さ2なので、1と-1は等しく、0の場合だけ結果が変わります。

負けているプレイヤーの得点は、-wとwの符号を反転することで取得できます。ここでも長さ3が活かされています。

残念ながら、このアプローチでは最短は狙えそうにないです。やはり各所にある配列の[]が足を引っ張ります。この問題のルール上、必ず毎ターンどちらかに得点が入るので、片方の得点とターン数の情報だけあれば十分で両プレイヤーの得点を保持することが、そもそも無駄だったようです。

ちなみにこの問題の元ネタは「キミのコードが汚い理由 − @IT情報マネジメント」という記事のようです。当時、この記事の修正後のコードがそもそもあまり美しくない(しかもバグってる)と批判されたようですが、既にゴルフ脳に侵されている私は、コードを見た瞬間に「長すぎて美しくない」と感じてしまいました。やばいね、ゴルフ脳。

2011年10月19日 【プログラミング】 | コメント(0) |

この記事へのトラックバックURL


この記事へのトラックバック
この記事へのコメント

コメントを書く
お名前: [必須入力]

メールアドレス:

ホームページアドレス:

コメント: [必須入力]

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。