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

紆余曲折の結果、wajさんによって究極のコードが提起された。それは、2.5進数を使うというものだった。

まず問題点をクリアにしよう。

main(d){for(d=time()&1?'xxx':yy;d/=2;)puts(d&1?"no":"yes");}

こう書いてしまうと、forの終了条件 d/=2 の意味するところは、2で割った結果が0になったとき、すなわち、その1step前ではdが1のときという意味になる。(dが0の場合は、その一回前にループ終了条件を満たして終了しているはずだからありえない) よって、forループを脱出する直前のputsでは、noが表示される。2つのInputの最後のテストケースがnoならばこれでいいのだが、あいにく、片方はno,片方はyesである。よって、このプログラムではいけない。

この問題を回避するために我々は3進数を導入した。/=2の部分を/=3に変更した。この結果、xxxの部分は3文字から4文字に。yyの部分は2桁から3桁になった。

main(d){for(d=time()&1?'xxxx':yyy;d/=3;)puts(d&1?"no":"yes");}

(上の文章をコピペして一部変更する)
こう書けば、forの終了条件 d/=3 の意味するところは、3で割った結果が0になったとき、すなわち、その1step前ではdが1か2のときという意味になる。(dが0の場合は、その一回前にループ終了条件を満たして終了しているはずだからありえない) よって、forループを脱出する直前のputsするときに、yesかnoかの出力を選択する余地がある。

これに対し、wajさんの提起したその究極のコードとは、こうだ。

main(d){for(d=time()&1?'zMM':90;d*=.4;)puts(d&2?"no":"yes");}

*=.4 の部分が何とも怪しげだ。shiftのために2で割っていくのが2進数、3で割っていくのが3進数。.4は、0.4の意味であり、2/5倍。すなわち、5/2で割っているから、これは5/2=2.5進数だ。

2.5進数で表すことによって、定数部を'zMM'と90というように1文字ずつ削ることが可能になった。そのかわり、d/=3がd*=.4と1文字増えるのでトータルでは、1文字減。これで61byteだ。

(さきほどの文章をコピペして一部変更する)
こう書けば、forの終了条件 d*=.4 の意味するところは、0.4を掛けた結果が0になったとき、すなわち、その1step前ではdが1か2のときという意味になる。(dが0の場合は、その一回前にループ終了条件を満たして終了しているはずだからありえない)　よって、forループを脱出する直前のputsするときに、yesかnoかの出力を選択する余地がある。

以下、この2.5進数の定数をどうやって決定しているのか簡単に説明しておく。

いま、[a,b) を a以上b未満を意味するものとする。{ a,b } は集合を意味するものとする。

たとえば、d*=.4を実行したとき、d=1になる数が欲しいとする。dはint型だから暗黙のうちに小数部が切捨てられる。すなわち、[1,2)×2.5 = [2.5,5) = { 3,4 } このとき、d*=.4のあと、d=1になる偶数のほうのdを選択したいなら、{3,4}のうち4のほうを選択しておけばいい。

同様に、d*=.4を実行したときに、d=2になる数は、[2,3)×2.5 = [5,7.5) = { 5,6,7 }　このとき、d*=.4のあと、d=2になる奇数のほうのdを選択したいなら、{ 5,6,7 }のうち、5か7を選択すればいい。

ところで0.4以外にはダメなのだろうか？いま2.5進数で考えたが、a進数ではどうなるか考えてみよう。

(さきほどの文章をさらにコピペして一部変更する)
forの終了条件 d/=a の意味するところは、aで割った結果が[0,1)になるとき、すなわち、その1step前ではdが[0,a) のときという意味になるが、dが0の場合は、その一回前にループ終了条件を満たして終了しているはずだからありえないので、結局のところ [1,a) である。これが、「forループを脱出する直前のputsするときに、yesかnoかの出力を選択する余地がある」ようにしようと思えば、a > 2である必要がある。たとえば、a = 3(3進数)のときは、[1,3) = { 1, 2 }になって、「forループを脱出する直前のputsするときに、yesかnoかの出力を選択する余地がある」

要するに、2.5進数でなくとも、2.1進数であろうが、2.0001進数であろうが構わなかったのである。d*=a のaとしてはaが .5 だと2進数。.4だと2.5進数。.3だと3.3進数の意味になるので、.4しか選択の余地がない。(つづく)