require_relative 'util'
# --- Day 3: Spiral Memory ---
#
# You come across an experimental new kind of memory stored on an
# infinite two-dimensional grid.
#
# Each square on the grid is allocated in a spiral pattern starting at
# a location marked 1 and then counting up while spiraling
# outward. For example, the first few squares are allocated like this:
#
# 17 16 15 14 13
# 18 5 4 3 12
# 19 6 1 2 11
# 20 7 8 9 10
# 21 22 23---> ...
#
# While this is very space-efficient (no squares are skipped),
# requested data must be carried back to square 1 (the location of the
# only access port for this memory system) by programs that can only
# move up, down, left, or right. They always take the shortest path:
# the Manhattan Distance between the location of the data and square
# 1.
#
# For example:
#
# - Data from square 1 is carried 0 steps, since it's at the access
# port.
# - Data from square 12 is carried 3 steps, such as: down, left, left.
# - Data from square 23 is carried only 2 steps: up twice.
# - Data from square 1024 must be carried 31 steps.
#
# How many steps are required to carry the data from the square
# identified in your puzzle input all the way to the access port?
#
# Your puzzle input is 312051.
input = 312_051
def spiral_iterator
Enumerator.new do |y|
directions = [:east, :north, :west, :south].cycle
steps = 1
loop do
direction = directions.next
steps.times { y << direction }
direction = directions.next
steps.times { y << direction }
steps += 1
end
end
end
class Swiper
def initialize
@i = 1
@x = 0
@y = 0
end
def walk(direction)
case direction
when :east then @x += 1
when :north then @y += 1
when :west then @x -= 1
when :south then @y -= 1
end
@i += 1
end
def spiral(n)
iter = spiral_iterator
walk(iter.next) while @i != n
[@x, @y]
end
end
def easy(n)
swiper = Swiper.new
x, y = swiper.spiral(n)
x.abs + y.abs
end
assert(easy(1) == 0)
assert(easy(12) == 3)
assert(easy(23) == 2)
assert(easy(1024) == 31)
puts "easy(input): #{easy(input)}"
# --- Part Two ---
# As a stress test on the system, the programs here clear the grid and
# then store the value 1 in square 1. Then, in the same allocation
# order as shown above, they store the sum of the values in all
# adjacent squares, including diagonals.
# So, the first few squares' values are chosen as follows:
# - Square 1 starts with the value 1.
# - Square 2 has only one adjacent filled square (with value 1), so it
# also stores 1.
# - Square 3 has both of the above squares as neighbors and stores the
# sum of their values, 2.
# - Square 4 has all three of the aforementioned squares as neighbors
# and stores the sum of their values, 4.
# - Square 5 only has the first and fourth squares as neighbors, so it
# gets the value 5.
# Once a square is written, its value does not change. Therefore, the
# first few squares would receive the following values:
# 147 142 133 122 59
# 304 5 4 2 57
# 330 10 1 1 54
# 351 11 23 25 26
# 362 747 806---> ...
# What is the first value written that is larger than your puzzle
# input?
# Your puzzle input is still 312051.
class StressTestSwiper < Swiper
def initialize
super
@seen = Hash.new { |h, k| h[k] = 0 }
@seen[[0, 0]] = 1
end
def neighbor_sum
@seen[[@x - 1, @y - 1]] + @seen[[@x, @y - 1]] + @seen[[@x + 1, @y - 1]] +
@seen[[@x - 1, @y]] + @seen[[@x + 1, @y]] +
@seen[[@x - 1, @y + 1]] + @seen[[@x, @y + 1]] + @seen[[@x + 1, @y + 1]]
end
def walk(direction)
super
@seen[[@x, @y]] = neighbor_sum
end
def spiral(n)
iter = spiral_iterator
walk(iter.next) until @seen[[@x, @y]] > n
@seen[[@x, @y]]
end
end
def hard(n)
swiper = StressTestSwiper.new
swiper.spiral(n)
end
assert(hard(1) == 2)
assert(hard(5) == 10)
assert(hard(23) == 25)
assert(hard(23) == 25)
assert(hard(150) == 304)
assert(hard(750) == 806)
puts "hard(input): #{hard(input)}"