miércoles, diciembre 22, 2010

Top de lenguajes de programación para 2011

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:

  1. JAVA
  2. C
  3. C++
  4. C#
  5. JavaScript
  6. Perl
  7. PHP
  8. VisualBasic
  9. Python
  10. Ruby
  11. Objective C
  12. ActionScript
  13. Groovy
  14. Go
  15. Scale
  16. Erlang
  17. Clojure
  18. Visual F++

lunes, diciembre 20, 2010

Cálculo de Frecuencias - Problema UVA 499

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;
    }
}

viernes, diciembre 17, 2010

Calculo de Salarios - Problema UVA 10295

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);
        }
    }
}

jueves, diciembre 16, 2010

Números de Smith - Problema UVA 10042

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;
                }
            }
        }
    }
}

miércoles, diciembre 15, 2010

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

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;
    }
}

martes, diciembre 14, 2010

Suma de Árbol - Problema UVA 112

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.

lunes, diciembre 13, 2010

Cola de Equipo - Problema UVA 540

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

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");
}

domingo, diciembre 12, 2010

Paréntesis Balanceados - Problema UVA 673

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;
    }
}

lunes, diciembre 06, 2010

Indice Tiobe para Noviembre de 2010

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

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

Evaluación de Expresiones en Groovy

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"

viernes, diciembre 03, 2010

Números Primos en Groovy

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

domingo, noviembre 28, 2010

Transformacion de Cadenas - El camino a seguir

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.

sábado, noviembre 27, 2010

Transformación de Cadenas

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.

viernes, noviembre 26, 2010

Problema de las Reinas - Version 2

Problem of eight queensImage 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);
    }
}
Enhanced by Zemanta

jueves, noviembre 25, 2010

Problema de las Reinas

Ocho reinas reina atacarr
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);
    }
}
Enhanced by Zemanta

lunes, noviembre 22, 2010

Máquina Virtual con AntLR

A continuación se presenta una primera versión de una máquina virtual escrita en ANTLR que reconoce un lenguaje con las siguientes posibles instrucciones: ADD, SUB, MUL, DIV, EXP, AND, OR, PUSH, STORE, WRITE, WRITELN, GOTO y JZERO:

grammar maquinavirtual;

@header {
 import java.util.Vector;
 import java.util.HashMap;
 import java.util.Map;
 import java.util.Stack;
}
@members{
 enum TipoInstruccion { vPUSH, cPUSH, STORE, ADD, SUB, MUL, DIV, EXP, AND, OR, cWRITE, WRITE, vWRITE, WRITELN, GOTO, JZERO }
 class Instruccion{
  TipoInstruccion tipo;
  int     operador;
  Instruccion(TipoInstruccion t, int o) { tipo = t; operador = o; }
  Instruccion(TipoInstruccion t)   { this(t,-1); }
 }
 
 Vector<Instruccion> tablaPrograma  = new Vector<Instruccion>();
 Vector<String>   tablaCadenas   = new Vector<String>();
 Vector<Double>   tablaConstantes = new Vector<Double>();
 Vector<String>   tablaVariables  = new Vector<String>();
 Stack<Double>   pila     = new Stack<Double>();
 Map<String,Double> memoria    = new HashMap<String,Double>();
 
 public void agregar(TipoInstruccion t) { tablaPrograma.add(new Instruccion(t)); }
 public void agregarStore(String var) {
  if(!tablaVariables.contains(var)) tablaVariables.add(var);
  tablaPrograma.add(new Instruccion(TipoInstruccion.STORE, tablaVariables.indexOf(var)));
 }
 public void agregarVPush(String var) {
  if(!tablaVariables.contains(var)) tablaVariables.add(var);
  tablaPrograma.add(new Instruccion(TipoInstruccion.vPUSH, tablaVariables.indexOf(var)));
 }
 public void agregarcPush(String val) {
  double num = Double.parseDouble(val);
  if(!tablaConstantes.contains(num)) tablaConstantes.add(num);
  tablaPrograma.add(new Instruccion(TipoInstruccion.cPUSH, tablaConstantes.indexOf(num)));
 }
 public void agregarWrite(String var) {
  var=var.substring(1,var.length()-1);
  if(!tablaCadenas.contains(var)) tablaCadenas.add(var);
  tablaPrograma.add(new Instruccion(TipoInstruccion.cWRITE, tablaCadenas.indexOf(var)));
 }
 public void agregarGoto(String val) {
  int num = (int) Double.parseDouble(val);
  tablaPrograma.add(new Instruccion(TipoInstruccion.GOTO, num));
 }
 public void agregarJZero(String val) {
  int num = (int) Double.parseDouble(val);
  tablaPrograma.add(new Instruccion(TipoInstruccion.JZERO, num));
 }
 public void ejecutar() {
  double a, b;
  for(int i=0; i<tablaPrograma.size(); i++) {
   Instruccion ins = tablaPrograma.get(i);
   switch(ins.tipo) {
    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 DIV: 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 EXP: b=pila.pop(); a=pila.pop(); pila.push(Math.pow(a,b)); break;
    case AND: b=pila.pop(); a=pila.pop(); pila.push(a==1.0 && b==1.0 ? 1.0: 0.0); break;
    case OR:  b=pila.pop(); a=pila.pop(); pila.push(a==1.0 || b==1.0 ? 1.0: 0.0); break;
    case WRITE:  System.out.print(pila.pop()); break;
    case WRITELN: System.out.println(); break;
    case cWRITE: System.out.print(tablaCadenas.get(ins.operador)); break;
    case cPUSH: pila.push(tablaConstantes.get(ins.operador)); break;
    case vPUSH: pila.push(memoria.get(tablaVariables.get(ins.operador))); break;
    case STORE: memoria.put(tablaVariables.get(ins.operador), pila.pop()); break;
    case GOTO: i=(int) ins.operador-2; break;
    case JZERO: if(pila.pop()==0) i=(int) ins.operador-2; break;
   }
  }
 }
}

programa  : instruccion+  { ejecutar(); } ;

instruccion : 'push' VARIABLE { agregarVPush($VARIABLE.text); }
    | 'push' NUMERO { agregarcPush($NUMERO.text); }
    | 'store' VARIABLE { agregarStore($VARIABLE.text); }
    | 'add'     { agregar(TipoInstruccion.ADD);}
    | 'sub'     { agregar(TipoInstruccion.SUB);}
    | 'mul'     { agregar(TipoInstruccion.MUL);}
    | 'div'     { agregar(TipoInstruccion.DIV);}
    | 'exp'     { agregar(TipoInstruccion.EXP);}
    | 'and'     { agregar(TipoInstruccion.AND);}
    | 'or'     { agregar(TipoInstruccion.OR);}
    | 'write' CADENA { agregarWrite($CADENA.text); }
    | 'write'    { agregar(TipoInstruccion.WRITE); }
    | 'writeln'  { agregar(TipoInstruccion.WRITELN); }
    | 'goto' NUMERO { agregarGoto($NUMERO.text); }
    | 'jzero' NUMERO { agregarJZero($NUMERO.text); }
    ;
    
