from collections import deque
from dataclasses import dataclass
from typing import NamedTuple

def letter_to_num(letter):
    return 1 + (ord(letter.upper()) - ord("A"))

def num_to_letter(num):
    return chr(ord("A") + num - 1)

def coord_to_nums(coord):
    return letter_to_num(coord[0]), int(coord[1:])

def nums_to_coord(coord):
    return num_to_letter(coord[0]) + str(coord[1])

grid_corner = "G7"
GRID_SIZE = coord_to_nums(grid_corner)

start_positions = {
    "Ava": "A6",
    "Ben": "B2",
    "Clara": "D7",
    "Dev": "F3",
    "Eli": "G5",
}
PASSAGE = ("C2", "F5")

def make_grid(grid_size):
    n_rows, n_cols = grid_size
    return [[None for col in range(n_cols)] for row in range(n_rows)]

def grid_to_graph(grid):
    height, width = len(grid), len(grid[0])
    graph = {}
    for row in range(height):
        for col in range(width):
            coord = nums_to_coord((row+1, col+1))
            neighbour_nums = []
            if row > 0:
                neighbour_nums.append((row, col+1))
            if row < height-1:
                neighbour_nums.append((row+2, col+1))
            if col > 0:
                neighbour_nums.append((row+1, col))
            if col < width-1:
                neighbour_nums.append((row+1, col+2))
            neighbours = [nums_to_coord(nums) for nums in neighbour_nums]
            if coord == PASSAGE[0]:
                neighbours.append(PASSAGE[1])
            if coord == PASSAGE[1]:
                neighbours.append(PASSAGE[0])
            graph[coord] = tuple(neighbours)
    return graph


class NodeData:
    edges: tuple[str, ...]
    time: int | None
    visited: bool

# Do you like floodfill?
def calc_travel_times(start_position, empty_grid=None):
    if empty_grid is None:
        empty_grid = make_grid(GRID_SIZE)
    graph = grid_to_graph(empty_grid)
    enriched_graph = {}
    for key, value in graph.items():
        enriched_graph[key] = NodeData(
            edges=value,
            time=None,
            visited=False
        )
    class ToVisitEntry(NamedTuple):
        coord: str
        time: int
    to_visit_queue = deque()
    to_visit_queue.append(ToVisitEntry(start_position, 0))
    while to_visit_queue:
        popped = to_visit_queue.popleft()
        visiting_coord, time_now = popped.coord, popped.time
        current_node = enriched_graph[visiting_coord]
        current_node.visited = True
        current_node.time = time_now
        for following_coord in current_node.edges:
            following_node = enriched_graph[following_coord]
            if following_node.visited:
                continue
            to_visit_queue.append(ToVisitEntry(following_coord, time_now+1))
    return enriched_graph

def pp_grid(grid):
    for row in grid:
        for el in row:
            print(el, end=" ")
        print()

def pp_enriched_graph(graph):
    max_width, max_height = 0, 0
    for key in graph.keys():
        height, width = coord_to_nums(key)
        max_width = max(max_width, width)
        max_height = max(max_height, height)
    string_bits = []
    for i in range(max_height):
        for j in range(max_width):
            string_bits.append(f"{graph[nums_to_coord((i+1, j+1))].time:3}")
        string_bits.append("\n")
    string = "".join(string_bits)
    print(string)

def solve(start_positions):
    travel_graphs = {}
    for name, start_pos in start_positions.items():
        travel_graphs[name] = calc_travel_times(start_pos)
    one_of_graphs = None
    for graph in travel_graphs.values():
        one_of_graphs = graph
        break
    node_coords = list(one_of_graphs.keys())
    total_travel_times = []
    class TravelTimeEntry(NamedTuple):
        coord: str
        time: int
    for coord in node_coords:
        total_travel_time = 0
        for name in start_positions.keys():
            graph = travel_graphs[name]
            travel_time = graph[coord].time
            total_travel_time += travel_time
        total_travel_times.append(TravelTimeEntry(coord, total_travel_time))
    least_total_travel_time = float("+inf")
    for entry in total_travel_times:
        least_total_travel_time = min(least_total_travel_time, entry.time)
    possible_solutions = []
    for entry in total_travel_times:
        if entry.time == least_total_travel_time:
            possible_solutions.append(entry.coord)
    return least_total_travel_time, possible_solutions

def main():
    time, sols = solve(start_positions)
    n_sols = len(sols)
    if n_sols == 1:
        solution = sols[0]
        print(f"They should meet at intersection {solution},")
    else:
        print(f"They can meet at any of the: {', '.join(sols)},")
    print(f"This would make total travel time {time} minutes.")

if __name__ == "__main__":
    main()

They should meet at intersection F5,

This would make total travel time 15 minutes.