Challenge2024>ProblemDay 9>Input

enum BlockType {
  File = '#',
  Free = '.',
}

type Block = {
  type: BlockType,
  space: number,
};

interface FileBlock extends Block {
  id: number,
};

type InputData = {
  blocks: Array<Block>,
};

type BlockUnit = {
  id?: number,
};

const solution: Fn = async ({ blocks }) => {
  const promise = new Promise<number>((resolve) => {
    setTimeout(() => {
      const allocation = getDiskAllocation(blocks);
      const compacted = compactDisk(allocation);
      const checksum = calculateChecksum(compacted);
      resolve(checksum);
    });
  });

  return promise;
};

const getDiskAllocation: GetAllocationFn = (blocks) => {
  const allocation: Array<BlockUnit> = [];

  for (const block of blocks) {
    const unit: BlockUnit = {};
    if (block.type === BlockType.File) {
      const file = block as FileBlock;
      unit.id = file.id;
    }

    allocation.push(...Array(block.space).fill(unit));
  }

  return allocation;
};

const compactDisk: CompactFn = (blocks) => {
  const allocation: Array<BlockUnit> = trimSpace([...blocks]);
  if (allocation.length === 0) { return allocation; }

  let freeIndex = getFreeSpace(allocation);
  while(freeIndex !== -1) {
    const file = allocation.pop();
    allocation.splice(freeIndex, 1, file!);
    trimSpace(allocation);
    freeIndex = getFreeSpace(allocation, freeIndex + 1);
  }

  return allocation;
}

const getFreeSpace: GetSpaceFn = (blocks, startIndex) => {
  let offSet = 0;
  if (startIndex && startIndex >= 0) { offSet = startIndex; }

  for (let i = offSet; i < blocks.length; i++) {
    if (blocks[i].id === undefined) { return i; }
  }

  return -1;
};

const trimSpace: TrimFn = (blocks) => {
  const trimmed = blocks;
  if (trimmed.length === 0) { return trimmed; }

  while (trimmed.slice(-1).pop()?.id === undefined) {
    trimmed.pop();
  }

  return trimmed;
};

const calculateChecksum: CalculateFn = (blocks) => {
  let checksum = 0;
  for (let i = 0; i < blocks.length; i++) {
    const block = blocks[i].id;
    if (!block) { continue; }
    checksum += (i * block);
  }
  return checksum;
};

const solution: Fn = async ({ blocks }) => {
  const promise = new Promise<number>((resolve) => {
    setTimeout(() => {
      const compacted = compactDisk(blocks);

      // check part 1 for getDiskAllocation definition
      const allocation = getDiskAllocation(compacted);

      // check part 1 for calculateChecksum definition
      const checksum = calculateChecksum(allocation);

      resolve(checksum);
    });
  });

  return promise;
};

const compactDisk: CompactFn = (blocks) => {
  const allocation: Array<Block> = trimSpace([...blocks]);
  if (allocation.length === 0) { return allocation; }

  let last: FileBlock | null = null;
  for (let i = blocks.length - 1; i >= 0; i--) {
    if (blocks[i].type === BlockType.File) {
      last = blocks[i] as FileBlock;
      break;
    }
  }
  if (last === null) { return allocation; }

  let fileId = last.id;
  while(fileId > 0) {
    const fileIndex = getFileBlockIndex(allocation, fileId);
    if (fileIndex === -1) { return allocation; }

    const file = allocation[fileIndex] as FileBlock;
    const freeIndex = getFreeSpace(allocation, file.space, fileIndex);
    if (freeIndex >= 0) {
      const free = allocation[freeIndex] as Block;

      const oldSpace: Block = { type: BlockType.Free, space: file.space };
      allocation.splice(fileIndex, 1, oldSpace);

      const newSpace: Array<Block> = [file];
      if (free.space > file.space) {
        free.space -= file.space;
        newSpace.push(free);
      }

      allocation.splice(freeIndex, 1, ...newSpace);
    }

    fileId--;
  }

  trimSpace(allocation);

  return allocation;
}

const getFileBlockIndex: GetFileFn = (blocks, id) => {
  for (let i = 0; i < blocks.length; i++) {
    if (blocks[i].type === BlockType.Free) { continue; }
    if ((blocks[i] as FileBlock).id === id) { return i; }
  }

  return -1;
};

const getFreeSpace: GetSpaceFn = (blocks, space, endIndex) => {
  let limit = blocks.length;
  if (endIndex && endIndex < blocks.length) { limit = endIndex; }

  for (let i = 0; i < limit; i++) {
    const block = blocks[i];
    if (block.type === BlockType.Free && block.space >= space) { return i; }
  }

  return -1;
};

const trimSpace: TrimFn = (blocks) => {
  const trimmed = blocks;
  if (trimmed.length === 0) { return trimmed; }

  while (trimmed.slice(-1).pop()?.type === BlockType.Free) {
    trimmed.pop();
  }

  return trimmed;
};