Solution for Advent of Code 2017 - Day 14: Disk Defragmentation

Link to the puzzle text

Part 1

In this puzzle, we use the knot hash function fomr day 10 to generate a grid. Each line is generated by taking the input, adding the line number to the string and hashing it. The resulting hex string is interpreted as binary for a 2D grid of 0 and 1. We are asked to count the number of 1s.

We reused the hash function from before. The grid generation needed no extra attention, just making sure the binary string was padded to 128 bits. For counting the 1s, we can also just iterate over the lines and count up per line.

Part 2

In part 2, we should count up the number of continous regions of 1s. Two cells are connected horizontally and vertically, not via diagonals.

We count the number of regions by going throught the grid line by line until we find a 1. We then use a recursive fill algorithm to delete all connected cells. The number of regions is then increased by one.

def fill(grid, i, j):
    grid[i][j] = "0"
    neighbours = [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]
    for x, y in neighbours:
        if 0 <= x < 128 and 0 <= y < 128:
            if grid[x][y] == "1":
                fill(grid, x, y)

The fill algorithm is a bit unefficient, but was fast enough for us. Otherwise we could have used a flood fill to reduce the rechecking of cells.

Link to my solutions