Apuntes de Algoritmos y Programación

Multiprocesamiento recursivo en JAVA 7

2011-08-11T20:00:00.005-05:00

Una de las estrategias de diseño de algoritmos más comunes es la de "divide y vencerás", en la cual, un problema de tamaño relativamente grande se divide recursivamente en problemas más pequeños que son resueltos de la misma manera hasta que se encuentre un tamaño de problema mínimo que se resuelva de forma directa. Un ejemplo típico de problemas que pueden ser resueltos con este enfoque es el algoritmo de ordenación rápida o QuickSort (ver entrada dedica a este algoritmo aquí).

En la nueva versión de JAVA se ha hecho disponible una nueva funcionalidad que permite la ejecución de algoritmos del estilo "divide y vencerás" en múltiples hilos de ejecución que son asignados entre los diferentes procesadores de la máquina. En el siguiente ejemplo se presenta una versión modificada levemente del algoritmo de ordenación rápida para utilizar esta funcionalidad:

import java.util.concurrent.*;

public class Ordenador extends RecursiveAction {
    int[] v;        // El arreglo a ordenar
    int   inicio;   // Posición inicial desde la que se va a ordenar
    int   fin;      // Posición final hasta la que se va a ordenar
    
    Ordenador(int[] x, int i, int f) {
        v      = x;
        inicio = i;
        fin    = f;
    }
    
    // Este es el método que se ejecuta cada vez que se crea un hilo de ejecución recursiva
    public void compute() {         
        if(inicio >= fin ) return ; // Cuando el arreglo tiene un elemento está ordenado y termina el proceso.
        int pivote = inicio;        // Se selecciona como pivote el primer elemnto
        int izq = inicio + 1 ;      // Apuntador izquierdo
        int der = fin ;             // Apuntador derecho
        while(izq < der) {          // Este ciclo se realiza mientras los apuntadores no se hayan cruzado
            while(izq<=fin      && v[izq]< v[pivote]) izq++;    //  Si el elemento izquierdo es menor que el pivote avanza
            while(der>=inicio+1 && v[der]>=v[pivote]) der--;    //  Si el elemento derecho es mayor que el pivote, retrocede
            if(izq < der ) {        //  Si los apuntadores no se han cruzado se intercambian los elementos derecho e izquierdo
                int tmp = v[der];
                v[der] = v[izq]; 
                v[izq] = tmp;
            }   // fin if
        }   // fin while
        // Se intercambian el valor del pivote con el valor del apuntador derecho
        int tmp   = v[der];
        v[der]    = v[pivote];
        v[pivote] = tmp;
        //  Se llaman recursivamente los objetos que van a ordenar los dos subvectores
        invokeAll(new Ordenador(v, inicio, der-1), 
                  new Ordenador(v, der+1, fin));
    }
    
    public void quickSort(int inicio, int fin) {
        if(inicio >= fin ) return ; // Cuando el arreglo tiene un elemento está ordenado
        int pivote = inicio;        // Se selecciona como pivote el primer elemnto
        int izq = inicio + 1 ;
        int der = fin ;
        while(izq < der) {
            while(izq<=fin      && v[izq]< v[pivote]) izq++;
            while(der>=inicio+1 && v[der]>=v[pivote]) der--;
            if(izq < der ) {
                int tmp = v[der];
                v[der] = v[izq]; 
                v[izq] = tmp;
            }
        }
        int tmp   = v[der];
        v[der]    = v[pivote];
        v[pivote] = tmp;
        quickSort(inicio, der-1);
        quickSort(der+1, fin);
    }
}

Para probar el uso de esta clase se crea una clase diferente que contenga el método main, así como la creación del vector y la invocación del proceso. En este programa se prueban los tiempos de ejecución obtenidos para diferentes tamaños de problema con los métodos recursivo tradicional y el nuevo método multiproceso de Java 7:

import java.util.*;
import java.util.concurrent.*;

public class TestFork {
    static Random rnd = new Random();       // Generador de números aleatorios
    // Método para crear un vector de números enteros aleatorios
    public static int[] getVector(int N) {  
        int[] v = new int[N];
        for(int i=0; i<N; i++) v[i]=rnd.nextInt(2*N);
        return v;
    }
    
    public static void main(String[] args) {
        final int MAX_SIZE = 500_000_000;
        int size = 1;                                           // tamaño del vector a crear
        System.out.println("Prueba con método recursivo tradicional");
        while(size < MAX_SIZE) {                                // Mientras el tamaño no es mayor al máximo
            int[] v = getVector(size);      
            Ordenador     ord = new Ordenador(v,0,v.length-1);  // Se crea el objeto Ordenador
            long  t1 = System.currentTimeMillis();              // Tiempo de inicio del proceso
            ord.quickSort(0, v.length-1);                       // Invocación de la ordenación con el método recursivo simple
            long  t2 = System.currentTimeMillis();              // Tiempo final del proceso
            double t = (t2-t1)/1000.0;                          // Tiempo real
            System.out.printf("%,20d %20.4f %n", size, t);      // Tamaño del vector y el tiempo requerido para ordenarlo con el viejo modelo
            size*=2;
        } // fin while
        
        System.out.println("\nPrueba con método recursivo multiproceso");
        System.out.println("Numero de procesadores disponibleS: "+Runtime.getRuntime().availableProcessors());
        size=1;
        while(size < MAX_SIZE) {                                // Mientras el tamaño no es mayor al máximo
            int[] v = getVector(size);      
            Ordenador     ord = new Ordenador(v,0,v.length-1);  // Se crea el objeto Ordenador
            long  t1 = System.currentTimeMillis();              // Tiempo de inicio del proceso
            v = getVector(size);                                // Crea un vector del mismo tamaño
            ForkJoinPool pool = new ForkJoinPool();             // Pool de procesos
            pool.invoke(ord);                                   // Invocación del pool de procesos
            long  t2 = System.currentTimeMillis();              // Tiempo final del proceso
            double t = (t2-t1)/1000.0;                          // Tiempo real
            System.out.printf("%,20d %20.4f %n", size, t);      // Tamaño del vector y el tiempo requerido para ordenarlo con el viejo modelo
            size*=2;
        } // fin while
    }
}

Evaluador de expresiones en posfijo

2011-08-03T21:31:00.001-05:00

Este programa presenta un pequeño evaluador de expresiones en posfijo que son leídas una a una. Se pretende con él dar una breve introducción al curso de Estructuras de Datos 2, y de paso, revisar las nuevas funcionalidades de JAVA 7, entre las cuales están el uso del operador diamante y la evaluación de cadenas de caracteres en la instrucción switch.

