Spiral Memory
Tags: adventofcode, algorithms, programming, computerscience
Published: 2022-08-08 15:58:04

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

## Part 1
1. Spiraling out of - then into? - control!
2. Studying the DNA of this spiral and solving the puzzle

### Spiraling out of - then into? - control!
- I don't recall any prior spiral-related puzzles
- This seems like a fun pattern-identification puzzle
- Although, I need to see a much larger slice of the spiral to start analyzing how it grows

### Studying the DNA of this spiral and solving the puzzle
This animation shows my analysis and discovery of the answer happening in real-time:
![Solving Part 1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bnwckaadaocatk7ou34i.gif)

This was a manual process with a scavenger hunting algorithm:
```
Start with num as 1 and n as 0
Trying offsets between 1 and 8
Do as long as num is less than or equal to my puzzle input
  Increment num by the sum of offset and (the product of 8 and n)
  Increment n by 1
  Print the current states of num and n
```

- An `offset` of `7` got me closest to - and slightly greater than - my puzzle input
- Thankfully, this offset corresponded to a number in the spiral directly below `1`
- From there, I subtracted enough from that number to arrive at my puzzle input
- That number was the amount of steps left
- So, the sum of the amount of steps down - `n` in my algorithm - and the amount of steps left was my answer!

## Part 2
1. Yikes, I may have to build a spiral
2. Solving Part 1 again, but algorithmically
3. Solving Part 2 with a slightly more complex algorithm

### Yikes, I may have to build a spiral
- Solving this part manually will require a lot of careful arithmetic
- No, thanks
- I'd rather challenge myself to build the spiral from Part 1, hoping that - if I can - it will lend itself to solving Part 2

### Solving Part 1 again, but algorithmically
When re-analyzing the spiral:
- The number of times moving right, up, left, down increased in a repeatable pattern: each amount increments by 2
- I could build a dictionary where the keys are the incrementing numbers, and the values are the coordinates in the spiral
- Then go as many cycles as it took to fill the dictionary with the key I needed to know: my puzzle input
- Lastly, return the sum of the absolute values of the coordinates related to my desired key

This is how my algorithm works:
![Solving Part 1 algorithmically](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/95ob4ehvryjnz3yd3l3q.gif)

### Solving Part 2 with a slightly more complex algorithm
- In the setup, I create a variable, `match` that starts empty
- The added complexity comes from checking the eight adjacent cells each time a new cell in the spiral is added

I iterate through each adjacent cell coordinate:
```
If there is an adjacent cell, update its coordinate with that value
If there is no adjacent cell, update its coordinate with 0
```

Then, the condition:
```
If, after determining the value to populate a cell, it is greater than my puzzle input AND my match variable is empty
  Update match to the value of the cell
```

My algorithm goes a little over...but not by any significant amount.

The more important thing is it stores one and only `match`: the correct answer!

## I did it!!
- I solved both parts!
- I solved Part 1 twice: one naive way, and another algorithmic way!
- I made a couple GIFs that animate my analysis and algorithmic thinking in real-time!
- I surpassed my personal best star score! I now have `42` stars...with two opportunities left to increase that to 46!

This spiral puzzle was a wonderful, thought-provoking puzzle that had me mystified at first...digging for patterns.

I'll admit, I wasn't expecting something this difficult for me in the earliest five days.

On to my penultimate puzzle of 2017!