challenge.py

"""
constaninp@mixbook.com

Best Meeting Point
Given
A rectangular board of size N × M
3 or more travelers are placed in different cells of the board
The travelers can move vertically and horizontally only to adjacent cells
Moving one traveler to an adjacent cell costs one effort point
Problem
Write a program that outputs the coordinates of the cell which requires the minimum number of moves of all travelers
There can be several optimal solutions
Example
Input
1 - 0 - 0 - 0 - 1
|     |    |    |    |
0 - 0 - 0 - 0 - 0
|     |    |    |    |
0 - 0 - 1 - 0 - 0

1 0 X 0 1
0 0 0 0 0
0 0 1 0 0
Output
0, 2

* less travelers we move the better
"""
import sys

def get_travelers(board):
    travelers = []

    for row in range(len(board)):
        for col in range(len(board[row])):
            if board[row][col] == 1:
                travelers.append((row, col,))
    
    return travelers

def distance(point1, point2):
    point1x, point1y = point1
    point2x, point2y = point2

    cost_in_x = abs(point1x - point2x)
    cost_in_y = abs(point1y - point2y)

    return cost_in_x + cost_in_y

def get_costs_for_meeting_point(meeting_point, travelers):
    total_cost = 0

    for traveler in travelers:
        total_cost = total_cost + distance(meeting_point, traveler)
    return total_cost

def solve_with_brute_force(board, travelers):
    min_cost = sys.maxsize
    location = (None, None,)

    for row in range(len(board)):
        for col in range(len(board[row])):
            meeting_point = row, col
            cost_of_meeting_point = get_costs_for_meeting_point(meeting_point, travelers)
            if cost_of_meeting_point < min_cost:
                min_cost = cost_of_meeting_point
                location = meeting_point
    
    return location, min_cost
    
def solve(board):
    # get an initial meeting point for 3 or more travelers in a board
    travelers = get_travelers(board)

    return solve_with_brute_force(board, travelers)

def main():
    board = [
        [1,0,0,0,1],
        [0,0,0,0,0],
        [0,0,1,0,0]
    ]

    location, cost = solve(board)
    print(f"Location: {location}, Cost: {cost}")
    return location
    
if __name__ == '__main__':
    main()