Para este problema en particular no cree un algoritmo, simplemente use collections, que es un modulo que implementa de tipos de datos como dict, list, set y tuple pero de una manera “especializada”, básicamente son mas rápidos y tienen métodos muy útiles, en python 2.7 estan namedtuple, deque, Counter, OrderedDict, defaultdict y en python 3.2 en adelante empezaron agregar mas.

Cyclic Rotation

Problema:

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 also moved to the first place.

For example, the rotation of array A = [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7]. The goal is to rotate array A K times; that is, each element of A will be shifted to the right by K indexes.

Write a function:

def solution(A, K)

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 array A = [3, 8, 9, 7, 6] and K = 3, the function should return [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].

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

Solución:

import collections


''' Input list '''
A = [3, 8, 9, 7, 6]
''' Times the values will rotate '''
K = 3

def solution(A, K):
    ''' Rotate list A K times '''
    d = collections.deque(A)
    d.rotate(K)
    return list(d)

El problema nos dice que simplemente rotemos una lista A K veces, esto quiere decir que vamos a mover cada elemento de la lista un numero K de veces hacia la derecha, por ejemplo si A = [3, 8, 9, 7, 6] y  K = 3 nos retornaría [9, 7, 6, 3, 8]

  • En mi solución simplemente importo collections
  • Creo un objeto deque
  • uso el método rotate que recibe como parámetro las veces que quiero rotar ese objeto
  • Y por ultimo retorno el objeto deque en forma de lista con list()

Si leyeron mi post anterior, les comente que subiría el código a un repo de github y ya subí el código de binary gap y este a ese repo, esta vez y en el futuro incluí un prueba unitaria y el tiempo de ejecución con timeit, si quieren conocer un poco de lo que son pruebas unitarias pueden leerlo en el blog de la comunidad de Python de Tijuana, ahí se publico hace unos días un post sobre el tema.

Este sera el repo: https://github.com/OmarIbannez/codility-lessons

Este mas o menos es la manera en que estaré subiendo el código con timeit y unitest, si tienen alguna sugerencia de una mejor manera de como hacerlo es bienvenida.

import collections
import unittest
import timeit


''' Input list '''
A = [3, 8, 9, 7, 6]
''' Times the values will rotate '''
K = 3
''' List rotated K times '''
S = [9, 7, 6, 3, 8]


def solution(A, K):
    ''' Rotate list A K times '''
    d = collections.deque(A)
    d.rotate(K)
    return list(d)


def time_test():
    ''' Function to test the execution time '''
    solution(A, K)


class CyclicRotationTest(unittest.TestCase):
    ''' The expected return list from solution() must be equal to S '''
    def test_cyclic_rotation(self):
        self.assertEqual(solution(A, K), S)


if __name__ == "__main__":
    print(timeit.timeit(time_test))
    unittest.main()
It's only fair to share...Share on Facebook6Tweet about this on TwitterShare on Google+0Share on LinkedIn0Share on Reddit0Pin on Pinterest0Email this to someone

