AoC 2021 Day 12

day12.ts

type Node = {
  id: string;
}

type GraphMap = Map<string, Set<Node>>;

const parseInput = (input: string): GraphMap => {
  let map = new Map<string, Set<Node>>();
  const rows = input.trim().split('\n');

  rows.forEach((row) => {
    const [n1, n2] = row.split('-');
    const node1: Node = { id: n1 };
    const node2: Node = { id: n2 };

    if (!map.has(n1)) {
      map.set(n1, new Set());
    }

    if (!map.has(n2)) {
      map.set(n2, new Set())
    }

    map.get(n1).add(node2);
    map.get(n2).add(node1);
  });

  return map;
}

type CanVisitStrategy = (id: string, visited: Record<string, number>) => boolean;

const findPaths = (map: GraphMap, startId: string, endId: string, visited: Record<string, number>, canVisit: CanVisitStrategy): string[] => {
  if (startId === endId) return [endId];
  if (!canVisit(startId, visited)) return [];

  const _v = startId.toLocaleLowerCase() === startId ? { ...visited, [startId]: (visited[startId] || 0) + 1 } : visited;

  let paths: string[] = [];
  map.get(startId).forEach((n) => {
    const pathsFromN = findPaths(map, n.id, endId, _v, canVisit);
    paths.push(...pathsFromN);
  })

  return paths;
}

export const solveP1 = (input: string) => {
  const map = parseInput(input);

  const p1Strategy: CanVisitStrategy = (id: string, visited: Record<string, number>) => {
    if (id === 'start') return !visited.start;
    if (id === 'end') return !visited.end;
    return visited[id] !== 1;
  }

  return findPaths(map, 'start', 'end', {}, p1Strategy).length;
};

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

  const p2Strategy: CanVisitStrategy = (id: string, visited: Record<string, number>) => {
    if (id === 'start') return !visited.start;
    if (id === 'end') return !visited.end;
    if (id.toLowerCase() !== id) return true;

    // Visit this small cave if you haven't
    if (!visited[id]) return true;

    const hasVisitedSmallBefore = Object.values(visited).some(v => v > 1);
    return !hasVisitedSmallBefore;
  }

  const paths = findPaths(map, 'start', 'end', {}, p2Strategy);
  return paths.length;
}