As I did with last year / yesterday, I’ve written up a series of posts for the Advent of Code 2017 problems. Again, I didn’t manage to write them up as I did them, but this time around I least I finished mostly on time.

read more...

Source: The Halting Problem

Part 1: Implement a Turing machine defined as such:

Begin in state A. Perform a diagnostic checksum after 6 steps.

In state A: If the current value is 0: - Write the value 1. - Move one slot to the right. - Continue with state B. If the current value is 1: - Write the value 0. - Move one slot to the left. - Continue with state B.

…

> What is the final number of `1s` on the tape?





Most of this problem actually came down to reading the input:

```python
# Map of (current state, current value, key) -> value
# key is one of value, offset, state
transitions = {}
breakpoint = 0
state = None
pointer = 0
one_bits = set()

for line in lib.input():
    line = line.strip('- ')
    arg = line.split()[-1][:-1]

    if arg == 'steps':
        arg = line.split()[-2]

    try:
        arg = int(arg)
    except:
        pass

    # Store values based on that argument
    if line.startswith('Begin'):
        state = arg
    elif line.startswith('Perform'):
        breakpoint = arg
    elif line.startswith('In'):
        current_state = arg
    elif line.startswith('If'):
        current_value = arg
    elif line.startswith('Write'):
        transitions[current_state, current_value, 'value'] = arg == 1
    elif line.startswith('Move'):
        transitions[current_state, current_value, 'offset'] = 1 if arg == 'right' else -1
    elif line.startswith('Continue'):
        transitions[current_state, current_value, 'state'] = arg

As we did in part 1 of day 22, we’ll use a set to store the current state (store 1, if an index is not in the set, it’s 0). That gives us the ability to grow unbounded (so long as we have enough RAM).

read more...

Source: Electromagnetic Moat

Part 1: Given a series of reversible components of the form 3/4 (can connect a 3 on one end to a 4 on the other), form a bridge of components. The bridge’s strength is equal to the sum of component values. So 0/3, 3/7, and 7/4 has a strength of 0+3 + 3+7 + 7+4 = 24.

What is the strongest possible bridge?

read more...

Source: Coprocessor Conflagration

Part 1: Create a variation of the previous DuetVM with only the following four instructions:

• set X Y sets register X to Y
• sub X Y set register X to X - Y
• mul X Y sets register X to X * Y
• jnz X Y jumps with an offset of the value of Y, iff X is not equal to zero

If you run the given program, how many times is mul invoked?

read more...

Source: Sporifica Virus

Part 1: Implement a cellular automaton on an infinite grid of . and # pixels such that:

1. Start at (0, 0), facing Up
2. Repeat:

• If the cursor is on . swap it to # and turn Left
• If the cursor is on # swap it to . and turn Right
• Either way, after turning, move forward once

After 10,000 iterations, how many pixels were turned from . to #?

read more...

Source: Fractal Art

Part 1: Start with an input image made of . and # pixels. For n iterations, break the image into blocks:

• If the current size is even, break the image into 2x2 chunks and replace each with a 3x3 chunk
• If the current size is odd, break the image into 3x3 chunks and replace each with a 4x4 chunk

The replacement rules will be specified in the following format (example is a 3x3 -> 4x4 rule):

.#./..#/### => #..#/..../..../#..#  

In that example, replace this:

.#.
..#
###

With this:

#..#
....
....
#..#

Any rotation or reflection of a chunk can be used to match the input of a replacement rule.

After n = 18 iterations, how many # pixels are there?

read more...

Source: Particle Swarm

Part 1: Given the initial position, velocity, and acceleration of a large number of particles, which particle will stay the closet to the origin as the simulation runs to infinity?

read more...

Source: A Series of Tubes

Part 1: Take a network diagram of the following form:

|          
|  +--+    
A  |  C    

F—|–|-E—+ | | | D +B-+ +–+

> Starting at the single node at the top and following the lines, what order would the nodes be visited in?





First, load the entire network:

```python
data = {}
points = {}
entry = None

def is_point(c):
    return re.match('[A-Z]', c)

for y, line in enumerate(lib.input()):
    for x, c in enumerate(line):
        if c.strip():
            data[x, y] = c

        if is_point(c):
            points[c] = (x, y)

        if y == 0 and c == '|':
            entry = (x, y)

Then, calculate the path:

read more...

Source: Duet

Part 1: Create a virtual machine with the following instruction set:

• snd X plays a sound with a frequency equal to the value of X
• set X Y sets register X to Y
• add X Y set register X to X + Y
• mul X Y sets register X to X * Y
• mod X Y sets register X to X mod Y
• rcv X recovers the frequency of the last sound played, if X is not zero
• jgz X Y jumps with an offset of the value of Y, iff X is greater than zero

In most cases, X and Y can be either an integer value or a register.

What is the value recovered by rcv the first time X is non-zero?

read more...

Source: Spinlock¹

Part 1: Start with a circular buffer containing [0] and current_position = 0. For n from 1 up to 2017:

1. Step forward steps (puzzle input)
2. Input the next value for n, set current_position to n, increment n
3. Repeat

What is the value after 2017?

It’s a bit weird to describe, but the given example helps (assume steps = 3):

(0)
0 (1)
0 (2) 1
0  2 (3) 1
0  2 (4) 3  1
0 (5) 2  4  3  1
0  5  2  4  3 (6) 1
0  5 (7) 2  4  3  6  1
0  5  7  2  4  3 (8) 6  1
0 (9) 5  7  2  4  3  8  6  1

read more...