Day 9: Disk Fragmenter

The problem divided itself neatly into three discrete steps: Convert map to block structure; Perform compacting (different algorithm for each part); Calculate and return the checksum. I don't think the conversion and checksum steps were particularly interesting so I'll focus on the compacting.

The algorithm for Part 1 was easy enough: Walk from the left looking for empty blocks. When one is found, walk from the right looking for non-empty blocks. Then swap the two. I opted to alter the array in place rather than passing around clones of it; I don't generally like that sort of impure function because it's less readable, but in this case keeping track of everything in TS/JS would've been a lot of unnecessary mental overhead for me.

I started approaching Part 2 the same way but eventually realized I'd need to reverse the order of the loops (walk backward to find file blocks first, then walk forwards to find empty spaces that will fit them). I realized that way too late and it took some heavy debugging to figure out the problem, then I had to perform surgery on my nested looks to restructure them without mangling any of my logic.

I typically try to use descriptive variable names, but when I'm just iterating through an array I use i as my index. Similar nested loops will get j and rarely k as seen in today's code. Once it reaches that point it's kind of a brainfuck to keep track of which is which but I don't have a better convention to use.

type InputData = number[];
type Blocks = string[];

function formatInput(input: string): InputData {
  return input
    .trim()
    .split('')
    .map(char => Number(char));
}

const getBlocksFromMap = (diskMap: InputData): Blocks => {
  const blocks: Blocks = [];
  let currentId = 0;
  for (let i = 0; i < diskMap.length; i++) {
    if (i % 2) {
      // even numbered index (free space length)
      const newBlocks = new Array(diskMap[i]).fill('.') as Blocks;
      blocks.push(...newBlocks);
    } else {
      // odd numbered index (file length)
      const newBlocks = new Array(diskMap[i]).fill(`${currentId}`) as Blocks;
      blocks.push(...newBlocks);
      currentId++;
    }
  }
  return blocks;
};

// void function; modify the blocks array in-place
const compactBlocks = (blocks: Blocks): void => {
  // step forward from the left to find an empty block
  for (let i = 0; i < blocks.length; i++) {
    if (blocks[i] === '.') {
      // step backward from the end to find a file block
      for (let j = blocks.length - 1; j > i; j--) {
        if (blocks[j] !== '.') {
          blocks[i] = blocks[j];
          blocks[j] = '.';
          break;
        }
      }
    }
  }
};

// void function; modify the blocks array in-place
const compactFiles = (blocks: Blocks): void => {
  // step backward from the end to find the last file block
  let currentId = '';
  for (let i = blocks.length - 1; i >= 0; i--) {
    if (blocks[i] !== '.' && blocks[i] !== currentId) {
      currentId = blocks[i];
      let fileBlockCount = 0;
      // step backward from the last file block to count contiguous blocks for this file
      for (let j = i; blocks[j] === currentId; j--) {
        fileBlockCount++;
      }
      // step forward from the left to find the first empty block
      for (let j = 0; j < i; j++) {
        let emptyBlockCount = 0;
        // step forward from the first empty block to count contiguous empty blocks
        for (let k = j; blocks[k] === '.'; k++) {
          emptyBlockCount++;
        }
        if (emptyBlockCount > 0) {
          if (fileBlockCount <= emptyBlockCount) {
            blocks.fill(currentId, j, j + fileBlockCount);
            blocks.fill('.', i - fileBlockCount + 1, i + 1);
            break;
          }
        }
      }
    }
  }
};

const checksum = (blocks: Blocks): number => {
  let sum = 0;
  for (let i = 0; i < blocks.length; i++) {
    if (blocks[i] !== '.') {
      sum += Number(blocks[i]) * i;
    }
  }
  return sum;
};

export function run(input: string): string[] {
  const data = formatInput(input);

  const checksumCompactedBlocks = (diskMap: InputData): number => {
    const blocks = getBlocksFromMap(diskMap);
    compactBlocks(blocks);
    return checksum(blocks);
  };

  const checksumCompactedFiles = (diskMap: InputData): number => {
    const blocks = getBlocksFromMap(diskMap);
    compactFiles(blocks);
    return checksum(blocks);
  };

  return [`${checksumCompactedBlocks(data)}`, `${checksumCompactedFiles(data)}`];
}

/* Advent of Code 2024
 * Day 09: Disk Fragmenter
 */

