sábado, 21 de mayo de 2016

Espiral de Ulam

Un día durante una conferencia aburrida, un matemático llamado Stalisnaw Ulam jugando como no con los números, comenzó a dibujar en un papel el número 1 y girando alrededor de él en el sentido contrario a las agujas del reloj, siguió escribiendo el resto de números naturales consecutivamente formando así la espiral que lleva su nombre creando un cuadrado de n x n. Esta espiral tiene una particularidad y es que los números primos tienden a alinearse en diagonales. He aquí un ejemplo de como se forma, una espiral de 7 x 7 y una muestra mayor con los números primos remarcados:



37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 5 4 3 12 29
40 19 6 1 2 11 28
41 20 7 8 9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49
Espiral de Ulam de orden 7

Espiral de Ulam con 142000 iteraciones

Por otra parte desde el punto de vista algorítmico, formar una espiral mediante código es otro reto, se puede hacer de múltiples formas, pero en concreto se me ha ocurrido crear un algoritmo de creación de la espiral y poder así implementar una ordenación con java implementado la interfaz Comparator y Comparable.
Para crear la espiral, lo primero determino la posición inicial del 1 dentro del cuadrado antes de formarlo. Esto es fácil, obtenemos el cuadrado del mayor impar y el valor de la mitad de los lados correspondería a las coordenadas x,y.
El paso siguiente sería rotar desde el 1 en el sentido de las agujas del reloj, formando cuadrados de n x n almacenando su valor en una clase que guardará las coordenadas y el valor de cada posición; este objeto, lo salvaremos en un ArrayList.
Como las coordenadas se van agregando en este orden en el ArrayList , una vez creada la espiral tendremos que ordenar las coordenadas para visualizarla en pantalla.

¿Qué clases usaremos?
Una clase Coordinate que almacena tres atributos, los valores de x, y y el valor de la coordenada. Implementa interface Comparable<Coordinate>, por tanto debe contener el método compareTo .
Una clase que implementa la interfaz Comparator<Coordinate>, por tanto debe implementar obligatoriamente el método compare y dentro de este llamaría al método compareTo de la clase Coordinate.


Diagrama de clases

¿Cómo funciona el algoritmo?
Del siguiente modo:
  • Iteramos n veces como cuadrados alrededor del 1 tengamos que dibujar
  • Iteramos 4 veces por cada uno de estos cuadrados, ya que un cuadrado tiene 4 lados y lo que haremos es decirle con esta iteración es la siguiente coordenada de destino donde tiene que asignarle un valor
  • Iteramos n veces por cada lado para escribir n números
Y una vez creada la espiral, ¿como ordenamos el ArrayList?
Una vez creada la espiral, debemos leer el ArrayList y visualizarlo en pantalla, pero antes hay que ordenarlo de modo que la primera coordenada sea la (0,0), la segunda (0,1), las siguientes (0,2)....(0,6), (1,0), (1,1)....(1,6),(2,0),.... hasta la (6,6) y para ello dentro del método compareTo de la clase Coordinate.
Una vez ordenada el ArrayList, pasamos a imprimirla en pantalla con el método toString() iterando por la colección con un for con la salvedad de pasar a una nueva línea cada vez que se alcance el valor de n para formar el cuadrado.

Para otro día, un generador de espiral de Ulam con los números primos resaltados.
Aquí os dejo el código fuente de Java.

Un saludo

"Una ecuación no tiene para mí ningún significado a menos que exprese un pensamiento de Dios"
Srinivasa Ramanujan
package espiralulamproject;

/******************************************************
 *  @author:    Joaquín Martínez Rus (c) 2016
 *  @version:   1.0 
 *  File:       Coordinate.java
 *  Created:    19/05/2016
 *  Project:    Ulam Spiral. 
 *  Comments:   Clase Coordinate. Clase con coordenadas y valor asignados
 *              
 *******************************************************/
public class Coordinate implements Comparable{
    
    // 
    
    /**
     * Inicia una nueva instancia de la clase Coordenada
     */
    public Coordinate(){
      this.x=0;
      this.y=0;
      this.value=0;
    }
    
    /**
     * Inicia una nueva instancia de la clase Coordenada
     * @param _coor Coordenada
     */
    public Coordinate(Coordinate _coor){
      this.x=_coor.x;
      this.y=_coor.y;
      this.value=_coor.value;
    }
    
    /**
     * Inicia una nueva instancia de la clase Coordenada
     * @param _x
     * @param _y 
     */
    public Coordinate(int _x, int _y){
        this.x=_x;
        this.y=_y;
        this.value=0;
    }
    
    //  
    
    // 
    
    int x;
    int y;
    int value;
    
    //  
    
    // 


    /**
     * Obtiene una nuea coordenada a partir del origen
     * @param coordinate Coordenada
     * @return Coordenada
     */
    public Coordinate clone(Coordinate coordinate){
        return new Coordinate(coordinate.x, coordinate.y);
    }
    
    /**
     * Obtiene la Coordenada textual
     * @return Cadena de texto con la coordenada
     */
    @Override 
    public String toString(){
        return "(" + x + ", " + y + ") = " + this.value;
    }
    
