Pythonで同じx座標またはy座標を持つ最も近い点を見つけるプログラム

問題の概要

ある配列 pts に複数の点が与えられているとします。さらに、現在位置を表す別の点 (x, y) も与えられています。

ここで「有効な点」とは、現在位置と同じ x 座標、または同じ y 座標を共有する点と定義します。この中から、現在位置 (x, y) からのマンハッタン距離が最小となる有効な点のインデックスを返す必要があります。条件を満たす点が複数存在する場合は、インデックスが最も小さい点を返してください。

注: 2点 (a, b) と (p, q) の間のマンハッタン距離は、|a − p| + |b − q| で表されます。

例

入力が次の場合:

pts = [(1,2), (3,1), (3,4), (2,3), (4,4)]
pt = (2,4)

出力は 2 になります。これは、最近接の候補として (3,4) と (2,3) の2つの有効な点が存在しますが、(3,4) のインデックス（2）の方が (2,3) のインデックス（3）より小さいためです。

解決のための手順

この問題は、以下のステップに従って解くことができます。

• x, y に pt の値をそれぞれ代入する
• idx を -1 に初期化する（有効な点が見つからなかった場合の戻り値）
• smallest を無限大（infinity）に初期化する
• pts 内の各点 p に対して以下を繰り返す
  • p[0] が x と等しい、または p[1] が y と等しい場合:
    • dist := |x − p[0]| + |y − p[1]| を計算する
    • dist < smallest の場合:
      • idx を pts 内の p のインデックスに更新する
      • smallest を dist に更新する
    • dist == smallest の場合:
      • pts 内の p のインデックスが現在の idx より小さければ、idx と smallest を更新する
• 最後に idx を返す

実装例

それでは、上記の手順を Python コードで実装してみましょう。

def solve(pts, pt):
   x, y = pt
   idx = -1
   smallest = float("inf")
   for p in pts:
      if p[0] == x or p[1] == y:
         dist = abs(x - p[0]) + abs(y - p[1])
         if dist < smallest:
            idx = pts.index(p)
            smallest = dist
         elif dist == smallest:
            if pts.index(p) < idx:
               idx = pts.index(p)
               smallest = dist
   return idx

pts = [(1,2), (3,1), (3,4), (2,3), (4,4)]
pt = (2,4)
print(solve(pts, pt))

入力

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

出力

2

まとめ

このアルゴリズムは、すべての点を一度走査するだけでよいため、時間計算量は O(n) となります。各点について「有効かどうか」の判定を行い、有効であればマンハッタン距離を計算して最小値を追跡します。同距離の点が複数ある場合はインデックスの小さい方を採用することで、問題の要件を正しく満たすことができます。