zerosleeps

import heapq
from string import ascii_lowercase
from utils import get_raw_input


class Heightmap:
    def __init__(self, raw_input):
        self.input_to_heightmap(raw_input)

    def input_to_heightmap(self, raw_input):
        self.heightmap = []
        for y, line in enumerate(raw_input):
            row = []
            for x, char in enumerate(line):
                if char == "S":
                    self.start = (x, y)
                    row.append(0)
                elif char == "E":
                    self.goal = (x, y)
                    row.append(25)
                else:
                    row.append(ascii_lowercase.index(char))
            self.heightmap.append(row)

    @property
    def node_keys(self):
        return [
            (x, y)
            for y in range(len(self.heightmap))
            for x in range(len(self.heightmap[y]))
        ]

    def node_value(self, node_key):
        if node_key in self.node_keys:
            return self.heightmap[node_key[1]][node_key[0]]
        return None

    def get_neighboring_nodes(self, node):
        candidates = [
            (node[0], node[1] - 1),
            (node[0] + 1, node[1]),
            (node[0], node[1] + 1),
            (node[0] - 1, node[1]),
        ]
        return [
            candidate
            for candidate in candidates
            if candidate in self.node_keys
            and self.node_value(candidate) - self.node_value(node) <= 1
        ]

    def manhattan_distance(self, current, neighbor):
        return abs(current[0] - neighbor[0]) + abs(current[1] - neighbor[1])

    def reconstruct_path(self, came_from, current):
        final_path = [current]
        while current in came_from.keys():
            current = came_from[current]
            final_path.insert(0, current)
        return final_path

    def a_star(self):
        open_set = [(0, self.start)]
        came_from = {}
        g_score = {self.start: 0}
        while open_set:
            current = heapq.heappop(open_set)[1]
            if current == self.goal:
                return self.reconstruct_path(came_from, current)
            for neighbor in self.get_neighboring_nodes(current):
                tentative_g_score = g_score[current] + 1
                if neighbor not in g_score or tentative_g_score < g_score[neighbor]:
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g_score
                    heapq.heappush(
                        open_set,
                        (
                            tentative_g_score
                            + self.manhattan_distance(current, neighbor),
                            neighbor,
                        ),
                    )


if __name__ == "__main__":
    heightmap = Heightmap(get_raw_input("day_12_input.txt"))
    print(f"{len(heightmap.a_star())=}")