Resolviendo el #TuentiContest: Problema 2 – TLang

21Jun11

¡Oh! las interpretaciones y los enunciados incompletos.

Continúo publicando mis soluciones. Para el segundo problema nos pedían interpretar un «lenguaje» inventado con los siguientes ejemplos:

Entrada:
^= 1 2$
^# 2 2$
^@ 3 1$


Salida:
3
4
2


Esta solución la implementé en Java y hace uso de una pila para interpretar las peticiones.

Análisis del problema

De los problemas con huecos en su enunciado, este es uno de los peorcitos (a mi parecer). Para empezar con los ejemplos dados, ya aparecen varias interpretaciones, al menos para la segunda entrada, la cual puede ser perfectamente un producto o una potencia. La primera y la tercera indican más claramente suma y resta (la segunda podría ser suma también pero asumimos que cada operador es único).

De aquí que una primera implementación puede llevarnos (como de hecho me llevó) al fracaso total. Primero, porque no consideré operaciones anidadas y segundo porque no pensé que alguno de esos operadores pudiera ser también unario.

Así que, como fue algo usual durante la competencia, el resto de la información tenías que sacarla de los datos de prueba.

--- INPUT ---------------------------------
^= ^# ^# 245 136$ ^@ 16$$ 17$
^@ ^# 176 ^# 113 185$$$
^= 275 ^# 163 264$$
^# ^= 10 ^# 149 74$$ 191$
^= ^@ 240 172$ ^@ 62 33$$

Con el primer ejemplo vemos lo incompleto del planteamiento del problema. Para empezar, efectivamente te muestran que puede haber operaciones anidadas (con lo cual los símbolos «^» y «$» pasan a representar los paréntesis de las matemáticas) y además, te lanzan el detallazo de que el operador «@» (que supuestamente representaba la resta de dos números) puede recibir un solo parámetro.

Así que a los ejemplos que te muestran el «uso» del lenguaje inventado debemos sumarle que la resta no es resta siempre. También puede ser el operador unario «-«.

El problema es que dada la picardía del test puedes preguntarte si los otros operadores podrían ser unarios también. Tiene «sentido» para la suma pues normalmente usamos el signo «+» para denotar los números positivos. Así que cosas como «+2» o «+4» son válidas (aunque redundantes). Pero ¿y la multiplicación? «*3» no tiene ningún sentido (no, no vale decir el contenido de 3, C freaks). ¿O será que el único unario es la resta, por la redundancia y el absurdo de los otros dos? Personalmente pienso que cualquier opción es válida dado que el problema ni pone ejemplos ni aclara nada.

Dicho lo dicho, lo que asumí fue lo siguiente: cuando un operador recibe un solo parámetro, asumo que el primero es cero. Así obtengo la redundancia del «+», el negativo del «-» y acepto vivir con el factor cero de la multiplicación. Quizás podría ser más limpio que para la multiplicación el primer operador sea «1», pero es ver una zebra blanca de rayas negras o negra de rayas blancas (además de que, para empezar, matemáticamente «*3» no tiene sentido).

Solución enviada

Mi solución se basa en el uso de una pila para lidiar con la anidación. Voy agregando operadores y operandos a la pila y en el momento que me encuentre un «$», desempilo para realizar la operación. He visto una buena solución utilizando PHP y expresiones regulares que la hacen mucho más corta en número de líneas (y me gusta más que la mía) pero que aumenta la complejidad de ejecución al tener que evaluar patrones en cada iteración.

Sin más preambulos, aquí va:

import java.util.*;
public class TLang {

  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);

    while(scan.hasNextLine()) {
      String line = scan.nextLine();
      Scanner calc = new Scanner(line);
      ArrayList<String> pila = new ArrayList<String>();
      while(calc.hasNext()){
        String token = calc.next();
        pila.add(token);
        while(token.endsWith("$")){
          token = resolver(pila);
        }
      }

      System.out.println(pila.get(0));
    }
  }

  private static String resolver(ArrayList<String> pila) {
    String s2 = pila.remove(pila.size()-1);
    String s1 = pila.remove(pila.size()-1);
    String op = (pila.size() > 0) ? pila.remove(pila.size()-1) : null;

    if(s1.startsWith("^")) {
      if (op != null) pila.add(op);
      op = s1;
      s1 = "0";
    }

    int dolar = s2.indexOf("$");
    String cantidad = s2.substring(dolar); // $+
    s2 = s2.substring(0,dolar);

    int bd1 = Integer.parseInt(s1);
    int bd2 = Integer.parseInt(s2);

    int result;
    if(op.equals("^=")) {
      result = bd1 + bd2;
    } else if(op.equals("^#")) {
      result = bd1 * bd2;
    } else {
      result = bd1 - bd2;
    }

    String newResult;
    if(cantidad.length() > 1){ // Si se cierra más de $
      newResult = result+cantidad.substring(1); // dejo el resto
    } else {
      newResult = String.valueOf(result);
    }

    pila.add(newResult);
    return newResult;
  }
}

Solución mejorada

Sin duda, me gusta más la solución que les comenté de expresiones regulares. Y sobre la mía tengo una cosa que decir también. Pequé de novato al usar un ArrayList como pila (he resaltado la línea de la vergüenza), teniendo las clases LinkedList y (mejor aún) Stack a mi disposición. Si SUN Microsystems (Q.E.P.D.) hubiese visto esto, me revocaba la certificación.

Y tú ¿en qué lenguaje lo resolviste?

Filed under: Computación, Tiempo Libre, TuentiContest   |  5 Comments
Etiquetas: algoritmos, competencia, contest, java, pila, problemas, programación, soluciones, tlang, tuenti