Advent of Code - Day 9-10

When I saw the puzzle, I felt confident that this would be reasonably easy. This is a “defragmentation” task, where we first have to unpack information about a filesystem in a “dense format” like this:

Where the first number represents the size of a file, then the second the size of a free space, then the size of the next file, etc. Files have “ids” which are allocated in sequential order, so that the input above is “unpacked” into “File 0 of size 2, followed by 3 empty spaces, followed by file 1 of size 3, etc.”. Putting the numbers of the file ids and the empty spaces as ., this lead to this representation:

Part 1

For the first task we have to move file blocks into the empty spaces, starting from the right (so we first put the last 9 into the first empty space, etc.) The final result of the puzzle is a “checksum”, computed as the sum of the file ids of each block multiplied by their corresponding position in the sequence.

I had a fairly clear idea of how to proceed, at least for an initial inefficient solution, but I got into some weird bugs when I worked on it in the morning. I got the right answer on the test sample, but couldn’t get it on the actual puzzle data. I got frustrated and stopped, restarted from scratch in the evening, and then made it work. But I didn’t want to spend more time on it so my solution for this puzzle is fairly bad – but it works!

After loading the content of the input file into a long string, I started by splitting it into the two parts – file lengths and space lenghts – thanks to some slicing:

flen = data[::2]
slen = data[1::2] + '0'
fid = range(len(flen))

fid will contains the sequence of file ids, and we added a space of size 0 to the slen so that all three sequences have the same length, which makes the second part of constructing the “unpacked” string a lot easier. The result is stored as a list of integers (for the file ids) or None (for spaces):

def parse_data(fname, per_file: bool = True) -> list[int | None]:
    data = load_as_str(fname).strip()
    flen = data[::2]
    slen = data[1::2] + '0'
    fid = range(len(flen))
    unpacked = []
    for fl, sl, fi in zip(flen, slen, fid):
        unpacked += [fi]*int(fl)+[None]*int(sl)
    return unpacked

I implemented the “defragment” algorithm by moving two pointers, one from the left and one from the right. Each time we hit a None on the left, we swap it with the file id from the right. Once the left pointer crosses the right pointer, we stop.

def defragment(data: list[int | None]):
    data = data.copy()
    left = 0
    right = len(data)-1

    while left < right:
        if data[left] is None and data[right] is not None:
            data[left] = data[right]
            data[right] = None
            left += 1
            right -= 1
        elif data[left] is not None:
            left += 1
        else:
            right -= 1

    return data

def checksum(data: list[int | None]):
    return sum([x*i for i,x in enumerate(data) if x is not None])

This time I got the right answer also on the real data. I didn’t have the energy to try to understand exactly what I had done wrong before, so I just deleted the non-working code and decided to move on.

An unsurprising part 2

This is the first time in the challenge that I immediately guessed what part 2 would be after looking at the part 1 puzzle. In fact, when I saw the description of the “defragmenting” method, my first reaction was “wait, shouldn’t you try to keep the files in one piece?”, and that is what we have to do now: instead of moving each file block into an empty space, we have to move the entire file into the first empty space that is big enough to accomodate it.

Despite the fact that I knew this was coming, my code was not well-prepared to handle it, and it took a bit of reworking to make it work.

First, we change our parsing method so that it can unpack “per file”, in which case we present the data as a list of tuples (file_id, file_size) and (None, space_size):

def unpack_per_position(flen: list[str], slen: list[str]) -> list[int | None]:
    fid = range(len(flen))
    unpacked = []
    for fl, sl, fi in zip(flen, slen, fid):
        unpacked += [fi]*int(fl)+[None]*int(sl)
    return unpacked

def unpack_per_file(flen: list[str], slen: list[str]) -> list[tuple[int | None, int]]:
    fid = range(len(flen))
    unpacked = []
    for fl, sl, fi in zip(flen, slen, fid):
        unpacked += [(fi, int(fl))]+[(None, int(sl))]
    return unpacked[:-1]

def parse_data(fname, per_file: bool = True) -> list[int | None | tuple[int | None, int]]:
    data = load_as_str(fname).strip()
    flen = data[::2]
    slen = data[1::2] + '0'
    if per_file:
        return unpack_per_file(flen, slen)
    return unpack_per_position(flen, slen)

By this point I just wanted to get it done so I didn’t try to make my original defragment function more generic, I just solved the second part as a separate function. First, we reverse-sort the file ids. For each file starting from the last, we find its position on the list, then moving from left to right we look for an empty space and check if its large enough, in which case we make the swap. There are a couple of things to take care of for it to work: if the size of the space and the size of the file match, we can make a straight swap. But if the space was larger, we have to make sure that we keep a space of size space_size-file_size after the file. Finally, if at some point our “from the left” pointer meets our current file position, we can move on to the next file as we can only move files “to the left”.

