最近のあなごる問題

anarchy golf C js

sort by first occurrence

js

トップ 0mg さんの 64B 解。

for(r=readline;s=r();)r[s]=[r[s]]+s+"\n";for(s in r)putstr(r[s])

まず、

r[s]=[r[s]]+s+"\n"

この部分。[ r[s] ] は、r[s] が undefined の時、"" (null string) になる。murky-satyr さんが Basic Code Golf の時に使った技だ。今回 0mg さんは、配列の初期化に絡めてうまい使い方をしている。

print([undefined].toString()==='')     // true
print([null].toString()==='')          // true

次に、putstr() 。引数を文字列化して、改行なしで出力するというもの。これも、SpiderMonkey の version が上がって入ってきたものなのか？それとも、前からあったのか？

C

C は、どうもうまく書けず、出さずじまい。文字列操作は、C では疲れるな。
inaniwa さんは、ハッシュ関数を定義し、うまくまとめている。

#define S s[(*p|p[1])%2000+404]
s[9999];*p=s;main(){for(;gets(p+=4);)++S;for(p=s;--S<0?p+=4,*p:puts(p););}

文字列の先頭の 8 バイト(*p|p[1])を使ってハッシュしている。全部で 80 個程度のデータなので、s[9999] や %2000 がちょっと大きすぎるように見えるが、たぶん、もっと良いハッシュが見つからないということなのだろう。配列 s[] の先頭の方には、gets() で読み込んだ文字列を入れるため、出現回数のカウンタ領域には、404 のオフセットを付けている。#2 の入力データが 100 個なので、1 個あたり 4 ワード(16バイト)使って、404 としている。

prefix to postfix

同系統の問題として、infix to postfix や postfix to infix がある。また、function call expression も postfix と考えることもできた。
sed/vi は、function call expression と同じで、パターンの置換を繰り返すことで解がもとまった。
また、js/C/C++/groovy は、以下のロジックで再帰的に処理することで解が求まる。教科書にでも載っていそうな方法だ。

入力　　　処理
＝＝＝　　＝＝＝＝＝＝
数字　　　出力
演算子　　次項、次々項を処理した後に出力
空白　　　次項を処理した後に出力

プログラミング言語っぽく書くと、

function f(){
    char c=nextInput();
    if(cは数字){
        output(c);
    }
    else if(cは演算子){
        f(),f(),output(c);
    }
    else{//cは空白
        f(),output(c);
    }
}

空白の処理は別として、これは、パースされてツリー（AST）となった、二項演算子を組み合わせた数式の処理と同じだ。こう考えると、prefix 記法は、ツリーを畳み込んだ表現と見ることができるな。っと思って wikipedia 見てみたら、そう書いてあった。

C

C はトップをゲットしたが、ちょっと面白いコードとなった。

f(c){write(read(0,&c,1)+c/24&1||f(c&8&&f()));}main(){main(f());}

細かい数式 ( c/24&1 や f(c&8&&f()) ) は、わかりにくいが、上述の再帰ロジックを実行してるだけ。
f() は、一行処理するとちょうど戻ってくるので、main() では、繰り返し呼んでいる。その呼び出し方は、for 文とかではなく、main() を再帰させている。これは、無限ループだ。ただし、再帰なため、スタックが増えていき、やがてスタックオーバーフローを起こして、signal を受け取り終了するというもの。通常、このような異常終了ケースでは、C 言語の場合、出力が行われないが、本解答の場合、出力は、stdio パッケージではなく、write() システムコールで行っているため、ユーザー空間でバッファリングされず、異常終了前に出力はなされるので、うまくいく。
また、f() の引数、c はスタックに取られているため、read() の後、上位バイトにごみが残ったままになる。そのため、本解答は、ごみの状態により成功しないこともある。投稿した時は、5 回目くらいでうまくいった。因みに、以下のようにすると、必ず成功するようになる。

f(c){write(read(0,&c,1)+c/24&1||f(c&8&&f()));}main(){main(f(0));}  // 65B
f(c){write(read(c=0,&c,1)+c/24&1||f(c&8&&f()));}main(){main(f());} // 66B

Golomb Sequence

endless 問題。その数列の構成法が面白いな。
http://en.wikipedia.org/wiki/Golomb_sequence
しかも、この一般項が黄金比を用いて表されるところが、また面白い。黄金比を p とすると、

a(n) = round(p ^ (2 - p) * n ^ (p - 1) + 0.5)

と表される。
解答方針は、上記式と、定義に従い数列を構成していく方法と、あと、以下の漸化式を用いる方法があるが、上記式によるものが効率が良いようだ。

a(1) = 1
a(n + 1) = 1 + a(n + 1 − a(a(n)))

〜〜〜〜〜
strbonacci FIXED を出題した。C は、やはり文字列処理がやりにくいので、面倒だ。なんとか、116B まで行ったが、トップ hinoe さんは、105B を出している。あと、11B もあるのか。縮まりそうにない。