# LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

## #1 October 14 2010

arithma
Member

### Exercise - Rotate Array

Given an array of numbers, and a rotate parameter, move the elements of the array to the right (for a positive rotate parameter and to the left for a negative one). Overflowing elements will wrap around to the other end of the array.

Example:
rotate: +1
array: 0 1 2 3 4 5 6
result: 6 0 1 2 3 4 5

Extra
Since the above can be easily solved by creating another array and mapping elements then copying back to the array, here's an extra challenge.

Your result must be a list of pairs. These pairs designate the swaps between elements that when all done sequentially will return the desired output. In a sense you're returning instructions from a constrained instruction set. Each pair is the two index parameters that will be passed to a swap function.

You can essentially replace the array with a single count number since the content of the array should not affect the result. I was hoping this sentence would have resolved the ambiguity.

Example:
rotate: -1
array: [0 1 2 3]
result: (0, 1), (1, 2), (2, 3)... this transforms the above array into: [1 2 3 0]

Same Example:
rotate: -1
array: [a b c d]
should return the same result, transforming the array to: [b c d a]

In essence, all the algorithm needs is the array size and the shift parameter.
[a b c d] swap (0, 1) -> [b a c d]
[b a c d] swap (1, 2) -> [b c a d]
[b c a d] swap (2, 3) -> [b c d a]

Hope that clarifies things.

Last edited by arithma (October 14 2010)

## #2 October 14 2010

mesa177
Member

### Re: Exercise - Rotate Array

This is using the 'circshift' command in Matlab (as written in Command Window):

>> array = (0:1:6)

array =

0     1     2     3     4     5     6

>> circshift(array,[0,1])

ans =

6     0     1     2     3     4     5

I'll write the code for reading the given commands:
rotate: num
array: [bla,bla,bla...]
with a text file and post it soon

As for the extra part, the result of the transform you made is [3 0 1 2].
The actual transform to be conducted is either:
(0,3), (1,3), (2,3) or
(0,3), (1,2), (1,3) or
(0,3), (2,3), (1,2)
I'll also work on this

## #3 October 14 2010

Georges
Member

### Re: Exercise - Rotate Array

Nice exercise Arithma.
This technique is used in Cryptography too. It's an Encryption By Substitution.

Caesar Cipher
The earliest known use of a substitution cipher, and the simplest, was by Julius Caesar. The Caesar cipher involves replacing each letter of the alphabet with the letter standing three places further down the alphabet. For example,

plain:  meet me after the toga party
cipher: PHHW PH DIWHU WKH WRJD SDUWB

Note that the alphabet is wrapped around, so that the letter following Z is A. We can define the transformation by listing all possibilities, as follows:

plain:  a b c d e f g h i j k l m n o p q r s t u v w x y z
cipher: D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

----
As for the solution, Here's mine. (in C#)

class RotateArray
{
public static int key;
public static string Rotate(string textToRotate)
{
StringBuilder origText = new StringBuilder(textToRotate);
StringBuilder rotText = new StringBuilder(textToRotate.Length);
int c;

for (int i = 0; i < textToRotate.Length; i++)
{
c = (int)origText[i];
c = (c + key);

rotText.Append((char)c);
}
return rotText.ToString();
}
}

And a quick use of that class in a windows form.

private void performRotation()
{
int key = (Convert.ToInt16(rotationKey.Value)); // Got through a numeric updown control.
string rotated;
RotateArray.key = key; // Provide the rotation key.

rotated = RotateArray.Rotate(txtOriginalText.Text); // Perform rotation on textbox text

txtEncryptedText.Text = rotated;
}

Edit: Please note that this method covers all possible combinations of inputs. (Numbers, characters, etc.)

Last edited by Georges Raad (October 14 2010)

## #4 October 14 2010

arithma
Member

### Re: Exercise - Rotate Array

Please check the edit for some disambiguation. mesa, what I posted the first time is indeed correct. It's a little bit out of place to "assume that I am wrong in solving the problem that I am proposing" as opposed to "placing an inquiry for more information about the problem so that the examples make sense".

Last edited by arithma (October 14 2010)

## #5 October 14 2010

mesa177
Member

### Re: Exercise - Rotate Array

arithma wrote:

Please check the edit for some disambiguation. mesa, what I posted the first time is indeed correct. It's a little bit out of place to "assume that I am wrong in solving the problem that I am proposing" as opposed to "placing an inquiry for more information about the problem so that the examples make sense".

Ok Skafi, you meant the numbers in the swap transfrom are the entries on the array => there is no such thing as entry 0 => use entry numbers 1, 2, 3 and 4

## #6 October 14 2010

arithma
Member

### Re: Exercise - Rotate Array

mesa177 wrote:
arithma wrote:

Please check the edit for some disambiguation. mesa, what I posted the first time is indeed correct. It's a little bit out of place to "assume that I am wrong in solving the problem that I am proposing" as opposed to "placing an inquiry for more information about the problem so that the examples make sense".

Ok Skafi, you meant the numbers in the swap transfrom are the entries on the array => there is no such thing as entry 0 => use entry numbers 1, 2, 3 and 4

This depends on the language you are using. MATLAB uses base-1 while most other languages use base-0.

## #7 October 14 2010

Georges
Member

### Re: Exercise - Rotate Array

Here's another solution that fits the extra part you wanted:
[a b c d] swap (0, 1) -> [b a c d]
[b a c d] swap (1, 2) -> [b c a d]
[b c a d] swap (2, 3) -> [b c d a]

int[] myIntArray = new int[6] {0, 1, 2, 3, 4, 5 };
int[] myArray = new int[6] { 0, 1, 2, 3, 4, 5 };

