ChatGPT created 3d maze shortest route search

3d-maze.ts

import { Queue } from './queue';  // Queue data structure for breadth-first search

// Coordinate class to represent a point in the maze
class Coord {
  constructor(public x: number, public y: number, public z: number) {}
}

// Helper function to check if a coordinate is within the bounds of the maze
function isValidCoord(maze: number[][][], coord: Coord): boolean {
  return (
    coord.x >= 0 &&
    coord.x < maze.length &&
    coord.y >= 0 &&
    coord.y < maze[0].length &&
    coord.z >= 0 &&
    coord.z < maze[0][0].length
  );
}

// Helper function to get the neighbors of a coordinate
function getNeighbors(maze: number[][][], coord: Coord): Coord[] {
  const neighbors: Coord[] = [];
  const dirs = [
    [0, 1, 0],
    [0, -1, 0],
    [1, 0, 0],
    [-1, 0, 0],
    [0, 0, 1],
    [0, 0, -1],
  ];
  for (const dir of dirs) {
    const neighbor = new Coord(coord.x + dir[0], coord.y + dir[1], coord.z + dir[2]);
    if (isValidCoord(maze, neighbor)) {
      neighbors.push(neighbor);
    }
  }
  return neighbors;
}

// Find the shortest path through a 3D maze using breadth-first search
function shortestPath(maze: number[][][], start: Coord, end: Coord): Coord[] {
  const queue = new Queue<Coord>();
  const visited = new Set<string>();  // Set of coordinates visited during the search
  const predecessor: { [key: string]: Coord } = {};  // Map of a coordinate's predecessor in the path
  queue.enqueue(start);
  visited.add(start.toString());
  while (!queue.isEmpty()) {
    const current = queue.dequeue();
    if (current.x === end.x && current.y === end.y && current.z === end.z) {
      // End coordinate has been reached, so construct and return the path
      const path: Coord[] = [current];
      let next = current;
      while (predecessor[next.toString()]) {
        next = predecessor[next.toString()];
        path.unshift(next);
      }
      return path;
    }
    for (const neighbor of getNeighbors(maze, current)) {
      if (!visited.has(neighbor.toString())) {
        visited.add(neighbor.toString());
        predecessor[neighbor.toString()] = current;
        queue.enqueue(neighbor);
      }
    }
  }
  // No path was found
  return [];
}

__tests__.ts

describe('shortestPath', () => {
  it('should return an empty array if the start or end coordinates are outside the bounds of the maze', () => {
    const maze = [[[0]]];
    const start = new Coord(-1, 0, 0);
    const end = new Coord(0, 0, 0);
    expect(shortestPath(maze, start, end)).toEqual([]);
    expect(shortestPath(maze, end, start)).toEqual([]);
  });

  it('should return an empty array if there is no path through the maze', () => {
    const maze = [[[1]]];
    const start = new Coord(0, 0, 0);
    const end = new Coord(0, 0, 0);
    expect(shortestPath(maze, start, end)).toEqual([]);
  });

  it('should return the correct shortest path through the maze', () => {
    const maze = [      [[0, 0, 1, 0], [0, 0, 1, 0], [0, 0, 0, 0]],
      [[0, 0, 1, 0], [0, 0, 1, 0], [0, 0, 0, 0]],
      [[0, 0, 0, 0], [0, 0, 1, 0], [0, 0, 0, 0]],
    ];
    const start = new Coord(0, 0, 0);
    const end = new Coord(2, 2, 3);
    const expectedPath = [start, new Coord(1, 0, 0), new Coord(1, 1, 0), new Coord(2, 1, 0), new Coord(2, 2, 0), new Coord(2, 2, 1), new Coord(2, 2, 2), new Coord(2, 2, 3)];
    expect(shortestPath(maze, start, end)).toEqual(expectedPath);
  });

  it('should return the correct shortest path through a maze with multiple solutions', () => {
    const maze = [      [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]],
      [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]],
      [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]],
    ];
    const start = new Coord(0, 0, 0);
    const end = new Coord(2, 2, 3);
    const expectedPath = [start, new Coord(1, 0, 0), new Coord(1, 1, 0), new Coord(2, 1, 0), new Coord(2, 2, 0), new Coord(2, 2, 1), new Coord(2, 2, 2), new Coord(2, 2, 3)];
    expect(shortestPath(maze, start, end)).toEqual(expectedPath);
  });
});

queue.ts

export class Queue<T> {
  private data: T[] = [];

  enqueue(item: T): void {
    this.data.push(item);
  }

  dequeue(): T | undefined {
    return this.data.shift();
  }

  peek(): T | undefined {
    return this.data[0];
  }

  isEmpty(): boolean {
    return this.data.length === 0;
  }
}