#import "Basic";
#import "File";

main :: () {
    input, success := read_entire_file("inputs/day_09.txt");
    assert(success);

    disk_part_1: [..] int;
    defer array_free(disk_part_1);

    creating_file := true;
    file_index := 0;
    max_file_index := 0;

    file_disk_positions: [..] int;
    file_sizes: [..] int;
    defer array_free(file_disk_positions);
    defer array_free(file_sizes);

    for input {
        // For some reason, leaving this out (and thus treating the trailing
        // newline as a size of 218, due to how the size is calculated) doesn't
        // seem to affect the results? To be safe, I'm going to keep it in, just
        // in case it's only a quirk with my input specifically.
        if it == #char "\n" {
            continue;
        }

        // We need the size twice if we're creating a file, so it's better to
        // define it up here.
        size := it - #char "0";

        block: int;
        if creating_file {
            block = file_index;

            if file_index > max_file_index {
                max_file_index = file_index;
            }

            file_index += 1;

            array_add(*file_disk_positions, disk_part_1.count);
            array_add(*file_sizes, size);
        } else {
            block = -1;
        }

        for 1..size {
            array_add(*disk_part_1, block);
        }

        creating_file = !creating_file;
    }

    // Needed to detect gaps in part 1.
    file_size_total := 0;
    for file_sizes {
        file_size_total += it;
    }

    // We need to do this before the disk is modified for part 1. This doesn't
    // need to be a resizeable array because unlike in part 1, we won't be
    // popping blocks off it like it's a stack.
    disk_part_2 := array_copy(disk_part_1);
    defer array_free(disk_part_2);

    while part_1_loop := true {
        block := pop(*disk_part_1);
        if block == -1 {
            continue;
        }

        for disk_part_1 {
            if it == -1 {
                disk_part_1[it_index] = block;
                break;
            }
        }

        // If there are no remaining gaps between files, we're finished.
        for disk_part_1 {
            if it == -1 {
                break;
            }

            if it_index == file_size_total - 1 {
                break part_1_loop;
            }
        }
    }

    // Because it's guaranteed in part 1 that there will be no gaps between
    // files, we can stop looping here as soon as we reach an empty block.
    checksum_part_1 := 0;
    for disk_part_1 {
        if it == -1 {
            break;
        }

        checksum_part_1 += it * it_index;
    }

    print("Part 1: %\n", checksum_part_1);

    // You have to mark for loops with #v2 right now for the new reversing
    // behavior to work. This will eventually no longer be required, so if I
    // remember I'll remove the #v2 here when that happens.
    for #v2 < file_index: 0..max_file_index {
        position := file_disk_positions[file_index];
        size := file_sizes[file_index];

        moved_file := false;
        for new_position: 0..position - 1 {
            end := new_position + size - 1;

            for new_position..end {
                if disk_part_2[it] != -1 {
                    continue new_position;
                }
            }

            for new_position..end {
                disk_part_2[it] = file_index;
            }

            moved_file = true;

            // There's a kind of unusual loop structure here, where if we reach
            // the end of the loop we always break. Maybe this could be
            // refactored for better clarity, though it reads okay to me right
            // now.
            break;
        }

        if moved_file {
            for position..position + size - 1 {
                disk_part_2[it] = -1;
            }
        }
    }

    // Unlike in part 1, there may be gaps between files, so we're forced to
    // iterate through the whole disk.
    checksum_part_2 := 0;
    for disk_part_2 {
        if it != -1 {
            checksum_part_2 += it * it_index;
        }
    }

    print("Part 2: %\n", checksum_part_2);
}

At first I didn't want to materialize the disk in memory, because I was fairly sure that part 2 would be something like "now don't use single digits but runs of six digits to denote the ranges". That took up a long time unnecessarily. Part 1 was easy after deciding to materialize the disk, but part 2 took a very long time until all edge cases were handled... I think this was the worst puzzle so far for me, from a time-taken to enjoyment ratio.

pub fn make_disk(input: &PuzzleInput) -> Vec<u64> {
    let mut disk: Vec<u64> = vec![];

    for (i, &d) in input.disk.iter().enumerate() {
        if i % 2 == 0 {
            for _ in 0..d {
                disk.push(i as u64 / 2);
            }
        } else {
            for _ in 0..d {
                disk.push(u64::MAX);
            }
        }
    }

    disk
}

