2007年03月

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 はいいなぁ．

phpプログラムに dat=<?xml version="1.0" encoding="UTF-8"?> というクエリを URLエンコードして POST で送ったら，あるサーバでは echo $_REQUESTdat; の結果が <?xml version="1.0" encoding="UTF-8"?> になり，別のサーバは <?xml version=\"1.0\" encoding=\"UTF-8\"?> のようにクオーテーションがエスケープされてしまった．んで，原因がまったくわからず自分のプログラムがおかしいと思って無駄な時間を費やし…

結論としては magic_quotes_gpc などというものが勝手にエスケープしてくれていると．てきとうに調べると次のようなコードが見つかったので使ってみた．get_magic_quotes_gpc() というのがフラグになってるのねと．

<?php
 function gpc_stripslashes($st) {
 if (get_magic_quotes_gpc()==1) {  
  return stripslashes($st);  
 } else {  
  return $st;  
 }  
} 

参考：

http://www.spencernetwork.com/Forums/bin/YaBB.cgi?board=cgi;action=display;num=1122598707

結局 javascript 単体で他のホストの Web Servide を REST アクセスで利用するのも無理と．ブラウザ側の設定かえてすべてアクセス許可とかやればいいけどそんな作業をやらせたくない．しゃーないからメインのページを php で書いて通信をリダイレクトさせるか…　だいぶ面倒になってきた．

編集画面での改行位置に自動で改行(<br />)を入れるようにしているのだけど Nucleus は <pre> タグの内部にまで改行を入れてくれる．結果として二重の改行となってしまいひじゃうに見栄えが悪い．

ということで，ソースをいじって <pre> タグの内部に改行入れないようにしてみた．nucleus/libs/globalfunctions.php にある addBreaks というのが編集後の保存時に改行を挿入している関数らしい．

function addBreaks($var) { return nl2br($var); }

php のnl2br という関数を使って一律に改行の挿入を行っているので，これを pre タグの内部と外部で挙動が変わるように変更．

function addBreaks($var) {
  $i=0;
  $v2="";
  $n=mb_strlen($var);
  while($i<$n){
    $p=mb_strpos($var,"<pre",$i);
    if($p==FALSE){
      $v2.=nl2br(mb_substr($var, $i));
      break;
    }
    $v2.=nl2br(mb_substr($var, $i,$p-$i));
    $i=$p;
    $p=mb_strpos($var,"</pre>",$i);
    if($p==FALSE){
      $v2.=mb_substr($var, $i);
      break;
    }
    $v2.=mb_substr($var, $i,$p-$i);
    $i=$p;
  }
  return $v2;
}

もっときれいに書けるだろうけど必要十分なので汚さはむし．

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

がんばってルールを適用するプログラムを書いたのだが埋め込みに勝てそうにない．どうせなので両方出してしまえ．

自分の発表も終わったので増えてた問題をsedで解く．delete duplicate lines と Phone Key Pad はstatistics を見る限り ebanさんと同じコードになったもよう．palindromize は 57 bytes で shinhさんと並んだけどコードは微妙に違うらしい．もうチョイ考えてみやう．寝ながら．

人間抜かれると抜き返したくなる．ということで当初のプログラムからアルゴリズムを変えることなく約半分までがんばって縮めた．いまのところアルゴリズムの選択は間違っていなかったみたい．

red-black SOR を書いてみる．思いのほか単純にかけた．でもパラメータの値をどの程度にすればよいかわからず．ま，いいか．

文字列を与えられてたときに，その文字列を出力する最短の Brainf*ck プログラムを作りたい．使用するメモリセルの数を固定すると Assembly-line scheduling ににてるかなぁとか思ったら依存関係が思いのほか複雑で単純でないみたい．文字列を構成する文字の種類が限られているので，でかいテーブルをぶん回せばDPになるかも…

90bytes前後からなかなか縮まらなかったのだが，アルゴリズムを切り替えたら突然46bytesまで縮んだ．s コマンドのに p オプションをつけたのが正解らしい．

バブルソートを実装して走らせたら timeout を食らった．高々260文字程度のソートに7秒近くかかるのは駄目らしい．しょうがないのでバケットソートに切り替えてどうにか成功．サイズは204bytesで，これ以上はあまり縮みそうにない．バブルソートのほうが202bytesで少し小さいのが残念…　マージソートとかも書いてみようか？