Challenge 5: La inteligencia artificial en la recolección de gemas en mazmorras

Ver el enunciado original

La inteligencia artificial (AI) es una de las aplicaciones de la programación que más despierta mi interés. El interés de un completo neófito, por otra parte. Me resulta increíble a la par que impresionante que mediante algoritmos de programación, que no dejan de ser matemáticos, podamos simular un comportamiento tan humano como la inteligencia.

Supongo, porque pese a mi declarado interés por la materia tengo que reconocer que no soy un seguidor de sus avances, que estará muy lejos de su objetivo aunque, parece ser, que ya existen programas conversacionales con los que es muy difícil no olvidar que se está hablando con una máquina.

Pero volvamos al problema que nos ocupa: aplicar la inteligencia artificial para que una computadora juegue a un juego. Tiene unas normas muy sencillas, con lo que el algoritmo es asequible.

Hacer jugar inteligentemente a un ordenador en este tipo de juegos se basa en la fuerza bruta. Haremos que nuestro algoritmo simule todos los posibles movimientos válidos del jugador, o sea del ordenador, asignaremos una puntuación a cada posición final y guardaremos la mejor jugada junto con su mejor puntuación. Esto nos lleva a explorar un árbol de posiciones. El primer nivel tiene cuatro posiciones, los cuatro movimientos válidos de la ficha, en el segundo nivel, por cada posición del nivel anterior, tendremos tres movimientos válidos (como máximo) y así hasta el nivel/movimiento Z que es el final del juego, cuando desaparecen las gemas que hemos de recolectar.

Antes que nada tenemos que modelar el juego. Esto es, expresarlo en una forma que el ordenador pueda manejar.

En este juego es muy sencillo. Modelaremos el tablero mediante un array de enteros de dimensión 2 (una tabla bidimensional) donde cada casilla será una posición del array. En cada posición almacenaremos un cero si la casilla está vacía y el valor de la gema en caso que tenga una. Llamaremos cells a este array y lo dimensionaremos con los valores máximos del tablero que nos dan en el problema. Inicializaremos a cero, al principio de cada caso de estudio, sólo las posiciones del array incluidas en las dimensiones del tablero del problema.

Los cuatro movimientos posibles (izquierda, arriba, derecha, abajo) los modelaremos con un entero de valor cero a tres.

Finalmente hay que evaluar cada movimiento posible. En este caso es muy sencillo, los puntos serán la suma del valor de las gemas recolectadas. Habrá que encontrar el movimiento que maximice esta puntuación.

Empezaremos con el primer movimiento, por ejemplo el movimiento cero (izquierda), luego el segundo movimiento, otra vez izquierda si se puede, y así sucesivamente hasta llegar al movimiento Z. En cada movimiento habremos ido sumando los valores de las gemas que hayamos recolectado. Al final obtendremos la puntuación de esta combinación de movimientos. Guardaremos esta combinación como la mejor de momento y guardamos la puntuación obtenida.

Deshacemos el último movimiento, restando de la puntuación el valor de la gema que hubiéramos recolectado en este movimiento, y ejecutamos el siguiente movimiento obteniendo una nueva puntuación que compararemos con la que tenemos guardada como mejor. Si la puntuación de esta combinación es mayor guardamos esta combinación como la mejor y su puntuación como la máxima hasta el momento. Si es menor o igual no hacemos nada.

Si ya no hay más movimientos en el último paso deshacemos el paso anterior, ejecutamos el siguiente de este penúltimo paso y el primer movimiento del último paso y repetimos todo el proceso.

Y así hasta que terminemos con todas las combinaciones.

Para guardar el estado de la combinación actual emplearemos un array de enteros, puesto que hemos modelado cada movimiento con un entero, que tendrá Z elementos. Nuevamente dimensionamos este array con el valor máximo de Z que fija el enunciado del problema. A este array lo llamamos l de level (nivel).

Los valores máximos los defino en sentencias #define para emplear estas constantes con su nombre en vez de su valor. ¿Por qué? Porque la lectura del programa va a ser más intuitiva y, si nos cambia uno de estos valores, es infinitamente más sencillo cambiar el valor de la constante al principio del programa que andar buscando por todo el mismo dónde puede aparecer esta constante numérica.

La posición en el tablero del carácter que se mueve la almacenaremos en las variables enteras x e y. La puntuación del movimiento actual lo iremos calculando en la variable pt que inicializaremos a cero e iremos sumando y restando en ella el valor de las gemas que recolectemos y devolvamos conforme hagamos y deshagamos los movimientos de nuestro carácter. En la variable ptmax almacenaremos la máxima puntuación obtenida. La inicializaremos a -1 para que la primera puntuación que obtengamos sea mejor y no tengamos que implementar un caso especial en el algoritmo para el primer movimiento completo que procesemos. En el caso de un programa real de inteligencia artificial para jugar al juego necesitaríamos un array adicional para guardar la cadena de movimientos que se corresponde con la puntuación máxima alcanzada en cada momento (ptmax), pero como el enunciado del problema sólo nos pide que devolvamos la máxima puntuación que se puede obtener esta variable no es necesaria.

