Day 6

The set up for this puzzle is that we have a number of bins with different values in them. An algorithm is used to try to even out the values in the bins. It functions by picking up the contents of the largest bin (in order if there are ties) and then sequentially dropping one in each bin until the total is exhausted. It reminds me of mancala. Eventually, this process will arrive at some sort of loop and we're supposed to figure out how long that will take.

Start by loading up the data and formatting it:

import pandas as pd
import numpy as np

initial = open('/Users/Sven/py_files/aoc_2017/d6_input.txt')
initial = initial.read()
initial = initial.split('\t')
initial = [int(x) for x in initial]

initial_np = np.array(initial, dtype = 'int')
n_bins = len(initial_np)
initial_np

array([ 2,  8,  8,  5,  4,  2,  3,  1,  5,  5,  1,  2, 15, 13,  5, 14])

Now we'll write a function that can redistribute the largest cell and return another np.array.

The first line of the function is still a bit mysterious to me. Without it, the marx function will actually modify the global variable initial_np. This has something to do with mutable vs immutable types. In R, this would not be an issue since the instance of x within the function's execution environment will not be the same as the argument fed to the function.

def marx(x):
    x = np.copy(x)
    max_index = x.argmax()
    # scoop up the contents and start to redistribute
    scoop = x[max_index]
    x[max_index] = 0
    for i in range(1, scoop + 1):
        x[(max_index + i) % n_bins] += 1
    return(x)

Now test it and see that it does not modify initial_np

print(marx(initial_np))
print(initial_np)

[ 3  9  9  6  5  3  4  2  6  6  2  3  0 14  6 15]
[ 2  8  8  5  4  2  3  1  5  5  1  2 15 13  5 14]

Great, now we want to keep doing this process and adding the results to a list so we can check whether or not we've hit this state before. Set up and use a while loop:

moves = 0
states = [initial_np]
uniques = 1
while moves == uniques - 1:
    moves += 1
    states.append(marx(states[-1]))
    uniques = len(np.unique(states, axis = 0))
moves

3156

Part 2

Cool, now we've just got a small tweak for the second part. We're asked how long the cycle is following this first repeated value. We could carry the experiment forward with the first value that repeated or just find that value in our list and find the difference from the end.

Carrying forward:

loop_list = [states[-1]]
loop_list

[array([ 0, 13, 12, 10,  9,  8,  7,  5,  3,  2,  1,  1,  1, 10,  6,  5])]

moves = 0
uniques = 1
while moves == uniques - 1:
    moves += 1
    loop_list.append(marx(loop_list[-1]))
    uniques = len(np.unique(loop_list, axis = 0))
moves

1610

We can also find the location that its equal like this:

# matches = states.apply(lambda x: np.equal(x, states[-1]))
matches = [np.array_equal(x, states[-1]) for x in states]
matches_where = np.where(np.array(matches))

matches_where[0][1] - matches_where[0][0]

1610