佳境
C++で完全最小ハッシュを吐き出すPythonスクリプトのデバッグが佳境に入ってきた。キリンの配置を最小ハッシュ化すると片方が持ち駒であるときに正しい値にならない。頭の整理のために問題を書いてみる。
問題を再現する最小のパターンにするとUnordered(And(Or(Choice(3), Choice(1)), Choice(2)))、Choiceの3, 2, 1にそれぞれthree, two, oneと変数名をつけることにしよう。このとき、まずAnd(Or(...))の書き換えパターンによってOr(And(three, two), And(one, two))になる。ここまではOK。次にこれがUnordered(Or(...))の書き換えパターンによって
Or( Or( Unordered(And(three, two)), Unordered(And(one, two)) ), And( And(three, two), And(one, two) ) )
こうなる。
この外側のOrの範囲は問題なく動いている。問題は後半。整数から局面へのデコーダの該当部分のソースを見てみよう
}else{ // And(And(Choice(3), Choice(2)), And(Choice(1), Choice(2))) is_choice2_1 = false; and2 = or3 - 24; and0 = and2 / 2; and1 = and2 % 2; // And(Choice(3), Choice(2)) choice1 = and0 / 2; choice0 = and0 % 2; // Choice(3) three = choice1; // Choice(2) two = choice0; // And(Choice(1), Choice(2)) choice2 = and1 / 2; choice0 = and1 % 2; // Choice(1) one = choice2; // Choice(2) int two2 = choice0; // HERE if(is_choice2_0){ three_1 = three; two_1 = two; one_0 = one; two_0 = two2; // HERE }else{ three_0 = three; two_0 = two; one_1 = one; two_1 = two2; // HERE }
HEREと書かれている部分は手で修正した。もとはtwo。Unordered(Or(X, Y))のXとYに同一の名前の変数があると衝突して上書きしてしまうという現象。
書いて散歩したらわかった!if(is_choice2_0)は、もともとencoderが(ture, false)の時と(false, true)の時を同一視するためにまとめてつけて、decoderにも深く考えずに逆向きの変換にしてつけたのだけども、まずdecoderには分岐が必要ない(片方を返せばいいだけだから)
あと、最後にまとめてやっているけど// And(Choice(1), Choice(2))の直後でthree_1 = three; two_1 = two;してあれば、そのあとの処理でtwoが上書きされても痛くも痒くもない。
根本的な問題点は最後にまとめてやっていることだ。よし、修正しよう。
Pythonのコードはこんなのになっている
result += Renderer.multiline_if( oname + "_0", [Renderer.assign(v + "_1", v) for typ, v, com in self.r1.args] + [Renderer.assign(v + "_0", v) for typ, v, com in self.r2.args], [Renderer.assign(v + "_0", v) for typ, v, com in self.r1.args] + [Renderer.assign(v + "_1", v) for typ, v, com in self.r2.args])
あと当たり前だけどもencoderも同じ問題を抱えている。
if(is_choice2_1){ three = three_0; two = two_0; one = one_1; two = two_1; }else{ three = three_1; two = two_1; one = one_0; two = two_0; }
修正した!OK, テスト通過!
むう、一気にラスボスに攻め込んだがtestがfailするなぁ。なんかマイナスになっている値があるし。問題が再現する範囲で削るか。
かなり小さくなった。
All = And( Unordered( Or( Choice(2, "foo"), Choice(1, "bar"), "is_bar") ), Choice(2, "baz"))
これをテストすると(0がfail)
111111110000
1@0(0): 1, 1, 0, 0, 0, 12345, 12345, 1@1(1): 1, 1, 0, 0, 1, 12345, 12345, 1@2(2): 0, 1, 12345, 12345, 0, 0, 0, 1@3(3): 0, 1, 12345, 12345, 1, 0, 0, 1@4(4): 0, 1, 12345, 12345, 0, 0, 1, 1@5(5): 0, 1, 12345, 12345, 1, 0, 1, 1@6(6): 0, 1, 12345, 12345, 0, 1, 1, 1@7(7): 0, 1, 12345, 12345, 1, 1, 1, 0@8(49388): 1, 0, 12345, 0, 0, 0, 12345, 0@9(49389): 1, 0, 12345, 0, 1, 0, 12345, 0@10(49388): 1, 0, 12345, 0, 0, 1, 12345, 0@11(49389): 1, 0, 12345, 0, 1, 1, 12345,
なんかあふれてるし(12345はundef代わり)
とりあえずi = 8の時を追えばいいのね。
えーと、encoderの条件分岐がおかしくてundefの値を拾ってしまっているね。よくこれで動いたないままで。
OK, わかった。Unorder(Or(...))が書き換えられてOr(Or(Unordered(.....)))になるときに、Orには「Unorderedによって書き換えられたフラグ」が立つのだけど、And(Or(...))の書き換えでOr(And(...))にするときにそのフラグを引き継いでいない。直したら子の小さいテストは通るようになった。あたらめてラスボスに挑戦…むう、まだ0のところがあるなぁ。
1@59(59): 0, 0, 12345, 12345, 0, 2, 3, 3, 1@60(60): 0, 1, 12345, 0, 0, 12345, 1, 1, 1@61(61): 0, 1, 12345, 0, 0, 12345, 1, 2, 1@62(62): 0, 1, 12345, 0, 0, 12345, 1, 3, 1@63(63): 0, 1, 12345, 0, 0, 12345, 2, 2, 1@64(64): 0, 1, 12345, 0, 0, 12345, 2, 3, 1@65(65): 0, 1, 12345, 0, 0, 12345, 3, 3, 0@66(-1610694590): 0, 1, 12345, 0, 0, 12345, 65541, -2147385340, 0@67(-1610792896): 0, 1, 12345, 0, 0, 12345, 65541, -2147385339, 0@68(-1610891203): 0, 1, 12345, 0, 0, 12345, 65541, -2147385338, 0@69(-1610989511): 0, 1, 12345, 0, 0, 12345, 65541, -2147385337, 1@70(70): 0, 1, 12345, 1, 0, 12345, 1, 1, 1@71(71): 0, 1, 12345, 1, 0, 12345, 1, 2, 1@72(72): 0, 1, 12345, 1, 0, 12345, 1, 3, 1@73(73): 0, 1, 12345, 1, 0, 12345, 2, 2, 1@74(74): 0, 1, 12345, 1, 0, 12345, 2, 3, 1@75(75): 0, 1, 12345, 1, 0, 12345, 3, 3, 0@76(-1610694580): 0, 1, 12345, 1, 0, 12345, 65541, -2147385340, 0@77(-1610792886): 0, 1, 12345, 1, 0, 12345, 65541, -2147385339, 0@78(-1610891193): 0, 1, 12345, 1, 0, 12345, 65541, -2147385338, 0@79(-1610989501): 0, 1, 12345, 1, 0, 12345, 65541, -2147385337, 1@80(80): 0, 1, 12345, 0, 1, 12345, 0, 0,
最後の2つの数字に注目すると1,1 1,2 1,3 2,2 2,3 3,3 と来て4つゴミが入っている。