ショートコーディング：きのこ危機一髪【解説2】
本エントリはCodeIQで2015年3月6日～同年3月27日に出題された「ショートコーディング：きのこ危機一髪」という問題とその解法に関する記事です。
ショートコーディング：きのこ危機一髪【解説2】
◆注意
本問は「ショートコーディング」・「コードゴルフ」と呼ばれる、ソースコードをできるだけ短く書く遊びの一環として出題されたものですので、一般的なプログラミング解説とは少し異なります。
◆ビット演算でより単純に
1回のループできのこ数は約半分になります。ある値を半分にするには、2進数で言えば1ビットシフト、偶奇を調べるには最下位ビットのON/OFFで簡単な操作です。しかも偶奇の判定箇所は決まっています。 少し具体的な値で調べてみます。たとえば、入力nが1000～1010と、そのときの出力（正解）を列挙してみます。
1000 1 1 1 1 1 0 1 0 0 0 675 1 0 1 0 1 0 0 0 1 1 1001 1 1 1 1 1 0 1 0 0 1 681 1 0 1 0 1 0 1 0 0 1 1002 1 1 1 1 1 0 1 0 1 0 681 1 0 1 0 1 0 1 0 0 1 1003 1 1 1 1 1 0 1 0 1 1 683 1 0 1 0 1 0 1 0 1 1 1004 1 1 1 1 1 0 1 1 0 0 683 1 0 1 0 1 0 1 0 1 1 1005 1 1 1 1 1 0 1 1 0 1 681 1 0 1 0 1 0 1 0 0 1 1006 1 1 1 1 1 0 1 1 1 0 681 1 0 1 0 1 0 1 0 0 1 1007 1 1 1 1 1 0 1 1 1 1 683 1 0 1 0 1 0 1 0 1 1 1008 1 1 1 1 1 1 0 0 0 0 683 1 0 1 0 1 0 1 0 1 1 1009 1 1 1 1 1 1 0 0 0 1 673 1 0 1 0 1 0 0 0 0 1 1010 1 1 1 1 1 1 0 0 1 0 673 1 0 1 0 1 0 0 0 0 1
最下位ビットから見て偶数番目のみで比較すると、非常に良く似ています。しかし下位ビットは一致しない場合があります。そこで、入力値から1を引いてみます。
1000-1 1 1 1 1 1 0 0 1 1 1 675 1 0 1 0 1 0 0 0 1 1 1001-1 1 1 1 1 1 0 1 0 0 0 681 1 0 1 0 1 0 1 0 0 1 1002-1 1 1 1 1 1 0 1 0 0 1 681 1 0 1 0 1 0 1 0 0 1 1003-1 1 1 1 1 1 0 1 0 1 0 683 1 0 1 0 1 0 1 0 1 1 1004-1 1 1 1 1 1 0 1 0 1 1 683 1 0 1 0 1 0 1 0 1 1 1005-1 1 1 1 1 1 0 1 1 0 0 681 1 0 1 0 1 0 1 0 0 1 1006-1 1 1 1 1 1 0 1 1 0 1 681 1 0 1 0 1 0 1 0 0 1 1007-1 1 1 1 1 1 0 1 1 1 0 683 1 0 1 0 1 0 1 0 1 1 1008-1 1 1 1 1 1 0 1 1 1 1 683 1 0 1 0 1 0 1 0 1 1 1009-1 1 1 1 1 1 1 0 0 0 0 673 1 0 1 0 1 0 0 0 0 1 1010-1 1 1 1 1 1 1 0 0 0 1 673 1 0 1 0 1 0 0 0 0 1
これで完全に一致しました。奇数ビットは一致しませんが、解の奇数ビットは最下位ビットのみ1でそのほかはすべて0になっています。つまり、入力nに対してn-1の奇数ビットを0でマスクし、最下位ビットに1を立てるだけで解を得ることができます。
#include <stdio.h> int main() { int n; scanf("%d", &n); printf("%d\n", n-1 & 0xAAAA | 1); return 0; }
0xAAAAの部分は2進表記で1010101010101010で、これを用いて奇数ビットを0でマスクしています。
◆さあ、縮めよう
非常に短く書ける計算方法が見つかったところで、コードを短縮します。まずは通常通り、省けるものをすべて省きます。
main(n)
{
scanf("%d", &n);
printf("%d", n-1 & 10922 | 1);
}
今回は入力の上限を10000としています。10000は2進表記で10011100010000（14ビット）ですので、14ビットまでのマスク（10101010101010）で十分です。この値は10進表記で10922ですので、この値をそのまま書いておきましょう。このコードの不要な空白改行を取り除くと49Bになります。非常に短いコードができました。
main(n){scanf("%d",&n);printf("%d",n-1&10922|1);}
入力部分はgets()+atoi()関数を用いて、
main(n){printf("%d",atoi(gets(&n))-1&10922|1);}
のように書くとさらに短くなり47Bになります。 このあたりで、演算部分も少し工夫しておきます。10922は5ケタの数ですが、ビットを反転して01010101010101とすると5461になります。1ケタ少なくなりますから、これを利用しておきましょう。入力とマスクともにビット反転したもので計算すれば、あとから計算結果を反転させるだけで済みます。 nをビット反転させるには~nと書きますが、コード内では1を引いたもののビット反転が必要で、実際には~(n-1)が必要になります。冗長なコードに見えますが、~(n-1)は-nと等しくなります（この辺りが分かりにくければ、「2の補数」をキーワードに調べてみてください）。
main(n){printf("%d",-(-atoi(gets(&n))|5461));}
「~」ではなく「-」を使うことで、ビット反転しつつ最下位ビットに1を立てることに成功しています。これでさらに1B短くなり、46Bになりました。
◆最短コード44B
最短コードに向けて少し説明しておくことがあります。 次の例は標準入力から整数値を読み込み、それを出力するプログラムです。
main(n){printf("%d",atoi(gets(&n)));}
処理系によっては、このプログラムを
main(){printf("%d",atoi(gets()));}
のように引数を省略しても動く場合があります。もちろん今回の採点環境では動きません。 引数を省略した場合コールスタック上にある何らかの値が参照されます。ideone.com上でコンパイル・実行すると、gets()がコールされる前にコールスタックにeaxレジスタの値がpushされます。pushされる値をアドレスとして、そのアドレスにデータの書き込みが可能なら、うまく動いてくれますがideone.comではeaxレジスタの初期値が1であるため不可能でした。しかし、次のようにコードを書き替えるとうまく動きます。
main(){printf("%d",atoi(),gets());}
ほとんど同じコードですが、このように書くとgcc(4.9)はgets()をコールする前にebxレジスタの値がpushされるようになります。ebxレジスタの値をアドレスとしてgets()をコールすることで、運よくメモリ違反は起こらず値の読み込みに成功します。 このテクニックを利用することで、次のように44Bのコードを書くことができました。
main(){printf("%d",-(-atoi()|5461),gets());}
◆最短コード達成者の皆さん
最短コードにたどり着いた神コードを紹介しておきます。それぞれ異なったコードではありますが、基本的な考え方は同じです。gets()をコールする前にebxレジスタの値をpushするコードを書くことができれば引数を省略することができます。変数を宣言して、その初期値を計算式に組み込むことで実現しているのも面白いですね。
☆rotary-oさん
main(){printf("%d",~-atoi()&'窪'|1,gets());}
☆えちごやえちぜんさん
main(x){printf("%d",atoi(gets())-x&'檪'|x);}
☆SARUさん
main(){printf("%d",-(!gets()-atoi()|5461));}
☆hogeover30さん
main(n){printf("%d",n|~-atoi(gets())&'檪');}
☆みけCATさん
main(){printf("%d",-(5461|-atoi()),gets());}
「’窪’や’檪’って何？」という方のために少し補足しておきます。 UTF-8で’檪’は0xE6AAAA、’窪’は0xE7AAAAです。これらの文字をそのままUTF-8で保存すると、ファイルサイズが見た目より大きくなってしまいますが、SJISで保存しておくとそれぞれの文字は2Bとみなされます。今回の採点ルールではUTF-8に変換される前のファイルサイズが記録になりますので、10922という定数の代わりにこれらを用いることで1Bコードを短縮することが可能です。
◆文字コードが影響するコードについて
文字コードの判別や変換を行わなければ、’xx’=10922になるxxを見つけて埋め込むだけで良かったのですが、ideone.comでの採点（API使用）の都合上、文字コードの判別・UTF-8への変換が必要でした。APIを使用しない場合、たとえば
main(){printf("%d",atoi()-1&'*ｪ'|1,gets());}
のようなコードもideone.comで動かすことは可能ですが、今回は不正解としました。ご了承ください。
