AOC Day 11 2023

index.ts

import { sumBy } from "remeda";
import { Matrix, MatrixCell, MatrixPosition } from "./data-structures/matrix";

const exampleText = await Bun.file("example.txt").text();

const buildMatrix = (input: string) =>
  new Matrix(input.split("\n").map((n) => n.split("")));

const tagValues = (input: Matrix<string>) => {
  let count = 0;
  return input.createMappedMatrix((el, i, j) => {
    return el === "#" ? (count += 1) : ".";
  });
};

const expandMatrix = (input: Matrix<string>) => {
  const rowLength = input.rowCount();
  const originalRows = input.rows;
  let rowShift = 0;

  for (let i = 0; i < rowLength; i++) {
    const row = originalRows[i];
    if (row.every((n) => n === ".")) {
      input.addRow("-".repeat(input.colCount()).split(""), i + rowShift);
      rowShift++;
    }
  }

  const colLength = input.colCount();
  let colShift = 0;
  const adjustedColumns = structuredClone(input.columns);

  for (let j = 0; j < colLength; j++) {
    const col = adjustedColumns[j];
    if (col.every((n) => n === "." || n === "-")) {
      input.addColumn("-".repeat(input.rowCount()).split(""), j + colShift);
      colShift++;
    }
  }
  return input;
};

const getAllPairs = (input: Matrix<string>) => {
  const numbers = tagValues(input)
    .withPositions()
    .rows.flat()
    .filter((n) => typeof n.value === "number");

  const pairs = [];

  for (let i = 1; i <= numbers.length; i++) {
    for (let j = i + 1; j <= numbers.length; j++) {
      pairs.push([
        numbers.find((num) => num.value === i)!,
        numbers.find((num) => num.value === j)!,
      ]);
    }
  }
  return pairs;
};

const calculateAnswer = (input: Matrix<string>, rowWidthForExpansion = 1) => {
  const expandedMatrix = expandMatrix(input);
  const pairs = getAllPairs(expandedMatrix);
  return sumBy(pairs, (pair) => {
    const [
      {
        position: [leftI, leftJ],
      },
      {
        position: [rightI, rightJ],
      },
    ] = pair;

    const [minJ, maxJ] = [rightJ, leftJ].toSorted((a, b) => a - b);
    const [minI, maxI] = [rightI, leftI].toSorted((a, b) => a - b);

    let count = 0;
    let currentPosition = [minI, minJ] as MatrixPosition;

    while (JSON.stringify(currentPosition) !== JSON.stringify([maxI, maxJ])) {
      let nextCell: MatrixCell<string | number>;
      const timesLarger = rowWidthForExpansion;
      const currentCell = expandedMatrix.cell(currentPosition);

      if (maxI > currentPosition[0]) {
        nextCell = expandedMatrix
          .cell(currentPosition)
          .getAllNeighbors().bottomMiddle;
        count += currentCell.value() === "-" ? timesLarger : 1;
      } else if (maxJ > currentPosition[1]) {
        nextCell = expandedMatrix.cell(currentPosition).getAllNeighbors().right;
        count += currentCell.value() === "-" ? timesLarger : 1;
      } else {
        throw new Error("unhandled case");
      }

      currentPosition = nextCell.position;
    }

    return count;
  });
};

console.log(calculateAnswer(buildMatrix(exampleText)));
console.log(calculateAnswer(buildMatrix(exampleText), 999999));

matrix.ts

import { range } from "remeda";

type Position = [number, number];
export type MatrixPosition = [number, number];

export class MatrixCell<T> {
  position: Position;
  parent: Matrix<T>;

  constructor(position: Position, parent: Matrix<T>) {
    this.position = position;
    this.parent = parent;
  }

  value() {
    return this.parent.valueAt(this.position);
  }