pub fn part1(input: &PuzzleInput) -> String {
    let disk = make_disk(input);

    let mut fwd = 0;
    let mut bwd = disk.len() - 1;
    let mut defrag = Vec::with_capacity(disk.len());

    while fwd <= bwd {
        if disk[fwd] == u64::MAX {
            defrag.push(disk[bwd]);
            fwd += 1;

            loop {
                bwd -= 1;

                if disk[bwd] != u64::MAX {
                    break;
                }
            }
        } else {
            defrag.push(disk[fwd]);
            fwd += 1;
        }
    }

    checksum(&defrag).to_string()
}

fn checksum(defrag: &[u64]) -> u64 {
    defrag.iter().enumerate().map(|(i, &d)| d * i as u64).sum()
}

The algorithm basically works by scanning forward from the start for blanks, and then backwards from the end for something to fill them with. Then I just move the file into position. If the file is smaller than the blank space, I add the remaining blanks back to the front of the scan -- this works because the original array is contiguous and alternates between files and blanks -- or maybe it doesn't and the input is just benign, I'm too tired to fully analyze it now.

pub fn part2(input: &PuzzleInput) -> String {
    let disk = make_disk(input);
    let mut contiguous = vec![];
    let mut current_run = vec![];

    for i in 0..(disk.len() - 1) {
        current_run.push(disk[i]);
        if disk[i] != disk[i + 1] {
            contiguous.push(current_run);
            current_run = vec![];
        }
    }

    current_run.push(disk[disk.len() - 1]);

    if !current_run.is_empty() {
        contiguous.push(current_run);
    }

    let mut result = vec![];

    loop {
        if contiguous.is_empty() {
            break;
        }

        let xs = contiguous.remove(0);

        if xs.is_empty() {
            continue;
        }

        if xs[0] != u64::MAX {
            result.push(xs);
            continue;
        }

        let mut found = false;

        for idx in (0..contiguous.len()).rev() {
            let ks = &contiguous[idx];

            if ks.is_empty() {
                continue;
            }

            if ks[0] == u64::MAX {
                continue;
            }

            if ks.len() == xs.len() {
                result.push(ks.clone());
                contiguous[idx] = vec![u64::MAX; ks.len()];
                found = true;
                break;
            }

            if ks.len() < xs.len() {
                let diff = xs.len() - ks.len();
                result.push(ks.clone());
                contiguous[idx] = vec![u64::MAX; ks.len()];
                contiguous.insert(0, vec![u64::MAX; diff]);
                found = true;
                break;
            }
        }

        if !found {
            result.push(xs);
        }
    }

    result
        .iter()
        .flatten()
        .enumerate()
        .fold(0, |acc, (i, x)| {
            if *x != u64::MAX {
                acc + i * *x as usize
            } else {
                acc
            }
        })
        .to_string()
}

day_09    fastest       │ slowest       │ median        │ mean          │ samples │ iters
├─ part1  569.5 µs      │ 771.4 µs      │ 625.5 µs      │ 619.7 µs      │ 100     │ 100
╰─ part2  138.9 ms      │ 156.9 ms      │ 146.9 ms      │ 147.4 ms      │ 100     │ 100

Since all the gap sizes are 1-9, I suspect you could speed things up by storing separate lists of each size, sorted by position in memory. Then just take the head of each list from the needed size and above and pick the one with the minimum position. I haven't implemented this, but I think it should work and reduce the time substantially.