def defragment_per_file(data: list[int | None]):
    data = data.copy()
    fids = sorted([(f[0], f[1]) for f in data if f[0] is not None], reverse=True)
    for fid, fsize in fids:
        fpos = [f[0] for f in data].index(fid)
        for i, f in enumerate(data):
            if i > fpos:
                break
            if f[0] is None:
                if f[1] < fsize:
                    continue
                if f[1] == fsize:
                    data[i] = (fid, fsize)
                    data[fpos] = (None, fsize)
                    break
                data[i] = (fid, fsize)
                data.insert(i+1, (None, f[1]-fsize))
                data[fpos+1] = (None, fsize)
                break
    defrag = []
    for d0, d1 in data:
        defrag += [d0]*d1
    return defrag

Day 10 - climbing back on top

I like maps and I like mountains, so this challenge was already off to a good start: we have a topographic map, and we have to find paths from trailheads (at the “bottom”, or height 0) to the tops (height 9). The map is a grid like this:

And the rule is that a trail only goes “up”, by one unit of height at a time, and only in the four cardinal directions. So each path has to have 9 steps, going 0-1-2-…-9.

Part 1 - reachable tops

In the first part, we have to count for each trailhead (0) the number of tops (9) that can be reached using the aforementioned rules. The solution to the puzzle is the sum of reachable tops for each trailhead.

I thought a bit about how to represent the data to make the pathfinding bit easier, and then I realized that I could actually look at the grid as an oriented graph: from each node (position) there are some other nodes that can be reached. Those “neighbours” are the nodes in the four adjacent positions where the value is “one more”. So if A has a path towards B, B will not have one towards A.

So I decided to represent the data as a dict where each position was mapped to a list of accessible neighbours. We also separately keep a list of starting points (positions where value is 0) and endpoints (positions where value is 9). To construct the grid, we first parse the input file as a list of list of integers. Then, we go through each position, check which neighbours can be visited (and are within bounds), and adding to the starts and ends as needed:

Position = namedtuple("Position", ["row", "column"])

def in_bounds(r: int, c: int, maxrows: int, maxcols: int) -> bool:
    return (0 <= r < maxrows) and (0 <= c < maxcols)

def parse_grid(data: list[list[int]]) -> tuple[dict[Position, list[Position]], list[Position], list[Position]]:
    """Returns map Position -> list of neighbours
    + list of start and end points"""
    grid = {}
    starts = []
    ends = []
    maxrows = len(data)
    maxcols = len(data[0])
    for r, row in enumerate(data):
        for c, val in enumerate(data[r]):
            p = Position(r, c)
            grid[p] = []
            if val == 0:
                starts.append(p)
            elif val == 9:
                ends.append(p)   
            for neigh in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:
                nr, nc = neigh
                if not in_bounds(nr, nc, maxrows, maxcols):
                    continue
                if data[nr][nc] - val == 1:
                    grid[p].append(Position(nr, nc))
    
    return grid, starts, ends

def load_as_grid(fname: str | pathlib.Path, cast: Callable[[str], Any] = str) -> list[list[Any]]:
    data = []
    with open(fname, 'r') as fp:
        data = fp.readlines()
    return [[cast(c) for c in row.strip()] for row in data if len(row) != 0]

def load_data():
    data = []
    with open("day10", 'r') as fp:
        data = fp.readlines()
    return parse_grid([[int(c) for c in row.strip()] for row in data if len(row) != 0])

Now to count the reachable tops, we just have to follow the graph from the start and count how many unique ends we can get to. A bit of recursion felt appropriate here. The reachable_ends are kept in a set to avoid duplicates:

def find_paths(grid, start, ends, reachable_ends):
    if start in ends:
        reachable_ends.add(start)
        return
    for n in grid[start]:
        find_paths(grid, n, ends, reachable_ends)
    return

def main():
    grid, starts, ends = load_data("")

    scores = 0
    for start in starts:
        reachable_ends = set()
        find_paths(grid, start, ends, reachable_ends)
        scores += len(reachable_ends)
    print(f"Part 1 answer: {scores}")

Part 2 - wait, I’ve done that already?

This time, I hadn’t anticipated part 2 at all, yet this is the least amount of change I’ve had to do to the code so far. For part 2, we now have to count the number of unique paths from trailheads to tops, rather than the number of tops we can reach.

But we already go through all those paths. We just remove duplicate by using a set. So if we just use a list, we have our answer:

scores = 0
for start in starts:
    reachable_ends = []
    find_paths(grid, start, ends, reachable_ends)
    scores += len(reachable_ends)
print(f"Part 2 answer: {scores}")

Fine, that’s not entirely accurate, there is a second line that we need to change: in a set we have to use add and not append in the find_paths function. And… that’s it, part 2 done!

Day 9 - frustrating fragments

Part 1

An unsurprising part 2

Day 10 - climbing back on top

Part 1 - reachable tops

Part 2 - wait, I’ve done that already?