Kotlin

No lists were harmed in the making of this code.

import kotlin.text.flatMapIndexed

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

    fun part2(input: List<String>): 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<String>): 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<DiskBlock>
typealias DiscretizedDisk = List<DiskBlockElement>
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<List<Int>>()
    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

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})}

python

import aoc

def setup():
    dm = [int(x) for x in aoc.get_lines(9, stripped=True)[0]]
    ldm = len(dm)
    d = []
    f = 0
    for i in range(0, ldm, 2):
        lfi = dm[i]
        d.extend([f] * lfi)
        f += 1
        if i + 1 < ldm:
            lfr = dm[i + 1]
            d.extend([-1] * lfr)
    return d

def one():
    d = setup()
    h = 0
    t = len(d) - 1
    while h < t:
        if d[h] == -1:
            while t > h and d[t] == -1:
                t -= 1
            if t > h:
                d[h], d[t] = d[t], d[h]
                t -= 1
        h += 1
    print(sum(i * v for i, v in enumerate(d) if v != -1))

def two():
    d = setup()
    md = max(d)
    for fid in range(md, -1, -1):
        fis = [i for i, v in enumerate(d) if v == fid]
        if not fis:
            continue
        s, e = fis[0], fis[-1] + 1
        l, f, fi = e - s, 0, None
        for i in range(s):
            if d[i] == -1:
                if f == 0:
                    fi = i
                f += 1
                if f == l:
                    break
            else:
                f, fi = 0, None
        if fi is not None and f == l:
            d[fi:fi+l] = [fid]*l
            d[s:e] = [-1]*l
    print(sum(i * v for i, v in enumerate(d) if v != -1))

one()
two()

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

    static void DumpString(IEnumerable<DiskSpace> 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(),
    };
}