Shifting an array one postion to the left -- Non Function Vs Function

[Taylor_1989]

TL;DR

I seem to be getting mixed result for my for loop and function, but cant seem to understand why.

I am currently doing some task on a website called Codility (link and bottom of post). The task basically ask for me to create an algorithm to shift an array to the left K times (Full details below). Which seem to work for a non function but I still seem to be shifting it wrong as the output is incorrect when compared to the given answer. Also I put the same code in the function and get a completely different result, but really unsure why.

My code can be show below question.

Can anyone give adivce to where I have gone wrong. Thank's in advance.

Codiility Question:

An array A consisting of N integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is moved to the first place. For example, the rotation of array A = [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7] (elements are shifted right by one index and 6 is moved to the first place).
The goal is to rotate array A K times; that is, each element of A will be shifted to the right K times.
Write a function:

def solution(A, K)

that, given an array A consisting of N integers and an integer K, returns the array A rotated K times.
For example, given
A = [3, 8, 9, 7, 6] K = 3
the function should return [9, 7, 6, 3, 8]. Three rotations were made:
[3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7] [6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9] [7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]
For another example, given
A = [0, 0, 0] K = 1
the function should return [0, 0, 0]
Given
A = [1, 2, 3, 4] K = 4
the function should return [1, 2, 3, 4]
Assume that:

• N and K are integers within the range [0..100];
• each element of array A is an integer within the range [−1,000..1,000].

In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

[CODE lang="python" title="Comparsion between non function and function"]K = int(input('Please enter the number of rotation you wish to do on the given array : '))
for x in range(0, K):
temp = A[0] # Storing the intial element in the array
for y in range(0, len(A)-1):
A[y] = A[y+1] # Shifting each element within in the array to the left
# print(A[y])
A[len(A)-1] = temp # Subbing back in the intial element within the array to the end of the new array
print('===================================')
print('Result of Array shift by K = {}'.format(K))
print('===================================')
print()
print('Solution from for loop')
print(A)
print()
def solution(A, K):
K = int(input('Please enter the number of rotation you wish to do on the given array for function: '))
for x in range(0, K):
temp = A[0]
for y in range(0, len(A)-1):
A[y] = A[y+1]
A[len(A)-1] = temp
return(A)
pass

solution(A,4)
print()
print('Solution from function ')
print(A)[/CODE]

I have tested both codes simultaneously for the three given test arrays given in the question and the out put for both non zero arrays are as follows.

[CODE title="Output"]Oringal Array : [3, 8, 9, 7, 6]

Please enter the number of rotation you wish to do on the given array : 3
===================================
Result of Array shift by K = 3
===================================

Solution from for loop
[7, 6, 3, 8, 9]

Please enter the number of rotation you wish to do on the given array for function: 3

Solution from function
[8, 9, 9, 9, 3][/CODE]

[CODE title="Output"]Oringal Array : [1, 2, 3, 4]

Please enter the number of rotation you wish to do on the given array : 4
===================================
Result of Array shift by K = 4
===================================

Solution from for loop
[1, 2, 3, 4]

Please enter the number of rotation you wish to do on the given array for function: 4

Solution from function
[4, 4, 4, 4]

Process finished with exit code 0[/CODE]

 

[jedishrfu]

In shifting elements you have to remember the variable swap problem commonly used as an interview question in the early days of programming.

Namely:

A=1 and B=2 and you want to swap them so that A=2 and B=1

The simple (wrong) solution is:

A=B --> so that A now has B's value and then B=A so that B now has A's value.
A=2 --> so that A now has a 2 value and then B=2 so that B now has a 2 value

and now you ask what happened to the ONE.

The correct solution is to use a temporary variable to hold A's value before you change it:

T=A  --> save A's value in T (T=1)
A=B  --> move B's value to A (A=2)
B=T  --> move A's value saved in T to B (B=1)

Does that help?

EDIT: changed language because Python has a built-in swapping feature (thanks @Arman777 for pointing that out) that hides the temp variable and can prevent someone trying to understanding the true nature of the problem especially in languages without that feature.

 

[wle]

The indentation in line 24 is wrong. So the line 'A[len(A)-1] = temp' is outside the 'for x ...' loop in the function version unlike the not-function version.

 

[Arman777]

The indentation in line 24 is wrong. So the line 'A[len(A)-1] = temp' is outside the 'for x ...' loop in the function version unlike the not-function version.