import javax.swing.*; 
import java.util.*;
public class Evaluador {
    public static void main(String[] args) {
        int n;  // número de cadenas a evaluar
        String respuesta = JOptionPane.showInputDialog("Cuántos elementos va a procesar" ); 
        n = Integer.parseInt(respuesta); 
        // Evaluar las cadenas
        for(int i=0; i<n; i++) {
            Stack<Double> pila = new java.util.Stack<>();   // Nuevo en JAVA 7 - Operador diamante
            // Leer expresion
            String expresion = JOptionPane.showInputDialog("Expresión a evaluar" ); 
            // Evaluar expresion
            expresion        = expresion.trim();        // Elimina espacios al comienzo y al final
            String[]     exp = expresion.split("\\s+"); // Para separar por secuencias de uno o más espacios
            for(String x: exp) {                        // Para cada cadena 'x' del arreglo exp
                try {
                    double valor = Double.parseDouble(x);
                    pila.push(valor);                   // Meter valor en la pila
                }
                catch(NumberFormatException ex) {       // Excepcion si la cadena 'x' no se pudo pasar a número
                    double b = pila.pop();
                    double a = pila.pop();
                    switch(x) {         // NUEVO EN JAVA 7 - Evaluación de cadenas en los switch
                        case "+"    :   pila.push(a+b); break;
                        case "-"    :   pila.push(a-b); break;
                        case "*"    :   pila.push(a*b); break;
                        case "/"    :   pila.push(a/b); break;
                    } // end switch
                } // end catch
            } // end for
            // Mostrar respuesta
            JOptionPane.showMessageDialog(null,pila.pop(), "Respuesta", JOptionPane.PLAIN_MESSAGE);
        } // end for
    }
}

Índice TIOBE de Lenguajes de Programación para Julio de 2011

2011-08-02T09:11:00.001-05:00

Ya se encuentra disponible el índice de popularidad de lenguajes de programación TIOBE para agosto de 2011. La información completa se encuentra en la página http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html

Verificación de Números Vampiros

2011-07-28T09:13:00.000-05:00

Con este programa se pretende evaluar si cuatro dígitos recibidos forman un número vampiro:

public class Test1 {
    public static void testVampiro(int d1, int d2, int d3, int d4) {
        // Este método recibe cuatro dígitos y verifica en todas las posibles parejas de números
        // si la multiplicación de dos de ellas es igual a alguno de los números que se generan
        // con los 4 dígitos
        
        int[] v = { d1, d2, d3, d4 } ; // Se crea un vector con los 4 dígitos leídos
        int[] posibles = new int[24] ; // Con 4 dígitos solo se pueden formar 24 posibles valores 
        int   cont     = 0;
        int   a,b,c;
        boolean haySolucion = false;
        
        for(int i=0; i<v.length; i++) {
            for(int j=0; j<v.length; j++) {
                if(v[i]==v[j]) continue;  // No se pueden repetir
                for(int k=0; k<v.length; k++) {
                    if(v[k]==v[i]||v[k]==v[j]) continue;    // No se puede repetir
                    for(int l=0; l<v.length; l++) {
                        if(v[l]==v[i]||v[l]==v[j]|| v[l]==v[k]) continue;   // No se puede repetir
                        posibles[cont++] = v[i]*1000+v[j]*100+v[k]*10+v[l];
                    } // fin for l
                } // fin for k
            } // fin for j
        } // fin for i
        // Para probar los numeros posibles usar esta instrucción:
        // for(int x: posibles) System.out.println(x);
        
        // Para generar las parejas se hace el siguiente ciclo:
        ciclo:
        for(int i=0; i<v.length; i++) {
            for(int j=0; j<v.length; j++) {
                if(v[i]==v[j]) continue;  // No se pueden repetir
                a = v[i]*10 + v[j];       // Se obtiene el primer valor de dos dígitos
                for(int k=0; k<v.length; k++) {
                    if(v[k]==v[i]||v[k]==v[j]) continue;    // No se puede repetir
                    for(int l=0; l<v.length; l++) {
                        if(v[l]==v[i]||v[l]==v[j]|| v[l]==v[k]) continue;   // No se puede repetir
                        b = v[k]*10+v[l];   // Se obtiene el segundo valor de dos digitos
                        c = a*b ;           // Se obtiene la multiplicación de los dos valores
                        // Se verifica si el número generado está entre los posibles resultados
                        // y de ser así se escribe la respuesta y se termina el proceso
                        for(int x: posibles) {
                            if(c==x) {
                                System.out.println("Respuesta encontrada: "+a+" x " +b+" = "+c);
                                haySolucion=true;
                                break ciclo;
                            }  // fin if
                        } // fin for x
                    } // fin for l
                } // fin for k
            } //fin for j
        } // fin for i
        if(!haySolucion) System.out.println("No hay un numero vampiro con los digitos " + d1+", "+d2+", "+d3+" y "+d4);
        
    }
    public static void main(String[] args) {
        testVampiro(1,2,3,4);
        testVampiro(1,3,9,5);
        testVampiro(3,9,1,5);
    }
}

Cálculo del Tiempo de Ejecución de un Método

2011-02-21T08:43:00.001-05:00

Para facilitar el análisis de un programa, se puede utilizar una forma genérica, mediante el uso del paquete java.lang.reflect para calcular el tiempo de ejecución de cualquier función.

En este caso, el método ejecutar recibe el nombre de la clase, el nombre del método y el parámetro que recibe dicho método y retorna el tiempo que tarda el método en ser ejecutado.

import java.lang.reflect.*;

public static double ejecutar(String nombreClase, String nombreMetodo, Object parametro) throws Exception {
        double t1, t2;
        t1 = System.currentTimeMillis();
        Class    clase = Class.forName(nombreClase);
        Method  metodo = clase.getMethod(nombreMetodo,parametro.getClass());
        metodo.invoke(null, parametro);
        t2 = System.currentTimeMillis();
        return (t2-t1)/1000.0;
    }

En este ejemplo se va a calcular el tiempo requerido por el método de ordenación por inserción de la clase Algoritmos sobre un array de 10000 elementos:

public class TestEjecutar {
    public static void main(String[] args) throws Exception {
        int[] v = Algoritmos.crearVector(10000);
        System.out.println(Algoritmos.ejecutar("Algoritmos", "ordenacionInsercion", v));
    }
}

Maquina Virtual en JAVA

2011-02-14T09:56:00.001-05:00

Para crear la primera versión de una máquina virtual en lenguaje JAVA, basándonos en el modelo de Von Neumann, requerimos definir las estructuras de memoria que contendrán la lista de instrucciones a ser ejecutadas, la pila, la lista de constantes, la lista de variables y la tabla de valores de dichas variables.

Para la lista de instrucciones a ser ejecutada se crea una clase llamada Instrucción que cuenta básicamente con dos atributos, el tipo de instrucción y el índice del elemento en su respectiva tabla que va a ser operado con dicha instrucción. Los diferentes tipos de instrucción se definen con una enumeración así:

package maquinavirtual;
public enum TipoInstruccion {
    PUSH,
    vPUSH,
    nPUSH,
    STORE,
    ADD,
    SUB,
    DIV,
    MUL,
    GT,
    GE,
    LE,
    LT,
    EQ,
    NE,
    JZERO,
    GOTO,
    WRITE
}

Por su parte, la clase Instrucción queda definida de la siguiente manera:

package maquinavirtual;
public class Instruccion {
    TipoInstruccion tipo;
    int             operando;

