2007年03月

研究室にあったのでちょくちょく動かしているのだがいったい何時間動かせばよいのやら．次の機体を出すのに30分とかかかるものがかなり連鎖してくれてるしその連鎖自体が複数本存在してくれるので非常に時間がかかる．無敵コマンド使って放っておくだけなのである意味楽だけどこれって最短で何時間？　まじめにやった人間って存在するのだろうか？

メモリ，時計に続き，今日はシェーバーの外刃が欠けた．そういや自転車の後ろブレーキのワイヤーも先が切れていた気が…　次は何が壊れるのやら．

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

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

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

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

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

１２年間使ってきた目覚まし時計が１２時間で２時間も遅れるほどお疲れらしい．４月からもこの調子では少々困るので目覚まし時計を新調することに．店に行ってみると電波時計やら録音やら携帯から曲を演奏やらの機能つきがあったがそんな機能は必要ないので置いてあった中のほぼ最安を購入．1.2k円．アナログでELバックライトとスヌーズ機能付きであれば十分でしょう．

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

体がだるくベッドから出る気にならなず昨夜からの睡眠時間は１時間強．おきてから大分たつけどまだおかしい…

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

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

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

ようやく Suica で地下鉄乗れるようになったそうなので早速使ってみたり．パスネットを取り出すのに比べてだいぶ楽だ…　あとは Suica が全国で使えるようになってくれれば文句なし．ついでに，ETCみたいに通り抜けるだけになってくれるとありがたいなぁ．

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