Para encontrar la siguiente posición empleamos las variables auxiliares offX y offY. Que serán arrays con el desplazamiento en la primera coordenada (x) del tablero y en la segunda (y) de cada movimiento. Cada posición tendrá los valores del movimiento correspondientes al movimiento de valor su índice:

int offX[]={-1,0,1,0};

int offY[]={0,-1,0,1};

El desplazamiento de valor cero (izquierda) tendrá un desplazamiento en la primera componente de -1 y en la segunda componente de cero.

Finalmente necesitaremos otro array de la misma dimensión que l para guardar el valor de la gema que recolectemos en cada movimiento del carácter puesto que cuando nuestro carácter pase por una casilla con una gema tendremos que retirar ésta del tablero, es decir guardar cero en la posición correspondiente a la casilla; y cuando deshagamos el movimiento tendremos que volver a poner la gema en la casilla, es decir colocar el valor de la gema. Este array lo llamamos gem de gemas.
El algoritmo que recorre todos los posibles movimientos del carácter en el tablero hasta Z niveles, o movimientos individuales, se implementaría con Z bucles anidados en los que cada bucle recorrería todos los movimientos posibles (de cero a tres). Pero no hay una estructura en lenguaje C++ que directamente implemente bucles anidados hasta un nivel variable. Hasta donde yo conozco ningún lenguaje lo hace. Tendremos que programar nosotros mismos este bucle anidado de nivel variable.
Pensemos cómo hacerlo:
Nuestro algoritmo tendrá que generar el primer movimiento válido para cada nivel, evaluarlo, comparar la puntuación con la máxima obtenida hasta este momento, si la puntuación es mejor guardarla.
Deshacer el último movimiento, generar el siguiente movimiento al último nivel y volver a evaluar la posición y repetir el proceso anterior.
Si el último movimiento es ya el último posible deshacer el movimiento del nivel anterior (penúltimo), generar el siguiente movimiento a ese nivel y generar el primer movimiento desde el nivel siguiente hasta el último nivel. Evaluar y repetir el proceso. Si el penúltimo movimiento también es el último desharemos el del nivel anterior, generaremos el siguiente a ese nivel y los primeros desde el siguiente hasta el último. Y así sucesivamente.
Si cuando vayamos deshaciendo movimiento llegamos a que hemos llegado al último movimiento del primer nivel significa que la exploración ha terminado.
Así que lo primero que tenemos claro es que vamos a necesitar un bucle que vaya repitiendo el proceso de generar el siguiente movimiento a un nivel y los primeros movimientos desde el nivel siguiente hasta el último mientras vamos calculando la puntuación correspondiente a esos movimientos; comparar la puntuación con la guardada en ptmax y si es mayor almacenar en aquella variable el valor de este movimiento.
Como de momento no tengo claro cuál será la condición de final del bucle de momento empleo la instrucción while (true) para el bucle, que no termina nunca, y cuando tenga el interior del bucle programado ya veré si me resulta más fácil cambiar la condición del bucle o escribir un comando break dentro de alguna comparación en el interior del bucle.
Lo primero que haremos en el interior del bucle es generar el siguiente movimiento al nivel z. El movimiento anterior en este nivel ya estará deshecho o, en el caso de la primera iteración, nunca se llegó a hacer. Con esta premisa en mente vemos que el valor de z antes de la primera iteración tendrá que estar inicializada a cero porque comenzamos en el primer nivel y el array de control de los bucles anidados (l) correspondientes al primer nivel (l[0]) lo inicializaremos al valor -1, que no se corresponde con ningún movimiento pero que al incrementarlo, que es la operación que usaremos para pasar al siguiente movimiento, obtendremos el valor cero correspondiente al primer movimiento.
Así que lo que tenemos hasta este momento es:

        ptmax=-1; pt=0; // start
        x=X; y=Y; z=0;
        l[0]=-1;
        while (true)
        {
            // comienzo nivel z
        }

Vamos a pensar en el interior del bucle. Una primera aproximación:

        l[z]++;  // next
        bool valid=(l[z]<4);
        if (valid)
        {
            if ((z>0) && (abs(l[z]-l[z-1])==2))
                valid=false;
            else if ((x+offX[l[z]]<0) || (x+offX[l[z]]>=M) ||
                     (y+offY[l[z]]<0) || (y+offY[l[z]]>=N))
                valid=false;
            else
            {
                x+=offX[l[z]]; y+=offY[l[z]];
                pt+=cells[x][y];
                if (pt+(Z-z-1)*MAXVALGEM<=ptmax)
                // max. puntuacion inalcanzable, buscar otro
                {
                    valid=false;
                    pt-=cells[x][y];
                    x-=offX[l[z]]; y-=offY[l[z]];
                }
            }
        }
        if (valid)
        {
            gem[z]=cells[x][y];
            cells[x][y]=0;
            z++;
            l[z]=-1;
        }

