# Advent of Code (Day 3)

< 3 Dec 2017>

I worked on Advent of Code Day 3 and it took so much longer compared to the other challenges. I probably wouldn’t have even tried to finish if it wasn’t for my friend Branko who challenged me. Dude, kicked my butt… I’ll get him next time.

# First Challenge

I’m assuming you’re familiar with the challenge so I won’t go into detail of the specs here. Generally, imagine you are on an infinite checker board (grid) and you are standing on a square. You proceed to walk around your starting square in a spiral fashion and measure your Manhattan distance from your current position to the starting point in each move. The challenge required you to return this measurement at some large value.

I found a pattern in how many steps it took to get from a squared number of steps to the starting point.

number of steps | side path length | total distance to start |
---|---|---|

4 | 2 | (-1)**(2) * x |

(-1)**(2) * y * (1) | ||

(-1)**(2 - 1) * x (1) | ||

9 | 3 | (-1)**(3) * x |

(-1)**(3) * y * (2) | ||

(-1)**(3 - 1) * x (2) | ||

16 | 4 | (-1)**(4) * x |

(-1)**(4) * y * (3) | ||

(-1)**(4 - 1) * x (3) | ||

(n + 1)**2 | n | (-1)**(n) * x |

(-1)**(n) * y * (n - 1) | ||

(-1)**(n - 1) * x * (n - 1) |

Sum to square 1 at square n can be calculated through finding the distance at the nearest square number of steps and counting up the remaining steps from this point.

```
require 'matrix'
x = Vector[1, 0]
y = Vector[0, 1]
sum = Vector[0, 0]
(2..601).each do |n|
sum += (-1)**(n) * x
sum += (-1)**(n) * y * n
sum += (-1)**(n - 1) * x * n
end
puts sum
```

## My value was 361527

```
361527 is 601**2 + 326 more steps
sum at n == 601 is Vector[300, -300]
326 more steps
(-1)**(602) * x # one step
(-1)**(602) * y * (325) # 325 steps
Vector[300 + 1, -300 + 325]
[301, 25] and Mahattan
distance would be 301 + 25 = 326
326 total steps to square 1
```

# Second Challenge

For this challenge, there were values on each square that were the sum of the surrounding squares’ values. This part had me really look into the specs and try to understand what was happening. The pattern I found above didn’t make sense so I gave it another looksee and found the following pattern.

step | change in distance |
---|---|

1 | +x step right |

2 | +y step up |

3 | -x step back |

4 | -x step back |

5 | -y step down |

6 | -y step down |

7 | +x right |

8 | +x right |

9 | +x right |

10 | +y up |

11 | +y up |

12 | +y up |

In each layer of steps around the grid, the length of a side increased by 1 and there would be an equal number of x’s and y’s. Also the sign would flip from positive to negative as you walked up the right and up, to the back and down.

I imagined each step being a movement in the x or y direction. I would populate
an array `@@grid_steps`

for each layer and `shift`

a step off each move to
‘walk’ through the grid. When the array was empty, the number of x’s and y’s
would both increase by 1, flip sign, and I continue to shift off a step for each
move through the grid.

Also, I used a hash to store the values for each place on the grid. I’m not
sure if `Vector`

’s make good keys so I just used an array of the `Vextor`

’s x
and y position.

```
require 'matrix'
class Grid
@@grid_width = 0
@@current_place = Vector[0, 0]
@@grid_values = Hash.new(0)
@@grid_values[[0, 0]] = 1
@@grid_steps = []
def self.set_current_value
@@current_place += next_step
# I didn't need an arg but don't care to refactor atm
value = get_grid_values_around(@@current_place)
@@grid_values[
[@@current_place[0], @@current_place[1]]
] = value
end
def self.next_step
if @@grid_steps.size == 0
@@grid_width += 1
set_grid_steps_at_width
@@grid_steps.shift
else
@@grid_steps.shift
end
end
def self.set_grid_steps_at_width
x = Vector[1, 0]
y = Vector[0, 1]
x_step = (-1)**(@@grid_width + 1) * x
y_step = (-1)**(@@grid_width + 1) * y
@@grid_width.times { @@grid_steps << x_step }
@@grid_width.times { @@grid_steps << y_step }
end
def self.get_grid_values_around(current_step)
x = current_step[0]
y = current_step[1]
@@grid_values[[x + 1, y + 1]] +
@@grid_values[[x + 1, y]] +
@@grid_values[[x + 1, y - 1]] +
@@grid_values[[x, y + 1]] +
@@grid_values[[x, y - 1]] +
@@grid_values[[x - 1, y + 1]] +
@@grid_values[[x - 1, y]] +
@@grid_values[[x - 1, y - 1]]
end
end
n = 0
while (n < 361527)
n = Grid.set_current_value
end
puts n
```

Anyway, if the next challenges get much harder, I’m not sure I’ll have enough time to complete them. I’d be happy to just give it a shot. If I do, you’ll see my solution right on this blog.