Advent of Code 2024 - Day 9: Disk Fragmenter

:: programming, python, puzzle

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 
from advent import parse, digits

input = parse(9, digits)[0] + (0,)

def get_disk():
    disk = []
    i    = 0

    for f, s in zip(input[::2], input[1::2]):
        disk.append([ s, [ i for n in range(f) ] ])
        i += 1

    return disk

def checksum(disk):
    total = 0
    pos   = 0

    for s, *lsts in disk:
        for lst in lsts:
            for i in lst:
                total += pos * i
                pos += 1

        pos += s

    return total

def solve(compact):
    return checksum(compact(get_disk()))

def part1(disk):
    beg = 0
    end = len(disk) - 1

    while beg < end:
        dst_len = disk[beg][0]
        src_len = len(disk[end][1])

        if dst_len == 0 or src_len == 0:
            if dst_len == 0:
                beg += 1
            if src_len == 0:
                end -= 1
        else:
            for i in range(min(dst_len, src_len)):
                disk[beg][0] -= 1
                disk[end][0] += 1
                disk[beg][1].append(disk[end][1].pop())

    return disk

def part2(disk):
    def first_available(disk, start, end, size):
        for i in range(start, end):
            s, *_ = disk[i]
            if s >= size:
                return i

    def attempt_move(disk, beg, end, src_len):
        idx = first_available(disk, beg, end, src_len)

        if idx is not None:
            lst = disk[end][1:]

            if len(lst) > 1:
                disk[end-1][0] += src_len
            else:
                disk[end][0] += src_len

            disk[idx][0] -= src_len
            disk[idx].append(disk[end][1])
            disk[end][1] = []

    beg = 0
    end = len(disk) - 1

    while beg < end:
        dst_len = disk[beg][0]
        src_len = len(disk[end][1])

        if dst_len == 0:
            beg += 1
        else:
            attempt_move(disk, beg, end, src_len)
            end -= 1

    return disk

# ---------------------------------------------------------------------------------------------

assert solve(part1) == 6390180901651
assert solve(part2) == 6412390114238

Disclaimer

Short write up today because I burned way too much time debugging stupid errors! Because of that, the code is essentially the first thing that popped into my head i.e. I didn’t have time to do much refactoring to make it elegant. I may return to this blog post to provide a better description of the algorithms :)

Parsing

Today, we’re given a single string with digits alternating between the number of blocks for a file and the number of blocks of free space. I would like a list of pairs, one per file, where the first element is the number of blocks of free space, and the second element is a list of file ids, with one per block in the file. For the example of 2333133121414131402, I would like:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
 
[[3, [0, 0]],
 [3, [1, 1, 1]],
 [3, [2]],
 [1, [3, 3, 3]],
 [1, [4, 4]],
 [1, [5, 5, 5, 5]],
 [1, [6, 6, 6, 6]],
 [1, [7, 7, 7]],
 [0, [8, 8, 8, 8]],
 [0, [9, 9]]]

The following parsing code accomplishes this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
 
input = parse(9, digits)[0] + (0,)

def get_disk():
    disk = []
    i    = 0

    for f, s in zip(input[::2], input[1::2]):
        disk.append([ s, [ i for n in range(f) ] ])
        i += 1

    return disk

Prerequisites

The two parts differ in how they perform the compaction, so the solution is parameterized with a part higher order function:

1
2
 
def solve(compact):
    return checksum(compact(get_disk()))

Here is the checksum() helper function. We loop over the elements in the disk list. For part 2, it will be convenient to have each element of the disk list be of the form [ num_free_space, file1_list, file2_list, ... ] so this checksum() function expects multiple file lists:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
 
def checksum(disk):
    total = 0
    pos   = 0

    for s, *lsts in disk:
        for lst in lsts:
            for i in lst:
                total += pos * i
                pos += 1

        pos += s

    return total

Part 1

For part 1, we perform the compaction by simply moving one file block at a time from the end of the disk to available free space at the beginning of the disk:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
 
def part1(disk):
    beg = 0
    end = len(disk) - 1

    while beg < end:
        dst_len = disk[beg][0]
        src_len = len(disk[end][1])

        if dst_len == 0 or src_len == 0:
            if dst_len == 0:
                beg += 1
            if src_len == 0:
                end -= 1
        else:
            for i in range(min(dst_len, src_len)):
                disk[beg][0] -= 1
                disk[end][0] += 1
                disk[beg][1].append(disk[end][1].pop())

    return disk

For part 2, we only move entire files, if they will fit. Since we’ll be modifying the elements of the disk list as we go, I needed a way to keep track of files that have yet to be moved. To accomplish this, rather than mutate the file list, as in part 1, I simply add an additional list. This leaves the original file intact at the beginning of the list.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
def part2(disk):
    def first_available(disk, start, end, size):
        for i in range(start, end):
            s, *_ = disk[i]
            if s >= size:
                return i

    def attempt_move(disk, beg, end, src_len):
        idx = first_available(disk, beg, end, src_len)

        if idx is not None:
            lst = disk[end][1:]

            if len(lst) > 1:
                disk[end-1][0] += src_len
            else:
                disk[end][0] += src_len

            disk[idx][0] -= src_len
            disk[idx].append(disk[end][1])
            disk[end][1] = []

    beg = 0
    end = len(disk) - 1

    while beg < end:
        dst_len = disk[beg][0]
        src_len = len(disk[end][1])

        if dst_len == 0:
            beg += 1
        else:
            attempt_move(disk, beg, end, src_len)
            end -= 1

    return disk

New Python Concepts

  • append()
  • pop()
  • Extended unpacking with * e.g. for s, *lsts in disk:
  • Slicing with a step value e.g. input[1::2]

Conclusion

I wasn’t very pleased with my performance on today’s puzzle, but those days happen :) I don’t consider the solution very elegant. Even if I had more time, I’m not particularly motivated to come up with a more elegant solution for this particular puzzle, so on to the next day tomorrow.