En la primera línea generamos el siguiente movimiento del nivel z que es tan simple como incrementar la posición del array l correspondiente al nivel z.
Luego tenemos que averiguar si el movimiento resultante es válido. Para ello emplearemos la variable boolean valid. Iremos haciendo las comparaciones hasta que una resulte en movimiento inválido.
La primera es evidente: que el número del movimiento sea mayor que 3. Los movimientos válidos van del cero al tres.
La siguiente impone la condición que no es un movimiento válido deshacer el movimiento realizado justo con anterioridad. Por ejemplo si en el nivel anterior se ha desplazado el carácter a la derecha (valor 2) no es válido desplazarlo a la izquierda (valor 0). Tal y como hemos elegido los números para los desplazamientos los no válidos están situados a una distancia de dos unidades, de ahí la condición de que el valor absoluto  de la diferencia entre los movimientos de los dos niveles no sea 2. Esta condición, obviamente, no se puede aplicar al primer nivel. Todo ello combinado resulta en la primera instrucción if.
La siguiente condición impuesta es que el resultado del desplazamiento, posición (x+offX[l[z]], y+offY[l[z]]) esté dentro del tablero, o sea entre 0 y M para la primera coordenada y 0 y N para la segunda.
Si el movimiento es válido realizamos el movimiento y sumamos a la variable pt los puntos que haya en la casilla de destino. Imponemos entonces la última condición de validez del movimiento. Esta es que con los desplazamientos que quedan se pueda alcanzar la puntuación que hemos obtenido como máxima hasta este momento. La condición que está impuesta en el código es tan simple como ver si se supera la puntuación si en los movimientos restantes en todos ellos recolectásemos una gema de valor máximo.
Si el movimiento no es válido por esta última condición tenemos que deshacer las operaciones que hemos realizado por este movimiento, volver a la casilla anterior y restar los puntos que hemos sumado.
Si al final el movimiento resulta válido guardamos el valor de la gema de la casilla de destino en la variable gem para poder deshacer el movimiento y quitamos la gema del tablero poniendo en la casilla el valor cero. Si no hay gema estas dos operaciones no hacen nada. Avanzamos un nivel y colocamos en el array de control el valor -1 para que este mismo código genere el primer movimiento del nivel inferior.
¿Y si el movimiento no es válido?

    else
        while (++l[z]>=4)
            if (--z<0)
                break;
            else
            {
                cells[x][y]=gem[z];
                pt-=gem[z];
                x-=offX[l[z]]; y-=offY[l[z]];
            }

Pues generaremos el siguiente movimiento a ese nivel y si no podemos porque es el úlimo significará que el movimiento del nivel anterior ya se ha terminado, así que tendremos que deshacerlo y generar el siguiente movimiento. Usamos un bucle while en lugar de una comparación porque este mismo caso se puede repetir para el nivel anterior y sucesivamente hasta el primer nivel. Observad que he incluido el incremento en la comparación, como está colocado a la izquiera (operador pre-incremento) primero se incrementa la variable y luego se emplea su valor. En el interior del bucle decrementamos el nivel y lo hacemos nuevamente en el interior de una comparación porque me encanta matar dos pájaros de un tiro. Si el nivel ya decrementado es menor que cero significa que hemos terminado el análisis de los movimientos y sólo nos resta salir, si no deshacemos el movimiento del nivel z devolviendo a la casilla del tablero el valor de la gema que hubiera antes en él, guardado como recordaremos en la variable gem, descontamos estos puntos de la puntuación acumulada y deshacemos el movimiento del carácter.
Pero eso no es todo lo que tenemos que hacer porque tenemos que ver si la nueva posición que hemos encontrado en la cláusula else es válida. Eso supone hacer un salto en el programa hacia atrás hasta la definición de la variable valid. En C++ podemos emplear la instrucción goto y una etiqueta pero todo el mundo os desaconsejará esta opción porque hace más ilegibles los programas.
Es mejor solución incluir todas estas instrucciones que son susceptibles de repetirse en un bucle while y usar la instrucción break para salir de él cuando el movimiento sea válido, es decir en la parte del if que se ejecuta cuando valida es true.
Cuando termina el análisis de los movimientos nos saldremos del bucle que tenemos dentro del else con un break, pero no del exterior del que también tendríamos que salir. Así que incluimos en este bucle que añadimos la condición de no finalización de la exploración del árbol de movimientos (z>=0).
Con todo esto la parte inicial del bucle externo que va generando todos los movimientos válidos queda:

  // comienzo nivel z
  while ((z>=0) && (z<Z))
  {
      l[z]++;  // next
      while (z>=0)
      {
          bool valid=(l[z]<4);
          if (valid)
          {
              if ((z>0) && (abs(l[z]-l[z-1])==2))
                  valid=false;
              else if ((x+offX[l[z]]<0) || (x+offX[l[z]]>=M) ||
                       (y+offY[l[z]]<0) || (y+offY[l[z]]>=N))
                  valid=false;
              else
              {
                  x+=offX[l[z]]; y+=offY[l[z]];
                  pt+=cells[x][y];
                  if (pt+(Z-z-1)*MAXVALGEM<=ptmax)
                  // max. puntuacion inalcanzable, buscar otro
                  {
                      valid=false;
                      pt-=cells[x][y];
                      x-=offX[l[z]]; y-=offY[l[z]];
                  }
              }
          }
          if (valid)
          {
              gem[z]=cells[x][y];
              cells[x][y]=0;
              z++;
              l[z]=-1;
              break;
          }
          else
              while (++l[z]>=4)
                  if (--z<0)
                      break;
                  else
                  {
                      cells[x][y]=gem[z];
                      pt-=gem[z];
                      x-=offX[l[z]]; y-=offY[l[z]];
                  }
      }
  }