Console.WriteLine("Please Enter the Shift Parameter: ");

if (key < 0)
key = myIntArray.Length + key;

if (key > myIntArray.Length)
key = key % myIntArray.Length;

// Original Array.
Console.Write("\nOriginal Array\t: ");
for (int j = 0; j < myIntArray.Length; j++)
{
Console.Write(myIntArray[j].ToString() + " ");
}

for (int i = myIntArray.Length - 1; i >= 0; i--)
{
myArray[(i + key) % myArray.Length] = myIntArray[(i)];
}

Console.Write("\nOutput Array\t: ");
for (int j = 0; j < myArray.Length; j++)
{
Console.Write(myArray[j].ToString() + " ");
}

Console.Write("\n\nPress any key to exit...");

Edit: Code Corrected...

@Arithma:
1- In the case of a negative number, the result is the same as the positive shifting by a value of (length + negative key).
EX: At a shift Parameter of -2, the result is the same as a shift parameter of 4. (length + negative key)
(6 + (-2) = 4).

2- For a shift parameter larger than the length of the array, it's just enough to do this:
Key = Key % array.length

Last edited by Georges Raad (October 14 2010)

## #8 October 14 2010

arithma
Member

### Re: Exercise - Rotate Array

George I don't think your algorithm is correct. I tried it with a key value of 2 and -2. I got weird incorrect results.
For key = 2:

Original Array  : 0 1 2 3 4 5

Swap (5 - 1)    : 0 5 2 3 4 1
Swap (4 - 0)    : 4 5 2 3 0 1
Swap (3 - 5)    : 4 5 2 5 0 3
Swap (2 - 4)    : 4 5 4 5 2 3
Swap (1 - 3)    : 4 3 4 1 2 3
Swap (0 - 2)    : 2 3 0 1 2 3

Output Array    : 2 3 0 1 2 3

Additionally you ought to cater for cases where key < 0 and Abs(key)>length_of_array.

Let me also raise the bar a bit higher with this requirement:
Return the minimum number of swaps necessary to do the shift operation, and the corresponding swaps.

## #9 October 15 2010

mesa177
Member

### Re: Exercise - Rotate Array

Matlab with circshift command:

clear all
clc

fid = fopen('Circular Shift input.txt'); % Open file where input arrays and
% circular shift key are located
C = {};                           % Cell to store input arrays
SK = [];                          % Array to store shift keys
flag = 1;                         % Flag to indicate whether shift key or
% array is being extracted
fresult = {};                     % Cell to store shifted arrays
n = 1;
while ~feof(fid)                  % Read input arrays until end of file
tline = fgetl(fid);           % Read current line
if mod(flag,2)                % Shift key is being identified
flag = flag + 1;
k = 0;                     % Identify shift left or right
if (k+1 < length(tline))
while ~isequal(tline(k+1),' ')
k = k + 1;
end
else
error('Wrong input for demanding circular shift.');
end
tline = tline(k+2:end);
if isequal('-',tline(1))
SK(n) = str2double(tline(2:end))*(-1);
disp('Shift to left');
else
SK(n) = str2double(tline);
if ~SK(n)
disp('No shift performed');
else
disp('Shift to right');
end
end
n = n + 1;
else
flag = flag + 1;
k = 0;                     % Identify input array
if (k+1 < length(tline))
while ~isequal(tline(k+1),' ')
k = k + 1;
end
else
error('Wrong entry of input array.');
end
tline = tline(k+2:end);
cnt = 1;
while ~isempty(tline)
k = 0;
if (k+1 < length(tline))
while (k < length(tline))&&(~isequal(tline(k+1),' '))
k = k + 1;
end
else
k = 1;
end
C{n-1}(cnt) = str2double(tline(1:k));
cnt = cnt + 1;
if (length(tline) > 1)
tline = tline(k+2:end);
else
tline = [];
end
end
if (abs(SK(n-1)) > length(C{n-1}))
error('Shift cannot be performed. Key size exceeds length of array.');
else                       % Peforming circular shift
fresult{n-1} = circshift(C{n-1},[0,SK(n-1)]);
end
disp('The resulting shifted array is:');
disp(num2str(fresult{n-1}));
end
end
status = fclose(fid);             % Close file

Matlab with array concatenations:

clear all
clc

fid = fopen('Circular Shift input.txt'); % Open file where input arrays and
% circular shift key are located
C = {};                           % Cell to store input arrays
SK = [];                          % Array to store shift keys
flag = 1;                         % Flag to indicate whether shift key or
% array is being extracted
fresult = {};                     % Cell to store shifted arrays
n = 1;
while ~feof(fid)                  % Read input arrays until end of file
tline = fgetl(fid);           % Read current line
if mod(flag,2)                % Shift key is being identified
flag = flag + 1;
k = 0;                     % Identify shift left or right
if (k+1 < length(tline))
while ~isequal(tline(k+1),' ')
k = k + 1;
end
else
error('Wrong input for demanding circular shift.');
end
tline = tline(k+2:end);
if isequal('-',tline(1))
SK(n) = str2double(tline(2:end))*(-1);
disp('Shift to left');
else
SK(n) = str2double(tline);
if ~SK(n)
disp('No shift performed');
else
disp('Shift to right');
end
end
n = n + 1;
else
flag = flag + 1;
k = 0;                     % Identify input array
if (k+1 < length(tline))
while ~isequal(tline(k+1),' ')
k = k + 1;
end
else
error('Wrong entry of input array.');
end
tline = tline(k+2:end);
cnt = 1;
while ~isempty(tline)
k = 0;
if (k+1 < length(tline))
while (k < length(tline))&&(~isequal(tline(k+1),' '))
k = k + 1;
end
else
k = 1;
end
C{n-1}(cnt) = str2double(tline(1:k));
cnt = cnt + 1;
if (length(tline) > 1)
tline = tline(k+2:end);
else
tline = [];
end
end
if (abs(SK(n-1)) > length(C{n-1}))
error('Shift cannot be performed. Key size exceeds length of array.');
elseif (SK(n-1) > 0)       % Peforming circular shift
fresult{n-1} = horzcat(C{n-1}(end-SK(n-1)+1:end),C{n-1}(1:end-SK(n-1)));
elseif ~SK(n-1)
fresult{n-1} = C{n-1};
else
tS = length(C{n-1}) + SK(n-1);
fresult{n-1} = horzcat(C{n-1}(end-tS+1:end),C{n-1}(1:end-tS));
end
disp('The resulting shifted array is:');
disp(num2str(fresult{n-1}));
end
end
status = fclose(fid);             % Close file

