Resolviendo el #TuentiContest: Problema 6 – The clock

He vuelto. Después de dos problemas con tanta gracia por detrás, este era un merecido descanso. El problema 6 nos daba un reloj digital de leds (de esos que tienen una chicharra y un radio que suena horrible como despertador) y una cantidad de segundos para que nosotros contáramos cuantos leds se encendían durante ese tiempo. Este también lo resolví en C++ y afortunadamente no tuve que lidiar con ningún formato de entrada que me avergonzara. Recuerda que también tengo publicadas mis soluciones a los otros problemas del evento. Los problemas 5, 6 y 7 fueron mi racha de bugs durante la competencia. De hecho el problema 5 y este los envié mal cuando hice el submit. Lo que pasó en el 7 fue que estaba estuve un bug donde no era (por no detenerme a pensar) y perdí mucho tiempo. Al final lo envié bien, pero no nos adelantemos. Ahora, el reloj.

Análisis del problema

No voy a darle muchas vueltas a este asunto, aquí no hay grafos, recursiones, pilas ni nada que nos complique la vida. La gracia es saber cuántas luces se encienden con cada número y cuáles son los límites de cada posición. Un lápiz, un papel y una cara de tonto mientras pinto los número y cuento con la punta del lápiz, me dan esa información. Del 0 al 9 la cantidad de luces son, respectivamente: 6,2,5,5,4,5,6,3,7,6. Aquí viene la opción del que se faja (o se lo curra, o se esfuerza, o como sea que se diga en tu país) y del flojo. En este caso, yo me uní a los últimos sin vergüenza alguna. Bueno, sinceramente mi orgullo me hizo intentar ser de los primeros. Verás, con la cantidad de segundos, un par de divisiones enteras y un par de residuos, es muy fácil saber el valor final de cada luz. Y si tienes precalculado (ya ven que me gusta precalcular cosas) cuantas luces encienden por cada unidad de tiempo, puedes responder rápidamente. No hubo forma. Logré las luces de cada unidad de tiempo (creo) pero luego me volví un lío combinándolas así que eso de “responder rápidamente” al final no se me dio y me pasé al lado oscuro. ¿En qué consistió el lado oscuro? en un ciclo que vaya segundo a segundo moviendo cada dígito y acumulando el resultado. He visto que la mayoría de las soluciones lo resuelven así y en realidad es suficiente. Es un algoritmo de orden lineal y tiene (si NO lo implementas como yo) poco margen de error. El detalle más importante es notar que las horas solo llegan hasta el 23 y luego vuelven a cero, mientras que los minutos y segundos van hasta el 59. Que sí, que sí, que estoy descubriendo el agua tibia. Solución enviada (incorrecta) Sin más preámbulos, mi código. Te invito a que descubras dónde metí la pata antes de verlo en la siguiente sección.

#include <iostream>
using namespace std;

int main() {
  int seconds;
  int digits[10] = {6,2,5,5,4,5,6,3,7,6};
  while(cin >> seconds) {
    unsigned long result=0;
    while(seconds >= 0)
      for(int a=0;a<2 && seconds>=0;a++)
      for(int b=0;b<10 && seconds>=0;b++){
        if(a==2 && b==4) break;
        for(int c=0;c<6 && seconds>=0;c++)
        for(int d=0;d<10 && seconds>=0;d++)
        for(int e=0;e<6 && seconds>=0;e++)
        for(int f=0;f<10 && seconds>=0;f++){
          result += digits[a]+digits[b]+digits1+digits[d]+
                    digits[e]+digits[f];
          seconds--;
        }
      }
    }
    cout << result << endl;
  }
  return 0;
}

Solución correcta Del bug no me di hasta que llegué al otro problema con el fulano reloj y lo que hice fue modificar este algoritmo acorde al planteamiento (así que allá tampoco verás mucha gracia en la solución) y corregir el bug, obviamente.

for(int a=0;a<3 && seconds>=0;a++)

En esta solución sí hay mucha leña que cortar. Esos seis loops podrían reescribirse como dos, que aunque en cuestión de velocidad estés diciendo lo mismo, tienes menos sitios donde meter la pata (creo). La idea sería algo como esto:

for(int i=0;i<seconds;i++) {
  encender(leds,i);
  result += sumar(leds);
}
cout << result << endl;

Definiendo la funcion encender como una funcion que recibe un arreglo de 6 enteros y almacena en ellos los digitos a mostrar en el instante de tiempo i y la función sumar que recibiría los seis dígitos y sumaría las luces de cada uno. Como ven, las funciones encender y sumar involucran parte de los ciclos que escribí explícitamente en mi solución, por lo tanto ambas soluciones son igual de eficientes en velocidad. Pero, al ser una solución más modular, y sin tantos contadores, es más fácil de depurar y revisar. La solución que quiero ver (y si la hiciste, por favor deja tu enlace en los comentarios) es la forma directa O(1) que les comenté en el análisis. Con esa forma nos ahorramos los ciclos y los contadores y simplemente respondemos al segundo que nos pongan. ¿Alguien la tiene o sabe dónde está? Y tú ¿cómo lo resolviste?

One thought on “Resolviendo el #TuentiContest: Problema 6 – The clock

Deja un comentario