No Such Blog or Diary

deadline ギリギリで今回のサンプルにだけ有効なプログラムを出してしまった…　なので，別の方法で 85B にしたバージョンをここにさらしてみる．

:
s/^\([[({<]*\)\(\[]\|()\|<>\|{}\)/\1/
t
/^$/cyes
s/^[[({<]*/failed at: /
s/ $/ EOL/

んで，今回のサンプル入力では正しいプログラムにするには５行目を

s/[[({<]*/failed at: /

にしてやればいい．これで 84B になる．けどこーいうのはなんかいやだなぁと思う．

irori さんと shinh さんに軽く追い抜かれていたのでアルゴリズムを見直す．反復の一ステップをひとつの正規表現だけで実行するように変更．ついでに実行時間も改善されたもよう．現在 86B．statistics の差を見る限りではラベル部分での 2B の差に思える．

正規表現によるマッチング回数を減らし，正規表現の単純化もすることで TLE を克服．当初 142B だったが C言語に抜かれたのでプログラムを直し現在 117B まで縮んだ．

とりあえず，正規表現の処理スピードとしては

/^\(AB\|CD\|EF\|GH\)/

より

/^AB\|^CD\|^EF\|^GH/

のほうが速いらしい．

あと，

s/fuga/hoge/

と

/fuga/s//hoge/

だと後者のほうが遅い．二回マッチングを取っているみたい．条件部分でのマッチングと同じだからマッチング結果を使いまわしてほしいなぁ．

ここらが合わさると，

/^\(AB\|CD\|EF\|GH\)/{s///;b1}

では timeout だけど

/^\(AB\|CD\|EF\|GH\)/{s/..//;b1}

だと大丈夫などの現象が生じるらしい．

最近のあなごるの問題は埋め込みで解く問題が多いように感じたので（連続したので）簡単かつ埋め込みで解こうとは思わない問題を出してみた．問題は Bracket Matching で，括弧の対応が取れているかを答える問題．埋め込み防止のため，マッチしていない場合にはマッチできない括弧以降を出力するようした（yes/no だけではビットにエンコードされるので…）．また，入出力のサイズを大きくしてさらに埋め込みをやりたくなくなるようにした．

んで，毎度のごとく sed でちゃらっと組んで投げてみたら見事に timeout くらった．入力がでかすぎで処理に時間かかりすぎとのこと．この埋め込み防止策で自分の首を絞めるとはあほすぎる．

なんとなく収束してそうだしネタばれ的に書いてみる．この問題の鍵は勝敗判定部分を如何に簡単にするかだと思って組み始めた．とくに，じゃんけんはグー・チョキ・パーを巡回させても勝敗が変わらないので，適当な正規化をしてやるというのが短いコードへの近道かなぁと．

ということで，最初に考えたのが次の 73B のプログラム．

s/P\w*/5/g
s/[SC]\w*/2/g
s/[GR]\w*/0/g
:
y/025/250/
/^0/!b
/2/c>
/5/c<
c=

こいつは，まず各種グー・チョキ・パーを 0・2・5 に変換し，次に一人目の手がグーであるように両者の手を回転させ，最後に二人目の手を見て勝敗を判定する．判定は，一人目がグーであるので，二人目がチョキなら '>'，パーなら '<'，残りは '=' となる．

基本アルゴリズムはこのままで，以降最初と二番目のステップが縮まっていく．

一段階縮まったプログラムは次の 64B のプログラム．

s/P/5/g
s/[SC]/2/g
s/[GR]/0/g
:
y/025/250/
/^0/!b
/2/c>
/5/c<
c=

最初の一文字だけ見ればいいので無駄な置換をしないことにした．これで最初のステップの部分がだいぶ小さくなった．

が，一文字しか置換しないなら・・・ y コマンドでいいじゃん，と．この書き換えを始めて次の 49B を得た．

y/PSCGR/52200/
:
y/025/250/
/^0/!b
/2/c>
/5/c<
c=

で，yが二つに分かれてるのは無駄だなぁということで，先頭の y をひとつにくっつけてしまって最終的に次の 44B になった．

:
y/PSCGR025/05522250/
/^0/!b
/2/c>
/5/c<
c=

すっきり爽快無駄のないコード．Perl の現時点のコードより短い．やっぱり sed はいいなぁ．

あなごるの新しい問題を毎度のごとく sed でがんばる．埋め込むと簡単なので埋め込まない方針で，括弧のネストがないと仮定して317bytes．ひとまずこれ以上縮めるのは面倒なので投げてしまう．