Was really blanking on how to do this one nicely, so a bunch of stacked loops it is...
Also ended up writing two separate solutions for the first and second part, since I couldn't get acceptable performance otherwise. Still takes half a second on my machine, mainly on the second part.

This is technically the second implementation, the first one took minutes to calculate, so I wasn't really okay with stamping it as my solution-of-choice.

Can definitely still be improved, but I've been poking and prodding at this code for hours on end now, so it's long past time to let it sit for a while and see if I get any better ideas later.

int[] layout = new int[0];
public void Input(IEnumerable lines)
{
  layout = string.Join("", lines).ToCharArray().Select(c => int.Parse(c.ToString())).ToArray();
}

public void Part1()
{
  ushort?[] blocks = BuildBlockmap().ToArray();

  var it = 0;
  for (var i = blocks.Length - 1; i > it; i--)
  {
    if (blocks[i] == null)
      continue;

    while (it < blocks.Length && blocks[it] != null)
      ++it;

    if (it >= blocks.Length)
      break;

    (blocks[it], blocks[i]) = (blocks[i], null);
  }

  long checksum = 0;
  foreach (var part in blocks.OfType().Select((b, i) => i * b))
    checksum += part;

  Console.WriteLine($"Checksum: {checksum}");
}

public void Part2()
{
  var sparse = BuildSparsemap().ToList();

  for (var i = sparse.Count - 1; i >= 0; i--)
  {
    if (sparse[i].Item1 == null)
      continue;

    for (var j = 0; j < i; ++j)
    {
      if (sparse[j].Item1 != null)
        continue;

      if (sparse[i].Item2 > sparse[j].Item2)
        continue;

      var size = sparse[j].Item2;
      size -= sparse[i].Item2;

      (sparse[j], sparse[i]) = (sparse[i], (null, sparse[i].Item2));

      if (i + 1 < sparse.Count && sparse[i + 1].Item1 == null)
      {
        sparse[i] = (null, (ushort)(sparse[i].Item2 + sparse[i + 1].Item2));
        sparse.RemoveAt(i + 1);
      }

      if (sparse[i - 1].Item1 == null)
      {
        sparse[i - 1] = (null, (ushort)(sparse[i - 1].Item2 + sparse[i].Item2));
        sparse.RemoveAt(i);
      }

      if (size > 0)
        sparse.Insert(j + 1, (null, size));

      j = i + 1;
    }
  }

  int ind = 0;
  long checksum = 0;
  foreach (var (val, cnt) in sparse)
    for (var i = 0; i < cnt; ++i)
    {
      checksum += (val ?? 0) * ind;
      ++ind;
    }

  Console.WriteLine($"Checksum: {checksum}");
}

IEnumerable BuildBlockmap()
{
  ushort blockit = 0;
  bool block = true;
  foreach (var value in layout)
  {
    for (int i = 0; i < value; ++i)
      yield return block ? blockit : null;
    if (block)
      blockit++;
    block = !block;
  }
}

IEnumerable<(ushort?, ushort)> BuildSparsemap()
{
  ushort blockit = 0;
  bool block = true;
  foreach (var value in layout)
  {
    if (block)
      yield return (blockit++, (ushort)value);
    else
      yield return (null, (ushort)value);
    block = !block;
  }
}

C

First went with a doubly linked list approach, but it was quite verbose and we're dealing with short runs (max 9) anyway so back to the flat array​. Plenty fast too - on my 2015 PC:

day09  0:00.05  1648 Kb  0+179 faults

#include "common.h"

/*
 * First went with a doubly linked list approach, but it was quite verbose
 * and we're dealing with short runs (max 9) anyway.
 */
static char input[20*1000+1];
static short disk[200*1000];
int input_sz, disk_sz;

static void
defrag(int p2)
{
	int a,b, a0=0, run, gap;

	/*
	 * b runs back to front, finding files.
	 * a runs front to back (from first gap, a0), finding gaps.
	 *
	 * For part 1 we short circuit the file length check so it deals
	 * with single tiles.
	 */
	for (b=disk_sz-1; b > 0; b--) {
		/* find and measure next file from back */
		for (; b>0 && !disk[b]; b--) ;
		for (run=1; p2 && b>0 && disk[b-1]==disk[b]; b--, run++) ;

		/* find the first gap */
		for (; a0 < b && disk[a0]; a0++) ;

		/* find a gap large enough */
		for (a=a0, gap=0; a= run) break;
			}

		/* move if its */
		if (gap >= run)
			for (; run > 0; a++, run--) {
				disk[a] = disk[b+run-1];
				disk[b+run-1] = 0;
			}
	}
}

