# Advent of Code 2017, Day 3: Spiral Memory

## Part A

On Day 3 we are working with spiral memory. We have the following memory blocks that are laid out in a spiral:

``````17  16  15  14  13
18   5   4   3  12
19   6   1   2  11
20   7   8   9  10
21  22  23---> ...
``````

Whenever you want to fetch data from any block you need to access it via block number 1. This means you need to first move data from selected block to the block number 1. The goal of this task is to calculate the distance between given block number and block number 1.

If you look at the diagram you can see it is like onion rings. Block number 1 is surrounded by the first ring of 8 blocks. Then this ring is surrounded by another ring of 16 blocks and so on. So each next ring has 8 more memory blocks.

Now if you have just the most inner block, the size of the whole spiral is 1. If you have one additional ring the size will be 1 + 8 blocks. Add next ring and size will be 1 + 8 + 16 blocks. And so on. The size follows arithmetic series sum plus one additional element in the center.

We can implement this small method to return number of blocks given number of outer rings:

``````def sum(rings)
8 * rings * (rings + 1) / 2 + 1
end
``````

We can also reverse this method and find how many outer rings there are given the sum. For that we need to solve qudratic equation that we have above. Here is the method:

``````def solve(sum)
((Math.sqrt(sum) - 1) / 2).ceil
end
``````

And now the full solution:

``````def sum(rings)
8 * rings * (rings + 1) / 2 + 1
end

def rings(sum)
((Math.sqrt(sum) - 1) / 2).ceil
end

rings = rings(number)
start = sum(rings - 1) + 1
stop = sum(rings)
q = rings * 2
p = (number - start) % q
m = q / 2 - 1

puts (m - p).abs + rings
``````

So we read our input number and calculate on which outer rings it is placed. Then we calculate the first and last number on this ring. Our input number should be somewhere in between. We need to find out on which side and how far from the center axis.

Variable `q` holds the size of each side and `p` is the position on given side. Sides are numbered like on the diagram below:

`````` 2   2   2   2  1
3   2   2   1  1
3   3   x   1  1
3   3   4   4  1
3   4   4   4  4
``````

You can see that size of one side of the ring is just a ring number multiplied by 2. The first ring has 8 blocks in total and each side has 2 blocks. Second ring has 16 blocks and each side has 4 blocks.

So calculating `number - start` gives us the index of input number on the ring. For example, for number 23 the index will be 13. Now if you do modulo, `(number - start) % q` it will be the index of the input number on the specific side.

`m = q / 2 - 1` calculates the index of middle element on each side. It will be the same index on all sides for a given ring. Number 23 lies on second ring. Size of each side of second ring is 4 and middle element has index 1.

Finally we need to calculate the difference between index of our input number and index of middle element.

## Part B

In the second part we need to travel along this spiral starting from block number one and in each block we need to write a sum of all previous neighboring blocks. Here is how it can look:

``````147  142  133  122   59
304    5    4    2   57
330   10    1    1   54
351   11   23   25   26
362  747  806--->   ...
``````

The goal of this task is write the first value larger than our input number.

For the second part I didn’t have enough motivation to look for nice pattern and I just did the simulation of following the spiral and filling out the values. Here is the solution:

``````def move(position, movement)
[position + movement, position + movement]
end

def traverse_spiral
level = 1
position = [0, 0]
number = 2
size = 2

while true do
position = move(position, [1, 0])
yield [number, position]
number += 1
(size - 1).times do
position = move(position, [0, 1])
yield [number, position]
number += 1
end

position = move(position, [-1, 0])
yield [number, position]
number += 1
(size - 1).times do
position = move(position, [-1, 0])
yield [number, position]
number += 1
end

position = move(position, [0, -1])
yield [number, position]
number += 1
(size - 1).times do
position = move(position, [0, -1])
yield [number, position]
number += 1
end

position = move(position, [1, 0])
yield [number, position]
number += 1
(size - 1).times do
position = move(position, [1, 0])
yield [number, position]
number += 1
end

size += 2
end
end

index = 0
values = {
[0, 0] => 1
}
traverse_spiral do |number, (x, y)|
neighbors = [[x - 1, y], [x + 1, y], [x - 1, y - 1], [x, y - 1], [x + 1, y - 1], [x - 1, y + 1], [x, y + 1], [x + 1, y + 1]]

val = neighbors.map do |n|
values[n] || 0
end.sum

values[[x, y]] = val

if val > input_number
puts val
break
end
end
``````

So `traverse_spiral` starts infinite loop that travels along the spiral. We start with position `[0, 0]`, we make are moves on one side then turn and so on. After moving to the next block we yield the current number and position.

In `values` hash we maintain the values for already visited position. The main code is looping through next visited blocks, summing neighbors and writing new values.

When it reach number larger than our input, it prints it out.