Reporte EDD

Integrantes

• Ávalos Díaz Iván Alejandro.
• Solano Cisneros Sergio Sebastian.

Estructura de datos

• n: entero que representa la longitud de cada lado del cubo.
• stickers: matriz tridimensional de n×n×n. Cada celda contiene un número entero que corresponde a una cara del cubo '(0 1 2 3 4 5) que puede ser mapeado a un símbolo '(U D F B R L). Cada símbolo puede ser mapeado a su respectivo color o «sticker» '(w y b g o r), independientemente de su posición en la matriz.

Ejemplo

((n . 3)
 (stickers (((0 0 0)
             (0 0 0)
             (0 0 0))
            ((1 1 1)
             (1 1 1)
             (1 1 1))
            ((2 2 2)
             (2 2 2)
             (2 2 2))
            ((3 3 3)
             (3 3 3)
             (3 3 3))
            ((4 4 4)
             (4 4 4)
             (4 4 4))
            ((5 5 5)
             (5 5 5)
             (5 5 5))))

Métodos

Inicializar una estructura cubo

(make-cube n)

Rotar el cubo

(cube-rotate cube f l d #f) ; #f se quitará pronto, es para recursión.

Realizar rotaciones aleatorias

(cube-randomize cube n)

Imprimir el cubo

(cube-print cube)

Algoritmo

El algoritmo consiste en realizar rotaciones mediante una serie de pasos que involucran asignar los valores de los stickers de determinada fila o columna de una cara (en un determinado orden), hacia una fila o columna de otra cara (en otro determinado orden). Por ejemplo, mover la fila 1 de la cara 'B hacia la fila 1 de la cara 'R; o mover la fila 2 de la cara 'U hacia la columna 4 de la cara 'B`. De esta manera, se pueden realizar rotaciones sin conocer los valores de las celdas.

Las operaciones de matrices se basan en propiedades comunes de los cubos que son independientes de sus dimensiones, como por ejemplo, el hecho de que todos los cubos tienen 6 caras. Todas las operaciones que son dependientes de n, se llevan a cabo en relación al valor n especificado, haciendo posible manipular cubos de cualquier dimensión.

Una rotación al cubo hace mover una capa l paralela a la cara f, d giros de 90º en sentido de las manecillas del reloj. La capa 0 es la cara en sí. Un valor d=3 o d=-1 hace un movimiento de 90º en sentido contrario a las manecillas del reloj, mientras d=2 realiza uno de 180º.

Ejemplo

Para rotar la capa 0 de la cara 'U, 90º en sentido de las manecillas del reloj:

1. Copiar la fila 0 de la cara 'F hacia la fila 0 de la cara 'L.
2. Copiar la fila 0 de la cara 'R hacia la fila 0 de la cara 'F.
3. Copiar la fila 0 de la cara 'B hacia la fila 0 de la cara 'R.
4. Copiar la fila 0 de la cara 'L hacia la fila 0 de la cara 'B.
5. Rotar 90º la cara 'U.

Implementación

Este programa está escrito en CHICKEN Scheme, que es una implementación de Scheme, que a su vez es una familia de dialectos derivados de Lisp. Scheme es un lenguaje de programación minimalista, con un enfoque funcional y con lo mejor de Lisp: manipulación del código como información (y viceversa), listas enlazadas, tipado dinámico, meta-programación (modificar su propia sintaxis en tiempo de ejecución), REPL (read-eval-print loop, introducido por Lisp); así como características exclusivas como optimización de recursión final (tail-recursion optimization), etc. Scheme está construido en su totalidad por listas, su sintaxis se compone por listas en forma de expresiones S (introducidas por Lisp) en notación de prefijo.

CHICKEN Scheme proporciona un intérprete, un compilador a C portable y un repositorio con gran cantidad de paquetes (eggs). Se adhiere en su mayoría al estándar R5RS, con soporte experimental para R7RS, y extensiones adicionales que implementan estándares SRFI y utilidades exclusivas.

Debido a que, por el momento, este programa carece de una interfaz interactiva, es necesario ejecutarlo con el intérprete de CHICKEN para poder ejecutar los métodos disponibles. Para ejecutar el programa, se deben escribir los siguientes comandos en una terminal:

chicken-install srfi-1 srfi-13 srfi-28 list-utils
csi cube.scm