day9.ts

const parseInput = (input: string): number[][] => {
  const rows = input.trim().split('\n');
  return rows.reduce((res, rawRow) => {
    const nums = rawRow.split('').map(Number);
    return [...res, nums];
  }, []);
}

export const solveP1 = (input: string) => {
  const map = parseInput(input);
  const totalRows = map.length;
  const totalCols = map[0].length;

  let totalRisk = 0;

  for (let row = 0; row < totalRows; row++) {
    for (let col = 0; col < totalCols; col++) {
      const curr = map[row][col];
      const above = map[row - 1]?.[col];
      const right = map[row][col + 1];
      const below = map[row + 1]?.[col];
      const left = map[row][col - 1];

      const filtered = [above, right, below, left].filter(n => Number.isFinite(n));
      if (curr < Math.min(...filtered)) {
        totalRisk += 1 + curr;
      }
    }
  }

  return totalRisk;
};

export const solveP2 = (input: string) => {
  const map = parseInput(input);
  const heightMap = createHeightMap(map);

  const totalRows = heightMap.length;
  const totalCols = heightMap[0].length;

  const lowestPoints: Array<MapCell> = [];
  // Find lowest points to start from
  for (let row = 0; row < totalRows; row++) {
    for (let col = 0; col < totalCols; col++) {
      const curr = heightMap[row][col];
      const { above, right, below, left } = getNeighbourCells(curr, heightMap);

      const filteredHeights = [above, right, below, left].filter(c => !!c).map(c => c.height);
      if (curr.height < Math.min(...filteredHeights)) {
        // Enqueue
        lowestPoints.push(curr);
      }
    }
  }

  const visitQueue: Array<MapCell> = [];
  const basins: Array<MapCell[]> = [];
  // Visit lowest points to find basins
  while (lowestPoints.length) {
    const lowPoint = lowestPoints.pop();
    visitQueue.push(lowPoint);

    let currentBasin = [];
    while (visitQueue.length) {
      // Ignore visited cells
      const curr = visitQueue.pop();
      if (curr.visited) continue;

      // Otherwise, visit...
      currentBasin.push(curr);
      curr.visited = true;

      // Neighbours
      const { above, right, below, left } = getNeighbourCells(curr, heightMap);

      [above, right, below, left].forEach((direction) => {
        if (direction && !direction.visited && direction.height !== 9) {
          // Enqueue
          visitQueue.unshift(direction);
        }
      })
    }

    basins.push(currentBasin);
  }

  return basins.map((basin) => basin.length).sort((a, b) => a > b ? -1 : 1).slice(0, 3).reduce((a, b) => a * b);
}

// UTIL FUNCTIONS BELOW

type MapCell = {
  height: number;
  visited: boolean;
  row: number;
  col: number;
}

type HeightMap = MapCell[][];

const createHeightMap = (map: number[][]): HeightMap => {
  const totalRows = map.length;
  const totalCols = map[0].length;

  const res: HeightMap = [];

  for (let row = 0; row < totalRows; row++) {
    res.push([]);

    for (let col = 0; col < totalCols; col++) {
      const curr = map[row][col];
      const newCell: MapCell = {
        height: curr,
        visited: false,
        row,
        col,
      };

      res[row][col] = newCell;
    }
  }  

  return res;
}

type NeighbourCells = {
  above?: MapCell;
  right?: MapCell;
  below?: MapCell;
  left?: MapCell;
}

const getNeighbourCells = (cell: MapCell, heightMap: HeightMap): NeighbourCells => {
  const { row, col } = cell;
  const above = heightMap[row - 1]?.[col];
  const right = heightMap[row][col + 1];
  const below = heightMap[row + 1]?.[col];
  const left = heightMap[row][col - 1];

  return { above, right, below, left };
}