advent of code day 5

aoc_day05.ts

const input = await Deno.readTextFile("input.txt");

type Rule = {
  x: number;
  y: number;
};

const [order, pages] = input.split("\n\n");

function parseRules(rules: string): Rule[] {
  return rules.split("\n").map((rule) => {
    const [x, y] = rule.split("|").map(Number);
    return { x, y };
  });
}

function parseUpdates(updates: string): number[][] {
  const res = [];
  for (const update of updates.split("\n")) {
    const parts = update.split(",").map(Number);
    res.push(parts);
  }
  return res;
}

function isOrdered(update: number[], rules: Rule[]): boolean {
  const pageIndex: Map<number, number> = new Map();

  update.forEach((page, i) => {
    pageIndex.set(page, i);
  });

  for (const rule of rules) {
    const xIndex = pageIndex.get(rule.x);
    const yIndex = pageIndex.get(rule.y);

    if (xIndex !== undefined && yIndex !== undefined && xIndex > yIndex) {
      return false;
    }
  }

  return true;
}

function findMiddle(part: number[]): number {
  const m = Math.floor(part.length - 1) / 2;
  return part[m];
}

function fixOrder(update: number[], rules: Rule[]): number[] {
  const [graph, indegree] = buildGraph(update, rules);
  const queue: number[] = [];
  const sorted: number[] = [];

  indegree.forEach((degree, page) => {
    if (degree === 0) {
      queue.push(page);
    }
  });

  while (queue.length > 0) {
    const cur = queue.shift()!;
    sorted.push(cur);

    graph.get(cur)?.forEach((neighbor) => {
      indegree.set(neighbor, indegree.get(neighbor)! - 1);
      if (indegree.get(neighbor) === 0) {
        queue.push(neighbor);
      }
    });
  }

  return sorted;
}

function buildGraph(
  update: number[],
  rules: Rule[],
): [Map<number, number[]>, Map<number, number>] {
  const graph: Map<number, number[]> = new Map();
  const indegree: Map<number, number> = new Map();

  update.forEach((page) => {
    graph.set(page, []);
    indegree.set(page, 0);
  });

  rules.forEach(({ x, y }) => {
    if (contains(update, x) && contains(update, y)) {
      graph.get(x)?.push(y);
      indegree.set(y, (indegree.get(y) || 0) + 1);
    }
  });

  return [graph, indegree];
}

function contains(slice: number[], value: number): boolean {
  return slice.includes(value);
}

function processUpdates(rules: Rule[], updates: number[][]): [number, number] {
  let part1 = 0;
  let part2 = 0;
  const incorrect: number[][] = [];

  for (const update of updates) {
    if (isOrdered(update, rules)) {
      part1 += findMiddle(update);
    } else {
      incorrect.push(update);
    }
  }

  for (const update of incorrect) {
    part2 += findMiddle(fixOrder(update, rules));
  }

  return [part1, part2];
}

const rules = parseRules(order);
const updates = parseUpdates(pages);

const [part1, part2] = processUpdates(rules, updates);

console.log({ part1, part2 });