Day 11

Here we have an example of a hexagonal grid where we have to figure out how many tiles away a sequence of moves is from wherever you started. The first thing I'm noticing is that some of the moves directly cancel each other so a move of NW and SE kill each other as do moves of N and S. Second, I think there is a conversion scheme of sorts where we can condense pairs of moves into single moves in another direction. Moving NE and NW is the same as going N. The same is true of SE and SW.

I think using these facts we should be able to reduce this down to a much smaller sequence. I'll try to write this in a way that's not specific to my input.

In [1]:
import pandas as pd
import numpy as np

path = open('/Users/Sven/py_files/aoc_2017/d11_input.txt').read()
path = path.split(',')
path[:5]
Out[1]:
['s', 'nw', 's', 'nw', 'se']

Now we can use an np.array to take advantage of the counting techniques

In [2]:
path = np.array(path)
names, counts = np.unique(path, return_counts = True)
counts = dict(zip(names, counts))
counts
Out[2]:
{'n': 1265,
 'ne': 1545,
 'nw': 1362,
 's': 1224,
 'se': 1731,
 'sw': 1095,
 'sw\n': 1}

I'm going to make another dictionary that just labels the sides as numbers and we can use these numbers to do some cancellation.

In [3]:
sides = dict(zip(list(range(6)), ['n', 'ne', 'se', 's', 'sw', 'nw']))
sides
Out[3]:
{0: 'n', 1: 'ne', 2: 'se', 3: 's', 4: 'sw', 5: 'nw'}

Pairs of opposite sides can be cancelled with taking remainder by 3:

In [4]:
for i in range(3):
    sidenos = [x for x in sides.keys() if x % 3 == i]
    sidenames = [sides[side] for side in sidenos]
    bins = [counts[side] for side in sidenames]
    m = min(bins)
    for side in sidenames:
        counts[side] -= m
counts
Out[4]:
{'n': 41, 'ne': 450, 'nw': 0, 's': 0, 'se': 369, 'sw': 0, 'sw\n': 1}

This should leave us with at most three non-zero directions. There are three possiblities now: there are only two nonzero sides (ez), there is a string of three adjacent nonzero sides, or none of the three non-zero sides are adjacent. Let's write two more simplifications to deal with the second and third possibilities.

If we have no adjacent nonzero sides we can cancel them down in the same way as before:

In [5]:
for i in range(2):
    sidenos = [x for x in sides.keys() if x % 2 == i]
    sidenames = [sides[side] for side in sidenos]
    bins = [counts[side] for side in sidenames]
    m = min(bins)
    for side in sidenames:
        counts[side] -= m
counts
Out[5]:
{'n': 41, 'ne': 450, 'nw': 0, 's': 0, 'se': 369, 'sw': 0, 'sw\n': 1}

For the next one, well take adjacent triplets, find the min of the first and third side, subtract it from those sides, and add it to the middle side:

In [6]:
for i in range(6):
    sidenos = [x % 6 for x in list(range(i, i+3))]
    sidenames = [sides[side] for side in sidenos]
    bins = [counts[side] for side in sidenames]
    m = min(bins[0], bins[2])
    counts[sidenames[0]] -= m
    counts[sidenames[1]] += m
    counts[sidenames[2]] -= m
counts
Out[6]:
{'n': 0, 'ne': 491, 'nw': 0, 's': 0, 'se': 328, 'sw': 0, 'sw\n': 1}

This algorithm should guarantee we have two non-opposite directions meaning the sum of the counts is the total moves necessary:

In [7]:
sum(counts.values())
Out[7]:
820

Part 2

We're now asked the simple question of how far is the furthest point reached on the path. I think the easiest way to compute this is just to make the loops we wrote into a function and iterate it over successive sublists of the input.

In [8]:
# List this dictionary again for clarity:
sides = dict(zip(list(range(6)), ['n', 'ne', 'se', 's', 'sw', 'nw']))

# Define our counting function
def hex_dist(path):
    
    # Make a list of the counts of each direction. We have to accomidate for
    # the fact that not all directions will be present for a while by making 
    # a blank dictionary first and updating it:
    counts = dict(zip(sides.values(), [0 for x in range(6)]))
    names, counts_new = np.unique(path, return_counts = True)
    add_counts = dict(zip(names, counts_new))
    counts.update(add_counts)
    
    # Remove exact opposites, get to at most 3 directions:
    for i in range(3):
        sidenos = [x for x in sides.keys() if x % 3 == i]
        sidenames = [sides[side] for side in sidenos]
        bins = [counts[side] for side in sidenames]
        m = min(bins)
        for side in sidenames:
            counts[side] -= m
        
    # Remove unadjacent trios:
    for i in range(2):
        sidenos = [x for x in sides.keys() if x % 2 == i]
        sidenames = [sides[side] for side in sidenos]
        bins = [counts[side] for side in sidenames]
        m = min(bins)
        for side in sidenames:
            counts[side] -= m
    
    # Collapse adjacent trios:
    for i in range(6):
        sidenos = [x % 6 for x in list(range(i, i+3))]
        sidenames = [sides[side] for side in sidenos]
        bins = [counts[side] for side in sidenames]
        m = min(bins[0], bins[2])
        counts[sidenames[0]] -= m
        counts[sidenames[1]] += m
        counts[sidenames[2]] -= m
    
    # Return the distance:
    return(sum(counts.values()))

Now we iterate over the subsequences:

In [9]:
max_dist = 0
for i in range(len(path)):
    max_dist = max(max_dist, hex_dist(path[:(i+1)]))
max_dist
Out[9]:
1596