Example:

rotate: 3
array: 0 1 2 3 4 5 6
rotate: -2
array: 0 1 2 3 4 5 6 7 8 9 10

Shift to right
The resulting shifted array is:
4  5  6  0  1  2  3
Shift to left
The resulting shifted array is:
2   3   4   5   6   7   8   9  10   0   1

Still editing my swapping algorithm, found a good way to swap entries on arrays which have an odd number of entries and the number of swaps performed is length(array)-1 (for first example given it is 6) no matter how the shift is performed (to the right, to the left, a shift key of 1, 2, 3, etc...). Suddenly, I find out that I can decrease the number of swapping processes for specific shift keys. So the consistency I found suddenly crumbled :(
As for the even number of entries, the previously developed algorithm matches it so far, but there's one minor change done to it.

Last edited by mesa177 (October 15 2010)

## #10 October 15 2010

mesa177
Member

### Re: Exercise - Rotate Array

This is where I got so far in the swapping:

clear all
clc

fid = fopen('Circular Shift input.txt'); % Open file where input arrays and
% circular shift key are located
C = {};                           % Cell to store input arrays
SK = [];                          % Array to store shift keys
flag = 1;                         % Flag to indicate whether shift key or
% array is being extracted
fresult = {};                     % Cell to store shifted arrays
n = 1;
while ~feof(fid)                  % Read input arrays until end of file
tline = fgetl(fid);           % Read current line
if mod(flag,2)                % Shift key is being identified
flag = flag + 1;
k = 0;                     % Identify shift left or right
if (k+1 < length(tline))
while ~isequal(tline(k+1),' ')
k = k + 1;
end
else
error('Wrong input for demanding circular shift.');
end
tline = tline(k+2:end);
if isequal('-',tline(1))
SK(n) = str2double(tline(2:end))*(-1);
disp('Shift to left');
else
SK(n) = str2double(tline);
if ~SK(n)
disp('No shift performed');
else
disp('Shift to right');
end
end
n = n + 1;
else
flag = flag + 1;
k = 0;                     % Identify input array
if (k+1 < length(tline))
while ~isequal(tline(k+1),' ')
k = k + 1;
end
else
error('Wrong entry of input array.');
end
tline = tline(k+2:end);
cnt = 1;
while ~isempty(tline)
k = 0;
if (k+1 < length(tline))
while (k < length(tline))&&(~isequal(tline(k+1),' '))
k = k + 1;
end
else
k = 1;
end
C{n-1}(cnt) = str2double(tline(1:k));
cnt = cnt + 1;
if (length(tline) > 1)
tline = tline(k+2:end);
else
tline = [];
end
end
if (abs(SK(n-1)) > length(C{n-1}))
error('Shift cannot be performed. Key size exceeds length of array.');
elseif (SK(n-1) > 0)       % Peforming circular shift
N = SK(n-1);
fresult{n-1} = C{n-1};
if mod(length(C{n-1}),2)
if (N <= (length(C{n-1})-1)/2)
for i = 1:length(C{n-1})-1
if isequal(N,SK(n-1))
N = 1;
else
N = N + 1;
end
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
fresult{n-1}(end - SK(n-1) + N) = temp;
disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
',',num2str(length(C{n-1}) - SK(n-1) + N),')'));
disp(num2str(fresult{n-1}));
end
else
for i = 1:length(C{n-1})-1
if isequal(N,SK(n-1))
N = 1;
else
N = N + 1;
end
if (i <= SK(n-1))
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
fresult{n-1}(end - SK(n-1) + N) = temp;
disp(strcat('Step',num2str(i),': Swap (',...
num2str(i),',',...
num2str(length(C{n-1}) - SK(n-1) + N),')'));
disp(num2str(fresult{n-1}));
else
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end);
fresult{n-1}(end) = temp;
disp(strcat('Step',num2str(i),': Swap (',...
num2str(i),',',num2str(length(C{n-1})),')'));
disp(num2str(fresult{n-1}));
end
end
end
else
if (N <= (length(C{n-1})-1)/2)
for i = 1:length(C{n-1})-SK(n-1)
if isequal(N,SK(n-1))
N = 1;
else
N = N + 1;
end
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
fresult{n-1}(end - SK(n-1) + N) = temp;
disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
',',num2str(length(C{n-1}) - SK(n-1) + N),')'));
disp(num2str(fresult{n-1}));
end
else
for i = 1:SK(n-1)
if isequal(N,SK(n-1))
N = 1;
else
N = N + 1;
end
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
fresult{n-1}(end - SK(n-1) + N) = temp;
disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
',',num2str(length(C{n-1}) - SK(n-1) + N),')'));
disp(num2str(fresult{n-1}));
end
end
end
elseif ~SK(n-1)
fresult{n-1} = C{n-1};
else
tS = length(C{n-1}) + SK(n-1);
N = tS;
fresult{n-1} = C{n-1};
if mod(length(C{n-1}),2)
if (N <= (length(C{n-1})-1)/2)
for i = 1:length(C{n-1})-1
if isequal(N,tS)
N = 1;
else
N = N + 1;
end
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end - tS + N);
fresult{n-1}(end - tS + N) = temp;
disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
',',num2str(length(C{n-1}) - tS + N),')'));
disp(num2str(fresult{n-1}));
end
else
for i = 1:length(C{n-1})-1
if isequal(N,tS)
N = 1;
else
N = N + 1;
end
if (i <= tS)
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end - tS + N);
fresult{n-1}(end - tS + N) = temp;
disp(strcat('Step',num2str(i),': Swap (',...
num2str(i),',',...
num2str(length(C{n-1}) - tS + N),')'));
disp(num2str(fresult{n-1}));
else
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end);
fresult{n-1}(end) = temp;
disp(strcat('Step',num2str(i),': Swap (',...
num2str(i),',',num2str(length(C{n-1})),')'));
disp(num2str(fresult{n-1}));
end
end
end
else
if (N <= (length(C{n-1})-1)/2)
for i = 1:length(C{n-1})-tS
if isequal(N,tS)
N = 1;
else
N = N + 1;
end
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end - tS + N);
fresult{n-1}(end - tS + N) = temp;
disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
',',num2str(length(C{n-1}) - tS + N),')'));
disp(num2str(fresult{n-1}));
end
else
for i = 1:tS
if isequal(N,tS)
N = 1;
else
N = N + 1;
end
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end - tS + N);
fresult{n-1}(end - tS + N) = temp;
disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
',',num2str(length(C{n-1}) - tS + N),')'));
disp(num2str(fresult{n-1}));
end
end
end
end
disp('The resulting shifted array is:');
disp(num2str(fresult{n-1}));
end
end
status = fclose(fid);             % Close file

