Hubspot amulet (HubSpot) - 3つのレバーを回す

どんな問題？

Hubspot amulet
http://www.checkio.org/mission/hubspot-amulet/

レバーが3つあり、1つのレバーを回すと、他のレバーも回転する。レバーの関係は、3x3の行列で与えられる。レバーを1,2,3の順に回して、それぞれの角度が0, 225, 315度にするには、レバーをそれぞれの何度回せばよいか求めよ。

引数は、3x3の行列が list of list で与えられる。行列の要素（倍率）は10未満の正の整数。
戻り値は、3つのレバーの回転角度を list of int で返す。角度は、-180～180の整数とすること。

行列が、

[1 2 3],  #  1 f2 f3
[3 1 2],  # s1  1 s3
[2 3 1]   # t1 t2  1

のとき、

• レバー1をX度回すと、レバー2はXの2倍(f2)、レバー3はXの3倍(f3)回る。
• レバー2をX度回すと、レバー1はXの3倍(s1)、レバー3はXの2倍(s3)回る。
• レバー3をX度回すと、レバー1はXの2倍(t1)、レバー2はXの3倍(t2)回る。

例題：

checkio([
    [1, 2, 3],
    [3, 1, 2],
    [2, 3, 1]])
checkio([
    [1, 4, 2],
    [2, 1, 2],
    [2, 2, 1]])

どうやって解く？

単純に総当たりで試しても解けそうだ。ただ時間が掛かりそうなので、別のやり方を検討しよう。

連立方程式を作って解く方法もある。レバー1,2,3の角度を、a1,a2,a3とすると、

a1*1 + a2*s1 + a3*t1 = 0
a1*f2 + a2*1 + a3*t2 = 225
a1*f3 + a2*s3 + a3*1 = 315

が成り立つので、これを満たす a1,a2,a3を求めればよい。

f1,f2...の数値が決まっていれば簡単に解けるのだが、変数のままで解くのは難しい。
あれこれ調べていると、逆行列を使ってできるようだ。

A = [[1,s1,t1],[f2,1,t2],[f3,s3,1]]
X = [a1, a2, a3]
P = [0, 225, 315]

とすると、
AX=P
これを、
X=A^-1P
に変形すれば、答えが求められる。（A^-1は逆行列）

Aは引数の行列を転置させたものだから、引数を転置させて逆行列を求めてP[0, 225, 315]を掛ければいい。

def invert(matrix33):
    # 3x3行列の逆行列を求める
    (a11, a12, a13), (a21, a22, a23), (a31, a32, a33) = matrix33
    det = a11 * a22 * a33 + a21 * a32 * a13 + a31 * a12 * a23 - a11 * a32 * a23 - a31 * a22 * a13 - a21 * a12 * a33
    print(det)
    temp = [[a22 * a33 - a23 * a32, a13 * a32 - a12 * a33, a12 * a23 - a13 * a22],
            [a23 * a31 - a21 * a33, a11 * a33 - a13 * a31, a13 * a21 - a11 * a23],
            [a21 * a32 - a22 * a31, a12 * a31 - a11 * a32, a11 * a22 - a12 * a21]]
    return [[e / det for e in r] for r in temp]

def transposed(matrix):
    # 転置行列
    return [list(r) for r in zip(*matrix)]

def dot(matrix, vector):
    # 行列の乗算
    return [sum(a * b for a, b in zip(matrix[i], vector)) for i in range(len(vector))]

def checkio(matrix):
    # X = A-1 * P
    result = dot(invert(transposed(matrix)), [0, 225, 315])
    # 角度を-180～180に修正
    return [(round(e) + 180) % 360 - 180 for e in result]

これで完成・・・のはずだったのだが、実際にやってみると、引数が [1,3,5],[3,1,5],[2,5,1] のときにエラーになる。
正解は、[-135, -45, 135] のはずだが、出力された答えは [91, -28, -4] になっていた。厳密には [91.4516, -27.5806, -4.3548] という浮動小数点の値になっていて、上の連立方程式の解としては間違っていないようだが、整数値ではないので、問題の答えとしては不適切。

正解のXからPを逆算してみると、[0, 225, -765] となった。
なるほど、これは 0～360度の範囲に直せば [0,225,315] になるわけだから、連立方程式の答えではないが、問題の答えとしては正しいわけか。
つまり、最初に考えた、

a1*1 + a2*s1 + a3*t1 = 0
a1*f2 + a2*1 + a3*t2 = 225
a1*f3 + a2*s3 + a3*1 = 315

という式が不十分だったわけだ。

うーん、じゃあどうしたらいいだろう？
……
思いつかないので、最初に考えた総当たりを書いてみる。3つのレバーの回転角度を-180～180度の範囲ですべて試してみる。

まとめ（総当たり）

from itertools import product

def rotate(angles, matrix):
    result = [0, 0, 0]
    for i, angle in enumerate(angles):
        result[0] += matrix[i][0] * angle
        result[1] += matrix[i][1] * angle
        result[2] += matrix[i][2] * angle
    return [n % 360 for n in result]

def checkio(matrix):
    for angles in product(range(-180, 180), repeat=3):
        if rotate(angles, matrix) == [0, 225, 315]:
            return list(angles)

http://www.checkio.org/mission/hubspot-amulet/publications/natsuki/python-3/first/

Run&Checkをクリックしてから、かなり時間が掛かったが、なんとかクリア。
ちょっと不満足・・・。

他の人の答え

from itertools import product
 
def checkio(m):
    for x in product(range(-180,180,45), repeat = 3): # 45 = gcd(225, 315)
        t = [sum(m[j][i]*x[j] for j in range(3)) % 360 for i in range(3)]
        if t == [0, 225, 315]: return list(x)
 
    # Answer is only multiple of 45.

http://www.checkio.org/mission/hubspot-amulet/publications/Sim0000/python-3/multiple-of-45/

答えは45度の倍数になるのだから、1度ではなく45度区切りで総当たりすればいいわけか。
これは、言われてみればその通りなんだけど、思いつかなかった・・・。