fragment DIGITO : '0'..'9';
fragment LETRA  : 'a'..'z'|'A'..'Z';
NUMERO    :  DIGITO+('.' DIGITO+)?;
VARIABLE    : LETRA ( LETRA|DIGITO)*;
CADENA    : '"'.*'"';
ESPACIO    : (' '|'\t'|'\n'|'\r') { skip(); } ;
RESTO     : . ;      

Puede probar la máquina virtual desde AntLR con el siguiente programa de prueba:
push 4
store  a
push 3
store b
push a
push b
add
write
writeln
write "El fin"

jueves, noviembre 18, 2010

El problema del recorrido del caballo de ajedrez - heuristicas

La solución al problema del recorrido del caballo de ajedrez encontrada con el método de backtracking se tarda un tiempo considerable porque evalúa demasiadas alternativas que no forman parte de la solución. La prueba en un computador con procesador Intel core i5 con Windows 7 tardó cerca de 40 minutos con 67,890,999,999,999 de ensayos.

Una solución utilizando heurísticas para este problema se enfoca en la manera en cómo se evalúan las celdas una vez se ha marcado una de ellas y propone que la asignación del orden en que se evalúan las casillas dependa de la cantidad de casillas a la que cada una de ellas tenga alcance. Es decir, por ejemplo, que si una vez marcada una casilla, ésta tiene 5 posibles celdas a las que el caballo puede saltar, se debe ir primero a aquella casilla que tenga menos saltos posibles.

Para implementar esta solución, sólo debe agregarse a la solución propuesta anteriormente un método que ordene el arreglo de posibles casillas y llamar a dicha función una vez se calcule dicho arreglo así:

    public boolean resolverProblema(int f, int c, int num) {
            contador++;
            tablero[f][c] = num;
            if(num==numFilas*numColumnas) return true;
            int[][] posibles = buscarPosibles(f, c);
            ordenarPosibles(posibles);              // llamado a la nueva función
            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;
    }

    // nuevo método: ordena el arreglo de posibles casillas a saltar
    void ordenarPosibles(int[][] posibles) {
        for(int i=0; i<posibles.length; i++) {
            for(int j=i+1; j<posibles.length; j++) {
                int cuantosPosiblesI = buscarPosibles(posibles[i][0], posibles[i][1]).length;
                int cuantosPosiblesJ = buscarPosibles(posibles[j][0], posibles[j][1]).length;
                if(cuantosPosiblesJ<cuantosPosiblesI) {
                    int tmp0 = posibles[i][0];
                    posibles[i][0] = posibles[j][0];
                    posibles[j][0] = tmp0;
                    int tmp1 = posibles[i][1];
                    posibles[i][1] = posibles[j][1];
                    posibles[j][1] = tmp1;
                }
            }
        }
    }

Con este cambio el proceso tarda algo menos de un segundo y sólo tiene que entrar 64 veces al proceso de marcado de casillas, es decir, no hace ningún retroceso.

miércoles, noviembre 17, 2010

El problema del recorrido del caballo de ajedrez - backtracking

La peregrinación del caballo de ajedrez consiste en su paseo por todas las casillas del tablero sin pasar dos veces por la misma, utilizando sus movimientos: dos casillas horizontales y una vertical o a la inversa. Cuando desde la última casilla podamos pasar a la primera se trata de una "peregrinación cerrada".

Para resolver este problema se puede utilizar la técnica de backtracking con un algoritmo recursivo relativamente simple: marcar la posición solicitada, hacer una lista de las siguientes posiciones vacías a las que se puede saltar desde la posición marcar, y tomar la primera de ellas, marcándola entonces en forma recursiva. Si en alguno de los pasos recursivos no se alcanza una solución, la casilla se desmarca y se pasa a la siguiente que estaba en la lista. Si se termina la lista y no se llega a una solución, entonces se devuelve a la casilla anterior desde la que se hizo el llamado.

