The Halting Problem
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-07-14 18:14:57

## [Advent of Code 2017 Day 25](https://adventofcode.com/2017/day/25)

## Part 1
1. Recognizing the task
2. Understanding the language of the puzzle
3. Analyzing the example input
4. Forming a hypothesis based on the example running
5. Skip intro
6. Writing an algorithm that works on the example input
7. 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:
1. What value to write at the current position of the cursor
2. Whether to move the cursor left or right one slot
3. 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!