Aquí podemos llegar en dos situaciones: valiendo z negativo cuando hayamos explorado todos los movimientos o valiendo z=Z, es decir al final de un movimiento válido.
En el primer caso tenemos que salir del bucle externo con una instrucción break.
En el segundo compararíamos la puntuación del movimiento con la que tenemos guardada en ptmax y si es más alta guardaríamos la nueva puntuación. Sin embargo hacer esto sería redundante, aunque el programa funcionaría bien, por supuesto, porque si nos fijamos en la condición de validez de poder alcanzar los puntos máximos que se evalúa en el código para z=Z-1 (último nivel) nos queda la comparación como if (pt<=ptmax). Es decir que si la puntuación obtenida no es mayor que la máxima ya no habremos considerado el movimiento como válido. Lo que implica que si el código llega aquí es porque este movimiento es mejor que el mejor. Así que guardamos directamente la puntuación obtenida en este movimiento en la variable ptmax.
Finalmente decrementamos z para que quede al valor Z-1 (último nivel), desharemos el movimiento de este último nivel y dejaremos que el bucle externo comience una nueva iteración para buscar el siguiente movimiento válido.
Esta parte final del bucle quedaría así:

    if (z<0) break;  // end
    ptmax=pt;
    cells[x][y]=gem[--z];
    pt-=gem[z];
    x-=offX[l[z]]; y-=offY[l[z]];

Cuando termine el bucle externo en la variable ptmax queda la máxima puntuación alcanzable que es el dato que nos pide el problema, así que lo escribimos en la salida de nuestra aplicación.
No creo que haga falta comentar el bucle for que recorre todos los problemas que nos pidan y la parte del programa que lee los datos de los mismos.
Como siempre aquí os dejo el programa completo.

Challenge 4: Missing numbers

Ver el enunciado original

Tenemos un conjunto de números en un fichero y se trata de leerlos y averiguar y ordenar los que faltan. Como el tamaño del archivo que nos dan con los números es de 8589934192 bytes y cada número long ocupa 4 bytes sabemos que tenemos 2.147.483.548 números en el archivo. Si a 2³¹ restamos la anterior cantidad obtenemos el número de enteros que faltan en el archivo. En este caso son 100 los números que faltan.

100 valores es un número manejable, podemos guardar 100 números en la memoria de cualquier ordenador, pero 2³¹ no lo es.

Cuando se trata de averiguar cosas que faltan en un conjunto el algoritmo más simple es dimensionar un array de valores boolean con valores false (por ejemplo) con tantas posiciones como elementos tiene el conjunto completo. Conforme vayamos leyendo los elementos que sí tenemos vamos asignando el valor true al array anterior. Al final de la lectura de todos los elementos existentes hacemos una lectura de este array y los elementos que mantengan el valor false inicial son los que faltan.

Pero como dijimos antes no podemos dimensionar un array con 2³¹ elementos, así que nos olvidamos de este método. Al menos por el momento.

El método complicado

Lo que más me llama siempre la atención de tutoriales y cursos de programación es que siempre obtienen la solución correcta a la primera. Yo debo ser muy tonto porque rara vez me ocurre eso. Muy al contrario mi experiencia es que encuentro la solución, o mejor, una solución al problema a través de una serie de intentos, fallos y correcciones.

Como lo que me interesa transmitir no es sólo cómo se codifica en C++ sino, y para mí más importante, cómo se programa en cualquier lenguaje, quiero en estas entradas no solamente describir el código al que llegué en la resolución del problema sino el proceso que seguí para encontrarlo.

En este caso lo primero que pensé, por un instante sólo, fue en el método clásico que nombré anteriormente pero sabiendo de antemano que era demasiado simple para que fuera una solución del problema. No obstante hice los cálculos del principio de la entrada para saber que la premonición era cierta y el método inviable.

