どんな問題でも解けるコード!?

今回は,

どんな問題も,いくらでも大きい数値が使用可能ならば,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回の計算結果は全て異なるものになります(←深く考えず書いたので要確認w).
「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で解ける!!!!!と思いきや,現実は厳しいですw
数値が256までしかないので, この方法だけで問題が短く解けることはまずありません.

しかし, このような考え方から数値関数による長文圧縮の手法が生まれました.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2013-02-03 (日) 17:21:52 (2025d)