    Instruccion(TipoInstruccion t, int op) {
        tipo=t;
        operando=op;
    }

    Instruccion(TipoInstruccion t) {
        this(t,-1);
    }

    public String toString() {
        return String.format("%-10s %d", tipo, operando);
    }
}

La clase MaquinaVirtual, definida a continuación, define un lista o vector de objetos de la clas Instruccion que representará la lista de instrucciones a ser ejecutada; una pila de objetos Double para manejar la pila; una lista de String para la lista de variables definidas; una lista de Doubles para las constantes y un Mapa de Integer y Double para manejar los valores de las diferentes variables.

Esta clase tiene dos métodos principales: el método cargarArchivo que se encarga de leer un archivo de texto que trae codificado un programa en el lenguaje de la máquina virtual y alimenta la lista de variables, la lista de constantes y la lista de instrucciones a ser ejecutadas; y por otra parte está el método ejecutar que se encarga de leer la lista de instrucciones y recorrerla ejecutándolas.

package maquinavirtual;

import java.util.*;
import java.io.*;

public class MaquinaVirtual {
    Stack<Double>                     pila = new Stack<Double>();       // Pila
    Vector<Instruccion> listaInstrucciones = new Vector<Instruccion>(); // Programa a ejecutar
    Vector<Double>      listaNumeros       = new Vector<Double>();      // Tabla de numeros
    Vector<String>      listaVariables     = new Vector<String>();      // Tabla de variables
    Map<Integer,Double> tablaVariables     = new HashMap<Integer,Double>();  // Valores de las variables

    public void mostrarValores() {
        System.out.println("\nLista de Instrucciones");
        for(Instruccion i: listaInstrucciones) System.out.println(i);
        System.out.println("\nLista de Variables");
        for(String i: listaVariables) System.out.println(i);
        System.out.println("\nLista de Numeros");
        for(Double i: listaNumeros) System.out.println(i);
    }

    public void ejecutar() {
        for(int i=0; i<listaInstrucciones.size(); i++) {
            Instruccion  inst = listaInstrucciones.elementAt(i);
            //System.out.println("Inst: " +inst);
            TipoInstruccion t = inst.tipo;
            int            op = inst.operando;
            double          a, b;
            switch(t) {
                case ADD:   b=pila.pop(); a=pila.pop(); pila.push(a+b); break;
                case SUB:   b=pila.pop(); a=pila.pop(); pila.push(a-b); break;
                case MUL:   b=pila.pop(); a=pila.pop(); pila.push(a*b); break;
                case DIV:   b=pila.pop(); a=pila.pop(); pila.push(a/b); break;
                case GT:    b=pila.pop(); a=pila.pop(); pila.push(a>b ?1.0:0.0); break;
                case GE:    b=pila.pop(); a=pila.pop(); pila.push(a>=b?1.0:0.0); break;
                case LT:    b=pila.pop(); a=pila.pop(); pila.push(a<b ?1.0:0.0); break;
                case LE:    b=pila.pop(); a=pila.pop(); pila.push(a<=b?1.0:0.0); break;
                case EQ:    b=pila.pop(); a=pila.pop(); pila.push(a==b?1.0:0.0); break;
                case NE:    b=pila.pop(); a=pila.pop(); pila.push(a!=b?1.0:0.0); break;
                case WRITE: System.out.println(pila.pop()); break;
                case nPUSH: pila.push(listaNumeros.elementAt(op)); break;
                case vPUSH: pila.push(tablaVariables.get(op)); break;
                case STORE: tablaVariables.put(op, pila.pop()); break;
                case GOTO:  i=(int) (listaNumeros.get(op)-2); break;
                case JZERO: if(pila.pop()==0.0) i=(int) (listaNumeros.get(op)-2); break;

            }
        }
    }

    public void cargarArchivo(String nombreArchivo) {
        try {
            BufferedReader in = new BufferedReader(new FileReader(nombreArchivo));
            Instruccion     inst=null;
            TipoInstruccion t=null;
            int             posicion=-1;
            while(true) {
                String linea = in.readLine();
                if(linea==null) break;
                String[] elementos = linea.trim().split("\\s+");

                try {
                    t = TipoInstruccion.valueOf(elementos[0].toUpperCase());
                    if(elementos.length==1) {
                        inst = new Instruccion(t);
                        listaInstrucciones.add(inst);
                    }
                    else if(elementos.length==2) {
                        // El segundo componente es un nÃºmero
                        if(elementos[1].matches("\\d+(\\.\\d*)?")) {
                            Double numero = Double.parseDouble(elementos[1]);
                            if(!listaNumeros.contains(numero)) listaNumeros.add(numero);
                            posicion=listaNumeros.indexOf(numero);
                            if(t==TipoInstruccion.PUSH) t=TipoInstruccion.nPUSH;
                        }
                        // Si el segundo componente es una variable
                        else if(elementos[1].matches("\\p{Alpha}\\w*")) {
                            if(!listaVariables.contains(elementos[1])) listaVariables.add(elementos[1]);
                            posicion=listaVariables.indexOf(elementos[1]);
                            if(t==TipoInstruccion.PUSH) t=TipoInstruccion.vPUSH;
                        }
                        else {
                            System.err.println("Elemento desconocido: " +  elementos[1]);
                            System.exit(0);
                        }
                        inst = new Instruccion(t, posicion);
                        listaInstrucciones.add(inst);
                    }
                }
                catch(IllegalArgumentException ex) {
                    System.err.println("Error, instruccion no reconocida: " + elementos[0]);
                    System.exit(0);
                }
            }
        }
        catch(Exception x) {
            System.err.println("Error de algun tipo: " + x.getMessage());
        }
    }

}

Indice Tiobe para Enero de 2011

2011-02-03T09:35:00.002-05:00

Aplicaciones Web con OpenXava

2011-01-12T13:52:00.001-05:00

De acuerdo con Wikipedia, OpenXava es un marco de trabajo de código abierto para desarrollar aplicaciones de gestión de una forma efectiva. Permite el desarrollo rápido y fácil de mantenimientos y listados pero, a su vez, es lo suficientemente flexible para desarrollar complejas aplicaciones de gestión de la vida real como contabilidad, facturación, gestión de personal, nóminas, gestión de almacenes, etc.

Actualmente OpenXava genera aplicaciones web Java (J2EE/JavaEE), que pueden ser desplegadas en cualquier portal Java (JSR-168) como una aplicación de portlets.OpenXava es una herramienta libre.

Para poder trabajar con la aplicación de demostración es necesario descargar el programa desde el sitio web http://www.openxava.org/web/guest/home y, preferiblemente el ambiente de desarrollo de Eclipse para J2EE desde el sitio http://www.eclipse.org/downloads/

Siguiendo las instrucciones del mismo sitio web, es fácil poner en producción la aplicación web de ejemplo, así como es sorprendente ver que toda la aplicación de ejemplo queda reducida a estas dos clases en JAVA, ya que OpenXava provee automáticamente el resto:

package org.openxava.escuela.modelo;
 
import javax.persistence.*;
import org.openxava.annotations.*;
 