La solución en JAVA para esta solución es la siguiente:

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

    public ProblemaCaballo(int nf, int nc) {
        numFilas = nf;
        numColumnas = nc;
        tablero     = new int[nf][nc];
    }

    public void mostrarTablero() {
        for(int i=0; i<tablero.length; i++) {
            for(int j=0; j<tablero[i].length; j++) {
                System.out.printf("  %2d  |", 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*numColumnas) return true;
            int[][] posibles = buscarPosibles(f, c);
            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 f, int c) {
        int[][] resp = new int[8][2];
        int     pos  = 0;
        if(esValido(f-2,c-1)){ resp[pos][0]=f-2; resp[pos++][1]=c-1; }
        if(esValido(f-2,c+1)){ resp[pos][0]=f-2; resp[pos++][1]=c+1; }
        if(esValido(f-1,c-2)){ resp[pos][0]=f-1; resp[pos++][1]=c-2; }
        if(esValido(f-1,c+2)){ resp[pos][0]=f-1; resp[pos++][1]=c+2; }
        if(esValido(f+2,c-1)){ resp[pos][0]=f+2; resp[pos++][1]=c-1; }
        if(esValido(f+2,c+1)){ resp[pos][0]=f+2; resp[pos++][1]=c+1; }
        if(esValido(f+1,c-2)){ resp[pos][0]=f+1; resp[pos++][1]=c-2; }
        if(esValido(f+1,c+2)){ resp[pos][0]=f+1; resp[pos++][1]=c+2; }
        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) {
        ProblemaCaballo pc = new ProblemaCaballo(8,8);
        pc.resolverProblema(0,0,1);
        pc.mostrarTablero();
        System.out.printf("Cantidad de veces que entra al ciclo: %,d %n",  pc.contador);
    }
}

martes, noviembre 16, 2010

Problema de la mochila - Algoritmos Voraces

Si bien la solución por backtracking permite obtener la mejor solución al problema de la mochila, existe el problema de que cuando la cantidad de elementos a evaluar es relativamente grande, los tiempos de respuesta se vuelven prohibitivos. Por otro lado, la solución de agregar primero los elementos más costosos, o lo más livianos, no garantiza una solución óptima, o por lo menos parecida a la óptima.

Estas dos aproximaciones representan el concepto de algoritmos voraces, donde se selecciona una estrategia que permite decidir si un elemento se agrega o no a la solución. En los casos mencionados se utilizaba la estrategia del mayor costo o la del menor peso. Una mejor solución se presenta cuando se utiliza el costo por unidad de peso para ordenar los elementos, de esta manera, un elemento muy caro no se agrega si pesa demasiado en comparación con otro de menor valor, pero de mucho menor peso. La función resolverProblema queda entonces de la siguiente manera:

    public void resolverProblema() {
        // Comparador para ordenar los elementos del almacen por valor
        Comparator cmp = new Comparator<Elemento>() {
            public int compare(Elemento x, Elemento y) {
                return (int) (x.valor/x.peso - y.valor/y.peso);
            }
        };
        Collections.sort(almacen,cmp);  // ordena usando el comparador anterior
        Collections.reverse(almacen);   // reversa el orden de los elementos

        double pesoMochila=0;
        int    posicion=0;
        while(pesoMochila<pesoMaximo && posicion < almacen.size()) {
            Elemento tmp = almacen.get(posicion);
            if(pesoMochila + tmp.peso <= pesoMaximo) {
                mochila.add(tmp);
                pesoMochila+=tmp.peso;
            }
            posicion++;
        }
    }

En cuanto al desempeño de este método, su complejidad es la equivalente al proceso de ordenación de la lista de elementos por su valor por unidad de peso, que es O(N log N), ya que el proceso de llenado de la mochila es lineal.

En el caso de ejemplo, este método da una respuesta con un peso total de 18 Kg y un costo de $945, mientras que la respuesta obtenida por backtracking es de 20 Kg con un costo de $955, lo que muestras que se obtiene un valor muy cercano al óptimo en una fracción del tiempo.

Problema de la mochila - Backtracking

Resolver el problema de la mochila seleccionando los elementos más caros en primer lugar, o los más livianos, no necesariamente garantiza llegar a una solución ideal, pues es posible que otras combinaciones de elementos produzcan mejores resultados.

Para obtener la solución ideal se deben revisar todas las alternativas; y en este caso, se puede utilizar una estrategia de retroceso, o backtracking. En esta implementación, iniciando en el primer elemento del almacén, se evalúan dos posibilidades, agregar o no agregar el elemento a la mochila, y llamando recursivamente el método hasta que la mochila se llena; una vez llena, se compara con el máximo calculado anteriormente y se guarda la lista de elementos que genere el mayor valor en la mochila. Esta solución requiere una mochila temporal (tmpMochila) que se crea en forma similar a la mochila definitiva, y dos métodos que calculen el valor y el peso acumulado de dicha mochila temporal. La implementación queda entonces de la siguiente manera:

// Solución por backtracking
    public void resolverProblemaBT(int posicion) {
        double  pesoMochila=getPeso(tmpMochila);    // peso de la solucion temporal
        double valorMochila=getValor(tmpMochila);   // valor de la solucion temporal

        if( posicion>=almacen.size() ) {            // si ya se tuvieron en cuenta todos los elementos
            if(valorMochila>valorMaximo) {          // si el valor es mayor que el máximo anterior
                valorMaximo=valorMochila;           // se actualiza el valor mayor
                mochila.clear();
                mochila.addAll(tmpMochila);
            }
            return;
        }
        Elemento e = almacen.get(posicion);
        // Si el elemento se puede agregar, se envía a la mochila temporal
        if(pesoMochila + e.peso <= pesoMaximo) {
                tmpMochila.add(e);                  // Se agrega a la mochila temporal
                resolverProblemaBT(posicion+1);     // se revisa para el siguiente elemento
                tmpMochila.remove(e);               // Se retira el elemento
        }
        // Si no se pudo agregar, o ya se agregó y se retiró, se revisa para el siguiente
        resolverProblemaBT(posicion+1);
    }

    double getPeso(List<Elemento> tmp) {
        double respuesta=0;
        for(Elemento e: tmp) respuesta+=e.peso;
        return respuesta;
    }

    double getValor(List<Elemento> tmp) {
        double respuesta=0;
        for(Elemento e: tmp) respuesta+=e.valor;
        return respuesta;
    }

El método de invocación quedaría de la siguiente manera (no olvidar crear el vector tmpMochila como un Vector de objetos de tipo Elemento):

    public static void main(String[] args) {
        ProblemaMochila pm = new ProblemaMochila(20);
        pm.resolverProblemaBT(0);       // Inicia en el primer elemento disponible
        pm.mostrarMochila();
    }

Este método devuelve la solución óptima, puesto que evalúa todas las posibilidades, sin embargo, cuando el número de elementos disponibles es relativamente grande, la cantidad de operaciones a realizar hace prácticamente imposible utilizar el algoritmo, ya que su complejidad es del orden de O(N!), donde N es la cantidad de elementos del almacén.

Problema de la mochila

El problema de la mochila es un problema típico de programación entera que responde a la siguiente situación: imagínese que un ladrón entra a un almacén para substraer una serie de elementos con una única mochila que tiene una capacidad limitada en cuanto al peso que puede contener. Cada objeto que se introduce carga la mochila con más peso, pero a su vez representa un beneficio económico por el valor del mismo. El problema surge cuando se debe elegir qué objetos seleccionar para llevar en la mochila de forma que el beneficio sea máximo.

Esta situación se presenta con cierta frecuencia en los ámbitos económico e industrial, donde la mochila suele representar la restricción presupuestaria (cantidad máxima de recursos económicos de los que se dispone) y donde la utilidad de los objetos seleccionados se equipara a un beneficio económico por adquirir o llevar a cabo ciertas acciones.

Para modelar este problema se utilizará una clase denominada Elemento que contendrá solamente la descripción de cada elemento, su peso y su valor, así:

class Elemento {
    String nombre;
    double valor;
    double peso;
    Elemento(String n, double v, double p) {
        nombre=n;
        valor =v;
        peso  =p;
    }
    public String toString() {
        return String.format("%-15s %,12.2f %,12.2f", nombre, valor, peso);
    }
}

La modelación termina con una clase denominada ProblemaMochila en la que se crearán dos vectores para simular el almacén, es decir, los elementos disponibles, y la mochila, dónde se ubicarán los elementos a ser substraídos. Se tienen métodos adicionales para mostrar el contenido de la mochila, así como para llenar el almacén con los elementos iniciales:

import java.util.*;

public class ProblemaMochila {
    Vector<Elemento> almacen = new Vector<Elemento>();
    Vector<Elemento> mochila = new Vector<Elemento>();
    final double  pesoMaximo;

    public ProblemaMochila(int pm) {
        pesoMaximo = pm;
        cargarDatos();
    }

    public void cargarDatos() {
        almacen.add(new Elemento("TV",        300, 15));
        almacen.add(new Elemento("PS3",       100,  3));
        almacen.add(new Elemento("Libro Java", 10,  1));
        almacen.add(new Elemento("DVD Player",  5,  0.5));
        almacen.add(new Elemento("Blu-Ray",    50,  0.5));
        almacen.add(new Elemento("Balon",      30,  0.5));
        almacen.add(new Elemento("iPod",      150,  1));
        almacen.add(new Elemento("Printer",    20,  4));
        almacen.add(new Elemento("VideoBeam", 200,  4));
        almacen.add(new Elemento("LapTop",     20,  3));
        almacen.add(new Elemento("iPad",      150,  2));
        almacen.add(new Elemento("PC",        100,  5));
        almacen.add(new Elemento("BlackBerry",150,  0.5));
   }

     public void mostrarMochila() {
        double pesoMochila=0;
        double valorMochila=0;
        System.out.println();
        for(Elemento e: mochila) {
            System.out.println(e);
            pesoMochila+=e.peso;
            valorMochila+=e.valor;
        }
        System.out.println("------");
        System.out.printf("Peso  = %,12.2f %n", pesoMochila);
        System.out.printf("Valor = %,12.2f %n", valorMochila);
    }

    public static void main(String[] args) {
        // Crear una mochila que soporta hasta 20 Kg. de peso
        ProblemaMochila pm = new ProblemaMochila(20);
        pm.resolverProblema();
        pm.mostrarMochila();
    }
}

Para resolver el problema existen varias estrategias, entre las cuales pueden estar la de ir llenando la mochila con los elementos más costosos, o con los elementos menos pesados. En el caso de llenar la mochila con los elementos más costosos primero, el método resolverProblema se plantearía así:

public void resolverProblema() {
        // Comparador para ordenar los elementos del almacen por valor
        Comparator cmp = new Comparator<Elemento>() {
            public int compare(Elemento x, Elemento y) {
                return (int) (x.valor - y.valor);
            }
        };
        Collections.sort(almacen,cmp);  // ordena usando el comparador anterior
        Collections.reverse(almacen);   // reversa el orden de los elementos

        double pesoMochila=0;
        int    posicion=0;
        while(pesoMochila<pesoMaximo && posicion < almacen.size()) {
            Elemento tmp = almacen.get(posicion);
            if(pesoMochila + tmp.peso <= pesoMaximo) {
                mochila.add(tmp);
                pesoMochila+=tmp.peso;
            }
            posicion++;
        }
    }

Si se quiere ordenar usar otra estrategia, como la de ir llenando la mochila en primer lugar con los elementos más livianos, bastaría cambiar el comparador cmp para que reste pesos en lugar de valores

Proximamente se publicarán otros enfoques para resolver este problema.

miércoles, noviembre 10, 2010

Gramática de Lenguaje con Acciones Semánticas en ANTLR

La siguiente gramática en AntLR permite reconocer un pequeño lenguaje de programación que implementa desde el punto de vista léxico, números (enteros o reales positivos), variables y cadenas de caracteres.

Desde el punto de vista sintáctico, los programas se ven como una lista de instrucciones que, a su vez, pueden ser del tipo asignación, escritura, condicional, iterativa, de incremento o de decremento. La asignación de variables se hace sobre expresiones algebraicas que permiten el uso de variables, números, sumas, restas, multiplicaciones, divisiones y potencias, al igual que subexpresiones entre paréntesis.

Desde el punto de vista semántico, esta gramática traduce el texto recibido en un conjunto de instrucciones para ser ejecutado por una máquina virtual.

@header{
 package analizadores;
 import java.util.Vector;
 import java.util.HashSet;
}
@lexer::header{
 package analizadores;
}


// FUNCIONES PROPIAS DEL LENGUAJE
@members {
 Vector< String > vectorSalida=new Vector< String >();
 HashSet< String > variablesInicializadas=new HashSet< String >();
 
 public void escribir(String mensaje) {
  vectorSalida.add(mensaje);
 }
 public String getSalida() {
  String salida="";
  for(String x: vectorSalida) {
   salida+=(x+"\n");
  }
  return salida;
 }
 String errores="";
 public void emitErrorMessage(String mensaje) {
  errores+=(mensaje+"\n");
 }
 public String getErrores() { return errores; }
}

// REGLAS GRAMATICALES O SINTACTICAS
programa    : instruccion+ { System.out.println(getSalida()); };

instruccion   : v=VARIABLE '=' expresion ';'   { escribir("store \t"+$v.text); variablesInicializadas.add($v.text); } 
      | WRITE elemento (',' elemento)* ';' { escribir("writeln"); }
      |  condicional
      | iterativa
      | incremento
      | decremento
      ;
      
condicional   : IF '(' condicion ')' { int linea1 = vectorSalida.size(); escribir("jeq"); }
         bloque      { int linea2 = vectorSalida.size(); escribir("jump"); }
                { vectorSalida.set(linea1, "jeq\t" + (linea2+2)) ; }
         ( ELSE bloque )?  { vectorSalida.set(linea2, "jump\t" + (vectorSalida.size()+1)); }
      ;
      
iterativa   : WHILE       { int linea1 = vectorSalida.size(); }
        '('condicion ')'   { int linea2 = vectorSalida.size(); escribir("jeq"); }
        bloque      { escribir("jump\t"+ (linea1+1)); vectorSalida.set(linea2, "jeq\t"+(vectorSalida.size()+1));}
      ;
      
bloque    : instruccion 
      | '{' instruccion* '}'
      ;      
      
elemento    : expresion { escribir("write"); }
      | s=STRING  { escribir("write\t"+ $s.text); }
      ;      
      
expresion   : termino ( '+' termino {escribir("add");}
                             | '-' termino {escribir("sub");})* 
                  ;
                                  
termino    : factor ( '*' factor  {escribir("mul");}
          | '/' factor  {escribir("div");})* 
          ;
          
factor    : valor ( '^' valor {escribir("exp");} )*
      ;          
          
valor     : a=NUMERO      { escribir("push \t"+ $a.text); }
      | v=VARIABLE     { if(variablesInicializadas.contains($v.text)) escribir("push \t"+ $v.text); 
                 else emitErrorMessage($v.line+", "+$v.getCharPositionInLine()+": Variable no inicializada: " + $v.text);}
      | '(' expresion ')'
      ;

condicion   : expresion ( '>=' expresion { escribir("ge"); }
           | '<=' expresion { escribir("le"); }
           | '>'  expresion  { escribir("gt"); }
           | '<'  expresion  { escribir("lt"); }
           | '==' expresion  { escribir("eq"); }
           | '!=' expresion  { escribir("ne"); }
           ) ;

incremento   : v=VARIABLE '++' ';' {escribir("inc\t"+$v.text); } ;
decremento   : v=VARIABLE '--' ';' {escribir("dec\t"+$v.text); } ;

// REGLAS LEXICAS
fragment DIGITO : '0'..'9';
fragment LETRA  : 'a'..'z'|'A'..'Z';
NUMERO    : DIGITO+ '.'? DIGITO* ;
WRITE     : 'write'|'escriba'|'imprima'|'print';
IF      : 'if'|'si';
ELSE     : 'sino'|'else';
WHILE     : 'while'|'mientras'|'mientras que';
VARIABLE    : LETRA ( LETRA|DIGITO)* ;
ESPACIO    : (' '|'\t'|'\r'|'\n')  { skip(); } ;

COMMENT    :   '//' ~('\n'|'\r')* '\r'? '\n'      {$channel=HIDDEN;}
         |   '/*' ( options {greedy=false;} :  . )* '*/' {$channel=HIDDEN;}
         ;

STRING    :  '"' ( ESC_SEQ | ~('\\'|'"') )* '"'  ;

fragment ESC_SEQ :  '\\' ('b'|'t'|'n'|'f'|'r'|'\"'|'\''|'\\')
      |   UNICODE_ESC
      |   OCTAL_ESC
      ;
fragment UNICODE_ESC
      : '\\' 'u' HEX_DIGIT HEX_DIGIT HEX_DIGIT HEX_DIGIT
      ;
fragment HEX_DIGIT: ('0'..'9'|'a'..'f'|'A'..'F') ;
fragment OCTAL_ESC: '\\' ('0'..'3') ('0'..'7') ('0'..'7')
      |  '\\' ('0'..'7') ('0'..'7')
      |   '\\' ('0'..'7')
      ;
OTROCARACTER  : .        { System.out.println("error"); } ;

En una próxima entrada se estará publicando el cógido en AntLR también de la máquina virtual y las instrucciones para compilar, ejecutar y probar el lenguaje.

Operaciones con números grandes - multiplicación

Para la multiplicación de dos números grandes se puede utilizar, además de los métodos disponibles en la clase BigInteger, un enfoque basado en la multiplicación de uno de los números grandes por cada uno de los dígitos del otro, y haciendo las sumas correspondientes.

A continuación se presentan dos funciones de multiplicación para números grandes. En la primera se implementa la multiplicación de un entero grande por un dígito, y en la segunda, la de dos enteros grandes utilizando el método anterior y el de la suma de enteros grandes publicado anteriormente:

public static String multiplicacion(String nA, String nB) {
        String respuesta="0";
        String ceros="";
        int posA = nA.length()-1;
        while(posA>=0) {
            respuesta=suma(respuesta,multiplicacion(nA.charAt(posA),nB)+ceros);
            ceros+="0";
            posA--;
        }
        return respuesta;
    }

    public static String multiplicacion(char digito, String nB) {
        String respuesta="";
        int digA=digito-'0';
        int posB=nB.length()-1;
        int digB;
        int resto=0;
        while(posB>=0) {
            digB = nB.charAt(posB)-'0';
            int c = digA*digB+resto;
            resto=c/10;
            c = c%10;
            respuesta=c+respuesta;
            posB--;
        }
        if(resto>0) respuesta=resto+respuesta;
        return respuesta;
    }
}

