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
number = File.read("3.txt").to_i
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.
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[0] + movement[0], position[1] + movement[1]]
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
input_number = File.read("3.txt").to_i
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.