@Entity
public class Alumno {
    @Id @Column(length=2) @Required private int numero;
    @Column(length=40) @Required private String nombre;
    @ManyToOne @DescriptionsList private Profesor profesor;
 
    public int getNumero() { return numero; }
    public void setNumero(int numero) { this.numero = numero; }
    public String getNombre() { return nombre; }
    public void setNombre(String nombre) { this.nombre = nombre; }
    public Profesor getProfesor() { return profesor; }
    public void setProfesor(Profesor profesor){ this.profesor = profesor; }
}

package org.openxava.escuela.modelo;
 
import java.util.*;
import javax.persistence.*;
import org.openxava.annotations.*;
 
@Entity
public class Profesor {
    @Id @Column(length=5) @Required private String codigo;
    @Column(length=40) @Required private String nombre;
    @OneToMany(mappedBy="profesor") private Collection<Alumno> alumnos;
 
    public String getCodigo() { return codigo; }
    public void setCodigo(String codigo) { this.codigo = codigo;}
    public void setAlumnos(Collection<Alumno> alumnos) { this.alumnos = alumnos; }
    public void setNombre(String nombre) { this.nombre = nombre; }
    public String getNombre() { return nombre; }
    public Collection<Alumno> getAlumnos() { return alumnos; }
}

En el siguiente video se puede encontrar una breve introducción a OpenXava provista por el grupo de AltainetGroup:

Openxava + mysql + Eclipse from alta inet on Vimeo.

Top de lenguajes de programación para 2011

2010-12-22T12:15:00.000-05:00

De acuerdo con el portal especializado eweek.com, y con base en la información de TIOBE anteriormente relatada, la siguiente es la lista de los 18 principales lenguajes de programación para el año 2011:

JAVA
C
C++
C#
JavaScript
Perl
PHP
VisualBasic
Python
Ruby
Objective C
ActionScript
Groovy
Go
Scale
Erlang
Clojure
Visual F++

Cálculo de Frecuencias - Problema UVA 499

2010-12-20T23:26:00.000-05:00

Este problema busca calcular el o los caracteres que más se repiten en una cadena. El enunciado está expuesto en la página http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=440

import java.io.*;

class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String args[]) throws Exception {
        Main myWork = new Main();   // create a dinamic instance
        myWork.Begin();             // the true entry point
        System.exit(0);
    }

    void Begin() throws Exception {
        while(true) {
            String linea = in.readLine();
            if(linea==null) break;
            System.out.println(procesarCadena(linea));
        }
    }

    public String procesarCadena(String cadena) {
        cadena=cadena.replaceAll("[^\\p{Alpha}]", "");
        char[] arreglo = cadena.toCharArray();
        byte[] contador = new byte[256];
        for(char c: arreglo) contador[c]++;
        int max=0;
        for(int i=0; i<contador.length; i++) if(contador[i]>max) max=contador[i];
        String respuesta="";
        for(int i=0; i<contador.length; i++) if(contador[i]==max) respuesta+=(char) i;
        return respuesta+" "+max;
    }
}

Calculo de Salarios - Problema UVA 10295

2010-12-17T14:12:00.000-05:00

Este problema calcula el valor del salario para un cargo teniendo en cuenta la ocurrencia de determinadas palabras claves dentro del texto de la descripción del cargo. El enunciado del problema se encuentra en la dirección http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1236

import java.io.*;
import java.util.*;

class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String args[]) throws Exception {
        Main myWork = new Main();   // create a dinamic instance
        myWork.Begin();             // the true entry point
        System.exit(0);
    }

    void Begin() throws Exception {
        Map<String, Integer> mapa = new HashMap<String, Integer>();
        String[] tmp = in.readLine().split("\\s+");
        int cantidadPalabras = Integer.parseInt(tmp[0]);
        int cantidadTextos   = Integer.parseInt(tmp[1]);
        for(int i=0; i<cantidadPalabras; i++) {
            tmp = in.readLine().split("\\s+");
            String keyword = tmp[0];
            int      costo = Integer.parseInt(tmp[1]);
            mapa.put(keyword, costo);
        }
        for(int i=0; i<cantidadTextos; i++) {
            String texto = "";
            while(true) {
                String linea = in.readLine();
                if(linea.charAt(0)=='.' && linea.length()==1) break;
                texto+=(" " + linea);
            }
            int salario = 0;
            tmp = texto.split(("\\s+"));
            for(String x: tmp) if(mapa.containsKey(x)) salario+=mapa.get(x);
            System.out.println(salario);
        }
    }
}

Números de Smith - Problema UVA 10042

2010-12-16T19:06:00.003-05:00

Básicamente, este problema busca encontrar números en los que la suma de sus dígitos sea igual a la suma de sus factores primos. El enunciado está en el enlace http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=983

import java.io.*;

class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String args[]) throws Exception {
        Main myWork = new Main();   // create a dinamic instance
        myWork.Begin();             // the true entry point
    }

    public int sumaDivisores(int n) {
        double raiz = Math.sqrt(n);
        int tmp = n;
        int respuesta=0;
        while(n%2==0) { respuesta+=2; n>>=1; }
        for(int i=3; i<=raiz; i+=2) {
            if(n%i==0) {
                respuesta+=sumaDigitos(i);
                n = n/i;
                i-=2;
            }
        }
        if(n!=tmp && n!=1) respuesta+=sumaDigitos(n);
        return respuesta;
    }

    public int sumaDigitos(int n) {
        int respuesta=0;
        while(n>0) {
            respuesta+=(n%10);
            n = n/10;
        }
        return respuesta;
    }

    public boolean esPrimo(long n) {
        double raiz = Math.sqrt(n);
        if(n==2) return true;
        if(n%2==0) return false;
        for(int i=3; i<=raiz; i+=2) if(n%i==0) return false;
        return true;
    }

    void Begin() throws Exception {
        int cont = 0;
        int numeroCasos = Integer.parseInt(in.readLine());
        while(cont<numeroCasos) {
            int numero = Integer.parseInt(in.readLine());
            while(true) {
                numero++;
                if(esPrimo(numero)) continue;
                if(sumaDigitos(numero)==sumaDivisores(numero)) {
                    System.out.println(numero);
                    cont++;
                    break;
                }
            }
        }
    }
}

Suma de Árbol - Problema UVA 112 - Versión 2

2010-12-15T20:32:00.000-05:00

Esta nueva versión trata de mejorar el desempeño reemplazando el uso de StringBuffers por operaciones con Strings, pero sigue dando más de los tres segundos en la evaluación de UVA:

import java.io.*;
import java.util.*;