martes, noviembre 09, 2010

Operaciones con números grandes - suma

Los lenguajes de programación manejan tipos de datos enteros, en los cuales hay un valor determinado para el número entero más grande que se puede manejar, teniendo en cuenta que para su almacenamiento se utiliza un determinado número de posiciones de memoria. En el caso de JAVA, un número entero ocupa 64 bits de memoria, por lo que el mayor número entero que se puede manejar es 9,223,372,036,854,775,807 equivalente a dos elevado a la 63 menos 1 (más información en el tutotial oficial de java).

El manejo de operaciones aritméticas simples con números enteros mayores al límite máximo permitido se debe manejar utilizando otro tipo de estrategias. Se puede utilizar la clase BigInteger que tiene implementados métodos para suma y multiplicación de números enteros grandes, o se puede hacer un ejercicio de programación utilizando la cadenas de caracteres (ó arreglos de caracteres) y el procedimiento de suma elemental que consiste en alinear los números e ir sumando los dígitos menos significativos de cada número y acumulando la respuesta en una nueva cadena.

A continuación se presenta una primera versión del método de suma de números enteros grandes:

public static String suma(String nA, String nB) {
        String respuesta="";
        int posA = nA.length()-1;
        int posB = nB.length()-1;
        int resto = 0;
        int digA, digB;

        while(posA>=0 || posB>=0) {
            digA = (posA>=0) ? nA.charAt(posA)-'0': 0;
            digB = (posB>=0) ? nB.charAt(posB)-'0': 0;
            int c = digA+digB+resto;
            if(c>=10) { resto=1; c=c-10;}
            else resto=0;
            respuesta=c+respuesta;
            posA--;
            posB--;
        }
        if(resto>0) respuesta=resto+respuesta;
        return respuesta;
}