I was just going to write that yes. Also you don't have to call K when you are writing the function since you are declaring K inside the function. So you can write,

def solution(A):
    K = int(input('Please enter the number of rotation you wish to do on the given array for function: '))
    for x in range(0, K):
        temp = A[0]
        for y in range(0, len(A)-1):
            A[y] = A[y+1]
        A[len(A)-1] = temp
    return A

print(solution([3, 8, 9, 7, 6]))

or

def solution(A,K):
    for x in range(0, K):
        temp = A[0]
        for y in range(0, len(A)-1):
            A[y] = A[y+1]
        A[len(A)-1] = temp
    return A

K = int(input('Please enter the number of rotation you wish to do on the given array for function: '))
print(solution([1,2,3,4], 4))

I also did not understand why you used "pass" after "return" ?

 

[Ibix]

Why use a loop at all? Is there some reason you can't do this with a couple of array slices? Edit: that makes the problem a one-liner in python.

 

[Arman777]

The correct solution is to use a temporary variable to hold A's value before you change it:

there's more simple way,

A = 2
B = 5
A, B = B, A
print(A)
print(B)

so in one line

A, B = B, A

we can do the "swapping" without using any temporary variable

 

[jedishrfu]

While that's true I used Python syntax not the features of the language to describe the actual issue.

I'll go back and change it to C code then.

 

[Arman777]

While that's true I used Python syntax not the features of the language to describe the actual issue.

I'll go back and change it to C code then.

Well yes, I just wanted to point it out for the OP if he was not aware of it

 

[Taylor_1989]

In shifting elements you have to remember the variable swap problem commonly used as an interview question in the early days of programming.

Namely:

A=1 and B=2 and you want to swap them so that A=2 and B=1

The simple (wrong) solution is:

A=B --> so that A now has B's value and then B=A so that B now has A's value.
A=2 --> so that A now has a 2 value and then B=2 so that B now has a 2 value

and now you ask what happened to the ONE.

The correct solution is to use a temporary variable to hold A's value before you change it:

T=A  --> save A's value in T (T=1)
A=B  --> move B's value to A (A=2)
B=T  --> move A's value saved in T to B (B=1)

Does that help?

EDIT: changed language because Python has a built-in swapping feature (thanks @Arman777 for pointing that out) that hides the temp variable and can prevent someone trying to understanding the true nature of the problem especially in languages without that feature.

Sorry I am a bit confused, because my temp variable is in the top for loop where I am storing the first value of the array then replaced it and added on to the end of the final array.

 

[jedishrfu]

Okay so you did this:

T=A[0]
A[0]=A[1]   // notice the pattern T<0 , 0<1 , 1<2 , 2<3 ... n<T
A[1]=A[2]
...
A[n]=T

that should work to shift to the left but not to the right:

T=A[n]
A[n]=A[n-1]  // notice the pattern T<n , n-0<n-1 , n-1<n-2 , n-2<n-3 ... 0<T
...
A[0]=T

There are other schemes as well, you just have be sure you don't stomp on a value and lose it.

 

[jedishrfu]

[CODE lang=python highlight="24"]K = int(input('Please enter the number of rotation you wish to do on the given array : '))
for x in range(0, K):
temp = A[0] # Storing the intial element in the array
for y in range(0, len(A)-1):
A[y] = A[y+1] # Shifting each element within in the array to the left
# print(A[y])
A[len(A)-1] = temp # Subbing back in the intial element within the array to the end of the new array
print('===================================')
print('Result of Array shift by K = {}'.format(K))
print('===================================')
print()
print('Solution from for loop')
print(A)
print()
def solution(A, K):
K = int(input('Please enter the number of rotation you wish to do on the given array for function: '))
for x in range(0, K):
temp = A[0]
for y in range(0, len(A)-1):
A[y] = A[y+1]
A[len(A)-1] = temp
return(A)
pass

solution(A,4)
print()
print('Solution from function ')
print(A)[/CODE]

Line 24 should indented one level

 

[Ibix]

Line 24 should indented one level

Also line 19 shouldn't be there - it overrides the passed-in value of K.