class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String args[]) throws Exception {
        Main myWork = new Main();   // create a dinamic instance
        myWork.Begin();             // the true entry point
    }

    void Begin() throws Exception {
        String       archivo = "";
        String         linea = null;
        final int       SIZE = 256;
        int    valorBusqueda = 0;
        int[]          arbol;
        int[]          sumas;
        Scanner        input = null;
        while(true) {
            linea = in.readLine();
            if(linea==null) break;
            archivo+=linea;
        }
        while(archivo.length()>0) {
            input             = new Scanner(archivo);
            valorBusqueda     = input.nextInt();
            archivo           = archivo.replaceFirst(valorBusqueda+"","");
            String tmpCadena  = getCadena(archivo);
            archivo           = archivo.substring(tmpCadena.length());
            arbol             = new int[SIZE];
            sumas             = new int[SIZE];
            procesar(tmpCadena, arbol, sumas, 0);
            if(buscar(valorBusqueda, sumas)) System.out.println("yes");
            else System.out.println("no");
        }
    }

    void procesar(String cadena, int[] arbol, int[] sumas, int nodo) {
       if(cadena.matches("\\s*\\(\\s*\\)")) return;
       cadena        = cadena.trim().substring(1,cadena.length()-1);
       String numStr = "";
       int       pos = 0;
       while(cadena.charAt(pos)!='(') numStr+=cadena.charAt(pos++);
       cadena       = cadena.substring(numStr.length());
       arbol[nodo]  = Integer.parseInt(numStr.trim());
       sumas[nodo]  = arbol[nodo]+sumas[(nodo-1)/2];
       String h1Str = getCadena(cadena);
       cadena       = cadena.substring(h1Str.length());
       h1Str        = h1Str.trim();
       String h2Str = getCadena(cadena);
       cadena       = cadena.substring(h2Str.length());
       h2Str        = h2Str.trim();
       procesar(h1Str, arbol, sumas, 2*nodo+1 );
       procesar(h2Str, arbol, sumas, 2*nodo+2 );
       if(sumas[2*nodo+1]>0 || sumas[2*nodo+2]>0) sumas[nodo]=0;
    }

    String getCadena(String sb) {
        int       numIzq = 0;
        int          pos = 0;
        String respuesta = "";
        do {
            while (sb.charAt(pos) == ' ') respuesta += sb.charAt(pos++);
            if (sb.charAt(pos) == '(') numIzq++;
            if (sb.charAt(pos) == ')') numIzq--;
            respuesta += sb.charAt(pos++);
        } while (numIzq > 0);
        return respuesta;
    }

    boolean buscar(int valor, int[] vector) {
        for(int x: vector) if(valor==x) return true;
        return false;
    }
}

Suma de Árbol - Problema UVA 112

2010-12-14T21:40:00.001-05:00

En este problema se ingresan uno o varios árboles binarios en notación de lenguaje LISP y se espera determinar si alguna de las ramas que inician en la raiz y terminan en una hoja suman un valor dado para cada árbol.

El enunciado se encuentra en la dirección http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=48

import java.io.*;
import java.util.*;

class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String args[]) throws Exception {
        Main myWork = new Main();   // create a dinamic instance
        myWork.Begin();             // the true entry point
    }

    void Begin() throws Exception {
        String archivo = "";
        while(true) {
            String linea = in.readLine();
            if(linea==null) break;
            archivo+=linea;
        }
        while(archivo.length()>0) {
            Scanner input = new Scanner(archivo);
            int valorBusqueda = input.nextInt();
            archivo = archivo.replaceFirst(valorBusqueda+"","");
            StringBuffer tmp = new StringBuffer(archivo);
            String tmpCadena = getCadena(tmp);
            int[]   arbol = new int[256];
            int[]   sumas = new int[arbol.length];
            //System.out.println(tmpCadena);
            procesar(tmpCadena, arbol, sumas, 0);
            if(buscar(valorBusqueda, sumas)) System.out.println("yes");
            else System.out.println("no");
            archivo = tmp.toString();
        }
    }

    void procesar(String cadena, int[] arbol, int[] sumas, int nodo) {
       if(cadena.matches("\\(\\s*\\)")) return;
       cadena = cadena.trim();
       StringBuffer tmp1 = new StringBuffer(cadena);
       tmp1.deleteCharAt(tmp1.length()-1);
       tmp1.deleteCharAt(0);
       String numStr = "";
       while(tmp1.charAt(0)!='(') { numStr+=tmp1.charAt(0); tmp1.deleteCharAt(0); }
       arbol[nodo]=Integer.parseInt(numStr);
       sumas[nodo]=arbol[nodo]+sumas[(nodo-1)/2];
       String h1Str = getCadena(tmp1);
       String h2Str = getCadena(tmp1);
       procesar(h1Str, arbol, sumas, 2*nodo+1 );
       procesar(h2Str, arbol, sumas, 2*nodo+2 );
       if(sumas[2*nodo+1]>0 || sumas[2*nodo+2]>0) sumas[nodo]=0;
    }

    String getCadena(StringBuffer sb) {
       int       numIzq = 0;
       String respuesta = "";
       do {
           while(sb.charAt(0)==' ') sb.deleteCharAt(0);
           if(sb.charAt(0)=='(') numIzq++;
           if(sb.charAt(0)==')') numIzq--;
           respuesta+=sb.charAt(0);
           sb.deleteCharAt(0);
       } while(numIzq>0);
        return respuesta;
    }

    boolean buscar(int valor, int[] vector) {
        for(int x: vector) if(valor==x) return true;
        return false;
    }
}

Esta solución funciona con todos los casos de prueba pero se excede en el tiempo máximo de evaluación de tres segundos. Se esperan comentarios y sugerencias.

Cola de Equipo - Problema UVA 540

2010-12-13T18:27:00.002-05:00

El problema de colas de equipo se puede resolver en java utilizando una cola de colas. El enunciado del mismo se encuentra en el enlace http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=481

import java.io.*;
import java.util.*;

class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String args[]) throws Exception {
        Main myWork = new Main();   // create a dinamic instance
        myWork.Begin();             // the true entry point
    }

    void Begin() throws Exception {
        int cont = 0;
        while(true) {
            cont++;
            // Cada caso comienza con un numero de equipos t entre 1 y 1000
            int t = Integer.parseInt(in.readLine());
            if(t==0) break;                     // Si t=0, el proceso termina
            System.out.println("Scenario #" + cont);
            // En este mapa se relaciona cada elemento con el equipo al que pertenece
            Map<Integer, Integer> mapa = new HashMap<Integer, Integer>();
            // Para cada uno de los equipos
            for (int i=0; i<t; i++) {
                String[] tmp = in.readLine().split("\\s+");
                // El primer número de la línea es la cantidad de miembros del equipo
                int numMiembros = Integer.parseInt(tmp[0]);
                for (int j = 1; j<=numMiembros; j++) {
                    mapa.put(Integer.parseInt(tmp[j]), i);  // Cada miembro se guarda en el mapa
                }
            }
            String instruccion;
            Queue<Queue> colaE = new LinkedList<Queue>();   // Cola de colas
            do {
                // Cada renglón es una instruccion ENQUEUE, DEQUEUE o STOP
                String[] tmp = in.readLine().split("\\s+");
                instruccion = tmp[0];
                // Si es ENQUEUE la segunda parte de la instrucción es el valor a encolar
                if(instruccion.equals("ENQUEUE")) {
                    int valor  = Integer.parseInt(tmp[1]);  // Valor a encolar
                    int equipo = mapa.get(valor);           // Equipo al que pertenece
                    boolean flag = true;
                    // Identifica si en la cola hay algún miembro de su equipo
                    for (Queue<Integer> x : colaE) {    
                        if (x.isEmpty()) colaE.remove(x);
                        if (!x.isEmpty()) {
                            // Si hay un miembro del equipo se agrega al final de esa subcola
                            if (mapa.get(x.peek()) == equipo) {
                                x.add(valor);
                                flag = false;
                                break;
                            }
                        }
                    }
                    if(flag) {
                        // Si no hay miembros del equipo en la cola, crea una nueva subcola y se agrega
                        Queue<Integer> temporal = new LinkedList<Integer>();
                        temporal.add(valor);
                        colaE.add(temporal);
                    }
                }
                // Si es DEQUEUE se eliminan las subcolas vacías y se retira el primer elemento
                if (instruccion.equals("DEQUEUE")) {
                    while (colaE.peek().size() == 0) colaE.remove();
                    System.out.println(colaE.peek().poll());
                }
                if(instruccion.equals("STOP")) System.out.println();
            } while (!instruccion.equals("STOP"));
        }
    }
}