martes, octubre 26, 2010

Guía de estilo de JAVA

A continuación se transcribe, desde la página del curso Curso práctica en ingeniería de software publicado por el Instituto Tecnológico de Massachussets (MIT) en su iniciativa de cursos libres OpenCourseWare  traducidos a su vez al español por el portal Universia, una guía de estilo para programar en java:




Boletín S1: Guía de estilo de Java™

Visión global

El estilo del código constituye una parte crucial en el ejercicio de la buena ingeniería del software. El objetivo se centra en escribir código que sea claro y fácil de entender, y que al mismo tiempo reduzca el esfuerzo que se emplea en hacer ampliaciones o modificaciones futuras.
Hay varios aspectos del código que lo pueden hacer más legible. Algunos de los más importantesson el empleo de nombres descriptivos, así como el uso de una indentación coherente y decomentarios informativos.
En el curso 6.170 no le indicamos que siga un estilo de código detallado. No obstante, esperamos que su código sea claro y fácil de entender. Este boletín le facilita una serie de directrices generales dentro de las cuales usted debería desarrollar un estilo de código propio y logrado.

Nombres descriptivos

Debería usar nombres nemónicos para los paquetes, los tipos, las variables y las etiquetas de ramificación, mediante los cuales se pudiese vislumbrar su uso y/o significado. Esto no significa que
los nombres tengan que ser muy largos. Por ejemplo, nombres como i y j servirían para nombrar los índices de bucles cortos, ya que los programadores conocen por convención los significados y usos de estas variables.

Le aconsejamos que siga una convención común que consiste en poner en mayúsculas los nombres
de las clases y en empezar los nombres de las variables y de los paquetes con letra minúscula. Existen otras convenciones comunes tales como escribir el nombre completo de las constantes en mayúsculas; no le pediremos que siga ninguna convención en concreto, pero debería elegir aquellas que le resultaran útiles y seguirlas de manera coherente.

Indentación coherente

Una indentación coherente del código ayuda al lector a comprender la estructura lógica de mismo,
al facilitarle la tarea de ver dónde acaban las sentencias if y los bucles while, etc. 
Debería hacer uso de estrategias coherentes; por ejemplo, sea coherente en cuanto a si pone el corchete en la misma línea que el if o en la línea siguiente, o en cuanto a la apariencia de sus bloques try-catch-finally.Examine el código del libro de texto para observar una muestra de estilo; puede desarrollar su propio código con total libertad si le resulta más cómodo.
Emacs proporciona un modo autoindent, que activa la indentación automática. Debería utilizarlo para dar formato a su código al mismo tiempo que lo escribe y volver a darle formato después de
realizar alguna modificación. También puede usar grind para dar a su código un formato decente para la impresión, incluso si el fichero fuente no está bien indentado.

Comentarios informativos

No cometa el error de escribir comentarios por todas partes --un comentario malo o inútil es peor que no poner nada. Si la información está clara en el código, el añadir un comentario simplemente supondrá trabajo de más para el lector.
    i++;    // se incrementa i     ESTE COMENTARIO ES INÚTIL
