No Such Blog or Diary

朝一で秋葉へ行き初期不良らしきメモリの動作確認をしてもらった．店でのテストでもエラーでまくりだったので，無事初期不良として新品に交換してもらえた．雨の中メモリの交換だけに秋葉へ往復するのは疲れる…　とりあえずこの新しいのがはずれでないことを祈りつつＯＳを再インストールして環境整備．しばらくは高負荷をかけて慣らし運転しなおさないとなぁ．

最近Windowsの調子がおかしいかなぁと思っていたところ，今日はとうとうセーフモードですら起動しなくなった．とりあえずインストールディスクで修復を試すが途中で落ちる．しょうがないので再インストールをしてみるが異常に遅い．いろいろやった末にハード側がおかしいという結論に至り，memtest を走らせてみたら画面の下半分が真っ赤．どうやらメモリが死んでるらしい．買ってからまだ二週間なので初期不良で交換だろうけどすでに店が閉まっている時刻なので明日まで保留．ＰＣのパーツに限らず初期不良にあたったのは初めてだ．

正規表現によるマッチング回数を減らし，正規表現の単純化もすることで 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 はいいなぁ．