type Point = [number, number];

type Node = {
  point: Point;
  height: number;
  neighbors: Node[];
  distance: number;
  visited: boolean;
};

type Graph = Record<string, Node>;

const initializeNodes = (input: string) => {
  const rows = input.split("\n");
  const graph: Record<string, Node> = {};
  let start: Point = [0, 0];
  let end: Point = [0, 0];
  rows.forEach((row, x) => {
    for (let y = 0; y < row.length; y++) {
      graph[`${x}, ${y}`] = {
        point: [x, y],
        height: row.charCodeAt(y),
        neighbors: [],
        distance: Infinity,
        visited: false,
      };
      if (row[y] === "S") {
        start = [x, y];
        graph[`${x}, ${y}`].height = "a".charCodeAt(0);
      }
      if (row[y] === "E") {
        end = [x, y];
        graph[`${x}, ${y}`].height = "z".charCodeAt(0);
      }
    }
  });
  return { start, end, graph };
};

const setNewStart = (graph: Graph, start: Point) => {
  for (const key in graph) {
    const node = graph[key];
    node.distance = Infinity;
    node.visited = false;
    if (node.point[0] === start[0] && node.point[1] === start[1]) {
      node.distance = 0;
    }
  }
};

const populateNeighbors = (graph: Graph, downhill: boolean = false) => {
  for (const key in graph) {
    const node = graph[key];
    const [x, y] = node.point;
    node.neighbors = [
      graph[`${x - 1}, ${y}`],
      graph[`${x}, ${y - 1}`],
      graph[`${x + 1}, ${y}`],
      graph[`${x}, ${y + 1}`],
    ].filter(
      (x) =>
        !!x &&
        (downhill ? x.height >= node.height + -1 : x.height <= node.height + 1)
    );
  }
};

const getMinUnvisitedNode = (graph: Graph) => {
  let minNode: Node | null = null;
  for (const key in graph) {
    const node = graph[key];
    if (!node.visited && (!minNode || minNode.distance > node.distance)) {
      minNode = node;
    }
  }
  return minNode;
};

const populateDistances = (graph: Graph) => {
  let currentNode = getMinUnvisitedNode(graph);

  while (currentNode) {
    currentNode.visited = true;
    const currentDistance = currentNode.distance + 1;

    currentNode.neighbors.forEach((neighbor) => {
      neighbor.distance = Math.min(currentDistance, neighbor.distance);
    });
    currentNode = getMinUnvisitedNode(graph);
  }
};

// Part I
export const getDistanceToEnd = (input: string) => {
  const { start, end, graph } = initializeNodes(input);
  setNewStart(graph, start);
  populateNeighbors(graph);
  populateDistances(graph);

  return graph[end.join(", ")].distance;
};

// Part II
export const getMinPath = (input: string) => {
  const { end, graph } = initializeNodes(input);
  setNewStart(graph, end);
  populateNeighbors(graph, true);
  populateDistances(graph);
  let minPath = Infinity;
  const rows = input.split("\n");
  rows.forEach((row, x) => {
    for (let y = 0; y < row.length; y++) {
      if (row[y] === "a" || row[y] === "S") {
        minPath = Math.min(minPath, graph[`${x}, ${y}`].distance);
      }
    }
  });
  return minPath;
};