Of course some of the lines can be placed in functions to minimize the code length of the main program, but I'm too lazy to generate them for now

Example:
rotate: -2
array: 0 1 2 3 4 5 6 7
rotate: 6
array: 0 1 2 3 4 5 6 7 8 9 10

Shift to left
Step1: Swap (1,3)
2  1  0  3  4  5  6  7
Step2: Swap (2,4)
2  3  0  1  4  5  6  7
Step3: Swap (3,5)
2  3  4  1  0  5  6  7
Step4: Swap (4,6)
2  3  4  5  0  1  6  7
Step5: Swap (5,7)
2  3  4  5  6  1  0  7
Step6: Swap (6,8)
2  3  4  5  6  7  0  1
The resulting shifted array is:
2  3  4  5  6  7  0  1
Shift to right
Step1: Swap (1,6)
5   1   2   3   4   0   6   7   8   9  10
Step2: Swap (2,7)
5   6   2   3   4   0   1   7   8   9  10
Step3: Swap (3,8)
5   6   7   3   4   0   1   2   8   9  10
Step4: Swap (4,9)
5   6   7   8   4   0   1   2   3   9  10
Step5: Swap (5,10)
5   6   7   8   9   0   1   2   3   4  10
Step6: Swap (6,11)
5   6   7   8   9  10   1   2   3   4   0
Step7: Swap (7,11)
5   6   7   8   9  10   0   2   3   4   1
Step8: Swap (8,11)
5   6   7   8   9  10   0   1   3   4   2
Step9: Swap (9,11)
5   6   7   8   9  10   0   1   2   4   3
Step10: Swap (10,11)
5   6   7   8   9  10   0   1   2   3   4
The resulting shifted array is:
5   6   7   8   9  10   0   1   2   3   4

Last edited by mesa177 (October 15 2010)

## #11 October 16 2010

Joe
Member

### Re: Exercise - Rotate Array

A C implementation of swapping that does not declare more variables:

#include <stdlib.h>
#include <stdio.h>
#define ARRAY_SIZE 6

void init_array(int* array, int size)
{
int i = 0;

for (i=0; i<size; i++)
{
array[i] = i;
}
}

void print_array (int* array, int size)
{
int i = 0;
for (i=0; i<size; i++)
{
printf ("%d\t", array[i]);
}

printf("\n");
}

void rotate_array (int* array, int size, int param)
{
int i, j;

for (i = 1; i <= param; i++)
{
for (j = size-1; j > 0; j--)
{
array[j-1] = array[j-1] + array[j];
array[j] = array[j-1] - array[j];
array[j-1] = array[j-1] - array[j];
}
}
}

int main (int argc, char** argv)
{
int array[ARRAY_SIZE];
int i;

init_array(array, ARRAY_SIZE);

rotate_array(array, ARRAY_SIZE, 2);

print_array (array, ARRAY_SIZE);
printf("\n");

return 0;

}

