Pythonでベクトルxを90度回転・加算してベクトルyに到達できるか判定するアルゴリズム

2次元平面上に3つのベクトル x、y、z があるとします。ベクトル x を起点として、「90度(時計回り)の回転」または「ベクトル z の加算」を必要な回数だけ繰り返すことで、ベクトル y に到達できるかどうかを判定するのがこの問題です。

たとえば、入力が x = (-4, -2)、y = (-1, 2)、z = (-2, -1) である場合、出力は True になります。x に対して z を加算する操作と 90 度の時計回り回転を組み合わせることで、y = (-1, 2) の位置に到達できるからです。

解法のアプローチ

この問題は、次の手順に沿って解くことができます。

1. util() 関数の定義

まず、引数として p、q、r、s の4つの値を受け取る関数 util() を定義します。

• d := r * r + s * s を計算します。
• d が 0 と等しい場合は、p と q がともに 0 であれば true を返し、そうでなければ false を返します。
• それ以外の場合は、(p * r + q * s) と (q * r − p * s) がどちらも d で割り切れるときに true を返し、割り切れない場合は false を返します。

2. メイン処理での判定

続いて、メインメソッド内で以下の判定を行います。

• util(p[0] − q[0], p[1] − q[1], r[0], r[1])、util(p[0] + q[0], p[1] + q[1], r[0], r[1])、util(p[0] − q[1], p[1] + q[0], r[0], r[1])、util(p[0] + q[1], p[1] − q[0], r[0], r[1]) のいずれか1つでも true を返せば、結果として True を返します。
• どの呼び出しも true を返さない場合は、False を返します。

ここで4つのパターンをチェックしているのは、90度の回転を繰り返すとベクトルの向きが「元のベクトル」「符号を反転させたベクトル」「90度回転させたベクトル」の組み合わせで変化しうるためです。これらすべてのケースを網羅的に確認することで、到達可能性を正確に判定できます。

実装例

以下のPythonコードを見ると、処理の流れがより理解しやすくなります。

def util(p, q, r, s):
    d = r * r + s * s
    if d == 0:
        return p == 0 and q == 0
    return (p * r + q * s) % d == 0 and (q * r - p * s) % d == 0

def solve(p, q, r):
    if util(p[0] - q[0], p[1] - q[1], r[0], r[1]) or util(p[0] + q[0], p[1] + q[1], r[0], r[1]) or util(p[0] - q[1], p[1] + q[0], r[0], r[1]) or util(p[0] + q[1], p[1] - q[0], r[0], r[1]):
        return True
    return False

p = (-4, -2)
q = (-1, 2)
r = (-2, -1)
print(solve(p, q, r))

入力

(-4, -2), (-1, 2), (-2, -1)

出力

True