Los buenos comentarios añaden información al código de manera clara y concisa. Por ejemplo, los comentarios son informativos si:
  • Permiten que el lector evite leer el alguna parte del código: el siguiente comentario ahorra al lector el esfuerzo de tener que averiguar el efecto de algunas fórmulas complicadas, y pone de manifiesto la intención del programador, de manera que las fórmulas se puedan revisar más tarde.
    // calcula la desviación estándar de los elementos de la lista que son 
    // menores que el valor límite
    
    for (int i=0; i<n; i++) {
    
        //...
    
    }
    Una aplicación importante de este tipo de comentario consiste en documentar los argumentos y los valores que devuelven las funciones, de modo que los clientes no tengan que leer la implementación para comprender cómo usar la función.
     
  • Explican un algoritmo o paso oscuro: esto es particularmente importante cuando los resultados
    de algún paso no quedan claros en ese trozo de código. Debería explicar algoritmos que puedan resultar engañosos, operaciones con efectos secundarios, números mágicos del código, etc.
    // Señal de que una nueva petición de transferencia se ha completado y está lista
    // para ser procesada. El hilo principal comenzará la transferencia del disco
    // la próxima vez que despierte y se dé cuenta de que esta variable ha cambiado.
    
    buffer_manager.active_requests ++;
  • Indican supuestos: ¿bajo qué supuestos funciona adecuadamente una parte del código?
    // La memoria intermedia (buffer) contiene al menos un caracter.
    // Si la memoria intermedia está vacía, el gestor de interrupciones vuelve sin
    
    // llamar a esta función.
    
    c = buffer.get_next_character();
  • Señalan deficiencias del código y partes de código incompleto: es habitual que la primera versión del código no esté completa; es importante señalar el código que se sabe que es incorrecto. Si se le agota el tiempo de entrega de un ejercicio y presenta un programa que no funciona correctamente en todas las entradas, esperamos que su código muestre que usted es consciente de esas deficiencias.
    if (n > 0) {
    
        average = sum / n;
    
    } else {
    
        // XXX necesita utilizar el promedio de decaimiento de la  iteración anterior.
        // Por ahora, use simplemente un valor arbitrario. 
        average = 15;
    
    }
Consejos:
  • No escriba primero el código para luego comentarlo; coméntelo sobre la marcha. Es poco probable que pueda volver y hacerlo más tarde.
  • No le exigiremos que escriba comentarios en cada objeto del programa como se hace en algunos cursos de ingeniería del software. Sin embargo, su nota dependerá considerablemente de la claridad del código y puede que alguna parte del programa que esté clara para usted, no resulte tan clara para el lector. Por lo tanto, le conviene añadir comentarios aclaratorios a todas las clases, campos y métodos.

lunes, octubre 25, 2010

Descargar documentos desde la red

Para descargar un archivo desde la red se utiliza la clase URL para tener acceso al archivo o documento de red y se abren un flujo de entrada y otro de salida para recorrer y copiar dicho documento.

import java.io.*;
import java.net.*;

public class TestDescarga {
    public static void main(String[] args) {
        // Por simplicidad se supondrá que el archivo a descargar y la ruta donde
        // se va a guardar son conocidas.
        String origen = "http://mit.ocw.universia.net/1.00/s02/class-sessions/lecture-31/lecture-31.pdf";
        String destino = "c:/downloads/salida.pdf";
        descargar(origen, destino);
    }

    public static void descargar(String origen, String destino) {
        try {
            // Paso 1: crear el objeto URL para enlazar la dirección del documento
            URL url = new URL(origen);

            // Paso 2: crear un flujo de entrada para leer el contenido del documento
            byte[] data = new byte[1024];
            DataInputStream in = new DataInputStream(url.openStream());

            // Paso 3: crear el archivo de salida
            FileOutputStream out = new FileOutputStream(destino);

            // Paso 4: recorrer el archivo de entrada
            int leidos;
            while(true) {
                leidos = in.read(data);
                if(leidos >= 0) out.write(data, 0, leidos);
                else break;
            } 
            out.flush();
            out.close();
        }
        catch(MalformedURLException x) {
            System.err.println("Error, dirección mal formada, intente más tarde");
        }
        catch(IOException x) {
            System.err.println("Error de IO: " + x.getMessage());
        }
    }
}

jueves, octubre 21, 2010

Números Primos

Verificación

Teniendo en cuenta que, por definición, un número primo es aquel que es divisible exclusivamente por sí mismo y por la unidad, se puede escribir una función que verifique si un número entero es primo dividiéndolo por todos los números entre 1 y él, y finalmente contar cuántos divisores tuvo. Si la cantidad de divisores es 2, entonces el número es primo, de lo contrario no lo es. Este algoritmo se puede representar como:

// Version inicial.  Cuenta el numero de divisores y si es menor o igual
// que dos entonces es primo.
    public static boolean esPrimoV1(long n) {
        long contador=0;
        for(long i=1; i<=n; i++) {
            if(n%i == 0) contador  ;
        }
        if(contador>=2) return false;
        else return true;
    }

Este algoritmo, si bien identifica si el número es primo, es bastante ineficiente, entre otras por razones tales como la espera para hacer todas las divisiones para decidir que un número no es primo aunque, si se omite la división por uno y por el mismo número, basta con encontrar un solo divisor más para determinar que el número no es primo. De la misma manera, el algoritmo divide el número por todos los pares anteriores a él cuando no es necesario, ya que diviéndolo por dos es suficiente para saber si es múltiplo de un número par.

Una versión optimizada del algoritmo es la siguiente:

// Version seis.  Hace los cálculos de funciones solo cuando es necesario
    public static boolean esPrimoV6(long n) {
        double raiz = Math.sqrt(n);
        if(n==2) return true;
        if(n%2==0) return false;
        for(long i=3; i<=raiz; i+=2) {
            if(n%i == 0) return false;
        }
        return true;
    }

Se sugiere calcular con las dos versiones el tiempo que se tarda en determinar si el número entero más grande que puede manejar java (Long.MAX_VALUE) es primo o no.

Generación

Si se quiere generar un conjunto de números primos, una posible alternativa es utilizar el método de Eratóstenes, en el cual se ubican en un vector todos los posibles números en un rango, e iniciando en el número 2 se marcan como no primos todos los múltiplos de dicho número; el proceso continua para todos los números no marcados.

El siguiente método genera un vector con todos los números enteros entre 1 y 2 a la 31:

// Generación de primos por el método de Eratóstenes
    public static int[] generarPrimos() {
        boolean[] tmp = new boolean[Integer.MAX_VALUE/2];
        for(int i=0; i<tmp.length; i++) tmp[i]=true;
        int contador  = tmp.length;
        int raiz      = (int) Math.sqrt(tmp.length);
        for(int i=2; i<=raiz; i++) {
            if(tmp[i]!=true) continue;
            for(int j=i*i; j<tmp.length;j+=i){
                if(tmp[j]==true) {
                    contador--;
                    tmp[j]=false;
                }
            }
        }
        int   j         = 0;
        int[] respuesta = new int[contador];
        for(int i=0; i<tmp.length; i++) if(tmp[i]==true) respuesta[j++]=i;
        return respuesta;
    }

Nótese que el arreglo tmp podría usarse para determinar de forma inmediata si un número dado es primo o no, pues bastaría con mirar si la posición respectiva de ese número en el arreglo hay un valor de falso o verdadero.

Ruta más corta - Solución por el algoritmo de Dijkstra

Para solucionar el problema de la ruta más corta entre dos nodos de un grafo se puede utilizar el Algoritmo de Dijkstra, el cual sigue el siguiente procedimiento para calcular la ruta más corta desde el nodo origen hasta cada uno de los nodos del grafo:


  • Crea una listas de nodos para almacenar los nodos con distancia mínima ya calculada
  • Crear una cola de prioridad para los nodos pendientes de evaluar
  • Inserta el nodo origen a la cola de prioridad
  • Mientras que haya nodos en la cola de prioridad
    • Extrae el primer nodo de la cola de prioridad (tmp)
    • Agrega el nodo tmp a la lista de nodos ya calculados
    • Genera una lista de los nodos conectados al nodo tmp que no estén en la lista de ya calculados
    • Para cada nodo de la lista (nod)
      • Calcula la distancia al origen con la distancia entre tmp y nod más la distancia calculada entre el origen y tmp.
      • Si el nodo nod no está en la cola de prioridad lo agrega
      • Si el nodo nod ya está en la cola de prioridad y la distancia con la que está guardado en la cola es menor, lo deja como está y sino, lo actualiza con la distancia calculada
    • Fin
  • Fin
Al finalizar este procedimiento se tiene una lista con la menor distancia desde el origen a cada nodo.

La clase Grafo descrita en un post anterior se puede modificar para incluir un nuevo método que calcula la menor ruta usando el algoritmo de Dijkstra con dos nuevos métodos: uno para calcular la distancia entre el origen y todos lo nodos, guardando estos resultados en una lista, y el segundo para mostrar la ruta entre el origen y el nodo destino tomando la información de la lista de distancias calculadas.  Se implementa también un método adicional para verificar si un nodo ya está en la lista de terminados:

import java.util.*;

public class Grafo {
    char[]  nodos;  // Letras de identificación de nodo
    int[][] grafo;  // Matriz de distancias entre nodos
    String  rutaMasCorta;                           // distancia más corta
    int     longitudMasCorta = Integer.MAX_VALUE;   // ruta más corta
    List<Nodo>  listos=null;                        // nodos revisados Dijkstra

    // construye el grafo con la serie de identificadores de nodo en una cadena
    Grafo(String serieNodos) {
        nodos = serieNodos.toCharArray();
        grafo = new int[nodos.length][nodos.length];
    }

    // asigna el tamaño de la arista entre dos nodos
    public void agregarRuta(char origen, char destino, int distancia) {
        int n1 = posicionNodo(origen);
        int n2 = posicionNodo(destino);
        grafo[n1][n2]=distancia;
        grafo[n2][n1]=distancia;
    }

    // retorna la posición en el arreglo de un nodo específico
    private int posicionNodo(char nodo) {
        for(int i=0; i<nodos.length; i++) {
            if(nodos[i]==nodo) return i;
        }
        return -1;
    }
    
    // encuentra la ruta más corta desde un nodo origen a un nodo destino
    public String encontrarRutaMinimaDijkstra(char inicio, char fin) {
        // calcula la ruta más corta del inicio a los demás
        encontrarRutaMinimaDijkstra(inicio);
        // recupera el nodo final de la lista de terminados
        Nodo tmp = new Nodo(fin);
        if(!listos.contains(tmp)) {
            System.out.println("Error, nodo no alcanzable");
            return "Bye";
        }
        tmp = listos.get(listos.indexOf(tmp));
        int distancia = tmp.distancia;  
        // crea una pila para almacenar la ruta desde el nodo final al origen
        Stack<Nodo> pila = new Stack<Nodo>();
        while(tmp != null) {
            pila.add(tmp);
            tmp = tmp.procedencia;
        }
        String ruta = "";
        // recorre la pila para armar la ruta en el orden correcto
        while(!pila.isEmpty()) ruta+=(pila.pop().id + " ");
        return distancia + ": " + ruta;
    }

    // encuentra la ruta más corta desde el nodo inicial a todos los demás
    public void encontrarRutaMinimaDijkstra(char inicio) {
        Queue<Nodo>   cola = new PriorityQueue<Nodo>(); // cola de prioridad
        Nodo            ni = new Nodo(inicio);          // nodo inicial
        
        listos = new LinkedList<Nodo>();// lista de nodos ya revisados
        cola.add(ni);                   // Agregar nodo inicial a la cola de prioridad
        while(!cola.isEmpty()) {        // mientras que la cola no esta vacia
            Nodo tmp = cola.poll();     // saca el primer elemento
            listos.add(tmp);            // lo manda a la lista de terminados
            int p = posicionNodo(tmp.id);   
            for(int j=0; j<grafo[p].length; j++) {  // revisa los nodos hijos del nodo tmp
                if(grafo[p][j]==0) continue;        // si no hay conexión no lo evalua
                if(estaTerminado(j)) continue;      // si ya fue agregado a la lista de terminados
                Nodo nod = new Nodo(nodos[j],tmp.distancia+grafo[p][j],tmp);
                // si no está en la cola de prioridad, lo agrega
                if(!cola.contains(nod)) {
                    cola.add(nod);
                    continue;
                }
                // si ya está en la cola de prioridad actualiza la distancia menor
                for(Nodo x: cola) {
                    // si la distancia en la cola es mayor que la distancia calculada
                    if(x.id==nod.id && x.distancia > nod.distancia) {
                        cola.remove(x); // remueve el nodo de la cola
                        cola.add(nod);  // agrega el nodo con la nueva distancia
                        break;          // no sigue revisando
                    }
                }
            }
        }
    }

    // verifica si un nodo ya está en lista de terminados
    public boolean estaTerminado(int j) {
        Nodo tmp = new Nodo(nodos[j]);
        return listos.contains(tmp);
    }

    // encontrar la ruta mínima por fuerza bruta
    public void encontrarRutaMinimaFuerzaBruta(char inicio, char fin) {
        int p1 = posicionNodo(inicio);
        int p2 = posicionNodo(fin);
        // cola para almacenar cada ruta que está siendo evaluada
        Stack<Integer> resultado = new Stack<Integer>();
        resultado.push(p1);
        recorrerRutas(p1, p2, resultado);
    }

    // recorre recursivamente las rutas entre un nodo inicial y un nodo final
    // almacenando en una cola cada nodo visitado
    private void recorrerRutas(int nodoI, int nodoF, Stack<Integer> resultado) {
        // si el nodo inicial es igual al final se evalúa la ruta en revisión
        if(nodoI==nodoF) {
            int respuesta = evaluar(resultado);
            if(respuesta < longitudMasCorta) {
                longitudMasCorta = respuesta;
                rutaMasCorta     = "";
                for(int x: resultado) rutaMasCorta+=(nodos[x]+" ");
            }
            return;
        }
        // Si el nodoInicial no es igual al final se crea una lista con todos los nodos
        // adyacentes al nodo inicial que no estén en la ruta en evaluación
        List<Integer> lista = new Vector<Integer>();
        for(int i=0; i<grafo.length;i++) {
            if(grafo[nodoI][i]!=0 && !resultado.contains(i))lista.add(i);
        }
        // se recorren todas las rutas formadas con los nodos adyacentes al inicial
        for(int nodo: lista) {
            resultado.push(nodo);
            recorrerRutas(nodo, nodoF, resultado);
            resultado.pop();
        }
    }

