maze.py

#!/usr/bin/env python3

MAXDEPTH = 10

counter = 0


class Maze:
    def __init__(self, values):
        self.values = values

    def available_steps(self, y, x):
        val = self.values[y][x]
        result = []
        if (
            y - val > 0
            and y - val < len(self.values)
            and x > 0
            and x < len(self.values[0])
            and self.values[y - val][x] >= 0
            and self.values[y - val + 1][x] > 0
        ):
            result.append((y - val, x))
        if (
            y + val > 0
            and y + val < len(self.values)
            and x > 0
            and x < len(self.values[0])
            and self.values[y + val][x] >= 0
            and self.values[y + val - 1][x] > 0
        ):
            result.append((y + val, x))
        if (
            y > 0
            and y < len(self.values)
            and x - val > 0
            and x - val < len(self.values[0])
            and self.values[y][x - val] >= 0
            and self.values[y][x - val + 1] > 0
        ):
            result.append((y, x - val))
        if (
            y > 0
            and y < len(self.values)
            and x + val > 0
            and x + val < len(self.values[0])
            and self.values[y][x + val] >= 0
            and self.values[y][x + val - 1] > 0
        ):
            result.append((y, x + val))
        if (
            y - val > 0
            and y - val < len(self.values)
            and x - val > 0
            and x - val < len(self.values[0])
            and self.values[y - val][x - val] >= 0
            and self.values[y - val + 1][x - val + 1] > 0
        ):
            result.append((y - val, x - val))
        if (
            y - val > 0
            and y - val < len(self.values)
            and x + val > 0
            and x + val < len(self.values[0])
            and self.values[y - val][x + val] >= 0
            and self.values[y - val + 1][x + val - 1] > 0
        ):
            result.append((y - val, x + val))
        if (
            y + val > 0
            and y + val < len(self.values)
            and x - val > 0
            and x - val < len(self.values[0])
            and self.values[y + val][x - val] >= 0
            and self.values[y + val - 1][x - val + 1] > 0
        ):
            result.append((y + val, x - val))
        if (
            y + val > 0
            and y + val < len(self.values)
            and x + val > 0
            and x + val < len(self.values[0])
            and self.values[y + val][x + val] >= 0
            and self.values[y + val - 1][x + val - 1] > 0
        ):
            result.append((y + val, x + val))
        return result

    def traverse(self, path):
        global counter
        counter += 1
        if counter % 100000 == 0:
            print(counter)
        cur_y, cur_x = path[-1]
        if len(path) > MAXDEPTH:
            return None
        elif self.values[cur_y][cur_x] == 0:
            return path
        else:
            for y, x in self.available_steps(cur_y, cur_x):
                if (y, x) in path:
                    continue
                new_path = self.traverse([*path, (y, x)])
                if new_path is not None:
                    return new_path
            return None


def get_input():
    raw_input = """0 0 0 0 0 0 0 0 0 4 7 7 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 5 4 4 8 3 3 4 6 3 0 0 0 0 0 0
0 0 0 0 1 4 5 1 1 1 4 5 1 7 1 3 5 0 0 0 0
0 0 0 4 9 4 9 6 7 5 5 5 8 7 6 6 8 5 0 0 0
0 0 3 7 2 9 8 3 5 6 7 3 9 1 8 7 5 8 5 0 0
0 0 1 4 7 8 4 2 9 2 7 1 1 8 2 2 7 6 3 0 0
0 7 2 1 8 5 5 3 1 1 3 1 3 3 4 2 8 6 1 3 0
0 4 2 6 7 2 5 2 4 2 2 5 4 3 2 8 1 7 7 3 0
0 4 1 6 5 1 1 1 9 1 4 3 4 4 3 1 9 8 2 7 0
4 3 5 2 3 2 2 3 2 4 2 5 3 5 1 1 3 5 5 3 7
2 7 1 5 1 1 3 1 5 3 3 2 4 2 3 7 7 5 4 2 7
2 5 2 2 6 1 2 4 4 6 3 4 1 2 1 2 6 5 1 8 8
0 4 3 7 5 1 9 3 4 4 5 2 9 4 1 9 5 7 4 8 0
0 4 1 6 7 8 3 4 3 4 1 3 1 2 3 2 3 6 2 4 0
0 7 3 2 6 1 5 3 9 2 3 2 1 5 7 5 8 9 5 4 0
0 0 1 6 7 3 4 8 1 2 1 2 1 2 2 8 9 4 1 0 0
0 0 2 5 4 7 8 7 5 6 1 3 5 7 8 7 2 9 3 0 0
0 0 0 6 5 6 4 6 7 2 5 2 2 6 3 4 7 4 0 0 0
0 0 0 0 2 3 1 2 3 3 3 2 1 3 2 1 1 0 0 0 0
0 0 0 0 0 0 7 4 4 5 7 3 4 4 7 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 3 3 4 0 0 0 0 0 0 0 0 0"""
    processed_input = []
    for line in raw_input.split("\n"):
        processed_input.append([int(x) for x in line.split(" ")])
    return processed_input


m = Maze(get_input())
path = m.traverse([(10, 10)])
if path is not None:
    values = "".join(str(m.values[y][x]) for y, x in path)
    print(f"Path: {path}\nValues: {values}")
else:
    print("No path found")
print(f"Counter: {counter}")