AoC 2017 Day 16: Swing Your Partner

2017-12-16

Source: Permutation Promenade

Part 1: Running on the string a...p apply a series of the following commands:

sX rotates the string right by X positions
xX/Y swaps positions X and Y
pA/B swaps the letters A and B no matter their positions

AoC 2017 Day 15: Two Generators

2017-12-15

Source: Dueling Generators

Part 1: Create a pair of generators A and B where:

A_n = 16807 A_{n-1} \mod 2147483647
B_n = 48271 B_{n-1} \mod 2147483647

How many of the first 40 million values have matching values for the low 16 bits of each generator?

AoC 2017 Day 14: Knot Hash Gridinator

2017-12-14

Source: Disk Defragmentation

Part 1: Create a 128x128 grid. Generate each row by taking the knot hash of salt-{index}. The bits of the hash represent if a tile in the grid is free (0) or used (1).

Given your salt as input, how many squares are used?

AoC 2017 Day 13: Firewall Puncher

2017-12-13

Source: Packet Scanners

Part 1: Multiple layers are defined with rules of the form:

{index}: {depth}

Each layer will start at position 0, then once per tick will advance towards depth. Once it hits depth-1, it will return to position 0, taking 2*depth-1 per full cycle.

Calculate the sum of index * depth for any scanners that are at position 0 when you pass through them given an initial starting time.

AoC 2017 Day 12: Gridlock

2017-12-12

Source: Digital Plumber

Part 1: A network of nodes is defined by a list of lines formatted as such:

2 <-> 0, 3, 4


> In this case, node `2` is connected to `0`, `3`, and `4` and vice versa.

> How many nodes are in the group that contains the node `0`?





First, load the data into an [[wiki:adjacency map]]():

```python
nodes = set()
neighbors = collections.defaultdict(set)

for line in lib.input():
    source, destinations = line.split('<->')
    source = int(source.strip())
    nodes.add(source)

    for destination in destinations.strip().split(','):
        destination = int(destination.strip())
        nodes.add(destination)

        neighbors[source].add(destination)
        neighbors[destination].add(source)

Then, write a function that can take a node and recursively expand until it finds all nodes in the same group:

AoC 2017 Day 11: It's Full Of Hexagons

2017-12-11

Source: Hex Ed¹

Part 1: Work on a hex grid:

\ n / nw +–+ ne /
-+ +- \ / sw +–+ se / s \


> Given a series of steps (`n`, `se`, `ne`) etc, how many steps away from the origin do you end up?





This problem mostly comes down to representation. [This post from Red Blob games](https://www.redblobgames.com/grids/hexagons/) has the best write up of how to use hex coordinate systems I've ever seen. Since it handles distances better, I'm going to use a cube coordinate system, where each hex actually has an `x`, `y`, and `z` coordinate. Now that is decided, we can write up a map to translate directions into offsets, a way to add points together, and a distance function:

```python
neighbors = {
    'n' : (0, 1, -1),
    'ne': (1, 0, -1),
    'se': (1, -1, 0),
    's' : (0, -1, 1),
    'sw': (-1, 0, 1),
    'nw': (-1, 1, 0),
}

def add(p1, p2):
    x1, y1, z1 = p1
    x2, y2, z2 = p2
    return (x1 + x2, y1 + y2, z1 + z2)

def move(p, d):
    return add(p, neighbors[d.strip()])

def distance(p1, p2):
    x1, y1, z1 = p1
    x2, y2, z2 = p2
    return max(abs(x1 - x2), abs(y1 - y2), abs(z1 - z2))

That makes code for the actual question nice and clean:

AoC 2017 Day 10: Knot Cool

2017-12-10

Source: Knot Hash

Part 1: Starting with a list of the numbers from 1 to n and a list of lengths (as input):

Initialize current_position and skip_size to 0
For each length element in the lengths list:
Reverse the first length elements of the list (starting at current_position)
Move forward by length plus skip_size
Increment skip_size by 1

After applying the above algorithm, what is the product of the first two elements in the list (from the original first position, not the current_position)?

AoC 2017 Day 9: Garbage Gobbler

2017-12-09

Source: Stream Processing

Part 1: An input stream can contain:

groups are delimited by { and }, groups are nestable and may contain garbage or data (objects within a group are comma delimited)
garbage is delimited by < and >, groups cannot be nested within garbage, a ! within garbage is an escape character: !> does not end a garbage segment