    // evaluar la longitud de una ruta
    public int evaluar(Stack<Integer> resultado) {
        int  resp = 0;
        int[]   r = new int[resultado.size()];
        int     i = 0;
        for(int x: resultado) r[i++]=x;
        for(i=1; i<r.length; i++) resp+=grafo[r[i]][r[i-1]];
        return resp;
    }

    public static void main(String[] args) {
        Grafo g = new Grafo("abcdef");
        g.agregarRuta('a','b', 3);
        g.agregarRuta('a','e', 6);
        g.agregarRuta('a','f',10);
        g.agregarRuta('b','c', 5);
        g.agregarRuta('b','e', 2);
        g.agregarRuta('c','d', 8);
        g.agregarRuta('c','e', 9);
        g.agregarRuta('c','f', 7);
        g.agregarRuta('d','f', 4);
        g.agregarRuta('e','f', 4);
        char inicio = 'a';
        char fin    = 'd';
        String respuesta = g.encontrarRutaMinimaDijkstra(inicio, fin);
        System.out.println(respuesta);
    }
}


Esta clase requiere del uso adicionalmente de la clase Nodo, que va a servir para la cola de prioridad y para llevar registro de la distancia mínima desde el origen a un nodo, así como la referencia al nodo inmediatamente anterior:


public class Nodo implements Comparable<Nodo> {
    char id;
    int  distancia   = Integer.MAX_VALUE;
    Nodo procedencia = null;
    Nodo(char x, int d, Nodo p) { id=x; distancia=d; procedencia=p; }
    Nodo(char x) { this(x, 0, null); }
    public int compareTo(Nodo tmp) { return this.distancia-tmp.distancia; }
    public boolean equals(Object o) {
        Nodo tmp = (Nodo) o;
        if(tmp.id==this.id) return true;
        return false;
    }
}

martes, octubre 19, 2010

Programación Cliente/Servidor básica

Una aplicación cliente servidor requiere básicamente tres elementos: un programa servidor que atiende las peticiones de los clientes; un programa cliente que se conecta al servidor y; un protocolo de comunicaciones que indica la secuencia de mensajes que se pasan un cliente y un servidor.

En el siguiente ejemplo, el servidor será multiusuario, es decir, atenderá simultáneamente varios clientes, y para ello se utilizarán hilos -uno por cada cliente que se conecte- que atenderán en forma exclusiva el proceso de cada cliente. El cliente, por su parte, se conectará al servidor e iniciarán un diálogo (protocolo) en el cual el cliente enviará un número y el servidor devolverá el valor del área del círculo de radio igual al valor envíado por el cliente. El proceso para cada cliente terminará cuando se le envíe al servidor un valor negativo.

Servidor

El proceso del servidor inicia creando un ServerSocket para escuchar peticiones por el puerto 65432 (debe ser un valor entre 1225 y 65535 que no esté siendo utilizado en el equipo donde va a correr). Cada vez que un cliente ingrese se crea un nuevo objeto de la clase Socket y se instancia un nuevo hilo de la clase HiloServidor que se encargará de manejar la interacción con el cliente.


import java.io.*;
import java.net.*;
public class ServidorAreaCirculo {
    final int puerto = 65432;   // puerto sobre el que se esperarán conexiones
    ServerSocket  ss;
    public void proceso() {
        try {
            ss = new ServerSocket(puerto);
            while(true) {                       // ciclo infinito para esperar conexiones
                Socket socket = ss.accept();    // espera hasta que un cliente se conecta
                Thread   hilo = new Thread(new HiloServidor(socket));   // crea hilo hijo
                hilo.start();                   // inicia el hilo hijo que atiende al cliente
            }
        }
        catch(IOException x) {
            System.err.println("Error de conexión: " + x.getMessage());
        }
    }

    class HiloServidor implements Runnable {
        Socket socket;
        HiloServidor(Socket s) { socket = s; }
        public void run() {
            try {
                // crea flujos de entrada y salida
                BufferedReader in = new BufferedReader(
                                    new InputStreamReader(socket.getInputStream()));
                PrintWriter   out = new PrintWriter(socket.getOutputStream());
                // paso 1: envio mensaje de bienvenida
                out.println("Bienvenid@, este servidor calcula áreas de círculos");
                while(true) {
                    // paso 2: solicita envio del radio del círculo
                    out.println("Digite radio del circulo (ó número negativo para terminar): ");
                    out.flush();
                    // paso 3: recibe el radio y genera la salida a enviar
                    String cadena = in.readLine();
                    try {
                        double  radio = Double.parseDouble(cadena);
                        if(radio<0) break;
                        double area = Math.PI*Math.pow(radio,2);
                        cadena = "El área de un círculo de radio " + radio + " es " +
                                String.format("%,.4f", area);
                    }
                    catch(NumberFormatException x) {
                        cadena = "Error, la cadena recibida no es un número válido";
                    }
                    // paso 4: devuelve el mensaje al usuario
                    out.println(cadena);
                    out.flush();
                }
                out.println("Gracias por venir, vuelve pronto");
                out.flush();
                socket.close();
            }
            catch(IOException x) {
                System.err.println(x.getMessage());
            }
        }
    }

    public static void main(String[] args) {
        ServidorAreaCirculo s = new ServidorAreaCirculo();
        s.proceso();
    }
}


Cliente

En este caso, el cliente inicia abriendo un socket con el equipo y puerto donde debe estar esperando el programa servidor. Para la prueba se supone que el servidor debe estar ejecutándose en la misma máquina del cliente (localhost) en el puerto 65432.


import java.io.*;
import java.io.*;
import java.net.*;
import javax.swing.*;
import static javax.swing.JOptionPane.*;

public class ClienteAreaCirculo {
    public void proceso() {
        try {
            // Se crea socket conectado al servidor y puerto conocidos
            Socket     socket = new Socket("localhost",65432);
            // Se crean los flujos de entrada y salida
            PrintWriter   out = new PrintWriter(socket.getOutputStream());
            BufferedReader in = new BufferedReader(
                                new InputStreamReader(socket.getInputStream()));
            // Paso 1: se recibe mensaje de bienvenida del servidor
            String cadena = in.readLine();
            System.out.println(cadena);
            while(true) {
                // Paso 2: se recibe mensaje de solicitud de número
                cadena = in.readLine();
                System.out.println(cadena);
                // Paso 3: se pregunta al usuario el número a enviar
                cadena = showInputDialog(cadena);
                // Paso 4: se envia el número al servidor
                out.println(cadena);
                out.flush();
                // Paso 5: se recibe la respuesta del servidor
                cadena = in.readLine();
                System.out.println(cadena);
                if(cadena.startsWith("Gracias por venir")) break;
            }
        }
        catch(IOException x) {
           System.err.println("Error de conexión: "+x.getMessage());
        }

    }

    public static void main(String[] args) {
        ClienteAreaCirculo c = new ClienteAreaCirculo();
        c.proceso();
    }
}

Multiprocesamiento recursivo en JAVA 7

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 relativ...