Created
December 18, 2023 16:43
-
-
Save klahnen/3ad094cfd91e55e909aa38934d65c8ce to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
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() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment