The pathfinder solution code for my article Demystifying Recursion - Part 2

pathfinder.go

type Point struct {
	x int
	y int
}

type Path = []Point

func findPath(maze []string, wall string, start Point, end Point) Path {
	adjacents := [][]int{[]int{0, 1}, []int{1, 0}, []int{0, -1}, []int{-1, 0}}
	seen := [][]bool{}
	path := []Point{}

	for j := 0; j < len(maze); j++ {
		col := []bool{}
		for i := 0; i < len(maze[0]); i++ {
			col = append(col, false)
		}
		seen = append(seen, col)
	}

	_, completePath := walk(maze, wall, start, end, seen, path, adjacents)

	return completePath
}

func walk(maze []string, wall string, current Point, end Point, seen [][]bool, path Path, adjacents [][]int) (bool, Path) {
	if string(maze[current.y][current.x]) == wall {
		return false, nil
	}

	if current.y < 0 || current.y >= len(maze) || current.x < 0 || current.x >= len(maze[0]) {
		return false, nil
	}

	if seen[current.y][current.x] {
		return false, nil
	}

	if current.y == end.y && current.x == end.x {
		path = append(path, current)
		return true, path
	}

	path = append(path, current)
	seen[current.y][current.x] = true

	for _, adjacent := range adjacents {
		if isEnd, completePath := walk(maze, wall, Point{x: adjacent[0] + current.x, y: adjacent[1] + current.y}, end, seen, path, adjacents); isEnd {
			return isEnd, completePath
		}
	}

	path = path[0 : len(path)-1]

	return false, nil
}

pathfinder.py

from typing import TypeAlias, TypedDict

Point = TypedDict("Point", {"x": int, "y": int})
Path: TypeAlias = list[Point]
Seen: TypeAlias = list[list[bool]]
Adjacents: TypeAlias = list[tuple[int, int]]


def find_path(maze: list[str], wall: str, start: Point, end: Point) -> Path:
    adjacents = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    seen = [[False for _ in row] for row in maze]
    path: Path = []

    walk(maze, wall, start, end, seen, path, adjacents)

    return path


def walk(
    maze: list[str],
    wall: str,
    current: Point,
    end: Point,
    seen: Seen,
    path: Path,
    adjacents: Adjacents,
) -> bool:
    if maze[current["y"]][current["x"]] == wall:
        return False

    if (
        current["y"] < 0
        or current["y"] >= len(maze)
        or current["x"] < 0
        or current["x"] >= len(maze[0])
    ):
        return False

    if seen[current["y"]][current["x"]]:
        return False

    if current["y"] == end["y"] and current["x"] == end["x"]:
        path.append(current)
        return True

    path.append(current)
    seen[current["y"]][current["x"]] = True

    for x, y in adjacents:
        if walk(
            maze,
            wall,
            {"x": current["x"] + x, "y": current["y"] + y},
            end,
            seen,
            path,
            adjacents,
        ):
            return True

    path.pop()

    return False

pathfinder.ts

type Point = {
    x: number;
    y: number;
}

function findPath(
    maze: string[], 
    wall: string, 
    start: Point, 
    end: Point
): Point[] {
    const adjacents = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    const seen: boolean[][] = 
        Array.from(
            { length: maze.length }, 
            (_, i) => new Array(maze[i].length).fill(false)
        );
    const path: Point[] = [];

    walk(maze, wall, start, end, seen, path, adjacents);

    return path;
}

function walk(
    maze: string[],
    wall: string,
    current: Point,
    end: Point,
    seen: boolean[][],
    path: Point[],
    adjacents: number[][]
): boolean {
    if (maze[current.y][current.x] === wall) {
        return false;
    }

    if (current.y < 0 || current.y >= maze.length || current.x < 0 || current.x >= maze[0].length) {
        return false
    }

    if (seen[current.y][current.x]) {
        return false
    }

    if (current.y === end.y && current.x == end.x) {
        path.push(current);
        return true;
    }
			
    path.push(current);
    seen[current.y][current.x] = true;
			
    for (let i = 0; i < adjacents.length; i++) {
        const [x, y] = adjacents[i];
        if (walk(maze, wall, { x: current.x + x, y: current.y + y }, end, seen, path, adjacents)) {
			return true;
		}
    }
										 
	path.pop();

    return false;
}