Focus on the rotate_array() function. Items are swapped one by one. This method, though mathematical, has some computer limitations as array[j-1] + array[j could overflow. You could also use a boolean xor operation. This has been discussed in previous post.

I will try to output the pairs tomorrow.

## #12 October 17 2010

arithma
Member

### Re: Exercise - Rotate Array

This method, though mathematical, has some computer limitations as array[j-1] + array[j could overflow

To put the butter on the toast, you gotta keep in mind: int overflow is not defined in C++ (or perhaps it is just compiler specific, which can be good for different reasons). unsigned int overflow is defined, and the numbers just overlap. So if you cast whatever you need into int swap them and cast back you should be save with the plus and minus swap.

I really can't wrap my head around all your code mesa. It's just too much. Can you give out some psuedocode? In addition there's too much code on one hand, and too little swaps on the other hand, are there just too many switch conditions?

A litmus test for your algorithm: How many swaps approximately will there be for shifting a 1 million integers (~3.18MB) through these shifts: -1000, +1000, -100 000, +100 000.
I'll post a new exercise that may shed light on a particular special implementation that's very optimized for this swap thing.

## #13 October 17 2010

Joe
Member

### Re: Exercise - Rotate Array

To put the butter on the toast, you gotta keep in mind: int overflow is not defined in C++ (or perhaps it is just compiler specific, which can be good for different reasons). unsigned int overflow is defined, and the numbers just overlap. So if you cast whatever you need into int swap them and cast back you should be save with the plus and minus swap.

I'm guessing you're talking about the extra bit used for signs (as opposed to unsigned variables). Am I correct?

## #14 October 17 2010

arithma
Member

### Re: Exercise - Rotate Array

Here's the related exercise I was talking about: http://www.lebgeeks.com/forums/viewtopic.php?id=7584

@rahmu:
It's related, yes. Some C++ compilers may convert an int overflow into a saturated value (especially when dealing with digital signal processing). The standard leaves it up to the implementers to decide what fits and makes it easier for the domain. However the overflow behavior of an unsigned int is very well defined (wrap around the integer domain) and is compatible with your swap function (so even if it does overflow, it will still behave correctly). Do note that: the operators themselves take more memory than they save by removing the variable, and more so, the compiler may optimize out a temp value and replace the whole thing with an XCHANGE op code. It's always better to tell the compiler what is your intent rather than microoptimizing an algorithm (or at least it's suggested that you do as such, and if you care that much about that last bit of memory, why are you not using assembly to start with.. People developing high performance applications usually do optimize code that is called the most to assembly occasionally if the compiler doesn't take the hint... Think custom memory allocation for a VM (be it an environment or an OS virtualization system) and the likes..)

## #15 October 17 2010

arithma
Member

### Re: Exercise - Rotate Array

@mesa: I rechecked how your algorithm is working from the swaps, and I think I get the gist of it. You are mostly dividing the problem into two subparts. Shifting members around until you hit the max element, then you'd reverse the resulting array that you is left unoperated on.

I don't have matlab installed here, can you try this input and print the resulting swaps as well:
array: 0 1 2 3 4 5 6 7 8
shift: -2

Last edited by arithma (October 17 2010)

## #16 October 17 2010

arithma
Member

### Re: Exercise - Rotate Array

EX: At a shift Parameter of -2, the result is the same as a shift parameter of 4. (length + negative key)
(6 + (-2) = 4).

@George: What if the shift parameter is -1000? 6 + (-1000) = -994.
You should: ((k%n)+n)%k. This will solve all your troubles.
k%n belongs to (-n, n). This an open interval.
(k%n)+n belongs to (0, 2n)
((k%n)+n)%k belongs to [0, n). Capiche?

## #17 October 17 2010

mesa177
Member

### Re: Exercise - Rotate Array

Ok, so I added an enhancement and some extra comments to help (hopefully) in realizing the algorithm behind the swapping:

clear all
clc

fid = fopen('Circular Shift input.txt'); % Open file where input arrays and
% circular shift key are located
C = {};                           % Cell to store input arrays
SK = [];                          % Array to store shift keys
flag = 1;                         % Flag to indicate whether shift key or
% array is being extracted
fresult = {};                     % Cell to store shifted arrays
n = 1;
while ~feof(fid)                  % Read input arrays until end of file
tline = fgetl(fid);           % Read current line
if mod(flag,2)                % Shift key is being identified
flag = flag + 1;
k = 0;                     % Identify shift left or right
if (k+1 < length(tline))
while ~isequal(tline(k+1),' ')
k = k + 1;
end
else
error('Wrong input for demanding circular shift.');
end
tline = tline(k+2:end);
if isequal('-',tline(1))
SK(n) = str2double(tline(2:end))*(-1);
disp('Shift to left');
else
SK(n) = str2double(tline);
if ~SK(n)
disp('No shift performed');
else
disp('Shift to right');
end
end
n = n + 1;
else
flag = flag + 1;
k = 0;                     % Identify input array
if (k+1 < length(tline))
while ~isequal(tline(k+1),' ')
k = k + 1;
end
else
error('Wrong entry of input array.');
end
tline = tline(k+2:end);
cnt = 1;
while ~isempty(tline)
k = 0;
if (k+1 < length(tline))
while (k < length(tline))&&(~isequal(tline(k+1),' '))
k = k + 1;
end
else
k = 1;
end
C{n-1}(cnt) = str2double(tline(1:k));
cnt = cnt + 1;
if (length(tline) > 1)
tline = tline(k+2:end);
else
tline = [];
end
end
if (abs(SK(n-1)) > length(C{n-1}))
% Key size exceeds length of array
if (SK(n-1) > 0)
SK(n-1) = mod(SK(n-1),length(C{n-1}));
else
SK(n-1) = -mod(abs(SK(n-1)),length(C{n-1}));
end
end
if (SK(n-1) > 0)       % Peforming circular shift
N = SK(n-1);
fresult{n-1} = C{n-1};
if mod(length(C{n-1}),2) % Array has an odd number of entries
if (N <= (length(C{n-1})-1)/2) % Key is smaller than or equal to half the size of the array
for i = 1:length(C{n-1})-1
if isequal(N,SK(n-1))
N = 1;
else
N = N + 1;
end
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
fresult{n-1}(end - SK(n-1) + N) = temp;
disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
',',num2str(length(C{n-1}) - SK(n-1) + N),')'));
disp(num2str(fresult{n-1}));
end
else % Key is greater than half the size of the array
for i = 1:length(C{n-1})-1
if isequal(N,SK(n-1))
N = 1;
else
N = N + 1;
end
if (i <= SK(n-1))
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
fresult{n-1}(end - SK(n-1) + N) = temp;
disp(strcat('Step',num2str(i),': Swap (',...
num2str(i),',',...
num2str(length(C{n-1}) - SK(n-1) + N),')'));
disp(num2str(fresult{n-1}));
else
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end);
fresult{n-1}(end) = temp;
disp(strcat('Step',num2str(i),': Swap (',...
num2str(i),',',num2str(length(C{n-1})),')'));
disp(num2str(fresult{n-1}));
end
end
end
else % Array has an even number of entries
if (N <= (length(C{n-1})-1)/2) % Key is smaller than or equal to half the size of the array
for i = 1:length(C{n-1})-SK(n-1)
if isequal(N,SK(n-1))
N = 1;
else
N = N + 1;
end
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
fresult{n-1}(end - SK(n-1) + N) = temp;
disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
',',num2str(length(C{n-1}) - SK(n-1) + N),')'));
disp(num2str(fresult{n-1}));
end
else % Key is greater than half the size of the array
for i = 1:SK(n-1)
if isequal(N,SK(n-1))
N = 1;
else
N = N + 1;
end
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
fresult{n-1}(end - SK(n-1) + N) = temp;
disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
',',num2str(length(C{n-1}) - SK(n-1) + N),')'));
disp(num2str(fresult{n-1}));
end
end
end
elseif ~SK(n-1)
fresult{n-1} = C{n-1};
else
tS = length(C{n-1}) + SK(n-1);
N = tS;
fresult{n-1} = C{n-1};
if mod(length(C{n-1}),2) % Array has an odd number of entries
if (N <= (length(C{n-1})-1)/2) % Key is smaller than or equal to half the size of the array
for i = 1:length(C{n-1})-1
if isequal(N,tS)
N = 1;
else
N = N + 1;
end
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end - tS + N);
fresult{n-1}(end - tS + N) = temp;
disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
',',num2str(length(C{n-1}) - tS + N),')'));
disp(num2str(fresult{n-1}));
end
else % Key is greater than half the size of the array
for i = 1:length(C{n-1})-1
if isequal(N,tS)
N = 1;
else
N = N + 1;
end
if (i <= tS)
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end - tS + N);
fresult{n-1}(end - tS + N) = temp;
disp(strcat('Step',num2str(i),': Swap (',...
num2str(i),',',...
num2str(length(C{n-1}) - tS + N),')'));
disp(num2str(fresult{n-1}));
else
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end);
fresult{n-1}(end) = temp;
disp(strcat('Step',num2str(i),': Swap (',...
num2str(i),',',num2str(length(C{n-1})),')'));
disp(num2str(fresult{n-1}));
end
end
end
else % Array has an even number of entries
if (N <= (length(C{n-1})-1)/2) % Key is smaller than or equal to half the size of the array
for i = 1:length(C{n-1})-tS
if isequal(N,tS)
N = 1;
else
N = N + 1;
end
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end - tS + N);
fresult{n-1}(end - tS + N) = temp;
disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
',',num2str(length(C{n-1}) - tS + N),')'));
disp(num2str(fresult{n-1}));
end
else % Key is greater than half the size of the array
for i = 1:tS
if isequal(N,tS)
N = 1;
else
N = N + 1;
end
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end - tS + N);
fresult{n-1}(end - tS + N) = temp;
disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
',',num2str(length(C{n-1}) - tS + N),')'));
disp(num2str(fresult{n-1}));
end
end
end
end
disp('The resulting shifted array is:');
disp(num2str(fresult{n-1}));
end
end
status = fclose(fid);             % Close file

