Resolviendo el #TuentiContest: Problema 1 – Super hard Sum

Hola de nuevo. He conseguido un hueco en el día de hoy para comenzar a publicar mis soluciones  a los problemas de la 1º Competición de Programación Tuenti. Mi intención es seguir el orden de la competencia así que empezaré con el primer problema. Les ofreceré mis soluciones usando Java y bash.

Análisis del problema

El planteamiento del problema era bastante sencillo. Cada línea del input contendría una serie de números y la idea era dar el resultado de la suma de ellos. Las únicas condiciones que mencionaban eran que los números podrían ser negativosmuy grandes y que podrían estar separados por varios espacios. Con este planteamiento empezamos a considerar varias cosas:

  1. No nos dicen qué tipo de números son (enteros o reales) ni en que basen están
  2. Solo nos hablan de separados por varios espacios como variación de la entrada
  3. Los números pueden ser muy grandes

La consideración más importante es la número 3 pues les da permiso a poner números que no quepan en las representaciones tradicionales (32 o 64 bits). Debido a esto, el lenguaje que usemos debe tener implementada esa capacidad sino queremos hacerlo a mano. Con los casos de prueba además nos enteramos que los números pueden contener uno o varios ceros a la izquierda. Que contengan un solo cero a la izquierda (estaba el caso 010) abre el planteamiento a un problema de interpretación pues queda la duda de si el número es un octal o undecimalTenías que probar ambas formas para darte cuenta que efectivamente era un número decimal con un cero a la izquierda. Personalmente, no me gusta que haya información escondida en los test pues para eso está el planteamiento del problema.

Solución enviada

Afortunadamente Java implementa una aritmética de números grandes con sus clases BigInteger y BigDecimal y es muy fácil de utilizar. Además, como los números estaban en base decimal, BigDecimal funcionaría perfectamente así tuviera mil ceros a la izquierda. La condición de los espacios en blanco no presenta ningún problema, pues el parseo automático que ofrece la clase Scanner se encargará de lidiar con ello. El no decirnos en el planteamiento qué tipo de número eran nos obliga en primera instancia a usar BigDecimal para cubrir la posibilidad de que nos enviaran números reales. En definitiva, la sintaxis de Java hace el programa un poco largo pero igual es muy fácil de leer. Mi primera solución es la siguiente:

import java.math.BigDecimal;
import java.util.Scanner;

public class HardSum {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    while(scan.hasNextLine()) {
      String line = scan.nextLine();
      Scanner numbers = new Scanner(line);
      BigDecimal result = new BigDecimal("0");
      while(numbers.hasNext()){
        BigDecimal other = new BigDecimal(numbers.next());
        result = result.add(other);
      }
      System.out.println(result);
    }
  }
}

Solución mejorada

Mi solución al primer problema la programé desde mi Mac y por lo tanto, el uso de la consola es mucho más limitado (por defecto) que el de Linux. Sin embargo, una vez parado frente a una consola decente con su set completo de programas, nos encontramos con dos amigos que nos solucionarán todos los problemas.

  1. sed: Para corregir los posibles errores de input
  2. bc: La calculadora por consola preinstalada de Linux

Finalmente la solución Linux:

sed -re 's/(^|[ -])0+/1/g' -e 's/ ([0-9])/+1/g'
     -e 's/s+//g' -e 's/^+//g' | bc

Utilizo sed para eliminar los espacios en blanco repetidos y los que estén al principio y al final, elimino los ceros a la izquierda (dejando el posible signo menos) y precedo con un “+” todos los números positivos excepto el primero para indicarle una suma a la calculadora.

OK! Your program gives the right answer!
--- OUTPUT CHECK --------------------------
Line 1  [OK!]  : 0
Line 2  [OK!]  : 2
Line 3  [OK!]  : 0
Line 4  [OK!]  : 1
Line 5  [OK!]  : -1
Line 6  [OK!]  : 0
Line 7  [OK!]  : 10
Line 8  [OK!]  : 1

Me gusta bastante la segunda solución. Definitivamente, la consola de Linux no deja de sorprenderme. No sé si esté dejándome algún caso borde de lado, no creo. Si tienes alguna duda, quieres compartir tu solución o ves algún fallo en la mía, estás invitados a dejar un comentario. Y tú ¿en qué lenguaje lo resolviste?

4 thoughts on “Resolviendo el #TuentiContest: Problema 1 – Super hard Sum

Deja un comentario