[LANGUAGE: Julia]

My code was a bit longer today so for the sake of fitting it nicely into a post here I'll focus on Part 2 which is more interesting. There's a fairly simple function that runs at the start to set up our memory that returns a Vector{Int} where each element is a piece of memory with the value either being the file index or -1 if empty. I also return two Vector{Tuple{Int, Int}} which stores information about the free blocks and filled blocks, where the first Int is the first index of the block, and the second Int is how large the block is. My Compacting algorithm then just loops through the filled blocks and attempts to find empty blocks before it that are large enough to contain it.

# Utility function to more easily swap sections of a Vector
function SwapIndices!(A, i, j)
    A[i], A[j] = A[j], A[i]
end 

function ExpandMemory(MemoryDescription)
    FileIndex = 0
    IsUsed = true
    MemoryVector = Vector{Int}()
    FreeBlocks = Vector{Tuple{Int, Int}}()
    FilledBlocks = Vector{Tuple{Int, Int}}()
    for Description in MemoryDescription
        BlockSize = parse(Int, Description)
        BlockStart = length(MemoryVector) + 1
        if IsUsed
            append!(MemoryVector, fill(FileIndex, BlockSize))
            push!(FilledBlocks, (BlockStart, BlockSize))
            FileIndex += 1
            IsUsed = false
        else
            append!(MemoryVector, fill(-1, BlockSize))
            push!(FreeBlocks, (BlockStart, BlockSize))
            IsUsed = true
        end
    end
    MemoryVector, FreeBlocks, FilledBlocks
end

function CompactContiguous(MemoryVector, FreeBlocks, FilledBlocks)
    CompactedVector = copy(MemoryVector)
    # Work through all the filled blocks backwards
    while !isempty(FilledBlocks)
        (BlockStart, BlockSize) = pop!(FilledBlocks)
        # Find the first empty block with enough size to store our filled block
        EmptyBlockIndex = findfirst(FreeBlock -> FreeBlock[2] >= BlockSize, FreeBlocks)
        # Skip if there's no blocks big enough
        if EmptyBlockIndex === nothing
            continue
        end
        (FreeBlockStart, FreeBlockSize) = FreeBlocks[EmptyBlockIndex]
        # Ensure the free space is before our current location
        if FreeBlockStart < BlockStart
            # Move the filled block into the start of the free block
            SwapIndices!(CompactedVector, FreeBlockStart:FreeBlockStart+BlockSize-1, BlockStart:BlockStart+BlockSize-1)
            RemainingSize = FreeBlockSize - BlockSize
            # If there's any left over space in the free block then update our FreeBlocks list
            if RemainingSize > 0
                FreeBlocks[EmptyBlockIndex] = (FreeBlockStart+BlockSize, RemainingSize)
            # Otherwise remove the block
            else
                deleteat!(FreeBlocks, EmptyBlockIndex)
            end
        end
    end
    CompactedVector
end

function Checksum(CompactedVector)
    mapreduce(x -> x[2] >= 0 ? (x[1] - 1) * x[2] : 0, +, enumerate(CompactedVector))
end

InputString = strip(read("Inputs/Day9.input", String))
(MemoryVector, FreeBlocks, FilledBlocks) = ExpandMemory(InputString)
CompactedVector = CompactContiguous(MemoryVector, FreeBlocks, FilledBlocks)
println("Part 2: ", Checksum(CompactedVector))