2 thoughts on “Cyclic Rotation

  1. Jose A. Martinez says:

    Ya me emocione con Codility y prendí mi computadora para darle una intentada a este problema.

    ¿Qué tal si no tuviéramos acceso al método rotate que utilizas? Básicamente estas utilizando un método que nos han pedido escribir, por lo tanto creo que en la mayoría de los casos se esperaría que escribiéramos el código para rotar nosotros mismos dentro de la solución con la ayuda de estructuras de datos básicas, como queues, stacks, linked lists, binary trees, etc. poniendo atención no solo al O(n) de ejecución, si no también al uso de memoria a razón de el input, o el O(n) de espacio utilizado en estas estructuras de datos.

    Al estar pensando en una solución, se me ocurrió rotar el array índice por índice, de forma que hacemos lo siguiente con cada iteración, suponiendo el array A = [2, 3, 6, 7, 8] y K = 3:

    Iteración 1:
    [2, 3, 6, 2, 8]

    Iteración 2:
    [2, 7, 6, 2, 8]

    Iteración 3:
    [2, 7, 6, 2, 3]

    Iteración 4:
    [2, 7, 8, 2, 3]

    Iteración 5:
    [6, 7, 8, 2, 3]

    Al hacer este ejercicio, me encontré que efectivamente:

    1. Podemos mantener el valor del elemento que acabamos de sobreescribir y utilizarlo en la próxima iteración.
    2. El número de iteraciones es igual al número de elementos del array (duh!).

    Intenté hacer el mismo ejercicio con arrays de tamaño impar y encontré algunos problemas y sus respectivas soluciones:

    1. Al intentar rotar un número par de elementos, en algún momento puede que intentemos rotar un indice que ya hemos rotado con anterioridad. ¿Dé que forma podemos saber que índices ya rotamos?
    A: Podemos utilizar algún HashSet, que es una estructura de datos en la que podemos agregar objetos a las que se les calcula un hashcode de forma que el buscar objetos (método HashSet.Contains(T) en .NET) tenga tiempo de ejecución O(n) = 1, o tiempo constante.

    2. ¿Dé que forma podemos saber si vamos a intentar acceder a un índice que es mayor del tamaño del array a rotar?
    A: Podemos calcular el índice Mod tamaño del array, que básicamente regresaría el número de índices que nos hemos excedido. Es importante entender como al hacer Mod obtenemos un número que puede ir de 0 al tamaño del array – 1.

    3. ¿Qué pasa si intentamos rotar un array vacío?
    A: No necesitamos rotar nada!

    Es importante tener en cuenta cuanta memoria va a utilizar el HashSet, en este caso el número de elementos que contendrá es O(n) = n, ya que agregará un elemento por cada elemento en el input. El tiempo de ejecución también es O(n) = n, ya que se requieren n iteraciones para rotar completamente. Aquí esta mi código:
    http://pastebin.com/ZPUqtSnF

  2. Qué interesante algoritmo. Inicialmente yo había pensado en la inmutabilidad de los datos, así que yo lo hice con un par de ciclos (no anidados) logrando O(n) en cómputo y O(n) en memoria (ya contando la memoria de retorno).

    https://gist.github.com/alvarezp/0d4bd4a111efb76fb486

    Pero tu algoritmo “in-memory” (José) me llamó la atención.

    Sobre el “problema #1” que mencionas: No es que el problema se presente según si N es par o non. Si tienes N = 15 y K = 3 también te va a dar el mismo problema porque gcd(N, K) > 1.

    Para sortear este problema usando un HashSet (y si comprendí bien la explicación) en el peor de los casos usarás O(n) de memoria + O(n) del cálculo de hashes.

    Lo bueno es que no se necesita el HashSet para continuar con tu técnica. En el “problema #1” de tu técnica bien dices que acabarás de vuelta en “algún” elemento, pero específicamente, siempre será el elemento en el que comenzó el ciclo después de haber realizado la rotación en N / gcd(N, K) elementos distribuidos uniformemente a lo largo del arreglo, es decir, cada gcd(N, K) elementos.

    Entonces, si definimos lo siguiente:
    – G = gcd(N, K)
    – R(A, i): una vuelta (y sólo una) de tu algoritmo sobre el arreglo A comenzando por el elemento i.

    entonces se puede hacer esto:

    for (set_index = 0; set_index < G; set_index++) { R(A, set_index); }

    Para calcular el GCD: como son sólo dos números puedes usar la técnica de Euclides o cualquiera de sus ramificaciones (como el Binary GCD).

    Con esto, la complejidad en cómputo queda en O(n) sin la necesidad hashes y en memoria es prácticamente in-memory, es decir, O(1).

    La desventaja, claro está, es que se destruye el arreglo original.

    Disclaimer: No lo he probado en código aún.

Leave a Reply

Your email address will not be published. Required fields are marked *

Comment moderation is enabled. Your comment may take some time to appear.