Python logic to find minimum total distance between 2 groups of points on a cartesian system

Imagine a cartesian playing field. it has 3 flags in 3 different locations. Also has 3 players in 3 different locations. The objective is to get a player to the location of the flag. I am trying to assign which player should go to which flag by minimizing the total distance travelled by all 3 players. I am looking for a good python logic to implement this and identify which player should go to which flag.

# This is the dictionary of distances between each player and each flag.
# (A,B,C) are the flag IDs
# (x,y,z) are the player IDs
# so, the distance between Flag A and Player x is 12 units and so on

dist_dict = {
    "A": [{"x": 12}, {"y": 10}, {"z": 20}],
    "B": [{"x": 14}, {"y": 18}, {"z": 25}],
    "C": [{"x": 8}, {"y": 15}, {"z": 16}],
}

In this case the output expected is

[{'A':'y'},{'B':'x'},{'C':'z'}]

So, constraints to be considered are:

1. One player can only be assigned to one flag
2. The flag only needs to be reached once by any player
3. Select the scenario where the total distance traveled by all three players is minimum. hence, above player 'x' is assigned to flag 'B' even though 'x' is closer to flag 'C'

The data does not need to be stored in the way I have shown here. Please recommend a different way to storing that distance data if that makes it easier to get the desired output

The inner data structure (inside the dist_dict) could be a dictionary as well, so that you can access all the distance values by their keys.

Since you have only three players, it's feasible to iterate over all possible assignments of players to flags and see which one results in the lowest total distance. There is an itertools function to obtain this iterable: permutations.

from itertools import permutations

dist_dict = {'A': {'x': 12, 'y': 10, 'z': 20},
             'B': {'x': 14, 'y': 18, 'z': 25},
             'C': {'x': 8, 'y': 15, 'z': 16}}

flags = list(dist_dict)
players = list(dist_dict['A'])

min_total_dist = 1000

for player_order in permutations(players):
    total_dist = sum(dist_dict[flag][player] 
                     for flag, player in zip(flags, player_order))
    if total_dist < min_total_dist:
        min_total_dist = total_dist
        best_player_order = player_order

print("optimal solution:")
for player, flag in zip(best_player_order, flags):
    print(f"    player {player} to flag {flag}")

print(f"optimal total distance: {min_total_dist}")

optimal solution:
    player y to flag A
    player x to flag B
    player z to flag C
optimal total distance: 40

There are different ways to solve this. Here is a not-too-short answer with explanation:

from collections import defaultdict
from itertools import product

dist_dict = {
    "A": [{"x": 12}, {"y": 10}, {"z": 20}],
    "B": [{"x": 14}, {"y": 18}, {"z": 25}],
    "C": [{"x": 8}, {"y": 15}, {"z": 16}],
}


def get_indexes(t: tuple):
    """return a list containing the indexes of items of the `t` inside `player_moves"""
    return [lst.index(i) for lst, i in zip(player_moves.values(), t)]


# Creating a dictionary which maps player names to all available moves.
player_moves = defaultdict(list)
for lst in dist_dict.values():
    for d in lst:
        # Here a copy is needed because later we want to use this dictionary
        player, distance = d.copy().popitem()
        player_moves[player].append(distance)
print(player_moves)


# While iterating, we need to keep track of three things:
# 1. `minimun`: minimum sum of distances
# 2. `moves`: the instances that each player should go
# 3. `moves_indexes`: the indexes of numer 2.
minimun = float("inf")
moves = None
moves_indexes = None
# `product` generates all available moves for us.
for i in product(*player_moves.values()):
    indexes = get_indexes(i)

    # This check is needed because there shouldn't be a player with no move!
    if len(indexes) == len(set(indexes)):
        sum_of_distances = sum(i)
        if sum_of_distances < minimun:
            minimun = sum_of_distances
            moves = i
            moves_indexes = indexes

print(moves)
print(moves_indexes)
print({k: v[i].popitem()[0] for (k, v), i in zip(dist_dict.items(), moves_indexes)})

output:

defaultdict(<class 'list'>, {'x': [12, 14, 8], 'y': [10, 18, 15], 'z': [20, 25, 16]})
(14, 10, 16)
[1, 0, 2]
{'A': 'y', 'B': 'x', 'C': 'z'}

Use itertools.permutations, and minimize using a function that calculates the total distance. (You can take permutations either of the players, or of the flags. In this case I permute the flags.)

import itertools

dist = { # I have altered the format of this input slightly
        "A": {"x": 12, "y": 10, "z": 20},
        "B": {"x": 14, "y": 18, "z": 25},
        "C": {"x": 8, "y": 15, "z": 16},
    }

def total_distance(perm):
    return sum(d[flag] for d, flag in zip(dist.values(), perm))

best_perm = min(itertools.permutations("xyz"), key=total_distance)
result = dict(zip(dist, best_perm))

Another option usespandas and numpy, which is more complicated but might work faster if you have a large number of flags and players.

import pandas as pd
import numpy as np
import itertools
dist = pd.DataFrame({ 
    "A": {"x": 12, "y": 10, "z": 20},
    "B": {"x": 14, "y": 18, "z": 25},
    "C": {"x": 8, "y": 15, "z": 16},
})
# make a numeric index [0,1,2]
index = list(range(len(dist)))             

# get all permutations of [0,1,2]
perms = list(itertools.permutations(index))   

# find the index of the permutation of [0,1,2] that minimizes total distance
best_perm_index = dist.to_numpy()[perms, index].sum(axis=1).argmin()  

# get the permutation itself, as a list
best_perm = list(perms[best_perm_index])     

# convert back to a dictionary
result = dict(zip(dist.columns, dist.iloc[best_perm].index))