states = {
    "left" => "down",
    "down" => "right",
    "right" => "up",
    "up" => "left"
}
stepsx = {
    "right" => 1,
    "left" => -1
}
stepsy = {
    "up" => 1,
    "down" => -1
}
increases = {
    "left" => 1,
    "right" => 1
}
stepsx.default = 0
stepsy.default = 0
increases.default = 0

memory = Array.new(399)
399.times do |time| 
    memory[time] = Array.new(399, 0)
end

step = 1
x = 199
y = 199
memory[x][y] = 1
x += 1
state = "up"
memory[x][y] = 1

input = 289326

while(true) do
    dx = stepsx[state]
    dy = stepsy[state]
    step.times do |time|
        x += dx
        y += dy
        total = 0
        for i in -1..1 do
            for j in -1..1 do
                if(!(j == 0 && i == 0)) then total += memory[x + i][y + j] end
            end
        end
        puts total
        if(total > input) then exit() end
        memory[x][y] = total
    end
    state = states[state]
    step += increases[state]
end