(If you think it's incomprehensible now, you should have how it looked before I defined the hp macro)

defmodule AdventOfCode.Solution.Year2024.Day09 do
  use AdventOfCode.Solution.SharedParse

  @impl true
  def parse(input) do
    input
    |> String.trim()
    |> :binary.bin_to_list()
    # Parse all digits in the string
    |> Enum.map(&(&1 - ?0))
    # Expand each digit to a file or free segment of the corresponding length
    |> Enum.flat_map_reduce({:file, 0}, fn
      n, {:file, i} -> {List.duplicate(i, n), {:free, i + 1}}
      n, {:free, i} -> {List.duplicate(:_, n), {:file, i}}
    end)
    |> then(fn {disk, _acc} -> disk end)
  end

  def part1(disk) do
    disk
    |> shift_files_left_p1()
    |> checksum()
  end

  def part2(disk) do
    disk
    |> shift_files_left_p2()
    |> checksum()
  end

  defp shift_files_left_p1(disk) do
    file_blocks =
      disk
      |> Enum.reject(&(&1 == :_))
      |> Enum.reverse()

    {new_disk, _} =
      disk
      # Since all file blocks are being compacted left,
      # we know the number of blocks needed ahead of time.
      |> Enum.take(length(file_blocks))
      |> Enum.map_reduce(file_blocks, fn
        # See a free block: emit a file block off the end
        :_, [file_block | file_blocks] -> {file_block, file_blocks}
        # See a file block: emit the file block
        file_block, file_blocks -> {file_block, file_blocks}
      end)

    new_disk
  end

  defp shift_files_left_p2(disk) do
    files =
      disk
      |> Enum.reject(&(&1 == :_))
      |> Enum.reverse()
      |> Enum.chunk_by(& &1)

    disk = Enum.chunk_by(disk, & &1)

    files
    |> Enum.reduce(disk, &relocate_file/2)
    |> List.flatten()
  end

  # "Head pattern". Matches a list with pattern `pat` as head and anything as tail.
  # hp(:foo) expands to [:foo | _]
  # hp(my_var) expands to [my_var | _], binding `my_var` to the head of a nonempty list
  defmacrop hp(pat), do: quote(do: [unquote(pat) | _])

  ### Puts file at its new position (if one exists)
  ### and then replaces its old position with free blocks using `clear_file`
  defp relocate_file(file, disk)

  defp relocate_file(file, [hp(:_) = free | rest]) when length(file) <= length(free) do
    # Found a fit
    [file, Enum.drop(free, length(file)) | clear_file(hd(file), rest)]
  end

  defp relocate_file(file, [hp(:_) = free | rest]) do
    # Too small
    [free | relocate_file(file, rest)]
  end

  defp relocate_file(hp(id), hp(hp(id)) = disk) do
    # Reached the original file without finding a fit
    disk
  end

  defp relocate_file(file, [other_file | rest]) do
    # A different file
    [other_file | relocate_file(file, rest)]
  end

  ### Clears moved file after `relocate_file` puts it in new position
  defp clear_file(id, disk)

  defp clear_file(id, [hp(:_) = l_free, hp(id) = file, hp(:_) = r_free | rest]) do
    # Found the file and it has free space both before and after it
    [l_free ++ List.duplicate(:_, length(file)) ++ r_free | rest]
  end

  defp clear_file(id, [hp(:_) = l_free, hp(id) = file | rest]) do
    # Found the file and it has free space before only
    [l_free ++ List.duplicate(:_, length(file)) | rest]
  end

  defp clear_file(id, [hp(id) = file, hp(:_) = r_free | rest]) do
    # Found the file and it has free space after only
    [List.duplicate(:_, length(file)) ++ r_free | rest]
  end

  defp clear_file(id, [hp(id) = file | rest]) do
    # Found the file and it's surrounded by other files
    [List.duplicate(:_, length(file)) | rest]
  end

  defp clear_file(id, [other | rest]) do
    # A free space or a different file
    [other | clear_file(id, rest)]
  end

  defp checksum(disk) do
    disk
    |> Enum.with_index()
    |> Enum.reject(&match?({:_, _i}, &1))
    |> Enum.map(&Tuple.product/1)
    |> Enum.sum()
  end
end

Name             ips        average  deviation         median         99th %
Parse         659.55        1.52 ms     ±7.23%        1.50 ms        1.87 ms
Part 1        277.49        3.60 ms     ±6.45%        3.53 ms        4.24 ms
Part 2          1.11      897.97 ms     ±2.04%      898.05 ms      916.18 ms

Comparison: 
Parse         659.55
Part 1        277.49 - 2.38x slower +2.09 ms
Part 2          1.11 - 592.26x slower +896.45 ms

import itertools
import sys

flatten = itertools.chain.from_iterable
disk = list(flatten([i // 2] * int(char) if not i % 2 else [-1] * int(char)
                    for i, char in enumerate(sys.stdin.read().strip())))
left = 0
right = len(disk) - 1
while left < right:
    if disk[left] < 0 and disk[right] >= 0:
        disk[left] = disk[right]
        disk[right] = -1
    left += disk[left] >= 0
    right -= disk[right] < 0

print(sum(i * int(char) for i, char in enumerate(disk) if char >= 0))

from collections import Counter
import itertools
import sys

def index_disk(disk: list[int]) -> tuple[dict[int, int], dict[int, int]]:
    free_blocks = {}
    free_len = 0
    file_ids = {}
    for i in range(len(disk)):
        if disk[i] < 0:
            free_len += 1
            continue
        if free_len > 0:
            free_blocks[i - free_len] = free_len
        free_len = 0
        if disk[i] not in file_ids:
            file_ids[disk[i]] = i
    return free_blocks, file_ids

def find_free_blocks(free_blocks: dict[int, int], file_idx: int, file_len: int) -> tuple[int, int]:
    for free_idx, free_len in sorted(free_blocks.items()):
        if free_idx < file_idx and free_len >= file_len:
            return free_idx, free_len
    return -1, 0

flatten = itertools.chain.from_iterable
disk = list(flatten([i // 2] * int(char) if not i % 2 else [-1] * int(char)
                    for i, char in enumerate(sys.stdin.read().strip())))
free_blocks, file_ids = index_disk(disk)
file_lens = Counter(block for block in disk if block > 0)
for file_id, file_idx in sorted(file_ids.items(), reverse=True):
    file_len = file_lens[file_id]
    free_idx, free_len = find_free_blocks(free_blocks, file_idx, file_len)
    if free_idx < 0:
        continue
    for i in range(file_len):
        disk[free_idx + i] = file_id
        disk[file_idx + i] = -1
    del free_blocks[free_idx]
    if free_len > file_len:
        free_blocks[free_idx + file_len] = free_len - file_len

print(sum(i * int(char) for i, char in enumerate(disk) if char >= 0))

import "utils" as utils;

let input = utils::get_input(9, false);

// PART 1
let data = input.to_chars().map(|c| c.to_string().parse_int());
let head = 0;
let tail = if data.len() % 2 == 0 {
    data.len() - 2
} else {
    data.len() - 1
};

let output = [];

while head <= tail {
    let free_size = data[head];
    let file_size = data[tail];
    let file_position = tail/2;

    if head % 2 == 0 {
        output.push([head/2, data[head]]);
        head += 1;
    } else if free_size == file_size {
        output.push([file_position, file_size]);
        head += 1;
        tail -= 2;
    } else if free_size > file_size {
        output.push([file_position, file_size]);
        data[head] -= file_size;
        tail -= 2;
    } else if free_size < file_size {
        output.push([file_position, free_size]);
        data[tail] -= free_size;
        head += 1;
    }
}

let i = 0;
let total = 0;
for file in output {
    for j in range(0, file[1]) {
        total += (i + j) * file[0];
    }
    i += file[1];
}

print(`part 1: ${total}`);

// PART 2
let data = input.to_chars().map(|c, i| {
    let size = c.to_string().parse_int();
    if i % 2 == 0 {
        [i/2, size]
    } else {
        [-1, size]
    }
});

let num_files = if data.len() % 2 == 0 {
    data.len() / 2
} else {
    data.len() / 2 + 1
};

let last_file_pos = data.len()-1;
let first_free_pos = 0;
for file_id in range(num_files-1, 0, -1) {
    let file_pos = -1;
    for i in range(last_file_pos, 0, -1) {
        if data[i][0] == file_id {
            file_pos = i;
            last_file_pos = i;
            break;
        }
    }
    let file = data[file_pos];

    let free_pos = -1;
    let first_free = false;
    for i in range(first_free_pos, file_pos) {
        let entry = data[i];
        if entry[0] == -1 {
            if !first_free {
                first_free = true;
                first_free_pos = i;
            }
            if entry[1] >= file[1] {
                free_pos = i;
                break;
            }
        }
    }

    if free_pos == -1 {
        continue;
    } else if data[free_pos][1] > file[1] {
        data[free_pos][1] -= file[1];
        data[file_pos][0] = -1;
        data.insert(free_pos, file);
    } else {
        data[free_pos][0] = file[0];
        data[file_pos][0] = -1;
    }
}

let i = 0;
let total = 0;
for file in data {
    if file[0] != -1 {
        for j in range(0, file[1]) {
            total += (i + j) * file[0];
        }
    }
    i += file[1];
}

print(`part 2: ${total}`);