Solution for Advent of Code 2017 - Day 6: Memory Reallocation

Link to the puzzle text

Part 1

In this puzzle, we have a list of values and a mechanism to transform this list. In each step, the largest value in the list is distributed one at a time over the other elements in this list. We are asked to repeat this distribution step until we find a repeat state and get the number of steps until then.

The distribution could be done more efficiently, but we used a naive implementation:

index = numpy.argmax(state)
value = state[index]
state[index] = 0
while value > 0:
    index = (index + 1) % len(state)
    state[index] += 1
    value -= 1

For checking whether we have already seen this state, we convert the list into a string and keep a set of previously seen states. Once we have the first state already in this set, we return the current step number.

Part 2

In part 1, we found an infinite cycle, since the states repeat. In part 2, we should now answer the length of this infinite cycle. This can be different than the answer for part 1, for example in the following chain of states 1 -> 2 -> 3 -> 4 -> 3 -> 4 -> ...

We reused the code from part 1, and started at the previous end. This way we count only the number of steps inside a cycle. 

Link to my solutions