The ninth day of Advent of Code was yesterday 09/12/2024! If you’re here for the first time today, don’t forget to read the posts about Day 1, Day 2, Day 3, Day 4, Day 5, Day 6, Day 7 and Day 8.

I classified the ninth problem as easy (part 1) and medium (part 2).

Tips#

  • Remember that strings in Python are immutable

  • If you need to change string characters, you can transform it into a list of characters and convert it back when finished.

  • Lists can be manipulated by slices. You can extract multiple elements from a list at once, as well as change multiple elements using slice notation.

  • zip combines two iterables and is useful, for example, to traverse two lists simultaneously.

  • You can swap two elements using tuples in Python:

a, b = b, a

  • Lists are passed by reference. If your function changes the list, these changes will be visible outside the function.

  • IDs are integers and will be larger than single-digit numbers. When expanding the map, use integers to represent each ID. This might explain why your “checksum” isn’t working.

  • In part 1 of the problem, go step by step. Write a function that expands the map, another that finds free space, and one to execute the reorganization. Use the test values given by the problem to test each function.

  • Part 2 is a bit more complex, as the map is larger and the reorganization more complex, the solution O complexity should not be quadratic (O(n²)). In other words, if you need to generate the list of blank spaces from the beginning for each file, it will be very slow. Use list slice notation to be able to swap multiple elements at once.

  • In part 2, if you need to maintain a list of free space, remember that you can remove elements from the list (del, pop, remove) when the space is completely used. If the space is not fully used, remember to update the free space list.

How much Python do you need to know?#

The chapters refer to my book Introduction to Programming with Python.

  • Lists, tuples - Chapter 6
  • Strings - Chapter 7
  • Generators, itertools - Chapter 8

Answer# 

from aux import read_file_without_blank_lines

DISK_MAP = "2333133121414131402"
DISK_MAP_EXPANDED = "00...111...2...333.44.5555.6666.777.888899"
DISK_MAP_REARRANGED = "0099811188827773336446555566.............."
DISK_MAP_REARRANGED_2 = "00992111777.44.333....5555.6666.....8888.."


def list_to_string(list_input):
    return "".join(list_input)


def expand_map(disk_map: str) -> str:
    expanded = []
    mode = True
    id = 0
    for code in disk_map:
        if mode:
            expanded += [str(id)] * int(code)
            id += 1
        else:
            expanded += ["."] * int(code)
        mode = not mode
    return expanded


def free(disk: list[str]) -> int:
    for position, c in enumerate(disk):
        if c == ".":
            yield position


def used_from_right(disk: list[str]) -> int:
    position = len(disk) - 1
    while position >= 0:
        if disk[position] != ".":
            yield position
        position -= 1


def swap(disk: list[str], a: int, b: int, size: int = 1):
    disk[a : a + size], disk[b : b + size] = (
        disk[b : b + size],
        disk[a : a + size],
    )


def rearrange(disk: list[str]):
    for left, right in zip(free(disk), used_from_right(disk)):
        if right <= left:
            break
        swap(disk, left, right)


def continuous_free(disk: list[str]) -> (int, int):
    u = -1
    for p, c in enumerate(disk):
        if c == "." and u == -1:
            u = p
        elif c != "." and u != -1:
            yield u, p - 1
            u = -1


def continuous_used_from_right(disk: list[str]) -> (int, int):
    position = len(disk) - 1
    while position >= 0:
        if disk[position] != ".":
            end = position
            while disk[position] == disk[end] and position >= 0:
                position -= 1
            position += 1
            if position >= 0:
                yield position, end
        position -= 1


def rearrange_part_2(disk: list[str]):
    free_space = list(continuous_free(disk))
    for start, end in continuous_used_from_right(disk):
        size = end - start + 1
        for i, (free_start, free_end) in enumerate(free_space):
            if free_end >= start:
                break
            if free_end - free_start + 1 >= size:
                swap(disk, free_start, start, size)
                if free_end - free_start + 1 == size:
                    free_space.pop(i)
                else:
                    free_space[i] = (free_start + size, free_end)
                break


def checksum(disk: list[str]) -> int:
    s = 0
    for position, id in enumerate(disk):
        s += position * int(id) if id != "." else 0
    return s


# Test
expanded = expand_map(DISK_MAP)
assert list_to_string(expanded) == DISK_MAP_EXPANDED
rearrange(expanded)
assert list_to_string(expanded) == DISK_MAP_REARRANGED
check = checksum(expanded)
print("Test - part 1:", check)
assert check == 1928

# Part 1
input_data = read_file_without_blank_lines("09/input.txt")
expanded = expand_map(input_data)
rearrange(expanded)
check = checksum(expanded)
print("Part 1:", check)
assert check == 6283170117911

# Test - Part 2
expanded = expand_map(DISK_MAP)
rearrange_part_2(expanded)
assert list_to_string(expanded) == DISK_MAP_REARRANGED_2
check = checksum(expanded)
print("Test - Part 2:", check)
assert check == 2858

# Part 2
expanded = expand_map(input_data)
rearrange_part_2(expanded)
check = checksum(expanded)
print("Part 2:", check)
assert check == 6307653242596

# Output:
# Test - part 1: 1928
# Part 1: 6283170117911
# Test - Part 2: 2858
# Part 2: 6307653242596