<< Cuadrado lleno de
múltiplos de 17>>

Dificultad:

Se necesitan solamente conocimientos elementales de matemática. Algunos de los temas de computacion se pueden repasar leyendo las lecciones anteriores.

Lecciones anteriores:

Midiendo tiempos (con más información sobre como medir el tiempo que tarda el programa)

Bases de numeración (con más información sobre como separar un número en cifras)

Vamos a analizar un problema y comparar varias formas de resolverlo. En esta lección mostramos la solución más sencilla que es justamente la más lenta.

El problema original:

En la Segunda Ronda del Torneo del año 2000 tomamos un problema en tercer nivel que decía:

Se tiene un tablero de 4x4 en el que se anota un dígito en cada casilla. En cada fila y en cada columna se forma un número de cuatro dígitos. Un tablero de este tipo es legal si los ocho números que se forman así son múltiplos de 17. ¿Cuántos tableros legales distintos hay?

Resulto bastante difícil, así que la idea es discutir un poco algunas maneras de hacer que valla más rápido y la solución termine en un tiempo razonable.

Primera Propuesta:

Vamos a empezar con la versión más simple del programa y analizar algunas variaciones. El programa prueba con todas los posibles números en las primeras tres filas y trata de completar cada columna para que sea un múltiplo de 17. Si lo logra se fija si la última fila también es múltiplo de 17 y en este caso aumenta el contador

El programa separa los números en cifras utilizando una función. Llama a otra función para que busque cuál debería ser la ultima cifra de cada columna a medida que lo necesita. Para todas las cuentas usamos división(\) entera y módulo (Mod) que andan más rápido. El programa en QB es:

Dim L1 As Long
Dim L2 As Long
Dim L3 As Long

Dim C1 As Long
Dim C2 As Long
Dim C3 As Long
Dim C4 As Long

Dim Columna As Long

Dim Contador As Long

Dim Inicio As Single
Dim Tiempo As Single
Dim Pasos As Single

Inicio = Timer
Print
Print "Tiempo", "Tiempo", "Tableros", "Valor"
Print "Trans.(s)", "Estimado(H)", "Encontrados", "L1"
'L1, L2, L3 son las tres primeras filas
For L1 = 0 To 9999
  If L1 Mod 17 = 0 Then
    For L2 = 0 To 9999
      If L2 Mod 17 = 0 Then
        Tiempo = Timer - Inicio
        Pasos = L1 * 10000 + L2 + 0.1 ' "+.1" porque sino empieza de Cero
        Print Tiempo, Tiempo / Pasos * 10000 ^ 2 / 60 ^ 2, Contador, L1

        For L3 = 0 To 9999
          If L3 Mod 17 = 0 Then
            'En C1, C2, C3, C4 se guarda la ultima cifra de cada columna
            C1 = CompletarNumero(Cifra(L1, 1), Cifra(L2, 1), Cifra(L3, 1))
            C2 = CompletarNumero(Cifra(L1, 2), Cifra(L2, 2), Cifra(L3, 2))
            C3 = CompletarNumero(Cifra(L1, 3), Cifra(L2, 3), Cifra(L3, 3))
            C4 = CompletarNumero(Cifra(L1, 4), Cifra(L2, 4), Cifra(L3, 4))
            If C1 >= 0 And C2 >= 0 And C3 >= 0 And C4 >= 0 Then
              If C4 = CompletarNumero(C1, C2, C3) Then
                Contador = Contador + 1
              End If
            End If
          End If
        Next
      End If
    Next
  End If
Next
Print Contador

Function Cifra&(Numero As Long, Posicion As Long)  ' As Long
  Dim Columna As Long
  Dim Queda As Long
  Queda = Numero
  
  For Columna = 4 To Posicion + 1 Step -1'Cuenta para atras
    Queda = Queda \ 10
  Next Columna
  Cifra = Queda Mod 10
  'en C: Return Cifra
End Function

Function CifraString&(Numero As Long, Posicion As Long)  ' As Long
  CifraString = Val(Mid$(Str$(10000 + Numero), Posicion + 2, 1))
  'en C: Return Cifra
End Function

Function CompletarNumero&(N1 As Long, N2 As Long, N3 As Long)  'As Long
  Dim Valor As Long
  Dim Sobra As Long
  Dim Falta As Long
  Valor = N1 * 1000 + N2 * 100 + N3 * 10
  Sobra = Valor Mod 17
  If Sobra <> 0 Then
    Falta = 17 - Sobra
    If Falta >= 10 Then
      Falta = -1 'ERROR
    End If
  Else
    Falta = 0
  End If
  CompletarNumero = Falta
  'Return Falta
End Function