¿Cuál es el problema del algoritmo desechado? El espacio necesario para el almacenamiento. ¿Sobre qué deberíamos empezar a pensar? En cómo guardar la misma información (los números que vamos leyendo secuencialmente del archivo) de forma más eficiente.
Así que pensando en esto lo primero que se me ocurrió fue una solución que, a la postre, se demostró ser una elucubración mental. Sin embargo he dejado comentada la implementación al comienzo del fichero con la solución y no me resisto a comentarla.
La idea, que en principio me pareció genial, es que si los números me llegaban relativamente ordenados podría tener suficiente memoria para almacenar todos los números que iba leyendo si en vez de guardar los números individuales guardaba conjuntos de números consecutivos, de tal forma que sólo tenía que almacenar, en una estructura, el número inicial y el final del conjunto. Estos conjuntos los guardaría en una lista ordenada.
Todo esto se definiría así:

struct _extremos
{
    long start,end;
};

typedef _extremos extremos;
typedef list<extremos> listaExtremos;

El código sería así:

int main() // Muy lento
{
    long n;
    listaExtremos lista;
    extremos item;
    vector<long> perdidos;
    ifstream numbers("integers", ifstream::binary);
    long c=0;
    while (true)
    {
        if (++c % 1000==0)  cout<<c<<" - "<<lista.size()<<endl;
        numbers.read((char *)&n, sizeof(long));
        if (numbers.eof()) break;
        bool found=false;
        for (listaExtremos::iterator it=lista.begin(); !found && (it!=lista.end()); ++it)
        {
            if (it->start==n+1)
            {
                it->start=n;
                found=true;
            }
            else if (it->end==n-1)
            {
                it->end=n;
                if ((++it!=lista.end()) && (it->start==n+1))
                {
                    n=it->end;
                    (--it)->end=n;
                    lista.erase(++it);
                }
                found=true;
            }
            else if (it->start>n)
            {
                item.start=n; item.end=n;
                lista.insert(it, item);
                found=true;
            }
        }
        if (!found)
        {
            item.start=n; item.end=n;
            lista.push_back(item);
        }
    }
    cout<<"Resultado:"<<endl;
    n=0;
    for (listaExtremos::iterator it=lista.begin(); it!=lista.end(); ++it)
    {
        while (n<it->start)
        {
            perdidos.push_back(n);
            cout<< n << " , ";
            n++;
        }
        n=it->end+1;
    }
    return 0;
}

El bucle externo (while) se encarga de procesar todos los números del fichero hasta que se alcanza el final de éste, momento en el que mediante una sentencia break se termina el bucle.
El bucle interno recorre la lista de conjuntos que hemos ido guardando (en principio estará vacía) y una variable booleana (found) controla el final del bucle antes de llegar al final de la lista.
Comparamos el número recién leído con el valor mínimo del conjunto que procesamos, si el número es el anterior al leído lo guardamos en este conjunto, cambiando su valor mínimo por el nuevo mínimo.
Análogamente comparamos con el valor máximo del conjunto. Si aumentamos el conjunto por su final hay que hacer una comparación adicional para ver si el conjunto aumentado es correlativo con el siguiente conjunto, esto es no hay ningún número entre ambos, en cuyo caso unimos los dos en el primer conjunto, igualando su valor máximo con el valor máximo del siguiente conjunto, y eliminamos el segundo conjunto, con lo que recuperamos memoria, que es de lo que trata este algoritmo.
En el momento en que el valor mínimo sea mayor que el número que estamos procesando no hay que continuar la búsqueda y lo que procede es crear un nuevo conjunto en el que el valor máximo y el mínimo sean iguales al número procesado e insertar el nuevo conjunto en la lista delante del conjunto comparado para que la lista se mantenga ordenada.
El final del código no implementa la solución pedida al problema sino que simplemente muestra los números perdidos obtenidos, al tiempo que los almacena en una nueva lista, en este caso es un vector de longs, recorriendo la lista con los conjuntos obtenidos y guardando los números que van desde el máximo de un conjunto hasta el mínimo del siguiente.
El método parece funcionar (no dejé terminar la ejecución) pero es tremendamente lento por la cantidad y complejidad de las comparaciones a realizar por cada número tratado además del tiempo extra en mantener la lista ordenada.
Conclusión: método inservible por ineficiente, aunque posiblemente no diera un desbordamiento de memoria que, al fin y al cabo, es la idea que tenía en mente cuando pensé esta solución. Pero en cualquier caso un precioso tiempo perdido.

El método que funciona: divide y vencerás

En la vida de un programador los errores no pueden conducir al desánimo porque es el pan nuestro de cada día. Si te das cuenta, sin lugar a la menor duda, que el camino que has emprendido es incorrecto muchas veces es mejor abandonarlo y comenzar de nuevo que tratar de corregir algo que está mal de base. Sobre todo si, como en este caso, el tiempo invertido es despreciable. Como mucho me costará una taza más de café.

Del desánimo surgió la nueva idea. Como son muy pocos los números que faltan parece un derroche marcar todos los que están sea de la forma que sea. ¿Qué hacer entonces?

