_ しばらく前 Portal ってゲームをやってたんですよ。んーと、 こんなゲーム。小粒だけどこれは傑作。ケーキをあげましょう。で、最小ポータル数とか最小歩数とか目指して遊んでるうちに、この感覚ってなんかに似てるなー、と。ある場所に開けたポータルを別の目的で何度も再利用したり、ふつーの解き方ではあたりまえに通る経路を妙なやりかたでショートカットしたり、そういうのを見つけだすために脳から汁が出てくる感覚。なんだっけなー。
_ あ、わかった、code golf だ。最小バイト数で目的の出力を得るプログラムを書く遊び。てなわけでしばらく遠ざかってた あなごるに復帰。……というのが去年の11月ごろの話。
_ そんなわけで久しぶりにゴルフしてるわけなんだけど、最近のあなごるの問題。 Maximum Cyclic Segment Sumで sh でエントリーしたこたえ。えーっと、日和ってまじめに計算しないで解答埋めこみです。しかも正解が出るのは運がいいときだけ。まじめに計算するのもちゃんと作ったんだけど時間制限にひっかかってはねられるんだもん。いや、尋常ない数のループを sh でぶんまわすのは時間がかかって当たり前だからさ、作りはじめる前からタイムアウトするのはわかりきってたんだよね。作ってみました、やっぱりタイムアウトしました、ってのを確認するだけの作業。時間制限1秒で分単位の時間がかかってるようじゃどうにもならん。
_ まあせっかく作ったので、時間はかかるけどちゃんと計算して答を出すバージョンをさらしとく。ゴルフ的に縮める作業をはじめる前のまだ見易いもの。こっからサイズが縮むことはあっても、実行時間が縮む見込みはほとんどない。
while read a;do set -- $a p=`seq $#` for i in $p;do for j in $p;do x=`echo $@ $@|cut -d\ -f$i-|cut -d\ -f-$j` eval echo $[`echo $x|tr \ +`],$x done done|sort -n|tail -1|cut -d, -f2 done_ でも、あなごるほどの規模の問題ならばそんなに時間がかかるのは sh ぐらいなもんだよな、と思ってたら、最新の Up and Downを awk で書いてたものがまたタイムアウトの壁にぶち当たったよ。しくしく。まあ、制限ギリギリだっただけのようで、コードを変えずに何度かエントリーしなおしてるうちにたまたま制限時間内に終わって成功したけど。コードをムリヤリ短くするためにやってるムダなこと(本来2回必要なはずの for ループを1回に無理にまとめてるとか、その影響でループの外で1回やればいいだけの初期化作業をループの中につっこんで1000回近くまわすとか)をやめれば余裕で時間内で解けるのはわかってるんだけどさ、それをやるとやらないとでは20バイトぐらいは違うので。
_ んで、これだけムチャして縮めてまだ110バイト。こういう文字コードを扱う問題では、'A' とするだけで65という値が出てきたりそれ用の関数が存在したりするわけではない awk では文字と文字コードの対応表をまず自力で作成するところからはじめなきゃいかんのがつらい。もしかしたらあと2、3バイトぐらいは縮むかなぁ。
_ む。ムダな初期化をちゃんと1回で済ませて、かつ1バイト減らせた。最大のボトルネックが解消してないので相変わらず時間制限ギリギリだけど、それでも前よりは速くなった。これで109バイト。
_ ちなみに sh だと……。文字コードずらしは tr を呼ぶだけなのでカンタンにできるけど、1文字ごとに tr を実行するとまた尋常でない時間がかかるだろうなー。
_ それはそうと、ゴルファーな方には Portal オススメ。Portal をおもしろいと思った人にもゴルフオススメ。ケーキなんて嘘だ。