โปรแกรมหาจุดที่ใกล้ที่สุดซึ่งมี x หรือ y เหมือนกันด้วย Python

สมมติว่าเรามีชุดจุดในอาร์เรย์ pts และจุดปัจจุบัน (x, y) จุดที่ถูกต้อง (valid) คือจุดที่มี x เหมือนกันหรือ y เหมือนกับจุดปัจจุบัน เราต้องคืน index ของจุดที่ถูกต้องที่มีระยะทาง Manhattan น้อยที่สุดจากจุดปัจจุบัน ถ้ามีหลายจุด ให้คืน index น้อยที่สุด (Manhattan distance ระหว่าง (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) แต่ index ของ (3,4) น้อยกว่า

ขั้นตอนการแก้ปัญหา

• x, y = pt
• idx = -1, smallest = infinity
• วนลูปแต่ละ p ใน pts:
  • ถ้า p[0] == x หรือ p[1] == y:
    • dist = |x - p[0]| + |y - p[1]|
    • ถ้า dist < smallest: idx = index ของ p, smallest = dist
    • มิฉะนั้นถ้า dist == smallest และ index ของ p < idx: idx = index ของ p, smallest = dist
• คืนค่า idx

ตัวอย่างโค้ด

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