La idea es agrupar los números en grupos de números, por ejemplo por miles (es sólo un ejemplo, no lo haremos así). Hacer una primera lectura del fichero de números, asignando el número al grupo que corresponde y contando los números que aparecen en cada grupo. El número 23.250 corresponderá al grupo 23 (comenzando por el grupo 0).
Al final casi todos los grupos tendrán todos los números (mil en el ejemplo), en los grupos que falten números aplicaremos el método clásico pero ahora sólo tendremos que reservar memoria para los números pertenecientes a los grupos incompletos.
Necesitaremos una segunda lectura del fichero de números. En esta segunda lectura si el número pertenece a un grupo completo no hacemos nada y si pertenece a un grupo incompleto lo marcamos. Como cada grupo tiene mil números reservaremos espacio para mil booleanos por cada grupo incompleto.
El número 23.250 corresponderá con la posición 250 de su grupo. Al final de la segunda lectura tendremos sin marcar los números que faltan.

Cuanto más fácil sea asignar el número a su grupo más eficiente será el método. En el ejemplo del párrafo anterior elegir los grupos de 1.000 elementos hace que, para los humanos, sea muy fácil calcular el grupo  y la posición dentro del grupo (el número de delante del separador de miles y el de detrás).
Pero como para los ordenadores los números no están en base 10 sino en base 2 la forma fácil para el ordenador es que los grupos sean de 2^n elementos. Yo elegí hacer grupos de 65536 (2¹⁶) números porque un long se almacena en memoria usando 4 bytes de memoria, si tomo los dos bytes que almacenan los bits más significativos del long como si fuera un entero obtendré el índice del grupo de 65536 números al que pertenece el número. Es como dividir el número por 2¹⁶ y usar el cociente pero infinitamente más rápido.

Los punteros y la asignación dinámica de memoria

Ya sé que prometí en la introducción que este no iba a ser un curso del lenguaje C++ sino de programación y que, por tanto, no iba a entrar en los detalles del lenguaje. Pero los punteros merecen un trato especial.

¿Por qué?

Porque es un elemento que no existe en todos los lenguajes, al menos como está implementado en C y C++, y por lo tanto quien no esté familiarizado con estos lenguajes puede perderse cuando realmente su funcionamiento es de lo más simple.

Y además porque son fantásticos y peligrosos.

En realidad no hay un tipo puntero sino infinitos. Uno por cada tipo de variable que se pueda definir (incluyendo struct y class). Pero todos ellos tienen la particularidad que lo que guardan no es un dato guardado en la memoria del ordenador sino la dirección de la memoria donde está guardado el dato.

Los que aprendimos a programar en los tiempos en los que los microprocesadores eran muy simples (como mi caso que aprendí con un Z80 de Zilog montado sobre un ordenador Sinclair ZX-81) tenemos la ventaja de tener una representación muy clara de cómo se organiza la memoria. Es como un conjunto de casillas numeradas correlativamente en las que en cada una se puede almacenar un número entero (que para mí es un byte, aunque ahora ya son cantidades de más bits).

Pues bien en una variable puntero se almacena la dirección de una de estas casillas. Luego el compilador, en función del tipo del puntero, sabe sacar el valor al que apunta el puntero cogiéndolo de esa casilla y las siguientes.

Vemos que este tipo de variables se puede usar de dos formas: refiriéndose a la dirección que guarda o al valor al que apunta. Cuando hacemos referencia a la dirección que guardan escribimos el nombre de la variable tal cual, cuando nos referimos al valor guardado en esa dirección de memoria precedemos al nombre de un asterisco (*). Los punteros que apuntan a estructuras se especifica de otra manera, pero el funcionamiento es el mismo y de momento no los voy a emplear.

Podemos saber la dirección de cualquier variable anteponiéndole el operador & que significa dirección de. Este operador devuelve un puntero del mismo tipo que la variable sobre la que se aplica. Para pensar: podemos aplicar este operador sobre una variable de tipo puntero a algo y nos devolverá un tipo puntero a puntero a algo, y así indefinidamente...

Un tipo puntero a algo se define posponiendo un asterisco al tipo al que apunte. Por ejemplo para definir una variable apuntador que apunte a un entero (el espacio después del asterisco es opcional):

    int * apuntador;

Otra cosa interesante que podemos hacer con punteros es operar con ellos. Cuando sumamos a un puntero una cantidad hace que apunte a una posición de memoria que está más adelante en la memoria. Cada unidad que se incrementa un puntero hace que apunte a una posición de la memoria que está justo las posiciones que ocupa el tipo de dato al que apunta. Es decir cuando sumamos uno a un puntero apuntaría al siguiente número del mismo tipo almacenado a continuación. O dicho más simple, al siguiente elemento del array.

Y un último recurso que tiene que ver con la memoria y los punteros es el operador new y delete que permiten reservar una cantidad de memoria y liberarla después a través de la dirección del primer elemento.

Finalmente una advertencia: usar indebidamente los punteros puede provocar resultados catastróficos. Úselos con responsabilidad.

