I came across a question on twitter/X. I had some ideas on how to solve it. But then I thought why not ask our LLMs if they can solve it. So let’s take a look at the question.
I didn’t wanna type the question but Multi-modal LLMs for the win!
Claude Sonnet 3.5
Python Solution
from collections import deque
def parse_maze(grid):
"""Convert list of strings maze representation to 2D list and find target points."""
maze = [list(line) for line in grid]
target_points = []
for i, row in enumerate(maze):
for j, cell in enumerate(row):
if cell == "*":
target_points.append((i, j))
return maze, target_points
def get_neighbors(point, shape):
"""Get valid neighboring points (up, down, left, right)."""
y, x = point
neighbors = []
for dy, dx in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
ny, nx = y + dy, x + dx
if 0 <= ny < shape[0] and 0 <= nx < shape[1]:
neighbors.append((ny, nx))
return neighbors
def shortest_path_length(maze, start, end):
"""Calculate shortest path length between two points avoiding walls."""
if start == end:
return 0
visited = set()
queue = deque([(start, 0)])
visited.add(start)
while queue:
current, dist = queue.popleft()
for neighbor in get_neighbors(current, (len(maze), len(maze[0]))):
if neighbor not in visited and maze[neighbor[0]][neighbor[1]] != "#":
if neighbor == end:
return dist + 1
visited.add(neighbor)
queue.append((neighbor, dist + 1))
return float("inf")
def total_distance(maze, point, target_points):
"""Calculate sum of shortest path distances from point to all target points."""
return sum(shortest_path_length(maze, point, target) for target in target_points)
def solve_geometric_median_maze(grid):
"""Find the point that minimizes sum of distances to all target points."""
maze, target_points = parse_maze(grid)
min_total_dist = float("inf")
best_point = None
for i in range(len(maze)):
for j in range(len(maze[0])):
if maze[i][j] != "#":
dist = total_distance(maze, (i, j), target_points)
if dist < min_total_dist:
min_total_dist = dist
best_point = (i, j)
return best_point, min_total_dist
def visualize_solution(maze, solution_point):
"""Create a string visualization of the maze with the solution point."""
maze_with_solution = [row[:] for row in maze]
if solution_point:
maze_with_solution[solution_point[0]][solution_point[1]] = "O"
return "\n".join("".join(row) for row in maze_with_solution)
grid = [
"###################",
"# # # #",
"# * # * # #",
"# # # #",
"# # # # #",
"# # # #",
"# # * #",
"# # # #",
"# # #",
"# * # #",
"###################",
]
solution_point, total_dist = solve_geometric_median_maze(grid)
print(f"Best solution point (row, col): {solution_point}")
print(f"Total distance to all targets: {total_dist}")
maze, _ = parse_maze(grid)
print("\nSolution visualization:")
print(visualize_solution(maze, solution_point))
GPT4o
from queue import Queue
def solve_min_distance(grid):
row_lengths = [len(row) for row in grid]
if len(set(row_lengths)) > 1:
print("Warning: Grid rows have inconsistent lengths!")
print(f"Row lengths: {row_lengths}")
return None, None
grid_numeric = []
targets = []
for r, row in enumerate(grid):
grid_row = []
for c, char in enumerate(row):
if char == "#":
grid_row.append(1)
elif char == "*":
grid_row.append(2)
targets.append((r, c))
else:
grid_row.append(0)
grid_numeric.append(grid_row)
print("Grid numeric representation:")
for row in grid_numeric:
print(row)
if not targets:
print("No targets (*) found in the grid.")
return None, None
def bfs_distance(grid, start):
rows, cols = len(grid), len(grid[0])
visited = [
[-1 for _ in range(cols)] for _ in range(rows)
]
q = Queue()
q.put(start)
visited[start[0]][start[1]] = 0
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while not q.empty():
x, y = q.get()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if not (0 <= nx < rows and 0 <= ny < cols):
print(f"Skipping out-of-bounds position: ({nx}, {ny})")
continue
if (
visited[nx][ny] == -1 and grid[nx][ny] != 1
):
visited[nx][ny] = visited[x][y] + 1
q.put((nx, ny))
return visited
distance_maps = [bfs_distance(grid_numeric, target) for target in targets]
INF = float("inf")
refined_distance_maps = []
for i, distance_map in enumerate(distance_maps):
refined_map = []
for row in distance_map:
refined_map.append([cell if cell != -1 else INF for cell in row])
refined_distance_maps.append(refined_map)
print(f"Distance map for target {targets[i]}:")
for row in refined_map:
print(row)
rows, cols = len(grid_numeric), len(grid_numeric[0])
combined_distances = [[0] * cols for _ in range(rows)]
print(f"Grid size: {rows} rows, {cols} columns")
for r in range(rows):
for c in range(cols):
if all(refined_map[r][c] != INF for refined_map in refined_distance_maps):
combined_distances[r][c] = sum(
refined_map[r][c] for refined_map in refined_distance_maps
)
else:
combined_distances[r][c] = INF
print("Combined distances map:")
for row in combined_distances:
print(row)
min_distance = INF
optimal_position = None
for r in range(rows):
for c in range(cols):
if (
0 <= r < rows
and 0 <= c < cols
and grid_numeric[r][c] == 0
and combined_distances[r][c] < min_distance
):
min_distance = combined_distances[r][c]
optimal_position = (r, c)
if optimal_position is None:
print("No valid position found.")
return None, INF
return optimal_position, min_distance
grid = [
"###################",
"# # # #",
"# * # * # #",
"# # # #",
"# # # # #",
"# # # #",
"# # * #",
"# # # #",
"# # #",
"# * # #",
"###################",
]
optimal_position, min_distance = solve_min_distance(grid)
print(f"Optimal Position: {optimal_position}, Minimum Distance: {min_distance}")
Gemini-1206-Experimental
from collections import deque
def solve_grid_puzzle(grid):
"""
Finds the point in a grid that minimizes the sum of distances to target points,
respecting walls.
Args:
grid: A list of strings representing the grid. '#' for walls, '*' for targets, ' ' for empty spaces.
Returns:
A tuple: (row, col) of the optimal solution point, or None if no solution is found.
"""
def get_neighbors(row, col):
"""Returns valid neighbors of a cell (no walls)."""
neighbors = []
for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
new_row, new_col = row + dr, col + dc
if (
0 <= new_row < len(grid)
and 0 <= new_col < len(grid[new_row])
and grid[new_row][new_col] != "#"
):
neighbors.append((new_row, new_col))
return neighbors
def bfs(start_row, start_col):
"""Performs Breadth-First Search to find shortest distances from a target."""
distances = {}
queue = deque([(start_row, start_col, 0)])
visited = set()
while queue:
row, col, dist = queue.popleft()
if (row, col) in visited:
continue
visited.add((row, col))
if (
grid[row][col] == " "
):
distances[(row, col)] = dist
for neighbor_row, neighbor_col in get_neighbors(row, col):
queue.append((neighbor_row, neighbor_col, dist + 1))
return distances
targets = []
empty_spaces = []
for row_index, row in enumerate(grid):
for col_index, cell in enumerate(row):
if cell == "*":
targets.append((row_index, col_index))
elif cell == " ":
empty_spaces.append((row_index, col_index))
all_distances = {}
for target_row, target_col in targets:
all_distances[(target_row, target_col)] = bfs(target_row, target_col)
best_solution = None
min_total_distance = float("inf")
for solution_row, solution_col in empty_spaces:
total_distance = 0
valid_solution = True
for target_row, target_col in targets:
if (solution_row, solution_col) not in all_distances[
(target_row, target_col)
]:
valid_solution = False
break
total_distance += all_distances[(target_row, target_col)][
(solution_row, solution_col)
]
if valid_solution and total_distance < min_total_distance:
min_total_distance = total_distance
best_solution = (solution_row, solution_col)
return best_solution
grid = [
"###################",
"# # # #",
"# * # * # #",
"# # # #",
"# # # # #",
"# # # #",
"# # * #",
"# # # #",
"# # #",
"# * # #",
"###################",
]
solution = solve_grid_puzzle(grid)
if solution:
print("Best solution point:", solution)
else:
print("No solution found.")
Claude solved it in one shot, gpt4o did it in 2 shot, and gemini also took 2 shot.
