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

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