La implementación

Echemos un vistazo a la parte del programa que inicializa los datos:

    long n,c,indx;
    long cn[32768];
    bool *tabla[32768];

La tabla cn contendrá los contadores de números de cada grupo, ¿pero por qué dimensiono  la tabla tabla para todos los grupos (32768) si he dicho que no voy a necesitar anotar los números existentes de los grupos completos? Muy sencillo, porque no estoy reservando todavía el sitio para los 65536 booleanos que necesitaré por cada grupo sino solamente la memoria que necesitaría para guardar punteros que me apunten al comienzo de cada tabla de 65536 booleanos. La mayor parte de esta tabla no contendrá ningún dato válido porque sólo reservaré la memoria y guardaré por tanto el puntero a esta memoria para los pocos grupos no completos, pero tener el array de punteros dimensionado para todos los grupos simplifica el programa y los punteros ocupan la suficiente poca memoria como para permitirnos este derroche.

    unsigned short * low=(unsigned short *)&n;
    short * high=(short *)low+1;

Los punteros short* low y high así definidos me van a permitir realizar la división de la que hablaba antes para asignar un número a su grupo sin realizar ninguna operación. Vamos a ver esto con un poco más de detalle:
La variable n, definida de forma normal como de tipo long, habrá reservado en alguna zona de la memoria los bytes suficientes para almacenar este tipo de dato que, aunque puede variar según el compilador que usemos, siempre serán más de los 4 bytes que nosotros necesitamos. En esta variable almacenaremos el número que leemos desde el fichero.
El operador & devuelve la dirección de memoria donde está alojada la variable n, es decir, un puntero a la variable n. El truco está en cambiar el tipo de puntero, de esta forma como una variable short ocupa 2 bytes cuando pidamos el valor de la variable a la que apunta el puntero low no va a devolver el valor de la variable n, sino sólo el número que forman los dos primeros bytes de la variable que, en el procesador de mi equipo, resultan ser los bits de menos valor de la variable y, por lo tanto, el resto de la división que nos dará la posición del número dentro del grupo. Necesitamos definir el puntero unsigned para que los valores vayan de 0 a 65.535 que es la representación que nos interesa y no de -32.768 a 32.767.
La variable high así definida apuntaría al segundo elemento de un array de shorts que empezara en la misma dirección que n que, evidentemente, resultan ser los bytes 3º y 4º de la variable n. Al acceder al valor apuntado por esta variable obtendremos el cociente de dividir n para 65.536 pero sin realizar la operación. Nos dará el índice del grupo al que pertenece el número.
Y todo ello sólo por almacenar el número en la variable n. ¡Maravilloso!

    for (int i=0; i<32768; i++) cn[i]=0;

Inicializo el contenido de los contadores de los grupos a cero porque C++ no nos asegura que al definir una variable esta adopte ningún valor inicial sino uno aleatorio. No hace falta que inicialice la tabla de punteros porque lo haré cuando reserve memoria para los grupos que necesite directamente al valor del puntero bueno.

    ifstream numbers("integers", ifstream::binary);

    while (true)  // 1st pass

    {

        numbers.read((char *)&n, sizeof(long));

        if (numbers.eof()) break;

        cn[*high]++;

    }

El bucle que controla la primera lectura es muy parecido al bucle externo del método complicado pero en este caso el procesamiento por cada número se limita simplemente a la ejecución de la última sentencia. Como la instrucción read ha colocado el número en la variable n el puntero almacenado en la variable high apuntará al valor del índice del grupo al que pertenece el número; con lo que la última sentencia incrementa el contador del grupo al que pertenece el número que estamos procesando. ¡Impresionante que escribiendo tan poco obtengamos tantos resultados!

    n=0; c=0;

    for (int i=0; i<32768; i++)

    {

        if (cn[i]<65536)

        {

            tabla[i]=new bool[65536];

            for (long j=0; j<65536; j++)

                tabla[i][j]=false;

            n++;

            c+=65536-cn[i];

        }

        else

            tabla[i]=NULL;

    }

    // cout << "Resultado: " << n << " bloques con " << c << " faltas" << endl;

Momento de la reserva de memoria para los grupos incompletos. Mediante un bucle recorro todos los contadores y para los grupos en los que no haya contado 65536 números reservo memoria para un array de 65536 booleanos cuya dirección guardo en el elemento del array tabla correspondiente al grupo e inicializo el array recién asignado al valor false para todos sus elementos. Si el grupo está completo guardo en el elemento del array tabla correspondiente el valor NULL que corresponde con un puntero especial a una posición de memoria no válida. Sirve para comparar si un puntero tiene una dirección buena o no.

Una pequeña observación, fijaros en la incialización de la tabla de booleanos cómo he empleado el puntero a booleanos como si fuera una tabla de booleanos.

Al final del proceso en la variable c obtendré la cantidad de números que faltan y en la variable n la cantidad de grupos en los que están repartidos. Este último dato no se necesita pero lo puse en la fase de diseño por curiosidad y ahí se quedó.

