LLMs are going to take away our jobs

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

    # Try all empty spaces as potential solution points
    for i in range(len(maze)):
        for j in range(len(maze[0])):
            if maze[i][j] != "#":  # If not a wall
                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)


# Example grid
grid = [
    "###################",
    "#    #     #      #",
    "#  *  #  *  #     #",
    "#    #     #      #",
    "#  #  #  #        #",
    "#  #           #  #",
    "#  #        *     #",
    "#  #  #           #",
    "#     #           #",
    "#  *  #           #",
    "###################",
]

# Solve the maze
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}")

# Visualize solution
maze, _ = parse_maze(grid)
print("\nSolution visualization:")
print(visualize_solution(maze, solution_point))

GPT4o

from queue import Queue


def solve_min_distance(grid):
    # Check if all rows are of the same length
    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

    # Convert the grid to a numerical format: 0 = empty space, 1 = wall, 2 = target
    grid_numeric = []
    targets = []

    for r, row in enumerate(grid):
        grid_row = []
        for c, char in enumerate(row):
            if char == "#":
                grid_row.append(1)  # Wall
            elif char == "*":
                grid_row.append(2)  # Target
                targets.append((r, c))  # Store target positions
            else:
                grid_row.append(0)  # Empty space
        grid_numeric.append(grid_row)

    # Debug: Print grid numeric representation
    print("Grid numeric representation:")
    for row in grid_numeric:
        print(row)

    # Validate targets
    if not targets:
        print("No targets (*) found in the grid.")
        return None, None

    # Helper function to compute shortest path distance using BFS
    def bfs_distance(grid, start):
        rows, cols = len(grid), len(grid[0])
        visited = [
            [-1 for _ in range(cols)] for _ in range(rows)
        ]  # Distance initialized to -1 (unvisited)
        q = Queue()
        q.put(start)
        visited[start[0]][start[1]] = 0

        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # Up, down, left, right

        while not q.empty():
            x, y = q.get()

            for dx, dy in directions:
                nx, ny = x + dx, y + dy

                # Debug: Check next position
                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
                ):  # Not visited and not a wall
                    visited[nx][ny] = visited[x][y] + 1
                    q.put((nx, ny))

        return visited

    # Compute distance maps for each target
    distance_maps = [bfs_distance(grid_numeric, target) for target in targets]

    # Replace all occurrences of -1 in the distance maps with a large value (infinity)
    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)

        # Debug: Output the distance map
        print(f"Distance map for target {targets[i]}:")
        for row in refined_map:
            print(row)

    # Calculate the combined distance map
    rows, cols = len(grid_numeric), len(grid_numeric[0])
    combined_distances = [[0] * cols for _ in range(rows)]

    # Debug: Check grid size
    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

    # Debug: Output combined distances map
    print("Combined distances map:")
    for row in combined_distances:
        print(row)

    # Find the optimal point minimizing the sum of distances
    min_distance = INF
    optimal_position = None
    for r in range(rows):
        for c in range(cols):
            # Check that the coordinates do not go out of bounds and that we're not at a wall
            if (
                0 <= r < rows
                and 0 <= c < cols
                and grid_numeric[r][c] == 0
                and combined_distances[r][c] < min_distance
            ):  # Empty space
                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


# Test the function with your grid
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
            # Correctly check if the new position is within bounds for the specific row
            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)])  # (row, col, distance)
        visited = set()

        while queue:
            row, col, dist = queue.popleft()
            if (row, col) in visited:
                continue
            visited.add((row, col))

            if (
                grid[row][col] == " "
            ):  # Consider only empty spaces as potential solutions
                distances[(row, col)] = dist

            for neighbor_row, neighbor_col in get_neighbors(row, col):
                queue.append((neighbor_row, neighbor_col, dist + 1))

        return distances

    # Find target points and empty spaces
    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))

    # Calculate shortest distances from each target
    all_distances = {}
    for target_row, target_col in targets:
        all_distances[(target_row, target_col)] = bfs(target_row, target_col)

    # Find the best solution point
    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  # No path from target to this solution
                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


# Example usage with the provided grid:
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.