258. Tower of Hanoi

あなごるのCに参戦してるnotってのは僕です。
最近忙しいのであまりやれてないけど落ち着いたらまたやる予定。
Active problemsは一つも参戦してないので昔の問題の解説でもしようか。

258. Tower of Hanoi

n;main(o,t){for(t%=9;++n;)putchar(n>>-t?n=--o,10:(n-~o*(n&-n)<<~t)%3+65);}

まぁ最初なんで一番の自信作から。

１行目は(n&n-1)%3+65、２行目は*1%3+65と(n+(n&-n))%3+65なので
(n+(o?-1:1)*(n&-n))%3+65とまとめれる。
さらに変形して(n+(o?2:1)*(n&-n))%3+65
o?2:1が-~oと同じであることを利用すると三項演算子を使わずに書けて(n-~o*(n&-n))%3+65
まさかここまで縮むとは思ってなかったので鳥肌が立った。

ただし、これは入力が奇数だった場合の話。（入力読んでないけど）
入力が偶数だった場合'b'→'c','c'→'b'としなければならない。
要するに(n-~o*(n&-n))%3を0→0,1→2,2→1としなければならないということ。
最初は(n-~o*(n&-n))*(n%2?1:2)%3としていたが
２の偶数乗の３の剰余は１、２の奇数乗の３の剰余は２なので
入力が偶数なら奇数だけ左シフト、入力が奇数なら偶数だけ左シフトすればいい。
以上で(n-~o*(n&-n)<<~t)%3+65が導き出せる。

ほかにもn=--o（２行目の初期化とループ終了条件をあわせている）や
t%=9（あえてunsignedにしないことで１バイト稼げる）とか
74Bの中にいろいろ詰めこんであるコードなので見ていると和む。

次は何を書こうか。no deadlineだけどmaze solvingとかもそのうち解説したい。
何か希望の問題があったらコメントください。

*1:n|n-1)+1)%3+65を出力すればいいのだが この式をよく考えてみると(n-(n&-n