完全最小ハッシュ - 西尾泰和のはてなダイアリー

前回「算数は苦手なので」で局面が全部で何通りあるかを人間が計算するのは面倒だからプログラムを書いたという話をした。で、「局面からなるべく小さい範囲の整数へencode/decodeする*C言語的な意味でのfunction*を作る」をやろうとしていたのだが、これは要するに完全最小ハッシュだね。頭の中でこの二つがつながっていなかった。

で、AndとOrとChoiceとResource#takeに関しては何も難しいところがないのだけどもUnorderedが難しい。というのも、Andを*, Orを+で表現すると、Unordered(X + Y)は生成時にUnordered(X) + X * Y + Unordered(Y)に書き換えられていて、単に数を数えるだけならこれで十分なのだけどもエンコードをしようと思った場合はX * Yの部分が「一つ目の引数がXで二つ目がYだった場合」とその逆とがあるのを正規化するコードが必要になるわけだ。

あー、Andに正規化コードを吐くオプションを付け加えてその問題を解決しようとしたがそれではダメなのか。Unorderedを展開した結果は別の特別なOrじゃないといけないのか。分岐のためのフラグを二つとって、3通りに場合分けするノードが必要なのか。しかしそのノード自体がまたAndやUnorderedの中に入ったらどうするのか。むー。Orと同じようにくくりだす必要があるな。

整理しよう。Orが最も外になるようにくくりだす必要があるのはなぜだったか。それは同一のリソースからResource#takeが行われる場合、片方でtakeされたかどうかがもう片方の取れる選択肢に影響を与えるからだ。だからAnd(Or(r.take(), X), Y)のようなときにはOr(And(r.take(), Y), And(X, Y))に展開してしまって、Orの分岐の時点でdeepcopyしたコンテキストを渡すことでパラレルワールド化する。で、最後に足し合わせる。

あ、そうか、Orの条件分岐を与えられたフラグだけでやろうとするから(X, Y)と(Y, X)が別の部分に分かれてしまって問題になるのか。Orにもオプションをつけてやればいいのか。

    x = Choice(3, "foo")
    y = Choice(5, "bar")
    rule = Unordered(Or(x, y, "is_bar"))

これが

Or(
    And(Choice(3), Choice(5)), 
    Or(
        Unordered(Choice(3)), 
        Unordered(Choice(5))))

こうなって

(長いので削除)

こうなる。いっぱい中間結果を入れる変数が生成されているけど、gccが頑張って消してくれるはずだから気にしない。foo_0, foo_1, bar_0, bar_1, is_bar_0, is_bar_1の6つの引数をとって、or2の値を返せばOK。

で、デコーダの方は渡された整数をor2に入れてから

(長いので削除)

ん、とりあえずxor = Falseあたりがちょっと間違っているな。encodeで分岐の前に二つのフラグからxorの値を計算しているのと同様に、decodeでは分岐の後でxorの値を使って二つのフラグの値を計算しないと行けないんだな。となるといまxorは一時的な変数だから固定の名前でいいやってやってるけどネストする可能性があるからユニークな名前をつける必要があるわけか。

むー。カオスだ。いったん依存関係のグラフを作ってからコードに落とすべきだったのかもなぁ。

与えた引数をエンコードしてデコードするテストが走り始めた。ぼこぼこ落とし穴がある。一つ一つパズルを解いていく感じ。

えーと。エラーになるうちはまだいい。最後まで走って答えが違うとかやばい。
{'bar_1': 3, 'bar_0': 2, 'is_bar_1': True, 'is_bar_0': True}をエンコードして{'or2': 10}になった。えっと、これはあってるんだよな。

□
□□
□□□
□□■
□□

うん、0-originだから10番目だな。これをデコードするときになんで間違ってるのか。出力されたデコーダの該当部分のコード

is_bar_0 = False
if or2 < 21:
    is_bar_xor = True
    or1 = or2
    if or1 < 15:
        is_bar_0 = True
        unordered1 = or1
        n = 5
        choice1_0 = 0
        while unordered1 >= n:
            unordered1 -= n
            choice1_0 += 1
        choice1_1 = unordered1
        bar_0 = choice1_0
        bar_1 = choice1_1

ぶは、出力しているデコーダが全然間違っているw　nをデクリメントしないと行けないよね。む、それでも結果があわない。ああ、bar_0 = choice1_0はbar_0 = choice1_0 + choice1_1が正解か。違う。choice1_1 = unordered1がchoice1_1 = unordered1 + choice1_0になるのが正解か。そうだ。

次何すればいいんだ。And(Or(Choice, Choice))のテストをしてUnordered(Or(Choice, Choice))のテストをしたからResource#takeのテストが足りないんだな。

それのテストも通ったのでよろこんでキリンを処理しようとしたら

    if kirin_is_mochigoma_1:
        ,  = _0, _1
    else:
        ,  = _1, _0
    take0 = kirin

うへえ。項書き換えの結果「Unorderedで変換された」マークのついているAndは直下に持っているのが別のAndだからvar_name属性が空っぽだ。どうすんだこれ。 > Or(And(And(Take(Resource(X)), Choice(2)), And(Choice(1), Choice(2))), Or(Unordered(And(Take(Resource(X)), Choice(2))), Unordered(And(Choice(1), Choice(2)))))

あー、そうかー、直下のノードに対応している変数名だけがUnorderedでコピーされているわけでは名うて、子孫ノード全体のをコピーしているんだった。

        self.vars = [(typ, name + suffix, comment) 
                     for (typ, name, comment) in rule.vars
                     for suffix in ["_0", "_1"]]

だからここで復元する対象もこれを使えばいいのか。