テキストのプロパティは get-text-property で手に入る．face もプロパティなので (get-text-property (point) 'face) でカーソル位置の face がわかる．カーソル位置の face が適当な face だったら処理をするとかを次のように書ける．

(if (let ((prop (get-text-property (point) 'face))) (or (eq 'line-number-face prop) (eq 'over-under-full-face prop)))
 (しょり～))

これの場合 'line-number-face か 'over-under-full-face だったらなにかすると．

face の指定時に mouse-face を付けてあげるとマウスに反応して face を変えられる．font-lock-defaults に渡す font-lock-keywords のなかで，

(cons "\\(.*full ..box.*\\)\\(line.*\\)"
    '((1 over-under-full-face)
      (2 line-number-face)))

とか書くところを

(cons "\\(.*full ..box.*\\)\\(line.*\\)"
  '((1 (progn
        (set-text-properties (match-beginning 1) (match-end 1)
			    '(mouse-face highlight))
         'over-under-full-face))
    (2 (progn
         (set-text-properties (match-beginning 2) (match-end 2)
 			    '(mouse-face highlight))
          'line-number-face))))

のようにプロパティを設定する関数 set-text-properties を呼ぶようにする．よくわからんが 1 とか 2 とかの数字はマッチした subexpression の番号らしい．あとは，マウスが押されたときに関数を呼ぶように mode の設定のとこで

(local-set-key [mouse-1] 'hogehoge-suru-function)

とか設定しとけばいいみたい．

http://faq.sakura.ne.jp/wiki/wiki.cgi?cgi%a4%c8php#i16 を参考にしつつ PEAR のローカルコピーを作る．最大の難点は download_dir の設定が抜けていたためダウンロードできずに嵌ったことだった．つーわけで，ここらを考慮しつつ以下のようなコマンド列を発行してどうにか成功．

pear config-create /home/user/pear .pearrc
pear install -o PEAR
pear config-set download_dir $HOME/pear/temp
pear install -o channel://pear.php.net/Text_Highlighter-0.6.9

ついでに，php.ini にパスを通す記述をしておく．

include_path=".:/home/user/pear/pear/php"

ちょっとディレクトリ名があれかもしれない…

なにはともあれ，これで C++ や Java も使えるようになった．あとは elisp とか sed とかのための設定を作ればよいのかな．

http://wakka.xiffy.nl/syntaxhighlighter より入手．

PEAR の Text_Highlighter を使っているらしい．とりあえず pre タグでソースを書いてしまうので div でなく pre にクラスを書いて動くように修正．このプラグイン無しでも普通に表示できるようにHTMLエスケープされた文字列を食うように変更．ついでに，<?php と ?> で囲まれてない php もハイライトするうにあほな修正を入れてみた．

<?php
   function parseString(&$content) {
      $chk = ' class="highlight';
      if (strpos($content['body'],$chk) > 0 ||  strpos($content['more'],$chk) > 0) {
         if ($this->_setupPEAR()) {
            $supportedRules = $this->getOption('highlight_rules');
            $supported_highlighter = explode(',',$supportedRules);
            if (is_array($supported_highlighter)) {
               foreach ($supported_highlighter AS $key=>$syntax) {
                   $supported_highlighter[$key] = trim(strtolower($syntax));
               }
            } else {
               // fallback with default settings
               $supported_highlighter = $this->supported_highlighter;
            }
            $this->counter = 1;
            $highlight_str = '';
            $content_part = array('body','more');
            foreach ($content_part as $key) {
               // now check for all allowed syntax highlighter
               foreach ($supported_highlighter AS $syntax) {
                  $pattern = "/<pre class=\"highlight_".$syntax."\">(.*?)<\/pre>/esi";
                  $replacement = "\$this->highlight_code('\\1','".$syntax."')";
                  $content[$key] = preg_replace($pattern,$replacement,$content[$key]);
               }
            } // end content_part
         } else {
            doError('Check your settings - can not include PEAR::Text_Highlighter');
         }
         // some cleanup code
         ini_restore('include_path');
         unset($this->hl);
      }
   }
   function highlight_code($string, $mode)
   {
      // remove possible br tags from nucleus automatic linebreak convertion
      $string = preg_replace('/<br \/>[\n|\r| ]/', '', $string);
      $string = stripslashes($string);
      $string = str_replace ( array ( '&amp;' , '&quot;', '&apos;' , '&lt;' , '&gt;', '&apos;' ), array ( '&', '"', "'", '<', '>', '?' ), $string );
      $normflag=false;
      $va = strpos($string, "<?");
      if(strcmp($mode, 'php')==0 &&  ($va==FALSE || $va > 5)) {
    $normflag = true;
    $string = "<?php ".$string."?>";
      }
      // check is there a cached object
      if (!isset($this->hl[$mode])) {
         // create new highlighter object
         $options = array('tag' => $this->tag_mode,'numbers'=>$this->line_numbers);
         $this->hl[$mode] = & Text_Highlighter::factory($mode,$options);
      }
      // retrieve highlighted string
      $highlight_str = $this->hl[$mode]->highlight($string);
      // if higlight_mode == save add a dummy id to exclude from further parsing
      $checkid = '';
      if ($this->rendermode == 'save') {
          $checkid = 'id="np_hl_'.$this->counter.'" ';
      }
      // enclose with div container
      //$highlight_str = '<div '.$checkid.'class="highlight_'.$mode.'">'.$highlight_str.'</div>';
      $highlight_str = $highlight_str;
      $this->counter++;
      if($normflag){
    $highlight_str = str_replace("<span class=\"hl-inlinetags\">?&gt;</span>", "", $highlight_str);    
    $highlight_str = preg_replace("/(<span class=\"hl-inlinetags\">)?&lt;\\?php *\n(<\\/span>)?/", "", $highlight_str);    
      }
      return $highlight_str;
   }

追記：

Text_highlighter を新しくしたら <?php の後の空白とかの扱いが変わったらしい．なので最後のほうをちょっと書き換え．

<?php
    $highlight_str = preg_replace("/(<span class=\"hl-inlinetags\">)?<\\?php *(<\\/span>)?(<.*?>) *\n/", "\\3", $highlight_str);

編集画面での改行位置に自動で改行(<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．ひとまずこれ以上縮めるのは面倒なので投げてしまう．

P5B DELUXE のサウンドチップにはPC上の音を録音するための wave mixer がついてない．Line out と Line in を物理的につなげてしまえば録音できるのだがそれも少々いやなので…　Sound Blaster 5.1 という Sound Blaster の中で一番安いやつを買ってきた．2000円弱．そこらの掲示板ではダメなカードとして書かれているが出力部の性能なんかどうでもよい．というか，音の違いなんぞ圧縮かけてる時点で無用の長物．

風邪でダウン気味ではあるが電源がないと何もできないので電源を買いに．とりあえずまた T-ZONE で 剛力PLUG-in 450W を購入．ケーブルが着脱式かつメッシュ結束なのでケース内がだいぶすっきりした．ただ，前の電源に比べるとPFCがついてないのでブレーカーの心配がちょっと大きく．

さて，余った部品でもう一台作れそうなのでどうしましょ．ケースがないのでケースを買ってくるかむき出しか．どこかに安くていいケースがないかなぁ

今の構成にしてから３年以上たったので，自宅のメインPCを強化してみる．秋葉原へ行って一回りし，面倒になってT-ZONEで１３万円ほどまとめ買い．IDEのHDDがひとつくっつかなくなったのでHDDも安いのを購入．

新しい構成：

• CPU： Core 2 Duo E6600
• MEM： UMAX DDR2 800 2G DUAL (1GBx2)
• M/B： ASUS P5B Deluxe
• VGA： Leadtek WinFast PX7900GS TDH 256M
• HDD： Seagate Barracuda 7200.10 320G SATAII

過去の構成：

• CPU： Pentium 4 2.6C (Northwood)
• MEM： DDR 400 1.5G DUAL
• M/B： ASUS P4P800
• VGA： Leadtek WinFast A350XT TDH 128M

てきとうに選んだのにまた ASUS + Leadtek になってしまったらしい．別にオーバークロックするわけでもないのでM/Bも別の安いのでいい気もするが…　とりあえず組みあがったけど電源がおかしくなってきたので電源も買いに行かなくては．

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

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

プログラム盗用発見システムはいろいろな意味で面白かった気がする．ユーザの名前がわからないようにスタンドの名前を使ったり…　こういうシステムがあるとシステムで発見できないように盗用するシステムとか考えたくなる．不毛だとしても．

今年は加賀温泉．新幹線＋しらさぎで．

とりあえず Type-safe Linking of C Programs という話が一番記憶に残った．Cの分割コンパイル時における struct の扱いに関して知らないことが多かったことに気づく．同名だけど構造の違う struct が平気でリンクできてしまうものだったとは知らんかった．この現象を使ってなんか面白い挙動をするプログラムを作れないかなぁ？

どうでもいいけど晩飯おおすぎ．

どうも24台と48台で極端に性能が落ちている…　2の冪でないと通信のタイミングがうまくかみ合わないとかあるのだろうか？　ここら辺の怪しい挙動も帰ってきたら調べてみようか？

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

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

Canon 製のCISのスキャナが見つかった．しかしUSBでつなげてもうんともすんとも言わない．またゴミか…

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

ブランデー１＋貴腐ワイン３．左から：

• 洋ナシのブランデー（洋ナシ丸ごと一個入り）．フランスらしい．
• ハンガリーのトカイのアスーエッセンシア．
• ドイツのよくわからないTBA．
• フランスのバルザック（ソーテルヌ）のシャトークーテ．

とりあえず，トカイ＞ドイツ＞クーテの順でおいしかった気がする．値段の順とも言う．アスーエッセンシアは前に飲んだ４プットニョシュのよりだいぶ甘かった．単純に糖度が倍だからなぁ．これで素のエッセンシアになったらどんだけ甘くなるのやら．ま，高くて手が出ないけど．よくわからないTBAはトカイのより酸味のウェイトが高めだった．香りも強めだったかなと．ある意味ワインらしい．トカイのはどっちかってーとシロップに近いイメージか．クーテのは残り二つと比べると普通のワインだった気が…　次はぜひともディケムのを試してみたい．そして洋ナシのブランデーは洋ナシが丸ごと一個入ってるというネタ．ただのネタ．

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

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