Function CompletarNumeroBuscando&(N1 As Long,N2 As Long,N3 As Long)'As Long
  Dim Valor As Long
  Dim Ultimo As Long
  Valor = N1 * 1000 + N2 * 100 + N3 * 10
  For Ultimo = 0 To 9
    If (Valor + Ultimo) Mod 17 = 0 Then
      Exit For
    End If
  Next
  If Ultimo >= 10 Then Ultimo = -1
  CompletarNumeroBuscando = Ultimo
  'Return Ultimo
End Function

(Nota: Quizás L1, L2, L3 y C1, C2, C3, C4 deberían ser dos vectores(array) )

La primera es Cifra(Numero As Long, Posicion As Long) que se usa para separar los números en cifras. Cuenta las posiciones de izquierda a derecha, suponiendo que el número tiene cuatro "cifras" y si es necesario completa con ceros. Hay otra función que aparece como CifraString que hace exactamente lo mismo, pero utilizando cadenas de texto.

La otra función es CompletarNumero(N1 As Long, N2 As Long, N3 As Long) que dadas las primeras tres cifras de un número busca cuál es la cuarta para que sea un múltiplo de 17. Por ejemplo

CompletarNumero(1,7,0) da 0 porque 1700 es múltiplo de 17.
CompletarNumero(0,3,5) da 7 porque 0357 es múltiplo de 17.
CompletarNumero(0,0,2) da -1 para indicar un error ya que no hay ningún múltiplo de 17 entre 0020 y 0029.

La función CompletarNumeroBuscando hace lo mismo, pero más a mano, probando con todos los números posibles.

Comparando los tiempos:

Además el programa va mostrando cuanto tiempo lleva ejecutándose y una estimación de cuánto va a tardar. A veces es bueno hacer estas estimaciones para no quedarse esperando que el programa termine o pulir durante media hora un programa que tarda 10 minutos.

También la idea es que al practicar hagan varias versiones de las funciones para ver que tipo de cosas andan más rápido y acostumbrarse a usarlas. Al ejecutarlo utilizando las diversas funciones obtenemos los siguientes tiempos en una Pentium de ~100Mhz:

En realidad al principio (durante los primeros 2 o 3 minutos) el tiempo estimado que muestra el programa es mucho mayor (unas 17 veces :) ). Este pequeño misterio queda como ejercicio.

Como se puede ver en la tabla la función para separar en cifras que usa cadenas es mucho más lenta y le agrega unas 10 horas más al programa, ¡¡de manera que tarda casi el doble!!. El efecto de usar CompletarNumeroBuscando no es tan terrible, pero son unas 2 horas más de ejecución.

Una mejora importante se logra cambiando todos los "Long" por "Integer" (y los "& por "%"), bueno, todos menos 1 que hay que dejar como Long. Un error muy normal es confiarse de que ningún valor va a ser muy grande y usar Integer para ahorrar memoria y que el programa ande más rápido. Es importante darse cuenta a ojo cual es la única variable que no se puede achicar (otro ejercicio). (Ver Tabla de traducción de tipos de variables)

Otra ayuda importante para que le programa vaya más rápido es el uso de la división entera en todos los casos en que es posible. Sería interesante cambiarlas por divisiones normales y ver cuanto (más) tarda.

Más o menos carteles:

También es importante regular correctamente la cantidad de carteles. Si aparecen más de unos 10 carteles por segundo el tiempo que le toma a la computadora hacer que la información en la pantalla suba empieza a molestar y a hacer realmente más lento el programa. Si entre cartel y cartel pasan más de unos 10 segundos uno se empieza a aburrir y preguntarse si se colgó. Yo prefiero unos 2 o 3 por segundo, pero es cuestión de gusto.

Una forma de tener actualizado continuamente la pantalla sin que se consuma tanto tiempo es mediante la instrucción Locate (QB) o gotoxy (Pascal/C) que permite escribir siempre en un punto fijo de la pantalla.

En la siguiente tabla se compara el tiempo que tarda el programa poniendo carteles adentro de diferentes ciclos. Por ejemplo si se pone un cartel en pantalla adentro de todo, de manera que se actualiza cada vez que la tercera fila cambia, el tiempo aumenta considerablemente de unas 10 horas a 6 días.

En las lecciones siguientes vamos a hacerle a este programa algunos pequeños cambios para que vaya más rápido.

Ejercicios:

1. ¿Por qué durante los primeros dos o tres minutos el tiempo estimado es unas 17 veces el que realmente va a tardar?
   
2. ¿Cuál de todas las variables no se puede convertir en un Integer? ¿Por qué? ¿Por qué el resto si? Cambiar el programa y ver que funciona (dejarlo correr al menos unos 10 minutos).
   
3. La verdad es medio inútil que el programa pruebe con todos los números si después se va a quedar sólo con los múltiplos de 17. Modificarlo convenientemente
   

Lecciones siguientes:

Memorizando las respuestas

Otras formas de llenar el tablero