Skip Navigation
Advent Of Code @programming.dev
CameronDev @programming.dev

πŸ’Ώ - 2024 DAY 9 SOLUTIONS -πŸ’Ώ

Day 9: Disk Fragmenter

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

44 comments

  • Uiua

    Just a port of my Dart solution from earlier really, and it shows, as it takes about 30 seconds on the live data.

    (edit: I just noticed the little alien in the code (β‹…β‹…βˆ˜|β‹…βˆ˜|∘) which is literally flipping the stack (β•―Β°β–‘Β°)β•―οΈ΅ ┻━┻!)

    How to read this

    Try it live!

     
        
Data   ← "2333133121414131402"
FS     ← β†™βŒŠΓ·2⧻.▽≑⋕:β™­β‰βŠŸβŠƒ(⇑|β†―:Β―1)⧻.Data  # Build up a map of the FS.
MoveB  ← ⍜(⊑|β‹…)βŠƒ(β‹…β‹…βˆ˜|β‹…βˆ˜|∘) ⊑¯1.:βŠ’βŠšβŒ•Β―1. # Find a space, move block into it.
MoveBs ← ⍒(⍒(β†˜Β―1|=Β―1⊣)β†˜Β―1MoveB|>0β§»βŠšβŒ•Β―1)

TryMove ← ⨬(β—Œ|βˆ§βœβŠβ‡Œβ‰)/Γ—/>.
MoveFile ← (
  βŠƒ(βŠšβŒ•β†―:Β―1⧻|∘)βŠšβŒ•βŠ™.βŠ™.         # get posns from, start posn to.
  ⨬(β—Œβ—Œ|TryMove ⊟+βŠ™β—ŒΒ°βŠ,⊒)>0⧻. # check posn to is good, swap.
)
Check ← /+/Γ—βŠŸβ‡‘β§».β†₯0
&p Check MoveBs FS
&p Check ∧MoveFileβ‡Œ+1⇑/β†₯.FS

    (edit: improved. Part1 is instant, part2 is about 17sec, but the alien has left)

     
        
Data   ← "2333133121414131402"
FS     ← ▽≑⋕:↙⧻:β™­β‰βŠŸβŠƒ(⇑|β†―:Β―1)⧻..Data # Build up a map of the FS.
Ixs    ← βŠƒ(⊚¬|β‡ŒβŠš)β‰₯0                 # Get indices of space, and of blocks reversed.
SwapBs ← β–½βŠΈβ‰‘/>β‰βŠŸβˆ©β†™βŸœ:β†§βˆ©β§»,,           # Join them where space < block.

Files ← β‡Œβ‰‘(β–‘βŠš)⊞=⇑+1/β†₯.
Move  ← ∧(βœβŠβ‡Œ)β‰βŠŸ+⇑⧻,⊒ # (tos, froms, fs)
MoveFile ← (
  βŠšβŒ•βŠ™,β†―:Β―1⧻.                # List of possible starts
  ⨬(β—Œβ—Œ|⨬(β—Œβ—Œ|Move)>∩⊒,,)>0⧻. # Only valid, leftwards starts 
)
Check ← /+/Γ—βŠŸβ‡‘β§».β†₯0
&p Check βˆ§βœβŠβ‡ŒSwapBs⊸Ixs FS
&p Check βˆ§β—‡MoveFile Files .FS

  • 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

  • Julia

    Oh today was a struggle. First I did not get what exactly the task wanted me to do and then in part 2 I tried a few different ideas which all failed because I changed the disk while I was indexing into it. Finally now I reworked part 2 not moving the blocks at all, just using indexes and it works.

    I feel that there is definitely something to learn here and that's what I like about AoC so far. This is my first AoC but I hope that I won't have to put this much thought into the rest, since I should definitely use my time differently.

  • Haskell

    This was fun, I optimized away quite a bit, as a result it now runs in 0.04s for both parts together on my 2016 laptop.

    In part 1 I just run through the array with a start- and an end-index whilst summing up the checksum the entire time.
    In part 2 I build up Binary Trees of Free Space which allow me to efficiently search for and insert free spaces when I start traversing the disk from the back. Marking the moved files as free is omitted because the checksum is calculated for every file that is moved or not moved directly.

  • Haskell

    Quite messy

     haskell
        