Tight loops like this in python are a very bad idea. This is a very C/Java type solution, and in python you are fighting the language instead of playing to its strengths. Python let's you do the whole process in a single statement, by slicing off the last k elements of the array and appending the first (n-k) elements. Is there a reason you aren't doing this, @Taylor_1989? Unless you are forbidden from taking it for some reason I'd strongly recommend the approach. Try yours with a 10,000 element array and a K of 5,000. It takes my phone about 20s. My way is almost instantaneous.

 

[wle]

I was just going to write that yes. Also you don't have to call K when you are writing the function since you are declaring K inside the function.

Well the exercise says that the solution function should take K as a parameter, so it's really the line 'K = int(input(...' that shouldn't be there.

Also line 19 shouldn't be there - it overrides the passed-in value of K.

Tight loops like this in python are a very bad idea. This is a very C/Java type solution, and in python you are fighting the language instead of playing to its strengths. Python let's you do the whole process in a single statement, by slicing off the last k elements of the array and appending the first (n-k) elements. Is there a reason you aren't doing this, @Taylor_1989? Unless you are forbidden from taking it for some reason I'd strongly recommend the approach. Try yours with a 10,000 element array and a K of 5,000. It takes my phone about 20s. My way is almost instantaneous.

I was meaning to comment on this. There's also a language-independent reason that the OP's solution is slow which is that it rotates the list K places by rotating it 1 place K times. It's possible to do a lot better than that.

Also, rotating a list could potentially mean two different things: rotate the list in place (i.e., modify it) or build and return a new list with the elements rotated compared with the original. Modifying the list in place is generally the more difficult problem, particularly if you're trying to do it without using up a lot of temporary storage. The OP's code modifies the list in place, although the exercise doesn't clearly ask for that.

 

[jedishrfu]

Yes, modulo arithmetic on the indices would allow you to do it k steps at a time.

You could also create a new array and fill it in correctly and return it as the answer to avoid the swapping issue more memory but a cleaner looking solution.

 

[Taylor_1989]

Also line 19 shouldn't be there - it overrides the passed-in value of K.

Tight loops like this in python are a very bad idea. This is a very C/Java type solution, and in python you are fighting the language instead of playing to its strengths. Python let's you do the whole process in a single statement, by slicing off the last k elements of the array and appending the first (n-k) elements. Is there a reason you aren't doing this, @Taylor_1989? Unless you are forbidden from taking it for some reason I'd strongly recommend the approach. Try yours with a 10,000 element array and a K of 5,000. It takes my phone about 20s. My way is almost instantaneous.

The reason I did the approach and not slice, which I do no and did think about using is that I am currently just getting into python and C++ and thought that if I take a generic approach that using a easy language like python then crossing over to C++ and Java etc is more a syntax learning curve.

Maybe this is a wrong approach to learning, honeslty I am just going off by exploring the language and doing the challenges like codility.

Also for some reason I don't seem to be getting notifications when someone comment on the thread, yet I am watching the thread. Is there a reason for this?

 

[jedishrfu]

Some schools are adopting this approach of teaching python as the intro language and later migrating to C/C++ or Java in future courses based on student interest. A lot of Data Science in done using Python and its associated libraries Numpy Pandas, Matplotlib...

 

[Taylor_1989]

@jedishrfu just want to say thank you, although I was a bit slow on the uptake with your original hint.

In shifting elements you have to remember the variable swap problem commonly used as an interview question in the early days of programming.

Namely:

A=1 and B=2 and you want to swap them so that A=2 and B=1

The simple (wrong) solution is:

A=B --> so that A now has B's value and then B=A so that B now has A's value.
A=2 --> so that A now has a 2 value and then B=2 so that B now has a 2 value

and now you ask what happened to the ONE.

The correct solution is to use a temporary variable to hold A's value before you change it:

T=A  --> save A's value in T (T=1)
A=B  --> move B's value to A (A=2)
B=T  --> move A's value saved in T to B (B=1)

Does that help?

EDIT: changed language because Python has a built-in swapping feature (thanks @Arman777 for pointing that out) that hides the temp variable and can prevent someone trying to understanding the true nature of the problem especially in languages without that feature.

I eventually figured out the correct code show below and works for all cases given

for i in range(0,4):
    p = A[len(A)-1]
    for j in range(0,len(A)):
        temp = A[j]
        A[j] = p
        p = temp
print(A)

ingnor the 4. I was just testing a particular case.

 

[jedishrfu]

Better slow than never or is that better slow than too late. You'll do okay. You have the right attitude and perseverance to succeed.