Pythonで1つの座標点を別の座標点へ変換できるかどうかを判定するプログラム

問題の概要

開始点 (sx, sy) と目標点 (tx, ty) が与えられたとき、一連の移動操作によって開始点から目標点へ到達できるかどうかを判定します。ここでいう「移動」とは、ある点 (x, y) を (x, x+y) または (x+y, y) のいずれかに変換する操作のことです。

たとえば、入力が (sx, sy) = (1,1)、(tx, ty) = (4,5) の場合、出力は True になります。(1,1) → (2,1) → (3,1) → (4,1) → (4,5) という移動の連鎖が存在するためです。

解法のアプローチ

この問題は、目標点から逆算して開始点に戻れるかを調べることで効率的に解けます。以下の手順で solve() 関数を実装します。

• solve() 関数を定義し、sx, sy, tx, ty を引数として受け取ります。
• sx > tx または sy > ty の場合は False を返します(目標点が開始点を下回ると、それ以上到達できないため)。
• sx == tx の場合は、(ty - sy) mod sx == 0 かどうかを返します(x座標が一致している状態では、y座標の差分は sx の加算だけで埋められるため)。
• sy == ty の場合は、(tx - sx) mod sy == 0 かどうかを返します(y座標が一致している状態では、x座標の差分は sy の加算だけで埋められるため)。
• 上記以外の場合は、solve(sx, sy, tx-ty, ty) または solve(sx, sy, tx, ty-tx) を再帰的に呼び出します。

アルゴリズムのポイント

各移動では必ず片方の座標が増えていくため、目標点に達した直前の状態を考えると、「大きい方の座標から小さい方の座標を引いた値」が直前の点になります。この性質を利用して目標点側から差し引きながら再帰的に探索を進めることで、全パターンを網羅する非効率な探索を避けられます。

実装例

以下にPythonでの実装例を示します。

def solve(sx, sy, tx, ty):
    if sx > tx or sy > ty:
        return False
    if sx == tx:
        return (ty - sy) % sx == 0
    if sy == ty:
        return (tx - sx) % sy == 0
    return solve(sx, sy, tx - ty, ty) or solve(sx, sy, tx, ty - tx)

(sx, sy) = (1, 1)
(tx, ty) = (4, 5)
print(solve(sx, sy, tx, ty))

入力

(1,1), (4,5)

出力

True

まとめ

このプログラムでは、目標点から逆方向に辿る再帰的なアプローチと、座標が一致した時点での剰余演算による一括判定を組み合わせることで、開始点から目標点への到達可能性を効率的に判定できます。移動操作が単調に座標を増やす性質を持つため、条件を満たさない枝は早い段階で切り捨てられるのがポイントです。