Найти ближайший ключ в сетке словаря

Question

Предположим, у вас есть большая сетка, представленная словарем.В некоторых координатах есть «игроки», в то время как другие координаты пусты.Словарь

d = {(500,100): "player1", (480, 230): "player"}

(это местоположения игроков в сетке).

Теперь, если у вас есть координаты, скажем, (500, 90)Кто из двух игроков самый близкий?Я понимаю, что теорема Пифагора должна быть реализована каким-то образом, чтобы решить эту проблему, но я не понимаю, как реализовать ее в функции.Это самое дальнее, что я пришел:

d = {(500,100): "player1", (480, 230): "player"}
def nearest_player(grid, x-cor, y-cor):
'''print out (500,100) as the answer'''

Любые идеи будут с благодарностью.

Answer 1

Оказывается, вы можете сделать argmin в чистом Python с min(iterable, key=f), где f - это функция, которую нужно свернуть.Итак:

d = {(500,100): "player1", (480, 230): "player2"}

target_location = (500, 90)

def square_distance(v1, v2):
    return sum((x1 - x2)**2 for x1, x2 in zip(v1, v2))

nearest_location = min(d, key=lambda location: square_distance(location, target_location))
nearest_player = d[nearest_location]

Answer 2

Аналогично другим решениям, только немного по-другому.

d = {(500,100): "player1", (480, 230): "player2"}

target_location = (500, 90)

def get_square_distance(v1, v2):
    return sum((x1 - x2)**2 for x1, x2 in zip(v1, v2))

smallest_square_distance = float('inf')

for player_location, player in d.items():
    square_distance = get_square_distance(player_location, target_location)
    if square_distance < smallest_square_distance:
        closest_player = player
        smallest_square_distance = square_distance

print(closest_player)
Out: 'player1'

Я не уверен, что словарь - это лучшая структура данных для ваших целей.Список списков был бы более естественным.

Answer 3

Использование нормы NumPy:

In[9] newd = {np.linalg.norm(np.array(i)-np.array(c)):v for i, v in d.items()}

In [10]: newd
Out[10]: {10.0: 'player1', 141.4213562373095: 'player'}

In [12]: newd[min(newd)]
Out[12]: 'player1'

Answer 4

Вариант 1: грубая сила

Решением грубой силы может быть поиск всех игроков и поиск ближайшего:

# I renamed x-cor to x, and y-cor to y since these were not valid python names
def nearest_player(grid, x, y):
    best_distance = float('inf')
    best_player = None

    for pos, player in grid.items():
        # I actually use squared distance since this is 
        # equivalent to the "real" distance
        distance = (pos - x) ** 2 + (pos - y) ** 2

        if distance < best_distance:
            best_distance = distance
            best_player = player

    return best_player

Вариант 2

Более элегантный способ будет следующим:

def nearest_player(grid, x, y):
    distances = [(pos - x) ** 2 + (pos - y) ** 2 for pos in grid]
    return grid.values()[distances.index(min(distances))]

Что я здесь делаю?

Сначала вы вычисляете все расстояния:

distances = [(pos - x) ** 2 + (pos - y) ** 2 for pos in grid]

Это дает массив со всеми расстояниями.Затем я вычисляю индекс его минимума:

distances.index(min(distances))

, который для списка значений вашего grid дает игроку:

grid.values()[distances.index(min(distances))]

и вуаля:)

Примечание: Еще один шаг вперед

Просто для того, чтобы использовать мозг (я не знаю, правильный ли это английский).Давайте представим, что ваши настоящие ключи - это не координаты, а что-то другое (str, и вам нужно вычислить расстояние Левенштейна ).Вы можете сделать следующее:

def nearest(data, item, d):
    distances = [d(item, i) for i in data]
    return data.values()[distances.index(min(distances))]

, и вам действительно нужно предоставить функцию d (для расстояния), которая вычисляет расстояние между двумя элементами.И это все.

В вашем текущем случае d будет:

def euclidean_distance(x, y):
    return sum((x[i] - y[i]) ** 2 for i in range(0, len(x)))

, если вы предоставите x и y как tuple или list.