Note that the most part of the code is reading a text file which has the shift keys and the input arrays entered:

while ~feof(fid)                  % Read input arrays until end of file
tline = fgetl(fid);           % Read current line
if mod(flag,2)                % Shift key is being identified
flag = flag + 1;
k = 0;                     % Identify shift left or right
if (k+1 < length(tline))
while ~isequal(tline(k+1),' ')
k = k + 1;
end
else
error('Wrong input for demanding circular shift.');
end
tline = tline(k+2:end);
if isequal('-',tline(1))
SK(n) = str2double(tline(2:end))*(-1);
disp('Shift to left');
else
SK(n) = str2double(tline);
if ~SK(n)
disp('No shift performed');
else
disp('Shift to right');
end
end
n = n + 1;
else
flag = flag + 1;
k = 0;                     % Identify input array
if (k+1 < length(tline))
while ~isequal(tline(k+1),' ')
k = k + 1;
end
else
error('Wrong entry of input array.');
end
tline = tline(k+2:end);
cnt = 1;
while ~isempty(tline)
k = 0;
if (k+1 < length(tline))
while (k < length(tline))&&(~isequal(tline(k+1),' '))
k = k + 1;
end
else
k = 1;
end
C{n-1}(cnt) = str2double(tline(1:k));
cnt = cnt + 1;
if (length(tline) > 1)
tline = tline(k+2:end);
else
tline = [];
end
end
...

This is the enhancement made for when the shift key is greater than the size of the array:

if (abs(SK(n-1)) > length(C{n-1}))
% Key size exceeds length of array
if (SK(n-1) > 0)
SK(n-1) = mod(SK(n-1),length(C{n-1}));
else
SK(n-1) = -mod(abs(SK(n-1)),length(C{n-1}));
end
end

As for the jist of the code, it lies here (note that the same code is used for a shift key with a negative value but the shift is done according to "length(array) + shift key negative value" because as George pointed out previously a shift to the left is the same as a shift to the right by a shift key of "length(array) + shift key negative value"):

if (SK(n-1) > 0)       % Peforming circular shift
N = SK(n-1);
fresult{n-1} = C{n-1};
if mod(length(C{n-1}),2) % Array has an odd number of entries
if (N <= (length(C{n-1})-1)/2) % Key is smaller than or equal to half the size of the array
for i = 1:length(C{n-1})-1
if isequal(N,SK(n-1))
N = 1;
else
N = N + 1;
end
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
fresult{n-1}(end - SK(n-1) + N) = temp;
disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
',',num2str(length(C{n-1}) - SK(n-1) + N),')'));
disp(num2str(fresult{n-1}));
end
else % Key is greater than half the size of the array
for i = 1:length(C{n-1})-1
if isequal(N,SK(n-1))
N = 1;
else
N = N + 1;
end
if (i <= SK(n-1))
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
fresult{n-1}(end - SK(n-1) + N) = temp;
disp(strcat('Step',num2str(i),': Swap (',...
num2str(i),',',...
num2str(length(C{n-1}) - SK(n-1) + N),')'));
disp(num2str(fresult{n-1}));
else
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end);
fresult{n-1}(end) = temp;
disp(strcat('Step',num2str(i),': Swap (',...
num2str(i),',',num2str(length(C{n-1})),')'));
disp(num2str(fresult{n-1}));
end
end
end
else % Array has an even number of entries
if (N <= (length(C{n-1})-1)/2) % Key is smaller than or equal to half the size of the array
for i = 1:length(C{n-1})-SK(n-1)
if isequal(N,SK(n-1))
N = 1;
else
N = N + 1;
end
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
fresult{n-1}(end - SK(n-1) + N) = temp;
disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
',',num2str(length(C{n-1}) - SK(n-1) + N),')'));
disp(num2str(fresult{n-1}));
end
else % Key is greater than half the size of the array
for i = 1:SK(n-1)
if isequal(N,SK(n-1))
N = 1;
else
N = N + 1;
end
temp = fresult{n-1}(i);
fresult{n-1}(i) = fresult{n-1}(end - SK(n-1) + N);
fresult{n-1}(end - SK(n-1) + N) = temp;
disp(strcat('Step',num2str(i),': Swap (',num2str(i),...
',',num2str(length(C{n-1}) - SK(n-1) + N),')'));
disp(num2str(fresult{n-1}));
end
end
end
...

For the example you gave me Skafi:

rotate: -2
array: 0 1 2 3 4 5 6 7 8

Shift to left
Step1: Swap (1,3)
2  1  0  3  4  5  6  7  8
Step2: Swap (2,4)
2  3  0  1  4  5  6  7  8
Step3: Swap (3,5)
2  3  4  1  0  5  6  7  8
Step4: Swap (4,6)
2  3  4  5  0  1  6  7  8
Step5: Swap (5,7)
2  3  4  5  6  1  0  7  8
Step6: Swap (6,8)
2  3  4  5  6  7  0  1  8
Step7: Swap (7,9)
2  3  4  5  6  7  8  1  0
Step8: Swap (8,9)
2  3  4  5  6  7  8  0  1
The resulting shifted array is:
2  3  4  5  6  7  8  0  1

However, this example doesn't show the power of the algorithm developed because the minimum number of operations required to conduct the shift is length(array)-1 = 8.

For this example:
rotate: 3
array: 0 1 2 3 4 5

Shift to right
Step1: Swap (1,4)
3  1  2  0  4  5
Step2: Swap (2,5)
3  4  2  0  1  5
Step3: Swap (3,6)
3  4  5  0  1  2
The resulting shifted array is:
3  4  5  0  1  2

So instead of needing length(array)-1 = 6 steps of swapping, only 3 are required => minimum steps required to conduct the shift.

Last edited by mesa177 (October 17 2010)

## #18 October 17 2010

mesa177
Member

### Re: Exercise - Rotate Array

Semi version of pseudo-code (will not compile properly with Matlab, to do so use above code)