int
main(int argc, char **argv)
{

	int part, i,j;
	uint64_t ans[2]={};

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));
	
	input_sz = (int)fread(input, 1, sizeof(input), stdin);
	assert(!ferror(stdin));
	assert(feof(stdin));

	for (part=0; part<2; part++) {
		disk_sz = 0;

		for (i=0; i < input_sz && isdigit(input[i]); i++)
		for (j=0; j < input[i]-'0'; j++) {
			assert(disk_sz < (int)LEN(disk));
			disk[disk_sz++] = i%2 ? 0 : i/2+1;
		}

		defrag(part);

		for (i=0; i < disk_sz; i++)
			if (disk[i])
				ans[part] += i * (disk[i]-1);
	}

	printf("08: %"PRIu64" %"PRIu64"\n", ans[0], ans[1]);
	return 0;
}

https://github.com/sjmulder/aoc/blob/master/2024/c/day09.c

Also did 2016 day 6 because reasons and I think it turned out real nice!

#include 

int
main(int argc, char **argv)
{
	char buf[16], p1[9]="aaaaaaaa", p2[9]="aaaaaaaa";
	int counts[8][256]={}, i,j;

	if (argc > 1)
		freopen(argv[1], "r", stdin);

	while (fgets(buf, sizeof(buf), stdin))
		for (i=0; i<8 && buf[i] >= 'a' && buf[i] <= 'z'; i++)
			counts[i][(int)buf[i]]++;

	for (i=0; i<8; i++)
	for (j='a'; j<='z'; j++) {
		if (counts[i][j] > counts[i][(int)p1[i]]) p1[i] = j;
		if (counts[i][j] < counts[i][(int)p2[i]]) p2[i] = j;
	}

	printf("06: %s %s\n", p1, p2);
	

https://github.com/sjmulder/aoc/blob/master/2016/c/day06.c

Nim

Wrote ugly-ass code today, but it was surprisingly easy to debug and fast.

Solution:
Part 1: Parse data into a sequence of blocks and empty space like in example (I use -1 for empty space) and two indexes. First index goes 0 -> end, second index starts at the end. When we encounter empty space -> we use value from second index and decrement it (while skipping empty spaces). Repeat until both indexes meet at some point.

Part 2: Parse data into sequence of block objects and try to insert each data block into each empty space block before it. Somehow it all just worked without too many bugs.

Runtime (final version): 123 ms

type
  BlockKind = enum Data, Space
  Block = object
    size: int
    case kind: BlockKind
    of Data:
      index: int
    of Space:
      discard

func parseBlocks(input: string): tuple[blocks: seq[Block], id: int] =
  for i, c in input:
    let digit = c.ord - '0'.ord
    if i mod 2 == 0:
      result.blocks.add Block(kind: Data, size: digit, index: result.id)
      if i < input.high: inc result.id
    else:
      result.blocks.add Block(kind: Space, size: digit)

proc solve(input: string): AOCSolution[int, int] =
  block p1:
    var memBlocks = newSeqOfCap[int](100_000)

    var indBlock = 0
    for i, c in input:
      let digit = c.ord - '0'.ord
      if i mod 2 == 0:
        memBlocks.add (indBlock).repeat(digit)
        inc indBlock
      else:
        memBlocks.add -1.repeat(digit)

    var ind = 0
    var revInd = memBlocks.high
    while ind <= revInd:
      if memBlocks[ind] == -1:
        while memBlocks[revInd] == -1: dec revInd
        result.part1 += ind * memBlocks[revInd]
        dec revInd
      else:
        result.part1 += ind * memBlocks[ind]
      inc ind

  block p2:
    var (memBlocks, index) = parseBlocks(input)
    var revInd = memBlocks.high
    while revInd > 0:
      doAssert memBlocks[revInd].kind == Data

      var spaceInd = -1
      let blockSize = memBlocks[revInd].size
      for ind in 0..revInd:
        if memBlocks[ind].kind == Space and memBlocks[ind].size >= blockSize:
          spaceInd = ind; break

      if spaceInd != -1:
        let bSize = memBlocks[revInd].size
        let diffSize = memBlocks[spaceInd].size - bSize
        swap(memBlocks[spaceInd], memBlocks[revInd])
        if diffSize != 0:
          memBlocks[revInd].size = bSize
          memBlocks.insert(Block(kind: Space, size: diffSize), spaceInd + 1)
          inc revInd # shift index bc we added object

      dec index
      # skip space blocks and data blocks with higher index
      while (dec revInd; revInd < 0 or
             memBlocks[revInd].kind != Data or
             memBlocks[revInd].index != index): discard

    var unitIndex = 0
    for b in memBlocks:
      case b.kind
      of Data:
        for _ in 1..b.size:
          result.part2 += unitIndex * b.index
          inc unitIndex
      of Space:
        unitIndex += b.size

Codeberg repo

Rust

Pretty poor performance on part 2, was initially 10s, got down to 2.5s, but still seems pretty poor.

#[cfg(test)]
mod tests {
    fn checksum(p0: &[i64]) -> i64 {
        let mut csum = 0;
        for (i, val) in p0.iter().enumerate() {
            if *val == -1 {
                continue;
            }
            csum += *val * (i as i64);
        }
        csum
    }

    fn defrag(p0: &[i64]) -> Vec {
        let mut start = 0;
        let mut end = p0.len() - 1;

        let mut defragged = vec![];

        while start != end + 1 {
            if p0[start] != -1 {
                defragged.push(p0[start]);
                start += 1;
                continue;
            }
            if p0[start] == -1 {
                defragged.push(p0[end]);
                start += 1;
                end -= 1;
                while p0[end] == -1 {
                    end -= 1;
                }
            }
        }
        defragged
    }

    fn expand_disk(p0: &str) -> Vec {
        let mut disk = vec![];
        let mut file_index = 0;
        let mut is_file = true;
        for char in p0.chars() {
            let val = char.to_digit(10).unwrap();
            if is_file {
                for _ in 0..val {
                    disk.push(file_index)
                }
                file_index += 1;
            } else {
                for _ in 0..val {
                    disk.push(-1)
                }
            }
            is_file = !is_file;
        }
        disk
    }
    #[test]
    fn day9_part1_test() {
        let input: String = std::fs::read_to_string("src/input/day_9.txt")
            .unwrap()
            .trim()
            .into();

        let disk: Vec = expand_disk(&input);

        let defraged = defrag(&disk);

        let checksum = checksum(&defraged);

        println!("{}", checksum);
    }

    fn find_file(p0: &[i64], file: i64) -> (usize, usize) {
        let mut count = 0;
        let mut i = p0.len() - 1;
        while i > 0 && p0[i] != file {
            i -= 1;
        }
        // At end of file
        while i > 0 && p0[i] == file {
            count += 1;
            i -= 1;
        }
        (i + 1, count)
    }

    fn find_slot(p0: &[i64], size: usize, end: usize) -> Option {
        let mut i = 0;
        while i < end {
            while p0[i] != -1 && i < end {
                i += 1;
            }
            let mut count = 0;
            while p0[i] == -1 && i < end {
                i += 1;
                count += 1;
                if count == size {
                    return Some(i - count);
                }
            }
        }
        None
    }

    fn move_file(p0: &mut [i64], file: i64, size: usize, old_pos: usize, new_pos: usize) {
        for i in 0..size {
            p0[old_pos + i] = -1;
            p0[new_pos + i] = file;
        }
    }

    fn defrag2(p0: &mut [i64]) {
        let mut i = *p0.last().unwrap();
        while i > 0 {
            let (old_pos, size) = find_file(p0, i);
            match find_slot(p0, size, old_pos) {
                None => {}
                Some(new_pos) => {
                    if new_pos < old_pos {
                        move_file(p0, i, size, old_pos, new_pos);
                    }
                }
            }
            i -= 1;
        }
    }

    #[test]
    fn day9_part2_test() {
        let input: String = std::fs::read_to_string("src/input/day_9.txt")
            .unwrap()
            .trim()
            .into();

        let mut disk: Vec = expand_disk(&input);

        defrag2(&mut disk);

        let checksum = checksum(&disk);

        println!("{}", checksum);
    }
}

TypeScript

Actually kinda proud of my solution considering how hectic today has been! I actually didn't spend too much time on this solution too :) Runs in ~0.5s.

import { AdventOfCodeSolutionFunction } from "./solutions";
import { MakeEmptyGenericArray } from "./utils/utils";

const pretty_print = (disk: Array) => disk.reduce((prev, curr) => prev + (curr == -1 ? "." : curr), "");
const checksum = (disk: Array) => disk.reduce((prev, curr, index) => prev + (curr == -1 ? 0 : curr * index), 0);

const findSlice = (disk: Array, id: number, startFrom?: number) => {
    const sectionStart = disk.indexOf(id, startFrom);

    if (sectionStart == -1)
        return [-1, -1];

    let sectionEnd = sectionStart;

    while (disk.length > ++sectionEnd && disk[sectionEnd] == id);

    return [sectionStart, sectionEnd];
}

export const solution_9: AdventOfCodeSolutionFunction = (input) => {
    let isFile = false;
    let id = 0;

    // make the disk
    const disk = input.split("").flatMap((v) => {
        isFile = !isFile;
        const count = Number(v);

        if (isFile) {
            id++;
            return MakeEmptyGenericArray(count, () => id - 1);
        }

        return MakeEmptyGenericArray(count, () => -1);
    });

    // make a copy of the disk
    const fragmentedDisk = [...disk];

    // start moving elements on the disk
    let start = 0
    let end = fragmentedDisk.length - 1;
    while (start < end) {
        if (fragmentedDisk[start] != -1) {
            start++;
            continue;
        }

        if (fragmentedDisk[end] == -1) {
            end--;
            continue;
        }

        // swap the values
        fragmentedDisk[start] = fragmentedDisk[end]
        fragmentedDisk[end] = -1;

        start++;
        end--;
    }


    main: while (id-- > 0) {
        // find the section that has the file
        const [sectionStart, sectionEnd] = findSlice(disk, id); // this will never return -1
        const sectionLength = sectionEnd - sectionStart;

        // find any section that can fit the file
        let freeStart;
        let freeEnd = 0;
        do {
            [freeStart, freeEnd] = findSlice(disk, -1, freeEnd);

            // can't find any free spaces or too far right
            if (freeStart == -1 || freeStart > sectionStart)
                continue main;

        } while (freeEnd - freeStart < sectionLength);

        // switch places
        let i = 0;
        while(sectionStart + i < sectionEnd) {
            disk[freeStart + i] = id;
            disk[sectionStart + i++] = -1;
        }
    }


    // calculate the checksums
    return {
        part_1: checksum(fragmentedDisk),
        part_2: checksum(disk),
    }
}

C#

using System.Collections;
using System.Diagnostics;
using Common;

namespace Day09;

static class Program
{
    static void Main()
    {
        var start = Stopwatch.GetTimestamp();

        var sampleInput = Input.ParseInput("sample.txt");
        var programInput = Input.ParseInput("input.txt");

        Console.WriteLine($"Part 1 sample: {Part1(sampleInput)}");
        Console.WriteLine($"Part 1 input: {Part1(programInput)}");

        Console.WriteLine($"Part 2 sample: {Part2(sampleInput)}");
        Console.WriteLine($"Part 2 input: {Part2(programInput)}");

        Console.WriteLine($"That took about {Stopwatch.GetElapsedTime(start)}");
    }

    static object Part1(Input i)
    {
        var disk = i.Disk.ToList();
        
        while (true)
        {
            // Find the next free space with some blocks open.
            var nextFree = disk.FindIndex(d => (d is Free { Blocks: > 0 }));
            var nextUsed = disk.FindLastIndex(d => (d is Used { Blocks: > 0 }));

            if (nextFree > nextUsed) break;

            var free = disk[nextFree] as Free ?? throw new Exception("This is not a Free");
            var used = disk[nextUsed] as Used ?? throw new Exception("This is not a Used");
            var canMove = Math.Min(free.Blocks, used.Blocks);
            disk[nextFree] = free with { Blocks = free.Blocks - canMove };
            disk[nextUsed] = used with { Blocks = used.Blocks - canMove };

            var addingFree = disk[nextUsed - 1] as Free;
            disk[nextUsed - 1] = addingFree! with { Blocks = addingFree.Blocks + canMove };
            var addingUsed = used! with { Blocks = canMove };
            disk.Insert(nextFree, addingUsed);
        }

        // DumpString(disk);
        return CheckSum(disk);
    }

    static object Part2(Input i)
    {
        var disk = i.Disk.ToList();

        var lastUsedId = int.MaxValue;
        while (true)
        {
            // Find the next free space with some blocks open.
            var nextUsed = disk.FindLastIndex(d => (d is Used { Blocks: > 0 } u) && (u.Id < lastUsedId));
            if (nextUsed < 0) break;
            
            var nextFree = disk.FindIndex(d => (d is Free f) && (f.Blocks >= disk[nextUsed].Blocks));
            var used = disk[nextUsed] as Used ?? throw new Exception("This is not a Used");
            lastUsedId = used.Id;
            if ((nextFree < 0) || (nextFree > nextUsed)) continue; 

            var free = disk[nextFree] as Free ?? throw new Exception("This is not a Free");
            var canMove = Math.Min(free.Blocks, used.Blocks);
            disk[nextFree] = free with { Blocks = free.Blocks - canMove };
            disk[nextUsed] = used with { Blocks = used.Blocks - canMove };

            var addingFree = disk[nextUsed - 1] as Free;
            disk[nextUsed - 1] = addingFree! with { Blocks = addingFree.Blocks + canMove };
            var addingUsed = used! with { Blocks = canMove };
            disk.Insert(nextFree, addingUsed);
            
            // DumpString(disk);
        }

        return CheckSum(disk);
    }

    static long CheckSum(IEnumerable disk) => disk
        .SelectMany(d => Expand(d))
        .Select((d, i) => (d is Used u) ? (long)(i * u.Id) : 0)
        .Sum();
    
    static IEnumerable Expand(DiskSpace d)
    {
        for (int i = 0; i < d.Blocks; i++)
        {
            yield return d with { Blocks = 1 };
        }
    }

    static void DumpString(IEnumerable disk)
    {
        foreach(var s in disk.Select(d =>
            (d is Used u) ? new string((char)(u.Id + '0'), u.Blocks) :
            (d is Free { Blocks: > 0 } f) ? new string('.', f.Blocks) :
            ""))
        {
            Console.Write(s);
        }
        
        Console.WriteLine();
    }
}

public abstract record DiskSpace(int Blocks);
public record Free(int Blocks) : DiskSpace(Blocks);
public record Used(int Id, int Blocks) : DiskSpace(Blocks);

public class Input
{
    public DiskSpace[] Disk { get; private init; } = [];
    
    public static Input ParseInput(string file) => new Input()
    {
        Disk = File.ReadAllText(file)
            .TakeWhile(char.IsDigit)
            .Select(c => (int)(c - '0'))
            .Select((c, i) => ((i % 2) == 0) ? (DiskSpace)new Used(i / 2, c) : new Free(c))
            .ToArray(),
    };
}

Nushell

As I'm still on holiday and normal languages are a PITA to type on a phone, I though I'd try a compiled scripting language. I'm not very familiar with it so it took longer to code and also it's been running the first reduce step for 35 minutes so I've missed the 24h cutoff 😔

use std repeat
use std/iter

let memory = open input.txt | str trim 
  | split chars | chunks 2
  | enumerate | each {|pair| [
    ...($pair.index | repeat ($pair.item.0 | into int))
    ...("." | repeat (if ($pair.item|length) < 2 {0} else {$pair.item.1 | into int}))
  ]}
  | flatten

let defragged = (($memory | length) - 1)..(($memory | filter {$in != .} | length))
 | reduce --fold $memory {|i, acc| 
    let space = $acc | iter find-index {|$i| $i == .}
    $acc | update $space ($acc | get $i)
      | update $i .
  }

$defragged | enumerate
  | reduce --fold 0 {|i,acc| $acc + ($i.index * if $i.item == "." {0} else {$i.item | into int})}

C#

public class Day09 : Solver
{
  private string data;

  public void Presolve(string input) {
    data = input.Trim();
  }

  public string SolveFirst() {
    var arr = new List();
    bool file = true;
    int file_id = 0;
    foreach (var ch in data) {
      if (file) {
        Enumerable.Range(0, ch - '0').ToList().ForEach(_ => arr.Add(file_id));
        file_id++;
      } else {
        Enumerable.Range(0, ch - '0').ToList().ForEach(_ => arr.Add(-1));
      }
      file = !file;
    }
    int from_ptr = arr.Count - 1;
    int to_ptr = 0;
    while (from_ptr > to_ptr) {
      if (arr[to_ptr] != -1) {
        to_ptr++;
        continue;
      }
      if (arr[from_ptr] == -1) {
        from_ptr--;
        continue;
      }
      arr[to_ptr] = arr[from_ptr];
      arr[from_ptr] = -1;
      to_ptr++;
      from_ptr--;
    }
    return Enumerable.Range(0, arr.Count)
      .Select(block_id => arr[block_id] > 0 ? ((long)arr[block_id]) * block_id : 0)
      .Sum().ToString();
  }

  public string SolveSecond() {
    var files = new List<(int Start, int Size, int Id)>();
    bool is_file = true;
    int file_id = 0;
    int block_id = 0;
    foreach (var ch in data) {
      if (is_file) {
        files.Add((block_id, ch - '0', file_id));
        file_id++;
      }
      is_file = !is_file;
      block_id += (ch - '0');
    }
    while (true) {
      bool moved = false;
      for (int from_ptr = files.Count - 1; from_ptr >= 1; from_ptr--) {
        var file = files[from_ptr];
        if (file.Id >= file_id) continue;
        file_id = file.Id;
        for (int to_ptr = 0; to_ptr < from_ptr; to_ptr++) {
          if (files[to_ptr + 1].Start - files[to_ptr].Start - files[to_ptr].Size >= file.Size) {
            files.RemoveAt(from_ptr);
            files.Insert(to_ptr + 1, file with { Start = files[to_ptr].Start + files[to_ptr].Size });
            moved = true;
            break;
          }
        }
        if (moved) break;
      }
      if (!moved) break;
    }
    return files.Select(file => ((long)file.Id) * file.Size * (2 * ((long)file.Start) + file.Size - 1) / 2)
      .Sum().ToString();
  }
}

Rust

A bunch of fiddling with indices and sizes. In part 1 the disk is simulated in a Vec, for part 2 files and spaces are represented by their offset and size, collected in separate lists. Then these values are changed as necessary, with a whole bunch of mut. In particular, files are never moved within the list of files, only their offset changes.

fn part1(input: String) {
    let mut id: u64 = 0;
    let mut disk = Vec::new();
    let mut file = true;
    for b in input.trim().bytes() {
        let num: usize = (b - b'0') as usize;
        if file {
            disk.extend(vec![Some(id); num]);
            id += 1;
        } else {
            disk.extend(vec![None; num]);
        }
        file = !file;
    }

    let mut first_free = 0;
    while disk[first_free].is_some() {
        first_free += 1
    }

    let mut last_file = disk.len() - 1;
    while disk[last_file].is_none() {
        last_file -= 1
    }

    while first_free < last_file {
        disk[first_free] = disk[last_file];
        disk[last_file] = None;
        while disk[first_free].is_some() {
            first_free += 1
        }
        while disk[last_file].is_none() {
            last_file -= 1
        }
    }

    let checksum = disk
        .iter()
        .filter_map(|e| *e)
        .enumerate()
        .map(|(i, id)| i as u64 * id)
        .sum::();
    println!("{checksum}");
}

fn part2(input: String) {
    // Tuples of (idx, size)
    let mut free_spaces = Vec::new();
    // Tuples of (idx, size, id)
    let mut files = Vec::new();

    let mut id: u64 = 0;
    let mut disk_len = 0;
    let mut file = true;
    for b in input.trim().bytes() {
        let num = (b - b'0') as u64;
        if file {
            files.push((disk_len, num, id));
            id += 1;
        } else {
            free_spaces.push((disk_len, num));
        }
        disk_len += num;
        file = !file;
    }

    for (idx, size, _id) in files.iter_mut().rev() {
        match free_spaces
            .iter_mut()
            // Only search spaces left of file
            .take_while(|(sp_idx, _space)| sp_idx < idx)
            .find(|(_sp_idx, space)| space >= size)
        {
            None => {} // No space found
            Some((sp_idx, space)) => {
                // Move file into space
                *idx = *sp_idx;
                // Reduce free space
                *sp_idx += *size;
                *space -= *size;
            }
        }
    }

    let sum_range = |n| if n == 0 { 0 } else { (n * (n - 1)) / 2 };
    let checksum = files
        .iter()
        .map(|(idx, size, id)| (sum_range(idx + size) - sum_range(*idx)) * id)
        .sum::();
    println!("{checksum}");
}

util::aoc_main!();

Also on github

Python part 1

This is working for the demo, but not for the actual data. I'm a bit lost on why.

def part1(data: data) -> None:
    disk_map, free = gen_disk_map(data.getlines()[0])
    for f in free[:-2]:
        disk_map[f] = disk_map.pop(max(disk_map.keys()))
    print(sum([k * v for k, v in disk_map.items()]))


def gen_disk_map(raw: str):
    file_id = 0
    pos = 0
    disk_map, free = {}, []

    for read_index, val in enumerate(map(int, raw)):
        if read_index % 2 == 0:
            for _ in range(val):
                disk_map[pos] = file_id
                pos += 1
            file_id += 1
        else:
            free.extend(range(pos, pos + val))
            pos += val

    return disk_map, free

Kotlin

No lists were harmed in the making of this code.

import kotlin.text.flatMapIndexed

fun main() {
    fun part1(input: List): Long {
        val disk = parseInputDay09(input)
        return disk.compactFragmented().checksum()
    }

    fun part2(input: List): Long {
        val disk = parseInputDay09(input)
        return disk.blockify().compactContiguous().checksum()
    }

    val testInput = readInput("Day09_test")
    check(part1(testInput) == 1928L)
    check(part2(testInput) == 2858L)

    val input = readInput("Day09")
    part1(input).println()
    part2(input).println()
}

fun parseInputDay09(input: List): DiscretizedDisk {
    var id = 0
    return input[0].flatMapIndexed { index, char ->
        val size = "$char".toInt()
        if (index % 2 == 0) List(size) { DiskBlockElement(id) }
        else (List(size) { DiskBlockElement(-1) }).also { id++ }
    }
}

data class DiskBlockElement(val id: Int)  // -1 id is empty
data class DiskBlock(val id: Int, val indexRange: IntRange)

typealias Disk = List
typealias DiscretizedDisk = List
fun DiscretizedDisk.compactFragmented(): DiscretizedDisk {
    val freeSpace = count { it.id < 0 }
    val onlyFiles = reversed().filter { it.id >= 0 }
    var indexIntoOnlyFiles = 0
    val discretizedCompacted = map { if (it.id < 0) onlyFiles[indexIntoOnlyFiles++] else it }.dropLast(freeSpace) + List(freeSpace) { DiskBlockElement(-1) }
    return discretizedCompacted
}

fun Disk.compactContiguous(): DiscretizedDisk {
    var (onlyFiles, spaaaaace) = (this.partition { it.id >= 0 })
    onlyFiles = onlyFiles.reversed()

    val emptySpacesCreatedIndexes = mutableListOf>()
    var spaceRemaining = spaaaaace.first().indexRange.size()
    val emptyBlockReplacements = spaaaaace.map { emptyBlock ->
        buildList {
            spaceRemaining = emptyBlock.indexRange.size()
            while (spaceRemaining > 0) {
                val fittingBlockIndex = onlyFiles.indexOfFirst { it.indexRange.size() <= spaceRemaining }
                if (fittingBlockIndex == -1) {
                    add(DiskBlock(-1, (emptyBlock.indexRange.last() - spaceRemaining + 1)..emptyBlock.indexRange.last()))
                    break
                }
                val fittingBlock = onlyFiles[fittingBlockIndex]
                if (fittingBlock.indexRange.first <= emptyBlock.indexRange.last) {
                    add(DiskBlock(-1, (emptyBlock.indexRange.last() - spaceRemaining + 1)..emptyBlock.indexRange.last()))
                    break
                }

                val newDiscretizedIndex = with(emptyBlock.indexRange.last() - spaceRemaining + 1) { this until (this + fittingBlock.indexRange.size()) }
                add(fittingBlock.copy(indexRange = newDiscretizedIndex))
                spaceRemaining -= fittingBlock.indexRange.size()
                onlyFiles = onlyFiles.withoutElementAt(fittingBlockIndex)
                emptySpacesCreatedIndexes.add(fittingBlock.indexRange.toList())
            }
        }
    }

    val replaceWithEmpty = emptySpacesCreatedIndexes.flatten()
    var replacementIndex = 0
    return flatMap {
        if (it.id >= 0) listOf(it) else emptyBlockReplacements[replacementIndex++]
    }.discretize().mapIndexed { index, blockElement -> if (index in replaceWithEmpty) DiskBlockElement(-1) else blockElement }
}

fun DiscretizedDisk.blockify(): Disk = buildList {
    var blockID = this@blockify.first().id
    var blockStartIndex = 0
    this@blockify.forEachIndexed { index, blockElement ->
        if (blockElement.id != blockID) {
            add(DiskBlock(blockID, blockStartIndex until index))
            blockStartIndex = index
            blockID = blockElement.id
        } else if (index == this@blockify.lastIndex) add(DiskBlock(blockElement.id, blockStartIndex.. this@blockify.lastIndex))
    }
}

fun Disk.discretize(): DiscretizedDisk = flatMap { block -> List(block.indexRange.size()) { DiskBlockElement(block.id) } }

fun DiscretizedDisk.checksum(): Long = foldIndexed(0) { index, acc, blockElement ->
    if (blockElement.id >= 0) acc + index * blockElement.id else acc
}

J

Mostly-imperative code in J never looks that nice, but at least the matrix management comes out fairly clean. Part 2 is slow because I didn't cache the lengths of free intervals or the location of the leftmost free interval of a given length, instead just recalculating them every time. One new-ish construct today is dyadic ]\. The adverb \ applies its argument verb to sublists of its right argument list, the length of those sublists being specified by the absolute value of the left argument. If it's positive, the sublists overlap; if negative, they tile. The wrinkle is that monadic ] is actually the identity function -- we actually want the sublists, not to do anything with them, so we apply the adverb \ to ]. For example, _2 ]\ v reshapes v into a matrix of row length 2, without knowing the target length ahead of time like we would need to for $.