{-# LANGUAGE LambdaCase #-}

module Main where

import Control.Applicative
import Control.Arrow
import Control.Monad
import Control.Monad.ST
import Control.Monad.Trans
import Control.Monad.Trans.Maybe
import Data.Array.ST
import Data.Array.Unboxed
import Data.Char
import Data.List
import Data.Maybe

parse = zip ids . fmap digitToInt . takeWhile (/= '\n')

ids = intersperse Nothing $ Just <$> [0 ..]

expand :: [(a, Int)] -> [a]
expand = foldMap (uncurry $ flip replicate)

process l = runSTArray $ do
    arr <- newListArray (1, length l) l
    getBounds arr >>= uncurry (go arr)
  where
    go arr iL iR = do
        (iL', iR') <- advance arr (iL, iR)
        if iL' < iR'
            then swap arr iL' iR' *> go arr iL' iR'
            else return arr

swap arr i j = do
    a <- readArray arr i
    readArray arr j >>= writeArray arr i
    writeArray arr j a

advance arr (h, t) = (,) <$> advanceHead arr h <*> advanceTail arr t
  where
    advanceHead arr i =
        readArray arr i >>= \case
            Nothing -> return i
            _ -> advanceHead arr (succ i)

    advanceTail arr i =
        readArray arr i >>= \case
            Nothing -> advanceTail arr (pred i)
            _ -> return i

checksum = sum . zipWith (*) [0 ..]

process2 l = runSTArray $ do
    let idxs = scanl' (+) 1 $ snd <$> l
        iR = last idxs
    arr <- newArray (1, iR) Nothing
    forM_ (zip idxs l) $ \(i, v) -> writeArray arr i (Just v)

    runMaybeT $ go arr iR

    return arr
  where
    go :: MArr s -> Int -> MaybeT (ST s) ()
    go arr iR = do
        (i, sz) <- findVal arr iR

        (findGap arr sz 1 >>= move arr i) <|> return ()

        go arr $ pred i

type MArr s = STArray s Int (Maybe (Maybe Int, Int))

findGap :: MArr s -> Int -> Int -> MaybeT (ST s) Int
findGap arr n i = do
    mx <- lift $ snd <$> getBounds arr
    guard $ i <= mx
    ( do
            Just (Nothing, v) <- lift (readArray arr i)
            guard $ v >= n
            hoistMaybe $ Just i
        )
        <|> findGap arr n (succ i)

findVal :: MArr s -> Int -> MaybeT (ST s) (Int, Int)
findVal arr i = do
    guard $ i >= 1
    lift (readArray arr i) >>= \case
        Just (Just _, sz) -> hoistMaybe $ Just (i, sz)
        _ -> findVal arr $ pred i

move arr iVal iGap = do
    guard $ iGap < iVal

    Just (Nothing, gap) <- lift $ readArray arr iGap
    v@(Just (Just _, sz)) <- lift $ readArray arr iVal
    lift . writeArray arr iVal $ Just (Nothing, sz)
    lift $ writeArray arr iGap v

    when (gap > sz) . lift . writeArray arr (iGap + sz) $ Just (Nothing, gap - sz)

part1 = checksum . catMaybes . elems . process . expand
part2 = checksum . fmap (fromMaybe 0) . expand . catMaybes . elems . process2

main = getContents >>= print . (part1 &&& part2) . parse

  • PYTHON

    Execution Time: Part1 = 0.02 seconds. Part2 = ~2.1 seconds. total = ~2.1 seconds

    Aiming for simplicity over speed. This is pretty fast for not employing simple tricks like trees and all that.

    Edit:

    New version that is using a dictionary to keep track of the next empty slot that fits the current index.

    Execution Time: Part1 = 0.02 seconds. Part2 = ~0.08 seconds. total = ~0.08 seconds 80 ms

    Edit: final revision. I just realized that the calculating for "last_consecutive_full_partition" was not necessary and very slow. if I know all the next available slots, and can end early once my current index dips below all next available slots then the last_consecutive_full_partition will never be reached. This drops the time now to less than ~0.1 seconds

    Probably Final Edit: I found someone's O(n) code for OCaml. I tried to convert it to be faith fully in pure python. seems to work really really fast. 30-50 ms time for most inputs. seems to scale linearly too

    :::spoiler FastCode

     py
        
def int_of_char(x):
    return ord(x) - ord('0')

# Represent content as tuples:
# ('Empty', size) or ('File', id, size)
def parse(line):
    arr = []
    for i in range(len(line)):
        c = int_of_char(line[i])
        if i % 2 == 0:
            arr.append(('File', i // 2, c))
        else:
            arr.append(('Empty', c))
    return arr

def int_sum(low, high):
    return (high - low + 1) * (high + low) // 2

def size(elem):
    t = elem[0]
    if t == 'Empty':
        return elem[1]
    else:
        return elem[2]

def part1(array):
    total = 0
    left = 0
    pos = 0
    right = len(array) - 1

    while left < right:
        if array[left][0] == 'File':
            # File
            _, fid, fsize = array[left]
            total += fid * int_sum(pos, pos + fsize - 1)
            pos += fsize
            left += 1
        else:
            # Empty
            _, esize = array[left]
            if array[right][0] == 'Empty':
                right -= 1
            else:
                # Right is File
                _, fid, fsize = array[right]
                if esize >= fsize:
                    array[left] = ('Empty', esize - fsize)
                    total += fid * int_sum(pos, pos + fsize - 1)
                    pos += fsize
                    right -= 1
                else:
                    array[right] = ('File', fid, fsize - esize)
                    total += fid * int_sum(pos, pos + esize - 1)
                    pos += esize
                    left += 1

    # If one element remains (left == right)
    if left == right and left < len(array):
        if array[left][0] == 'File':
            _, fid, fsize = array[left]
            total += fid * int_sum(pos, pos + fsize - 1)

    return total

def positions(arr):
    total = 0
    res = []
    for e in arr:
        res.append(total)
        total += size(e)
    return res

def array_fold_right_i(f, arr, acc):
    pos = len(arr) - 1
    for elt in reversed(arr):
        acc = f(elt, pos, acc)
        pos -= 1
    return acc

def part2(array):
    def find_empty(size_needed, max_pos, pos):
        while pos <= max_pos:
            if array[pos][0] == 'File':
                raise Exception("Unexpected: only empty at odd positions")
            # Empty
            _, esize = array[pos]
            if esize >= size_needed:
                array[pos] = ('Empty', esize - size_needed)
                return pos
            pos += 2
        return None

    emptys = [1 if i < 10 else None for i in range(10)]
    pos_arr = positions(array)

    def fold_fun(elt, i, total):
        if elt[0] == 'Empty':
            return total
        # File
        _, fid, fsize = elt
        init_pos = emptys[fsize]
        if init_pos is None:
            new_pos = pos_arr[i]
        else:
            opt = find_empty(fsize, i, init_pos)
            if opt is None:
                new_pos = pos_arr[i]
            else:
                new_pos = pos_arr[opt]
                pos_arr[opt] += fsize
                emptys[fsize] = opt
        return total + fid * int_sum(new_pos, new_pos + fsize - 1)

    return array_fold_right_i(fold_fun, array, 0)

def main():
    with open('largest_test', 'r') as f:
        line = f.read().replace('\r', '').replace('\n', '')
    arr = parse(line)
    arr_copy = arr[:]
    p1 = part1(arr_copy)
    print("Part 1 :", p1)
    p2 = part2(arr)
    print("Part 2 :", p2)

if __name__ == "__main__":
    main()

  • Dart

    I just mapped the filesystem onto a list holding value at each block (with -1 for spaces), and manipulated that.

    It's slow, but it's honest work.

    Updated version

    Massive speedup from implementing a modified Knuth–Morris–Pratt algorithm -> around 0.5sec runtime for part 2.

    I really don't understand why efficiently matching a sublist isn't a builtin function. Implementing it manually was half an hour of unneeded head-scratching.

     
        
import 'dart:math';
import 'package:collection/collection.dart';
import 'package:more/more.dart';

List<int> parse(List<String> lines) => lines.first
    .split('')
    .map(int.parse)
    .mapIndexed((i, e) => List.filled(e, (i.isOdd ? -1 : i ~/ 2)))
    .flattened
    .toList();

part1(List<String> lines) {
  var fs = parse(lines);
  var i = 0;
  while ((i = fs.indexOf(-1)) >= 0) {
    while (fs.last == -1) {
      fs.removeLast();
    }
    fs[i] = fs.removeLast();
  }
  return fs.mapIndexed((i, e) => i * e).sum;
}

part2(List<String> lines) {
  var fs = parse(lines);
  for (var target in 1.to(fs.max + 1).reversed) {
    var index = fs.indexOf(target);
    var length = fs.skip(index).takeWhile((e) => e == target).length;
    int? space = findSpace(index, length, fs);
    if (space == null) continue;
    // Copy the file, clear old location.
    fs.setRange(space, space + length, List.filled(length, target));
    fs.setRange(index, index + length, List.filled(length, -1));
  }
  return fs.mapIndexed((i, e) => i * max(e, 0)).sum;
}

/// Knuth–Morris–Pratt algorithm
int? findSpace(int limit, int length, List<int> fs) {
  for (var si = 0; si < limit - length + 1; si++) {
    if (fs[si] != -1) continue;
    var match = true;
    for (var ssi in 0.to(length)) {
      if (fs[si + ssi] != -1) {
        si += ssi;
        match = false;
        break;
      }
    }
    if (match) return si;
  }
  return null;
}

  • 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(),
    };
}

  • 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 

     nim
        
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

  • 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.

  • 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:

     text
        
day09  0:00.05  1648 Kb  0+179 faults

    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!

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

  • Haskell

    Unoptimized as hell, also brute-force approach (laptops are beasts).

  • 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 πŸ˜”

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

  • Haskell

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

    • Second attempt! I like this one much better.

      Edit: down to 0.040 secs now!

       
          
import Control.Arrow
import Data.Either
import Data.List
import Data.Map (Map)
import Data.Map qualified as Map

type Layout = ([(Int, (Int, Int))], Map Int Int)

readInput :: String -> Layout
readInput =
  map (read . singleton) . head . lines
    >>> (scanl' (+) 0 >>= zip) -- list of (pos, len)
    >>> zipWith ($) (intersperse Right [Left . (id,) | id <- [0 ..]])
    >>> partitionEithers
    >>> filter ((> 0) . snd . snd) *** Map.filter (> 0) . Map.fromAscList

checksum :: Layout -> Int
checksum = sum . map (\(id, (pos, len)) -> id * len * (2 * pos + len - 1) `div` 2) . fst

compact :: (Int -> Int -> Bool) -> Layout -> Layout
compact select (files, spaces) = foldr moveFile ([], spaces) files
  where
    moveFile file@(fileId, (filePos, fileLen)) (files, spaces) =
      let candidates = Map.assocs $ fst . Map.split filePos $ spaces
       in case find (select fileLen . snd) candidates of
            Just (spacePos, spaceLen) ->
              let spaces' = Map.delete spacePos spaces
               in if spaceLen >= fileLen
                    then
                      ( (fileId, (spacePos, fileLen)) : files,
                        if spaceLen == fileLen
                          then spaces'
                          else Map.insert (spacePos + fileLen) (spaceLen - fileLen) spaces'
                      )
                    else
                      moveFile
                        (fileId, (filePos + spaceLen, fileLen - spaceLen))
                        ((fileId, (spacePos, spaceLen)) : files, spaces')
            Nothing -> (file : files, spaces)

main = do
  input <- readInput <$> readFile "input09"
  mapM_ (print . checksum . ($ input) . compact) [const $ const True, (<=)]

  • python

  • Kotlin

    No lists were harmed in the making of this code.

  • Rust

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

     rust
        
#[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<i64> {
        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<i64> {
        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<i64> = 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<usize> {
        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<i64> = expand_disk(&input);

        defrag2(&mut disk);

        let checksum = checksum(&disk);

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

  • 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.

    Also on github

  • 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 =. (&lt;"2) 0 2 |: _2 ]\ block_intervals
   if. 2 | #y do. result =. result 1}~ (}: &amp;.>) 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 =. &lt;: # 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 &lt;: 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 =. &lt;: p
         while. 0 = p { y do. p =. &lt;: 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.~ ((>: &amp; file_length) @: -~/)"1 free_intervals
   if. (target_free_index &lt; # free_intervals) do.
      'a b' =. target_free_index { free_intervals
      if. a &lt; {. 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
44 comments