Paréntesis Balanceados - Problema UVA 673 - Groovy

2010-12-13T01:00:00.007-05:00

La solución en groovy al problema de paréntesis balanceados presentado anteriormente, simplifica parte del código, en lo concerniente a la definición de clases, importación de librerías de clases y la declaración de variables. Sin embargo, el código central de evaluación de una cadena es prácticamente el mismo que en java, con la excepción de la utilización de un arreglo para manejar la pila y la palabra "times" para la ejecución de un ciclo por un determinado número de veces:

def evaluarCadena = { cadena ->
    pila = []
    for(c in cadena) {
        if(c=='[' || c=='(') { pila = pila + c; continue }
        if(pila.size()==0) return false
        x = pila[-1]            // Obtiene el último elemeno
        pila[-1]="#"            // Reemplaza el último por "#"
        pila = pila-pila[-1]    // Elimina de la colección todos los "#"
        if(c==')' && x!='(' ) return false
        if(c==']' && x!='[' ) return false
    }
    if(pila.size() > 0) false
    else true
}

input = new BufferedReader(new InputStreamReader(System.in))
numeroCasos = Integer.parseInt(input.readLine());
numeroCasos.times {
    boolean respuesta = evaluarCadena(input.readLine());
    if(respuesta==true) System.out.println("Yes");
    if(respuesta==false) System.out.println("No");
}

Paréntesis Balanceados - Problema UVA 673

2010-12-12T20:46:00.000-05:00

Este problema busca identificar si una cadena conformada exclusivamente por paréntesis redondos y cuadrados está correctamente formada. La descripción del problema se encuentra en el sitio de UVA en la dirección: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=614

Para resolver el problema se recurre a una pila como estructura de datos en la que se guardan los paréntesis izquierdos que se van leyendo, y que deben ser extraídos correctamente cuando aparezcan los paréntesis derechos en la expresión a evaluar.

import java.io.*;
import java.util.*;

class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String args[]) throws Exception {
        Main myWork = new Main();   // create a dinamic instance
        myWork.Begin();             // the true entry point
    }

    void Begin() throws Exception {
        // En la primera línea de la entrada se lee el número de casos a evaluar
        int numeroCasos = Integer.parseInt(in.readLine());

        // Cada caso se evalúa en forma individual
        for(int i=0; i<numeroCasos; i++) {
            boolean respuesta = evaluarCadena(in.readLine().toCharArray());
            if(respuesta==true) System.out.println("Yes");
            if(respuesta==false) System.out.println("No");
        }
    }

    boolean evaluarCadena(char[] cadena) {
        // Una pila es la estructura ideal para la evaluación de cadenas balanceadas
        Stack<Character> cola = new Stack<Character>();
        for(char c: cadena) {
            // los paréntesis izquierdos se agregan a la pila, mientras que los derechos
            // requieren sacar el elemento opuesto de la pila, de lo contrario hay error.
            if(c=='[' || c=='(') { cola.push(c); continue; }
            if(cola.isEmpty()) return false;
            if(c==')' && cola.pop()!='(') return false;
            if(c==']' && cola.pop()!='[') return false;
        }
        if(!cola.isEmpty()) return false;
        else return true;
    }
}

Indice Tiobe para Noviembre de 2010

2010-12-06T18:00:00.008-05:00

El índice TIOBE para el mes de noviembre no muestra variaciones en la popularidad de los dos primeros puestos que continúan siendo para JAVA y C. Destacan el descenso de un puesto de PHP con respecto al año inmediatamente anterior, y el de dos puestos para VisualBasic y JavaScript.

El Don

2010-12-06T12:00:00.003-05:00

Un apunte de humor para todos los que esperan sus reportes de notas:

Evaluación de Expresiones en Groovy

2010-12-06T10:05:00.001-05:00

En groovy es posible evaluar una expresión escrita en una cadena de caracteres utilizando tan sólo la instrucción "evaluate". A continuación se presenta un ejemplo que muestra un pequeño formulario utilizando las características de SwingBuilder de groovy:

import groovy.swing.SwingBuilder
import javax.swing.*
import java.awt.*

swing = new SwingBuilder()
swing.edt {
    frame(title:'Frame', defaultCloseOperation:JFrame.EXIT_ON_CLOSE, pack:true, show:true) {
        gridLayout(cols:2, rows:4)
        label("Expresion a evaluar");       JTextField txtExp  = textField("")
        label("Valor de la variable X   "); JTextField txtVal  = textField("")
        label("Respuesta");                 JTextField txtResp = textField("")
        button(
            text:'Ok',
            actionPerformed: {
                x = Double.parseDouble(txtVal.getText())
                X = x
                txtResp.setText(evaluate(txtExp.getText())+"")
            }
        )
    }
}

Para probar el funcionamiento basta con escribir una expresión en java como por ejemplo: Math.pow(x,2)-3*x+1, un valor para la variable x y darle click al botón "Ok"

Números Primos en Groovy

2010-12-03T11:33:00.003-05:00

En este programa se genera una lista de 10 números primeros utilizando el lenguaje Groovy. Es importante recordar que Groovy es un lenguaje de desarrollo rápido que utiliza la funcionalidad y genera código que corre sobre la máquina virtual de java (Información en wikipedia)

def esPrimo = {
    n -> if(n==2) return true
    if(n%2==0) return false
    raiz = Math.sqrt(n)
    for(i=3; i<=raiz; i+=2) if(n%i==0) return false
    return true
}
Random rnd = new Random()
listaPrimos = []
while(listaPrimos.size < 10) {
    numero = rnd.nextInt(1000000)
    if(esPrimo(numero)) listaPrimos.add numero
}
println listaPrimos

El programa muestra varias cosas interesantes sobre la funcionalidad de groovy como son las siguientes:
- No se definen clases pues el objetivo del programa no implica la creación de objetos
- No se requieren los punto y comas (;) al final de cada instrucción
- No se deben declarar las variables
- Existe el tipo de datos lista, que internamente se forma a partir de un LinkedList
- No se debe importar el paquete java.util
- Los métodos no se deben declarar ni en su valor de retorno ni en los parámetros que reciben