  getAllNeighbors() {
    const [x, y] = this.position;
    return {
      topLeft: this.parent.cell([x - 1, y - 1]),
      topMiddle: this.parent.cell([x - 1, y]),
      topRight: this.parent.cell([x - 1, y + 1]),
      left: this.parent.cell([x, y - 1]),
      right: this.parent.cell([x, y + 1]),
      bottomLeft: this.parent.cell([x + 1, y - 1]),
      bottomMiddle: this.parent.cell([x + 1, y]),
      bottomRight: this.parent.cell([x + 1, y + 1]),
    };
  }
}

export class Matrix<T> {
  rows: T[][] = [];
  columns: T[][] = [];

  constructor(rows: T[][]) {
    this.redrawFromRows(rows);
  }

  valueAt(position: Position) {
    return this.rows[position[0]][position[1]];
  }

  redrawFromRows(rows: T[][]) {
    this.rows = [];
    const rowLength = rows.length;
    for (let i = 0; i < rowLength; i++) {
      const row = rows[i];
      this.rows.push(row);
      for (let j = 0; j < row.length; j++) {
        if (!this.columns[j]) this.columns.push([]);
        this.columns[j][i] = row[j];
      }
    }
  }

  addRow(row: T[], afterRow: number) {
    if (afterRow === -1) {
      this.rows.unshift(row);
      this.redrawFromRows(this.rows);
      return;
    } else {
      const newRows = [
        ...this.rows.slice(0, afterRow + 1),
        row,
        ...this.rows.slice(afterRow + 1),
      ];

      this.redrawFromRows(newRows);

      return;
    }
  }

  addColumn(column: T[], afterColumn: number) {
    const rowLength = this.rows.length;
    for (let rowIndex = 0; rowIndex < rowLength; rowIndex++) {
      if (afterColumn === -1) {
        this.rows[rowIndex] = [column[rowIndex], ...this.rows[rowIndex]];
        continue;
      } else {
        this.rows[rowIndex] = [
          ...this.rows[rowIndex].slice(0, afterColumn + 1),
          column[rowIndex],
          ...this.rows[rowIndex].slice(afterColumn + 1),
        ];
      }
    }

    this.redrawFromRows(this.rows);
  }

  cell(position: Position) {
    return new MatrixCell(position, this);
  }

  toString(input = 2 as number | ((input: typeof this) => unknown)) {
    if (typeof input === "number") {
      let str = "";
      str +=
        "   " +
        range(0, this.columns.length)
          .map((n) => n.toString().padStart(input, "0"))
          .join(" ");

      for (let i = 0; i < this.rows.length; i++) {
        str += `\n${i.toString().padStart(2)}  ${this.rows[i].join(
          " ".repeat(input)
        )}`;
      }
      return str;
    }
    if (typeof input !== "number") {
      return input(this);
    }
  }
  colCount() {
    return this.columns.length;
  }

  rowCount() {
    return this.rows.length;
  }

  createMappedMatrix<R>(cb: (input: T, i: number, j: number) => R) {
    return new Matrix(
      this.rows.map((row, i) => row.map((el, j) => cb(el, i, j)))
    );
  }

  clone() {
    return new Matrix(structuredClone(this.rows));
  }

  maxBy(cb?: (input: T) => unknown) {
    let max: T | undefined;

    const cbActual = cb ? cb : (el: T) => el;

    for (let row of this.rows) {
      for (let cell of row) {
        if (!max) max = cell;
        if ((cbActual(cell) as any) > (cbActual(max) as any)) max = cell;
      }
    }
    return max;
  }

  minBy(cb?: (input: T) => unknown) {
    let min: T | undefined;

    const cbActual = cb ? cb : (el: T) => el;

    for (let row of this.rows) {
      for (let cell of row) {
        if (!min) min = cell;
        if ((cbActual(cell) as any) < (cbActual(min) as any)) min = cell;
      }
    }
    return min;
  }

  withPositions() {
    return this.createMappedMatrix((input, i, j) => ({
      position: [i, j],
      value: input,
    }));
  }
}