コードを短くするのって楽しいですよね？(3)

前回、「オーソドックスな解法は」と書いたが、tree自体が

  Tree ::= () | (integer Tree Tree)

のように再帰的に定義されているので、再帰降下法で解くのが自然だ。

以下、解答コードを含むので見たくない人は、見ないで！(｀ω´)

稲葉さんによる模範解答(サイズ関係なしの場合)はこう。

  // returns 0:not_found, 1:candidate_empty_tree, 2以上:found

  f(n){

    int v, ans;

    if( scanf(" (%d",&v) )

      ans = f(n-v)+f(n-v)&~1;  // nonempty. returns 0 or 2

    else

      ans = !n;                // empty. returns 0 or 1

    scanf(" )");

    return ans;

  }

  main(){

    int n;

    while( scanf("%d",&n)>0 )

      puts( f(n)>1?"yes":"no" );

  }

再帰降下法で降りていき、関数fは「()」を発見したときにそこまでの合計と一致していれば、1、一致しなければ0を返す。 f(n-v)+f(n-v)のようにしておけば、leafでは、左のfと右のfの両方が1を返すので、2になる。そこで、一致していればfは2(以上)を返すようにする。

これが一番、素直なコードであり、120バイト台でscanfを三回使用しているという人は、だいたいこのアルゴリズムで書いていると思われる。

ただし、コードの短さという観点で言えば、leafの判定がやや冗長だ。エラーチェックを考えず、「(」なり「)」なりが4回続けばleafというのを利用すればもっと単純化される。これは、私が昨日の日記で書いたソースを再帰形に変形することを考えると良いだろう。

以下、稲葉さんによるソース。

y,s;main(p,n){

for(;1&~getchar(scanf("%d ",&s)?n=p?s:n-s,s=3:--s|n||++y);

  p?y=puts(y?"yes":"no"):0)

  main(0,n);

}

argv!=0を利用しているのが憎い。あと、「1&~」の部分がいかにも怪しげだが、'('はキャラクターコードで40,')'は41。EOFは-1。よって、')'かEOFが見つかるごとに関数から抜け出したいのでこういう条件式になっている。これで108byte。(つづく)