La salida de mensajes por pantalla comentadas corresponden con las informaciones que me parecen pertinentes visualizar en la fase de diseño. Cuando son pocos uso esta técnica de comentar las líneas de código implicadas, en programas más grandes esta técnica es inviable por lo que hay que usar un macro_identificador (cláusula #define del compilador) para luego, gracias a la cláusula #ifdef, compilar o no las líneas de código que sólo deben ejecutarse en la fase de pruebas de la aplicación. Por costumbre llamo a este macro_identificador DEBUG.

    long *lost=new long[c];

    numbers.close();

    numbers.open("integers", ifstream::binary);

    while (true)  // 2nd pass

    {

        numbers.read((char *)&n, sizeof(long));

        if (numbers.eof()) break;

        if (tabla[*high]!=NULL)

            tabla[*high][*low]=true;

    }

Como ya sé cuántos números me faltan reservo la memoria para el array  que los va a contener. Aunque lo emplearé después de la segunda lectura del fichero de números prefiero reservar la memoria ahora para que si no tengo suficiente memoria se detenga el programa antes ahorrándome tiempo (y nervios).

Cierro el archivo y lo vuelvo a abrir para procesarlo de nuevo. No es una manera muy elegante de posicionarnos al comienzo del archivo pero es simple y efectiva.

El bucle de la segunda lectura vuelve a ser similar al de la primera, pero esta vez el procesamiento es un pelín más largo: si el valor almacenado en el array tabla correspondiente al grupo al que pertenece el número vale NULL significa que el grupo estaba completo y no hago nada, si no marco el booleano correspondiente a la posición de este número en su grupo a true. Observad cómo empleo un array de punteros a booleanos como si fuera un array de booleanos con una dimensión más.

Ya tengo casi todo el trabajo hecho, ahora a recoger los resultados:

    // cout << "Búsqueda de números..." << endl;

    n=0; indx=0;

    for (int i=0; i<32768; i++)

    {

        if (tabla[i]!=NULL)

        {

            for (long j=0; j<65536; j++)

            {

                if (!tabla[i][j])

                    lost[indx++]=n;

                n++;

            }

            delete[] tabla[i];

        }

        else

            n+=65536;

    }

La variable n me va a recorrer todos los números, indx es el índice en el array lost donde tengo que almacenar el siguiente número que falte, por tanto ambos se inicializan a cero.

El procesamiento se corresponde nuevamente con un bucle que va a recorrer todos los grupos. Si el grupo está completo (puntero vale NULL) sólo tengo que sumar 65536 a la variable n porque todos esos números están presentes. Si el grupo está incompleto necesitaré un bucle anidado que recorra las 65536 posiciones del array tabla correspondiente al grupo y en las posiciones que encuentre un valor false, que indica que el número falta, guardar el número que corresponda, que tendré en la variable n, en la tabla lost incrementando el índice indx. En cada iteración de este bucle interno incrementaré en uno la variable n con lo que al final del bucle a la variable n le habremos sumado 65536 como en el caso de los grupos completos.

Al final del bucle interno, como ya no se va a emplear más el array de booleanos correspondiente a ese grupo, libero la memoria que ocupa con la sentencia delete[]. Al reservar memoria con la sentencia new es obligatorio el liberarla explícitamente porque si no se pueden quedar zonas de la memoria del ordenador inutilizadas. Normalmente los modernos sistemas operativos detectan estos olvidos al finalizar el programa pero es mejor no dar por supuesto este comportamiento y crear programas limpios que liberen todo lo que usan. Es otro inconveniente de usar punteros.

Este procesamiento no es el más eficiente. Como sabemos cuántos elementos faltan en cada grupo se podría detener el bucle interno en el momento que se hayan encontrado esos elementos. El número que falta (n) se podría calcular a partir del índice del grupo (i) y de la posición del elemento en el grupo (j) simplemente escribiendo estos valores a través de los punteros high y low, es decir lo contrario a lo que hemos hecho antes, con lo que no necesitaríamos ir incrementando la variable n. Se os queda como tarea pero me temo que el beneficio que se obtenga será inapreciable porque son pocos los grupos a los que les faltan números.

Y ahora a resolver el problema:

    cin >> n;

    for (int i=0; i<n; i++)

    {

        cin >> indx;

        cout << lost[indx-1] << endl;

    }

Leo el número de casos a estudio. Por cada caso leo el índice y saco el valor del array lost correspondiente a ese índice. Tengo que restar uno porque el primer elemento del array lost tiene por índice cero.

Y ya sólo queda liberar el último trozo de memoria reservada manualmente y terminar:

    delete[] lost;

    return 0;

Los corchetes detrás de la sentencia delete le indican al compilador que la memoria que vamos a liberar se corresponde con un array, es decir que cuando se reservó con la sentencia new se indicó una cierta cantidad de elementos contiguos para ser reservados.

Y aquí el programa completo