[Codility] - CyclicRotation

[Filipe_O]

Boas malta!

A fim de melhorar as minhas competências em programação, decidi começar a resolver exercícios do Codility.
Para quem não conhece, o codility têm exercícios muito bons que ensinam a pensar como um programador.

Obtive 50% num determinado exercício, mas gostava de saber como tornar o código bullet proof, então deixo aqui o problema e a minha solução:
A zero-indexed 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 that, given a zero-indexed 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]
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]

Minha solução:

function solution(A, K) {
    var c=[];
    for (i=0;i<K; i++)
    {
        for (b=0;b<A.length;b++)
            {   
                if ((A.length-(1+i-b)) < A.length) 
                    c[b]=A[A.length-(1+i-b)];
                else
                c[b]=A[b-(1+i)];
            }
    }
    return c;
}

Como poderei melhorar o meu código?

Obrigado

 

[Flinger]

O problema do teu código é o número de iterações do ciclo estar dependente do tamanho do array.

o objectivo é reduzir o número de iterações.

Se reparares o array tem 2 partes:

A = [3, 8, 9, 7, 6] K = 3
the function should return [9, 7, 6, 3, 8].

[3 , 8] e [9, 7, 6]

Tudo o que tu tens de fazer é partir o array em 2 e trocar as metades
Usando memcpy, em C:

int* rotateK(int *source,int size,int *dest,int kRotations)
{
    int index=size-kRotations;

    memcpy(dest,&source[index],kRotations*sizeof(int));

    memcpy(&dest[kRotations],source,index*sizeof(int));

    return dest;
}

 

[anjo2]

Qual o objectivo? Optimização ou Algoritmia?

Supostamente eles querem que faças um pop e um append K vezes, em termos de optimização podes partir o array em 2 e fazer uma concatenação.

O que tu fizeste não é um nem outro, é uma solução forçada com o objectivo de funcionar e por isso os 50%, por funcionar.

 

[Flinger]

Qual o objectivo? Optimização ou Algoritmia?

Supostamente eles querem que faças um pop e um append K vezes, em termos de optimização podes partir o array em 2 e fazer uma concatenação.

O que tu fizeste não é um nem outro, é uma solução forçada com o objectivo de funcionar e por isso os 50%, por funcionar.

Não tinha visto o site. Estou habituado a exercícios de recrutamento, onde o foco é o desempenho, mas ao ver o exercício no site parece-me que o foco será a forma, pelo que sim, nesse caso dever-se-ia usar pop/push, ou, em javascript, pop e unshift, digo eu, que nada percebo de JS

 

[Filipe_O]

Pessoal, muito obrigado!
Na verdade, o meu problema foi desconhecer que era possível adicionar elementos ao inicio de um array (o unshift) sem ser "manualmente", substituindo o índice 0 do mesmo.
Ora, o meu problema prendia-se precisamente com o facto de necessitar de mover e não de substituir, o primeiro elemento do array.