どんな問題でも解けるコード！？

わけのわけらない"乱歩"を作って何億ステップも動かしてれば
どんな問題も解けるんじゃないかと思っていた時期が私にもありました．
再帰でこれが実装できるか否かは面白そうな問題ですね．

今回は，

  • どんな問題も，いくらでも大きい数値が使用可能ならば，14バイト以下で解ける


    • ということを紹介したいと思います．テクニックとしては数値手法，12バイト構文の周辺ですね．

    例えば次のコードを見てみましょう：

  • a(T):ra(T-64)sa(T+T), a(N)


    • これは大体N/64の2進法展開の計算に対応しています．
    64で割った余りを2倍し，さらに64で割った余りを2倍し…という計算がおこなわれますね．
    「大体対応」という半端な表現をしたのは，正確な2進法展開とはずれがあるからで，
    「割った余り」といっても0のときは64が生き残るという影響で，2進法展開とは異なります．
    また，商が0のときはrが1回，商が1のときはrが2回実行されますね．

    何はともあれ，この構文にN=1からN=64を代入した結果を考えると，
    最初の6回の計算結果は全て異なるものになります（←深く考えず書いたので要確認ｗ）．
    「rを(1回または2回)+s」を6セット並べるパターンは64通りあり，それが全部実現されます．

    これを，64よりも大きな数でやるとどうなるでしょうか？？
    "いくらでも大きな数値を使用可能"という前提に立つならば，
    「rを(1回または2回)+s」を10000セット並べるみたいなものも，
    Nの値を変化させるだけで全て12バイトで作り出せる計算になります！

    しかし残念ながら，これでは任意の問題が解けるわけではありません．
    細長い道を直進しようとすると，「rを(1回または2回)+s」だけでは不可能です．
    そこで，必ずrが「1回または2回」で出てくるというのを修正する必要があります．
    簡単な実装方法を2つ紹介しましょう（他にもあるかもしれないけど）．

    まずは，「rを(1回または4回)+s」を並べるというもので，これを実装するには
    2進法の代わりに4進法を使うだけです：

  • a(T):ra(T-A)sa(T+T), a(N)


    • AやNのところを大きな数にすると，「rを(1回または4回)+s」を自在に並べられます．
    直進したければrを4回やればいいですね．

    別の方針は，「sを(0回または1回)+r」を並べるというものです．
    普通に書くと1回または2回になるので，1回目は実行されないというような処理をつけます．

  • a(X,T):Xa(s,T-A)ra(,T+T), a(,N)


    • AやNのところを大きな数にすると，「sを(0回または1回)+r」を自在に並べられます．
    実行ステップ的にはこちらの方法の方がスマートでしょうか？？？

    任意の問題が14Bで解ける!!!!!と思いきや，現実は厳しいですｗ
    数値が256までしかないので，この構文はほぼ役立たずですね．
    「sを(0回または1回)+r」を7セット並べるがために，わざわざ
    10バイト以上使って数値関数を作るなんてしませんよね．

    …本当でしょうか？確かに14Bで解くという野望にはほど遠いですが，
    本当にこの方法は応用が利かないのでしょうか？
    以下では改めて，この構文の持つ可能性を考えてみましょう．

    上記の方法では，同じ関数でありながら，異なる数値に対して
    様々な動作を割り当てており，それらで全ての動作を網羅しているが
    ゆえに任意の問題を解くことができるのでした．
    当然255種類の数値しかないと，全ての動作を網羅するなんて不可能です．
    しかし，255種類の数値に例えば

  • rまたはsrを7個並べたもの全種類
  • s,rを7個並べたもの全種類
  • s,sr,srr,srrを3個並べたもの全種類

    • などを割り当てることは可能でしょう．256個数値がないので，
    2種類を8個並べたものや，4種類を4個並べたものすべてを割り当てることは
    不可能です…が，ほぼすべてを割り当てることはできますね．

    この，色んな材料を詰め込んだ数値関数を一度作ってしまうと，
    例えば，s,rを8個並べた文字列を全てa(N)の形で2バイトに圧縮できるようになります．
    （上に述べたように，全てではなく「ほぼ全て」なのですが，面倒なので全てと書いています）．
    例えばssrrrsrsrsssrsrrrsrrssrsrsrrrsrrsみたいなのが，a(A)a(B)a(C)a(D)みたいになって，
    これだけ見ると脅威の圧縮率ですね．
    160個並べたものならa(数値)を20個なので，40バイトになります．…が，
    b(A,B):a(A)a(B)みたいな定義をしておくと，（定義を除いて）30バイトで書けたりと，
    たくさん並んでいるものに対してはさらに圧縮率を上げることができます．
    極端な話，f(A,B,C,D,E,…,Z):a(A)a(B)a(C)a(D)a(E)…a(Z)みたいな26変数数値関数を
    一度作ってしまうと，s,rの並び208個を27バイトに押し込められるようになります．
    s,rの無作為な並びに対しては，関数定義に十分な準備を割くと，準備以降は
    ほぼ1/8に圧縮できることになるのです．

    残念ながら，1/8に近い圧縮率を実現するには，関数定義の準備にかなりのバイト数を必要とするため，
    ほとんどの問題はこの方法を使っても，準備だけで，普通な解のバイト数を大きくオーバーします．
    しかし，100バイトを超すような（？）規則の乏しい長文系の問題で，
    共通なパーツが少なく上手な圧縮が難しい状況になってくると，
    多少のコストを払ってでも1/8に近い圧縮率が手に入ると，コストを上回る利がある場合があります
    （そんな問題は少ないのですが…，大体どの問題を指しているのか分かりますよねｗ）．

    あと一応補足しておきますが，

  • a(X,T):Xa(s,T-64)ra(,T+T), a(,N)

    • という構文そのものは，こちらの手法では使えません．
    a(A)a(B)とか並べても，a(A)が無限の繰り返しに入って終わりませんね．
    適度に打ち切る必要があるし，打ち切ったら打ち切ったで不要な部分が実行されたりして
    色々工夫しないとダメっぽいです．筆者も最適な書き方はまだよくわかっていない状況ですが，
    255以下の数値で応用させる場合の関数準備は14バイトよりもだいぶかかりますね．

    数値関数の良い作り方や，どういう並びを数値に記憶させると良いかなどは，
    筆者はまだまだ分かっていないことだらけです．
    みんな研究してHOJ学の発展につなげてくれることに期待！

    戻る inserted by FC2 system