## Advent of Code 2017 Day 25

## Part 1

- Recognizing the task
- Understanding the language of the puzzle
- Analyzing the example input
- Forming a hypothesis based on the example running
- Skip intro
- Writing an algorithm that works on the example input
- Refactoring my algorithm to work on my puzzle input

### Recognizing the task

Abstractly, my task is:

Recreate the Turing machine and save the computer!

Algorithmically, my task is:

####
Solve for `X`

such that `X`

equals...

The diagnostic checksum a.k.a. the number of times 1 appears on the tape once the specified number of steps have been executed

### Understanding the language of the puzzle

- To solve the puzzle, I must
`create a whole new Turing machine from scratch`

- My input is a Turing machine blueprint
- A Turing machine has three parts:
`tape`

,`cursor`

and`states`

The `tape`

is simply depicted as:

```
... 0 0 0 0 0 0 ...
```

- It is an infinite list
- Each slot on the tape has two possible values: 0 (the starting value for all slots) and 1

The `cursor`

is an exact location in the `tape`

, represented by square brackets in the instructions:

```
... 0 0 0 [0] 0 0 ...
```

The `states`

are sets of rules, each containing three instructions.

Based on whether the cursor is pointing at a 0 or a 1, the current state says:

- What value to write at the current position of the cursor
- Whether to move the cursor left or right one slot
- And which state to use next

#### My impressions thus far

- An infinite list? That could be troublesome.
- Only modifying values, not deleting or creating? That could nullify performance concerns.
- Several states with conditions and instructions? Sounds like a list of functions...similar to the Intcode Computer I made throughout 2019.

### Analyzing the example input

The following blueprint is offered as example:

```
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.
In state B:
If the current value is 0:
- Write the value 1.
- Move one slot to the left.
- Continue with state A.
If the current value is 1:
- Write the value 1.
- Move one slot to the right.
- Continue with state A.
```

It specifies:

- Which state to use first
- The number of iterations to perform before counting all the
`1`

s - The quantity, names and rules for each state

As expected, each state consists of:

- Two conditions, based on the current value of the number at the location of the
`cursor`

in the`tape`

- For each condition, three instructions related to: 1) updating the value, 2) moving the cursor, 3) selecting the state to reference in the next iteration

### Forming a hypothesis based on the example running

The instructions depict a running of the example blueprint:

```
... 0 0 0 [0] 0 0 ...
... 0 0 0 1 [0] 0 ...
... 0 0 0 [1] 1 0 ...
... 0 0 [0] 0 1 0 ...
... 0 [0] 1 0 1 0 ...
... 0 1 [1] 0 1 0 ...
... 0 1 1 [0] 1 0 ...
```

My observations:

- The input specified 6 steps
- The illustration depicts the same amount of slots
- Due to the cursor moving left and right, it only ever moves to four of the six slots (2/3)

Conclusion:

A predefined array filled with 0s likely does not need a length equal to the number of specified steps

- I hope this is true, because my puzzle input specifies several million steps
- I therefore intend to create an array that is of a size half the specified steps...at least to start
- I'll rely on errors to determine whether I must increase the size of the array

### Skip intro

I'm not going to attempt to programmatically parse the puzzle input

- I'm less interested in converting text into rules
- I'm more interested in writing the states as functions and modifying an array

### Writing an algorithm that works on the example input

```
Create an array with a length equal to the number of steps to perform, where each value is 0
Set cursor to the location that is either in the middle or the location to the right of what would be the middle element
Set state to the first function - stored as 0 to reference the first element in the array of states
Create a list of states, filled with functions that follow this structure:
Store the value of the item in tape at the cursor
If the value is 0
Update the value to 0 or 1
Decrement or increment the value stored in cursor
Update state to the appropriate location in states
For i from 0 to the number of steps
Invoke the function stored at the location in states equal to the current value of state
Return the number of 1s remaining in tape
```

My algorithm generates `3`

, as desired.

### Refactoring my algorithm to work on my puzzle input

Now for the moment of truth:

- Will it finish in a reasonable amount of time for the amount of steps specified by my puzzle input?

Time to refactor!

...

- Refactored!
- Run!
- Finished in a second!
- Correct answer!

My algorithm only took a second to finish, even when the tape's length was equal to the amount of steps to process!

And when I adjust the array length to fractions of the fullest possible size, the algorithm only marginally gains performance...but it still works!

## Part 2

Since this is Day 25, Part 2 only unlocks when I collect 49 stars. Which I never anticipate achieving. That's ok, though.

## I did it!!

- I solved Part 1!
- I have solved 4/5 Day 25 Part 1s!

## Top comments (0)