Transformacion de Cadenas - El camino a seguir

2010-11-28T23:50:00.001-05:00

En el siguiente programa se complementa la clase ProblemaDistanciaCadenas para agregar un método que recorre la matriz de distancias para encontrar el camino de transformaciones que lleva de una cadena a la otra. Este método, que recibe el nombre de getCamino, recorre hacia atrás la matriz, mirando los elementos adyacentes que sean menores o que el elemento actual.

public class ProblemaDistanciaCadenas {
    String cadena1;
    String cadena2;
    int[][] distancia;

    ProblemaDistanciaCadenas(String c1, String c2) {
        cadena1=c1;
        cadena2=c2;
        distancia=new int[cadena1.length()+1][cadena2.length()+1];
    }

    public void mostrarMatriz() {
        System.out.print("      ");
        for(int i=0; i<cadena2.length(); i++) System.out.printf("%6s", cadena2.charAt(i));
        System.out.println();
        for(int i=0; i<distancia.length; i++) {
            if(i==0) System.out.print("  ");
            else System.out.printf("%2s", cadena1.charAt(i-1));
            for(int j=0; j<distancia[i].length; j++) {
                System.out.printf("%,4d  ", distancia[i][j]);
            }
            System.out.println();
        }
    }

    private int minimo(int... v) {
        int menor = Integer.MAX_VALUE;
        for(int x: v) if(x<menor) menor=x;
        return menor;
    }

    private void calcularDistancias() {
        char[] cad1 = cadena1.toCharArray();
        char[] cad2 = cadena2.toCharArray();
        for(int i=0; i<=cad1.length; i++) distancia[i][0]=i;
        for(int j=0; j<=cad2.length; j++) distancia[0][j]=j;
        for(int i=1; i<=cad1.length; i++) {
            for(int j=1; j<=cad2.length; j++) {
                int cambio=0;
                if(cad1[i-1]!=cad2[j-1]) cambio=1;
                distancia[i][j] = minimo(distancia[i-1][j]+1,           // borrar
                                         distancia[i][j-1]+1,           // insertar
                                         distancia[i-1][j-1]+cambio);   // cambiar
            }
        }
    }

    public int getDistancia() {
        int respuesta = distancia[distancia.length-1][distancia[0].length-1];
        return respuesta;

    }

    public void getCamino() {
        int i=distancia.length-1;
        int j=distancia[0].length-1;
        String[] ruta = new String[Math.max(cadena1.length(), cadena2.length())+1];
        int k=ruta.length;
         while(i+j>0) {
            if(i>0 && distancia[i-1][j]  < distancia[i][j]) {
                ruta[--k] = "Elimina '" + cadena1.charAt(--i)+"'";
            }
            else if(j>0 && distancia[i][j-1]  < distancia[i][j]) {
                ruta[--k] = "Inserta '" + cadena2.charAt(--j)+"'";
            }
            else if(i > 0 && j > 0 && distancia[i - 1][j - 1] < distancia[i][j]) {
                ruta[--k] = "Reemplaza '" + cadena1.charAt(--i) + "' por '" + cadena2.charAt(--j) + "'";
                continue;
            }
            else if(i > 0 && j > 0 && distancia[i - 1][j - 1] == distancia[i][j]) {
                ruta[--k] = "Avanza sin cambios";
                i--;
                j--;
            }
        }
       for(String x: ruta) System.out.println(x);
    }

    public static void main(String [] args) {
        ProblemaDistanciaCadenas pdc = new ProblemaDistanciaCadenas("algoritmos", "logaritmo");
        pdc.calcularDistancias();
        pdc.getCamino();
    }
}

La complejidad continúa siendo cuadrática pues la nueva función agregada solo recorre tantos elementos como filas o columnas tenga la matriz y no toda la matriz.

Transformación de Cadenas

2010-11-27T06:49:00.001-05:00

Este algoritmo responde a la pregunta de cuántas transformaciones unitarias se deben hacer para convertir una cadena de caracteres en otra. Las transformaciones unitarias pueden ser de tres tipos: insertar, eliminar o reemplazar un caracter.

El algoritmo a implementar es conocido como la Distancia de Levenshtein, el cual implementa una solución por programación dinámica en la cual, con la ayuda de una matriz que tiene tantas filas como la cantidad de caracteres de una cadena más uno, y tantas columnas como la cantidad de caracteres de la otra cadena más uno, se calcula el número de transformaciones que se deben hacer para transformar los N prefijos de la primera cadena en los M prefijos de la segunda cadena.

public class ProblemaDistanciaCadenas {
    String cadena1;
    String cadena2;
    int[][] distancia;

    ProblemaDistanciaCadenas(String c1, String c2) {
        cadena1=c1;
        cadena2=c2;
        distancia=new int[cadena1.length()+1][cadena2.length()+1];
    }

    public void mostrarMatriz() {
        System.out.print("      ");
        for(int i=0; i<cadena2.length(); i++) System.out.printf("%6s", cadena2.charAt(i));
        System.out.println();
        for(int i=0; i<distancia.length; i++) {
            if(i==0) System.out.print("  ");
            else System.out.printf("%2s", cadena1.charAt(i-1));
            for(int j=0; j<distancia[i].length; j++) {
                System.out.printf("%,4d  ", distancia[i][j]);
            }
            System.out.println();
        }
    }

    private int minimo(int... v) {
        int menor = Integer.MAX_VALUE;
        for(int x: v) if(x<menor) menor=x;
        return menor;
    }

    private void calcularDistancias() {
        char[] cad1 = cadena1.toCharArray();
        char[] cad2 = cadena2.toCharArray();
        for(int i=0; i<=cad1.length; i++) distancia[i][0]=i;
        for(int j=0; j<=cad2.length; j++) distancia[0][j]=j;
        for(int i=1; i<=cad1.length; i++) {
            for(int j=1; j<=cad2.length; j++) {
                int cambio=0;
                if(cad1[i-1]!=cad2[j-1]) cambio=1;
                distancia[i][j] = minimo(distancia[i-1][j]+1,           // borrar
                                         distancia[i][j-1]+1,           // insertar
                                         distancia[i-1][j-1]+cambio);   // cambiar
            }
        }
    }

    public int getDistancia() {
        int respuesta = distancia[distancia.length-1][distancia[0].length-1];
        return respuesta;

    }

    public static void main(String [] args) {
        ProblemaDistanciaCadenas pdc = new ProblemaDistanciaCadenas("Hola", "Colas");
        pdc.calcularDistancias();
        pdc.mostrarMatriz();
        System.out.println(pdc.getDistancia());
    }
}

La complejidad del algoritmo es cuadrática, o más exactamente, O(NxM), donde N es el tamaño de la primera cadena y M el de la segunda.

Problema de las Reinas - Version 2

2010-11-26T06:00:00.010-05:00

Image via Wikipedia

