Power Set

anarchy golf C

ちょっと前に http://golf.shinh.org/p.rb?Power+Set が終了した。この問題は、Power Set の表現と数値（二進数）との対応関係に気付くと解答が得られる。つまり、

 0: 0
 1: {0}
 2: {{0}}
 3: {0, {0}}
 4: {{{0}}}
 5: {0, {{0}}}
 6: {{0}, {{0}}}
 7: {0, {0}, {{0}}}
 8: {{0, {0}}}
 9: {0, {0, {0}}}
10: {{0}, {0, {0}}}
11: {0, {0}, {0, {0}}}
12: {{{0}}, {0, {0}}}
13: {0, {{0}}, {0, {0}}}
14: {{0}, {{0}}, {0, {0}}}
15: {0, {0}, {{0}}, {0, {0}}}
16: {{{{0}}}}

で、1, 3, 7, 15 を見るとわかるように、二進数表現の各ビットが LSB より

bit 0(  1): {0}
bit 1(  2): {{0}}
bit 2(  4): {{{0}}}
bit 3(  8): {{0, {0}}}
bit 4( 16): {{{{0}}}}
bit 5( 32): {{0, {{0}}}}
bit 6( 64): {{{0}, {{0}}}}
bit 7(128): {{0, {0}, {{0}}}}
bit 8(256): {{{0, {0}}}}
bit 9(512): {{0, {0, {0}}}}
...

のようになっていると考えることができる。ところが、これをもう一度よく見てみると、一番外側の中括弧 '{' と '}' を取り除くと、bit 番号自身をそのまま数値として Power Set の表現に対応させたものになっている。bit 0,1,2,3,... と最初の例にあげた数値 0,1,2,3,... の Power Set 表現が外側の中括弧を取り除くと同じだ。
つまり、入力の数値に対する Power Set 表現を得るには、入力の数値を二進数で処理し、各 Set bit に対する Power Set の表現を出力すればよい。その際、各 bit は、その bit 番号に対応する Power Set 表現を用いればよい。その bit 番号に対する Power Set 表現は、その bit 番号を数値とみなして同様に繰り返せばよい。つまり、リカーシブに処理すればよいことがわかる。
ちょっと、わかりにくいかもしれないが、たとえば、18 (10010B) を考えてみる。
10010B なので、LSB から 1 番目(0 基準)の bit と 4 番目の bit に対応した Power Set 表現をつなぎ合わせると解が得られる。つまり、

{ [1 番目の表現], [4 番目の表現] }

となる。で、1 は、1B、4 は、100B なので、

{ {0}, { [2 番目の表現] } }

となり、同様に処理して、、

{ {0}, { { [1 番目の表現] } } }

となり、結局、

{{0}, {{{0}}}}

となる。
う〜ん、あまりわかりやすい説明でないな。でも、まぁ、このようにリカーシブに処理していけば、解答が得られる。
さて、問題の入力は、1, 2, 4 だが、それらを上で説明した数値表現で示すと、1, 3, 65535 に対応する。これら 3 つの数の Power Set 表現を上に述べた方法で出力すれば本問の解答が得られる。
JavaScript の解答、Groovy の解答は、このようにして作成した。公開後、JavaScript の解答は、murky-satyr さんにより著しく縮められたが、方針は同じだ。
not さんの解答@Cも、上に述べたやり方と同じだ。入力に関しては、1 を 1, 2, 16 bit シフトさせたもの、つまり、2, 4, 65536 に変換しているが、すぐに 1 減算しているので、1, 3, 65535 を処理している。そして、ffs() を用いることで、bit 番号を得ている。その bit 番号に対して、リカーシブに処理関数を呼び Power Set 表現に変換してるところは、上で述べたとおりだ。ffs() の返す bit 番号は、1 基準なので、処理の最初で、1 減算することでうまく処理できている。
ffs() で、一番下の bit を処理した後は、

a&=a-!!main(ffs(a))

としているが、これは、

a&=a-1

と同じだ。私は、ここがなかなかすごいなと思うけど、これは、処理した一番下の bit のクリアーになっている。a に色々な数値を入れて試してみると、確かに一番下の bit をクリアーしているな。なんでそうなるんだろ？a が奇数なら LSB が立っているので、-1 すると、その LSB がクリアーされ、& すると、結局 a-1 と同じになる。a が偶数の場合は、一番下の set bit 以下が、all one に変換されるので、& を取ると、結局、その一番下の set bit がクリアーされるということか。これは、ちょっと、簡単には思いつけないな、、、っと言いつつ、この式は、過去に見たことがある気がする。何の時だったろう？
Power Set はなかなか難しい問題だった。
〜〜〜〜〜

Joshephus MamakoDate Sequence EASY

なかなか面白い問題だった、ってまだ終わってないけど。特に C は面白い。128B くらいの時は、bzero() を使っていたが、それをやめたら、122B ができた。ところがそれ以上縮まない。しばらく考えたが、全く別の方針を思いついたら、111B まで縮んだ。しかし、トップ inaniwa さんの、110B には、あと 1B だが、ちょっともう無理な気がする。これ、なかなか良問だな。

Number Sequence

どんな数列か考えよ、という問題。ただ、ヒントが与えられていたので、簡単すぎた。ヒント無しでいいんじゃないのかな？もう少し複雑にしてもいいと思う。

hexdump & hexdump2

ちょっと面倒過ぎ？難しくはないので、プログラムは書こうと思えば書けるが、ただ面倒なのでやる気が起きない。
〜〜〜〜〜
ところで、最近、ゴルフサーバーがなんか調子悪い気がする。パフォーマンスが。実行時間がかなり大きくぶれるような気がするし、また、ここ数日は、Groovy が timeout になってしまい、まったく通らない。何か、サーバーに変更が入りつつあるのかな？
〜〜〜〜〜
ところで(again)、先日、6/28 は誕生日だった。33歳になった。去年は、32歳。おととしは、31。その前は、30。さらにその前は、、、、2F 。年喰ったなぁ。多分、あなごる最年長だろうな。