    /**
     * Ordena dos coordenadas por su valor x e y
     * @param _coor Coordenada
     * @return Entero
     */
    @Override
    public int compareTo(Coordinate _coor) {
        int result=0;
        if (this.x <_coor .x="" else="" if="" result="-1;" this.x=""> _coor.x) {
            result= 1;
        }
        else {
            if (this.y <=_coor.y) {
                result= -1;
            }
            else {
                result= 1;
            }
        }
        return result;
    }
    
    //  
}




package espiralulamproject;
import java.util.Comparator;


/******************************************************
 *  @author:    Joaquín Martínez Rus (c) 2016
 *  @version:   1.0 
 *  File:       SpiralComparator.java
 *  Created:    19/05/2016
 *  Project:    Ulam Spiral. 
 *  Comments:   Clase SpiralComparator. 
 *              Clase que implementa Comparator 
 *******************************************************/
public class SpiralComparator implements Comparator<Coordinate> {
    @Override
    public int compare(Coordinate o1, Coordinate o2) {
        return o1.compareTo(o2);
    }
}






package espiralulamproject;
import java.util.ArrayList;


/******************************************************
 *  @author:    Joaquín Martínez Rus (c) 2016
 *  @version:   1.0 
 *  File:       EspiralUlam.java
 *  Created:    19/05/2016
 *  Project:    Ulam Spiral. 
 *  Comments:   Clase EspiralUlam
 *              
 *******************************************************/
public class EspiralUlam {
    
    // 
    
    /**
     * Inicia unanueva instancia de la clase Espiral de Ulam
     * @param num Número máximo
     */ 
     public EspiralUlam(int num){
         baseNumber=getBaseNumber(num);
         maxNumber=getMaxNumber(baseNumber);
         firstNumber=getFirstNumbers(maxNumber,baseNumber);
         getFirstCoordinate();
         firstCoordinate.value=1;
         coordinates.add(firstCoordinate);
         setSpiral( new Coordinate(firstCoordinate));
     }
    // 
    
    // 
    
     int firstNumber;
     int baseNumber;
     int maxNumber;
     Coordinate firstCoordinate;
     public ArrayList<Coordinate> coordinates=new ArrayList();
    
    // 
    
    // 
    
    /**
     * Obtiene el resultado de la espiral
     * @return Cadena de texto 
     */ @Override
     public String toString(){
         this.sort();
         int count=1;
         String textTemp=" ";
         String textOut="";
         for (Coordinate coordinate : coordinates) {            
              textTemp = count % baseNumber == 0?"\n":"\t";            
              textOut += coordinate.value + textTemp;
              count ++;
         }
         return textOut;
     }
    
    // 
    
    // 
    
    /**
     * Ordena el arrayList de números
     */ 
     private void sort(){         
         coordinates.sort(new SpiralComparator());        
     }
    
    /**
     * Obtiene el número base de la Espiral
     * @param number Número solicitado
     * @return Valor entero
     */
     private int getBaseNumber(int number){
         int n= (int)Math.sqrt((double)(number))+1;
         if (n%2==0) {
             n++;
         }
         return n;
     }
    
    /**
     * Obtiene el máximo número de la Espiral
     * @param number Número solicitado
     * @return Valor entero
     */
     private int getMaxNumber(int number){
         return number * number;
     }
    
    /**
     * Obtiene el primer número de la Espiral
     * @param iMaxNumber Máximo número de la espiral
     * @param ibaseNumber Número base de la espiral
     * @return Valor entero
     */ 
     private int getFirstNumbers(int iMaxNumber, int ibaseNumber){
         return iMaxNumber - 2*(ibaseNumber-1);
     }  
    
    /**
     * Obtiene la oordenada central de la espiral
     */
     private void getFirstCoordinate(){
         firstCoordinate=new Coordinate(baseNumber /2, baseNumber/2);
     }
    
    /**
     * Calcula la espiral de Ulam
     * @param _coor Coordenada central
     */
     private void setSpiral(Coordinate _coor){
         Coordinate temp=_coor;
        
         int lastNumber=1;
         for (int impar = 1; impar < baseNumber; impar +=2) {
              temp.x++;
              temp.y++;
              for (int lado = 0; lado < 4; lado++) {
              // 4 veces. una por lado del cuadrado
                  for (int i = 0; i <= impar; i++) {
                       temp.value= ++lastNumber;                      
                       coordinates.add(nextCoordinate(lado, temp));
                  }
              }  
         }       
     }
    
    /**
     * Obtiene la siguiente coordenada de la espiral
     * @param n Lado del cuadrado
     * @param _coor Coordenada de cálculo
     * @return Coordenada
     */
     private Coordinate nextCoordinate(int n, Coordinate _coor){
         switch (n) {
             case 0:
                 // UP. substract 1 to x
                 _coor.x--;
                 break;
             case 1:
                 //LEFT. substract 1 to y
                 _coor.y--;
                 break;
             case 2:
                 //DOWN. add 1 to x
                 _coor.x++;
                 break;
             case 3:
                 //RIGHT. add 1 to y
                 _coor.y++;
                 break;
         }
         return new Coordinate(_coor);
     }
     
}

No hay comentarios:

Publicar un comentario