% Peforming circular shift
N = key; % key is either the entered positive shift key or length(array) + negative shift key
shiftedArray = array;
if mod(length(array),2) % Array has an odd number of entries
if (N <= (length(array)-1)/2) % Key is smaller than or equal to half the size of the array
for i = 1:length(array)-1
if isequal(N,key) % Used pattern to select entry to be swapped
N = 1;
else
N = N + 1;
end
temp = shiftedArray(i); % Swap entry values
shiftedArray(i) = shiftedArray(end - key + N); % end resembles last entry on array
shiftedArray(end - key + N) = temp;
display "Step number: Swap (entry1,entry2)"; % that's what the jargon does in the
display shiftedArray;                        % original code
end
else % Key is greater than half the size of the array
for i = 1:length(array)-1
if isequal(N,key) % Used pattern to select entry to be swapped
N = 1;
else
N = N + 1;
end
if (i <= key) % Change of selected pattern of entry swapping
temp = shiftedArray(i); % Swap entry values
shiftedArray(i) = shiftedArray(end - key + N); % <= notice the index change =
shiftedArray(end - key + N) = temp;                                         %
display "Step number: Swap (entry1,entry2)";                                %
display shiftedArray;                                                       %
else                                                                           %
temp = shiftedArray(i); % Swap entry values                                 %
shiftedArray(i) = shiftedArray(end);           % <==========================%
shiftedArray(end) = temp;
display "Step number: Swap (entry1,entry2)";
display shiftedArray;
end
end
end
else % Array has an even number of entries
if (N <= (length(array)-1)/2) % Key is smaller than or equal to half the size of the array
for i = 1:length(array)-key % <= change in number of looping i.e. swapping repetitions =
if isequal(N,key)                                                                  %
N = 1;                                                                          %
else                                                                               %
N = N + 1;                                                                      %
end                                                                                %
temp = shiftedArray(i); % Swap entry values                                        %
shiftedArray(i) = shiftedArray(end - key + N);                                     %
shiftedArray(end - key + N) = temp;                                                %
display "Step number: Swap (entry1,entry2)";                                       %
display shiftedArray;                                                              %
end                                                                                    %
else % Key is greater than half the size of the array                                      %
for i = 1:key % <======================================================================%
if isequal(N,key)
N = 1;
else
N = N + 1;
end
temp = shiftedArray(i); % Swap entry values
shiftedArray(i) = shiftedArray(end - key + N);
shiftedArray(end - key + N) = temp;
display "Step number: Swap (entry1,entry2)";
display shiftedArray;
end
end
end

Last edited by mesa177 (October 17 2010)

## #19 October 17 2010

mesa177
Member

### Re: Exercise - Rotate Array

Now, if you run the code for some shift keys, you will notice erroneous results in the swapping process (either exceeding the number of swapping steps or requiring more swapping steps).

These are the shift keys that give wrong swapping results (tested for arrays with lengths reaching 15 entries):

(Format of writing: shift key bla gives error for arrays with bla entries)
key 3,5 for an array length of 8
key 6 for an array length of 9
key 3,4,5,6,7 for an array length of 10
key 3,4,7,8 for an array length of 11
key 5,6,7 for an array length of 12
key 5,8 for an array length of 13
key 3,4,5,6,8,9,10,11 for an array of length of 14
key 4,6,9,10,11,12 for an array of length of 15

No errors occur for arrays that have no more than 7 entries.

As you can see, there is no capability of logically tracing wrong shift key rotations.

Anyone care to point out something I've missed or has a better way for swapping with minimum steps acheived? (Yes, we can swap the last element over and over, but we won't have the minimum steps of swapping)

## #20 October 17 2010

arithma
Member

### Re: Exercise - Rotate Array

Hello all, I see Alaa has been quite busy with the exercise. I am glad you found the errors in your algorithm though it looks promising. After getting down my algorithm correctly, I researched a little and found an algo similar to what you're implementing.
Excuse me for not being able to parse all that much MATLAB to make sense of it. By the way, is it too much trouble to ask to code in C++? It's usually better to implement algorithms in an "atomic" language rather than one tuned for bulk operations like MATLAB (otherwise you'd end up hiding computational complexity and losing sight of the real value of a problem). However, in this exercise, I think the most trouble is our inability to read it so that to help you fast. I really hope you'd convert to C++ for many various reasons that we can talk about soon.

## #21 October 17 2010

arithma
Member

### Re: Exercise - Rotate Array

I will soon post the explanation, hopefully, on my blog. It shouldn't be too hard if you followed the other exercise through. I still advise anyone who's interested to go through that exercise first, and get back here to solve it.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MyRotate
{
class Program
{
static int count_circles(int n, int k)
{
if (k <= 1) return 1;
if (n == k) return n;
return count_circles(k, k - (n % k));
}

static void swap(ref int x, ref int y)
{
int temp = x;
x = y;
y = temp;
}

static int wrap(int i, int n)
{
return ((i % n) + n) % n;
}

static void rotate(int[] array, int k)
{
int n = array.Length;
k = wrap(k, n);
int count = count_circles(n, k);
int sub_n = n / count;
for (int i = 0; i < count; i++)
{
for (int j = sub_n - 2; j >= 0; j--)
{
int from = wrap((i + j * k), n);
int to = wrap((i + j * k + k), n);
Console.WriteLine("{0}-{1}", from, to);
swap(ref array[from], ref array[to]);
}
}
}

static void Main(string[] args)
{
Console.WriteLine("{0}", count_circles(11, 2));
Console.WriteLine("{0}", count_circles(10, 2));
Console.WriteLine("{0}", count_circles(10, 3));
Console.WriteLine("{0}", count_circles(10, 5));

int[] array = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
rotate(array, 2);
foreach (var i in array) Console.Write("{0} ", i);
Console.Write("\n");
}
}
}

## #22 October 18 2010

mesa177
Member

### Re: Exercise - Rotate Array

arithma wrote:

By the way, is it too much trouble to ask to code in C++? It's usually better to implement algorithms in an "atomic" language rather than one tuned for bulk operations like MATLAB (otherwise you'd end up hiding computational complexity and losing sight of the real value of a problem). However, in this exercise, I think the most trouble is our inability to read it so that to help you fast. I really hope you'd convert to C++ for many various reasons that we can talk about soon.

Don't I wish I still remember how to code with C++?
The last time I coded with C++ was 2 years ago. I still remember the bulk of it, but I lost my touch. I'll try to adjust back to C++, but I can't promise anything (I mean when I was solving this problem, I was like "which library do we include to use cout?!")

## #23 October 25 2010

arithma
Member

### Re: Exercise - Rotate Array

I posted a thorough explanation of the solution on my blog. Check it here.

## #24 October 25 2010

mesa177
Member

### Re: Exercise - Rotate Array

Touché, Mr.Skafi :)