data_file_name =: '9.data'
input =: "."0 , > cutopen fread data_file_name
compute_intervals =: monad define
   block_endpoints =. 0 , +/\ y
   block_intervals =. 2 ]\ block_endpoints
   result =. (<"2) 0 2 |: _2 ]\ block_intervals
   if. 2 | #y do. result =. result 1}~ (}: &.>) 1 { result end.
   result
)
'file_intervals free_intervals' =: compute_intervals input
interval =: {. + (i. @: -~/)
build_disk_map =: monad define
   disk_map =. (+/ input) $ 0
   for_file_int. y do.
      disk_map =. file_int_index (interval file_int)} disk_map
   end.
   disk_map
)
compact =: dyad define
   p =. <: # y  NB. pointer to block we're currently moving
   for_free_int. x do.
      for_q. interval free_int do.
         NB. If p has descended past all compacted space, done
         if. p <: q do. goto_done. end.
         NB. Move content of block p to block q; mark block p free
         y =. (0 , p { y) (p , q)} y
         NB. Decrement p until we reach another file block
         p =. <: p
         while. 0 = p { y do. p =. <: p end.
      end.
   end.
   label_done.
   y
)
disk_map =: build_disk_map file_intervals
compacted_map =: free_intervals compact disk_map
checksum =: +/ @: (* (i. @: #))
result1 =: checksum compacted_map

move_file =: dyad define
   'file_intervals free_intervals' =. x
   file_length =. -~/ y { file_intervals
   target_free_index =. 1 i.~ ((>: & file_length) @: -~/)"1 free_intervals
   if. (target_free_index < # free_intervals) do.
      'a b' =. target_free_index { free_intervals
      if. a < {. y { file_intervals do.
         c =. a + file_length
         file_intervals =. (a , c) y} file_intervals
         free_intervals =. (c , b) target_free_index} free_intervals
      end.
   end.
   file_intervals ; free_intervals
)
move_compact =: monad define
   for_i. |. i. # > 0 { y do. y =. y move_file i end.
   y
)
move_compacted_map =: build_disk_map > 0 { move_compact compute_intervals input
result2 =: checksum move_compacted_map

Haskell

Not a lot of time to come up with a pretty solution today; sorry.

import Data.List
import Data.Maybe
import Data.Sequence (Seq)
import Data.Sequence qualified as Seq

readInput :: String -> Seq (Maybe Int, Int)
readInput =
  Seq.fromList
    . zip (intersperse Nothing $ map Just [0 ..])
    . (map (read . singleton) . head . lines)

expand :: Seq (Maybe Int, Int) -> [Maybe Int]
expand = concatMap (uncurry $ flip replicate)

compact :: Seq (Maybe Int, Int) -> Seq (Maybe Int, Int)
compact chunks =
  case Seq.spanr (isNothing . fst) chunks of
    (suffix, Seq.Empty) -> suffix
    (suffix, chunks' Seq.:|> file@(_, fileSize)) ->
      case Seq.breakl (\(id, size) -> isNothing id && size >= fileSize) chunks' of
        (_, Seq.Empty) -> compact chunks' Seq.>< file Seq.<| suffix
        (prefix, (Nothing, gapSize) Seq.:<| chunks'') ->
          compact $ prefix Seq.>< file Seq.<| (Nothing, gapSize - fileSize) Seq.<| chunks'' Seq.>< (Nothing, fileSize) Seq.<| suffix

part1, part2 :: Seq (Maybe Int, Int) -> Int
part1 input =
  let blocks = dropWhileEnd isNothing $ expand input
      files = catMaybes blocks
      space = length blocks - length files
      compacted = take (length files) $ fill blocks (reverse files)
   in sum $ zipWith (*) [0 ..] compacted
  where
    fill (Nothing : xs) (y : ys) = y : fill xs ys
    fill (Just x : xs) ys = x : fill xs ys
part2 = sum . zipWith (\i id -> maybe 0 (* i) id) [0 ..] . expand . compact

main = do
  input <- readInput <$> readFile "input09"
  print $ part1 input
  print $ part2 input