Advent of Code 2022

Artifact 98762ae881ddd15e9c47050d9f9c0f5b29f04be2e68ac4673d41844667a056f1:

• File day7/scripts.ts — part of check-in [102ff92546] at 2022-12-07 07:17:46 on branch trunk — Add initial solution for day 7 (user: marv size: 2849)

import { Coll, Collection } from "util/collection";

// If blank strings/ints is not enough
export const inputMapper = (inputs: string) => inputs;

interface Dir {
  name: string;
  content: Collection<Dir | File>;
}

interface File {
  name: string;
  size: number;
}

function buildFileTree(inputs: Collection<string>): Dir {
  const dirs: Dir = { name: "/", content: Coll() };
  const cmds = inputs.slice(1);

  let currentDir = dirs;
  const parentDirs: Collection<Dir> = Coll();

  for (let i = 0; i < cmds.length; i++) {
    if (cmds[i].startsWith("$ cd")) {
      const dirName = cmds[i].split(" ")[2];

      if (dirName === "..") {
        currentDir = parentDirs.pop()!;
      } else {
        const dir = currentDir.content.find((d) => d.name === dirName) as Dir;
        parentDirs.push(currentDir);
        currentDir = dir;
      }
    }

    if (cmds[i].startsWith("$ ls")) {
      const content = Coll<Dir | File>();

      // Lets hope there are no empty dirs..
      for (let j = 1; i + j < cmds.length; j++) {
        const [a, b] = cmds[i + j].split(" ");

        if (a.match(/^[0-9]/)) {
          content.push({ name: b, size: parseInt(a) });
        } else if (a === "dir") {
          content.push({ name: b, content: Coll() });
        } else {
          i += j - 1;
          break;
        }
      }

      currentDir.content.push(...content);
    }
  }

  return dirs;
}

function isFile(dir: Dir | File): dir is File {
  return (dir as File).size !== undefined;
}

function getDirSize(dir: Dir): number {
  return dir.content.reduce((acc, c) => {
    if (isFile(c)) {
      return acc + c.size;
    } else {
      return acc + getDirSize(c as Dir);
    }
  }, 0);
}

const maxDirSize = 100_000 as const;

function getDirsBelowLimit(dir: Dir): Collection<Dir> {
  const dirs = Coll<Dir>();

  if (getDirSize(dir) < maxDirSize) {
    dirs.push(dir);
  }

  for (const d of dir.content) {
    if (isFile(d)) {
      continue;
    }

    dirs.push(...getDirsBelowLimit(d));
  }

  return dirs;
}

export function solution1(inputs: Collection<string>): number {
  const dirs = buildFileTree(inputs);

  return getDirsBelowLimit(dirs).map(getDirSize).x.sum();
}

const availableSpace = 70_000_000 as const;
const requiredSpace = 30_000_000 as const;

function getAllDirs(dir: Dir): Collection<Dir> {
  const dirs = Coll<Dir>();

  dirs.push(dir);

  for (const d of dir.content) {
    if (isFile(d)) {
      continue;
    }

    dirs.push(...getAllDirs(d));
  }

  return dirs;
}

export function solution2(inputs: Collection<string>): number {
  const dirs = buildFileTree(inputs);
  const leftoverSpace = availableSpace - getDirSize(dirs);
  const minimumSpace = requiredSpace - leftoverSpace;

  const allDirs = getAllDirs(dirs).map(getDirSize).filter((s) =>
    s >= minimumSpace
  ).x.sortAsc();

  return allDirs[0];
}