Teniendo en cuenta que en cada fila del tablero de ajedrez solo puede ir una reina, entonces es posible modelar el problema utilizando un solo vector, en el que hay tantas posiciones como filas, y el valor para cada posición es la columna en la cual se encuentra ubicada la reina de dicha fila.

La sugerencia (sin código) para realizar esta solución está en el blog de prothotype. La estrategia a utilizar está basada en backtracking y recursividad al igual que la solución presentada anteriormente.

public class ProblemaReinas2 {
    final int numFilas;
    int[]   tablero;
    int     contador;
    int     correctas=0;

    public ProblemaReinas2(int nf) {
        numFilas    = nf;
        tablero     = new int[nf];
        for(int i=0; i<tablero.length; i++) tablero[i]=-1;
    }

    public void mostrarTablero() {
        for(int i=0; i<tablero.length; i++) {
            for(int j=0; j<tablero.length; j++) {
                if(tablero[i]==j) System.out.printf("  %2d  |", tablero[i]+1);
                else System.out.printf("      |");
            }
            System.out.println();
            for(int j=0; j<tablero.length; j++) System.out.print("------+");
            System.out.println();
        }
        System.out.println();
    }

    public boolean resolverProblema(int fila, int columna) {
        //mostrarTablero();
        contador++;
        tablero[fila]=columna;
        correctas++;
        if(correctas==numFilas) return true;
        int[] posibles = buscarPosibles(fila+1);
        for(int c: posibles) {
            if(resolverProblema(siguienteFila(), c)) return true;
        }
        tablero[fila]=-1;
        correctas--;
        return false;
    }

    public int siguienteFila() {
        for(int i=0; i<tablero.length; i++) if(tablero[i]==-1) return i;
        return -1;
    }

    int[] buscarPosibles(int num) {
        int[] resp = new int[numFilas];
        int pos=numFilas;
        for(int i=0; i<resp.length; i++) resp[i]=i;
        for(int i=0; i<numFilas; i++) {
            if(tablero[i]!=-1) {
                resp[tablero[i]]=-1;
                pos--;
            }
        }
        for(int i=0; i<resp.length; i++) {
            if(resp[i]==-1) continue;
            for(int j=0; j<num; j++) {
                double fabs = Math.abs((num-j)*1.0/(resp[i]-tablero[j]));
                if(fabs==1.0 && resp[i]!=-1) {
                    resp[i]=-1;
                    pos--;
                    break;
                }
            }
        }
        int[] tmp = new int[pos];
        int i=0;
        for(int x: resp) if(x!=-1) tmp[i++] = x;
        return tmp;
    }

    public static void main(String[] args) {
        java.util.Random rnd  = new java.util.Random();
        int numFilas      = 8;
        int filaInicial   = rnd.nextInt(numFilas);
        int colInicial    = rnd.nextInt(numFilas);
        ProblemaReinas2 pr = new ProblemaReinas2(numFilas);
        pr.resolverProblema(filaInicial, colInicial);
        pr.mostrarTablero();
        System.out.printf("Cantidad de veces que entra al ciclo: %,d %n",  pr.contador);
    }
}

Problema de las Reinas

2010-11-25T09:01:00.001-05:00

El siguiente programa muestra como resolver el problema de las 8 reinas, generalizado para cualquier tamaño de tablero. El problema en sí trata de encontrar una forma de posicionar n reinas en un tablero de ajedrez de tamaño n x n, de tal manera que ninguna de las reinas ataque a ninguna de las otras. Una reina ataca todas las casillas que se encuentren en la misma fila, en la misma columna, o en las diagonales de la casilla en que está ubicada.

Este problema utiliza un esquema igual al utilizado en la solución del problema del salto del caballo, modelando el tablero como una matriz de n x n y utilizando un enfoque de backtracking para marcar una casilla, generar una lista de las siguientes casillas que no están amenazadas y revisar dicha lista en forma recursiva; si no se llega a la respuesta correcta, se devuelve el proceso para continuar con las siguiente casillas de la lista.

public class ProblemaReinas {
    final int numFilas;
    final int numColumnas;
    int[][] tablero;
    int     contador;

    public ProblemaReinas(int nf) {
        numFilas    = nf;
        numColumnas = nf;
        tablero     = new int[nf][nf];
    }

    public void mostrarTablero() {
        for(int i=0; i<tablero.length; i++) {
            for(int j=0; j<tablero[i].length; j++) {
                if(tablero[i][j]>0) System.out.printf("  %2d  |", tablero[i][j]);
                else System.out.printf("      |", tablero[i][j]);
            }
            System.out.println();
            for(int j=0; j<tablero[i].length; j++) System.out.print("------+");
            System.out.println();
        }
    }

    public boolean resolverProblema(int f, int c, int num) {
            contador++;
            tablero[f][c] = num;
            if(num==numFilas) return true;
            int[][] posibles = buscarPosibles();
            for(int i=0; i<posibles.length; i++) {
                if(resolverProblema(posibles[i][0], posibles[i][1], num+1)) return true;
            }
            tablero[f][c]=0;
            return false;
    }

    int[][] buscarPosibles() {
        int[][] resp = new int[numFilas*numColumnas][2];
        int[] sumaFilas = new int[numColumnas];
        int[] sumaColumnas = new int[numFilas];
        int     pos  = 0;
        for(int i=0; i<numFilas; i++) {
            for(int j=0; j<numColumnas; j++) {
                if(tablero[i][j]>0) {
                    sumaFilas[i]++;
                    sumaColumnas[j]++;
                }
            }
        }
        for(int i=0; i<numFilas; i++) {
            if(sumaFilas[i]>0) continue;
            for(int j=0; j<numColumnas; j++) {
                if(sumaColumnas[j]>0) continue;
                if(i>0 && j>0             && tablero[i-1][j-1] > 0) continue;
                if(i>0 && j<numColumnas-1 && tablero[i-1][j+1] > 0) continue;
                if(i<numFilas-1 && j>0    && tablero[i+1][j-1] > 0) continue;
                if(i<numFilas-1 && j<numColumnas-1 && tablero[i+1][j+1] > 0) continue;
                resp[pos][0]=i;
                resp[pos][1]=j;
                pos++;
            }
        }
        int[][] tmp = new int[pos][2];
        for(int i=0; i<pos; i++) { tmp[i][0] = resp[i][0]; tmp[i][1]=resp[i][1]; }
        return tmp;
    }

    boolean esValido(int f, int c) {
        if(f<0 || f>numFilas-1 || c<0 || c>numColumnas-1) return false;
        if(tablero[f][c]!=0) return false;
        return true;
    }

    public static void main(String[] args) {
        java.util.Random rnd  = new java.util.Random();
        int numFilas      = 8;
        int filaInicial   = rnd.nextInt(numFilas);
        int colInicial    = rnd.nextInt(numFilas);
        ProblemaReinas pr = new ProblemaReinas(8);
        pr.resolverProblema(filaInicial, colInicial,1);
        pr.mostrarTablero();
        System.out.printf("Cantidad de veces que entra al ciclo: %,d %n",  pr.contador);
    }
}