Abriendo una caja fuerte

“They got the money, hey / You know they got away
They headed down south and they’re still running today …”
The Steve Miller Band, “Take the Money and Run” (1976)

Como la entrada anterior trataba sobre recursividad, la técnica “divide y vencerás” y las funciones internas de C# 7, aprovecho para mostrar una solución a un problema que le plantearon a un antiguo colega que se presentó a una entrevista de trabajo en Google (debe haberle ido bien, porque lo aceptaron). El enunciado del problema es el siguiente:

Una caja fuerte está protegida mediante una combinación de cuatro dígitos decimales. La caja fuerte solo tiene en cuenta los cuatro últimos dígitos tecleados a la hora de decidir si los datos tecleados satisfacen la contraseña. Por ejemplo, si alguien teclea en la caja fuerte los dígitos 012345, con ello habrá probado las combinaciones 0123, 1234 y 2345. Obviamente, la secuencia de 40000 dígitos 0000000100020003…9999 abrirá con total seguridad la caja fuerte. Ahora bien, ¿podrían cubrirse todas las 10000 posibles combinaciones utilizando una secuencia de menor longitud? ¿Cuál es la longitud de la cadena más corta que permite probar todas las combinaciones?

Desde que mi ex-colega me lo describió, me pareció que el problema se prestaba para ser atacado mediante una función recursiva con la que se va avanzando o retrocediendo (backtracking) en el espacio de combinaciones del problema. Y como al que tiene un martillo todos los problemas se le parecen a un clavo, me puse inmediatamente a teclear y al cabo de una media hora le tenía preparado algo muy parecido al código siguiente:

using System;
using System.Linq;
 
namespace Geeks.SafeCrack
{
    static class MainClass
    {
        static void Main(string[] args)
        {
            GoForward(SafeData.InitialData);
        }

        static bool GoForward(SafeData safeData)
        {
            if (safeData.IsCracked)
            {
                PrintResults();
                return true;
            }

            var len = safeData.Sequence.Length;
            var a = (int) safeData.Sequence[len - 3] - '0';
            var b = (int) safeData.Sequence[len - 2] - '0';
            var c = (int) safeData.Sequence[len - 1] - '0';

            for (int d = 0; d <= 9; d++)
            {
                var index = SafeData.Index(a, b, c, d);
                if (safeData.Combinations[index])
                    continue;
                
                var newSequence = safeData.Sequence + (char)('0' + d);
                var newCombinations = (bool[]) safeData.Combinations.Clone();
                newCombinations[index] = true;
                if (GoForward(new SafeData(newSequence, newCombinations)))
                    return true;
            }
            return false;
 
            void PrintResults()
            {
                Console.WriteLine("Safe cracked!!!");
                var sequence = safeData.Sequence;
                Console.WriteLine("Length   = " + sequence.Length);
                Console.WriteLine("Sequence = " + sequence);
            }
        }
    }
 
    class SafeData
    {
        public SafeData(string sequence, bool[] combinations)
        {
            Sequence = sequence;
            Combinations = combinations;
        }
        public string Sequence { getprivate set; }
        public bool[] Combinations { getprivate set; }

        public bool IsCracked => Combinations.All(x => x);

        private readonly static SafeData initialData = 
            new SafeData("000"new bool[10000]);
        public static SafeData InitialData => initialData;

        public static int Index(int a, int b, int c, int d) =>
            1000 * a + 100 * b + 10 * c + d;
    }
}

Básicamente, en cada paso del algoritmo se examina con cuáles de los diez dígitos se puede extender la secuencia actual, añadiendo una nueva combinación a la lista de combinaciones ya probadas, y para cada uno de tales dígitos se avanza en profundidad. Una vez analizados los diez dígitos, se hace backtrack al contexto de la llamada inmediatamente anterior (que continuará recorriendo sus dígitos aún pendientes).

La longitud de cadena que produce el programa anterior es 10003, y dado que el programa está diseñado para retroceder masivamente una vez que se encuentra la primera solución, todo indica que navegué con mucha suerte, ya que ésta resulta ser precisamente la longitud óptima. El programa puede ser modificado fácilmente para explorar todo el espacio de combinaciones y enumerar todas las soluciones existentes, tarea que dejo al lector interesado. Pero la moraleja de esta historia no radica tanto en la utilización de la recursividad y el backtracking como en la importancia de la preparación teórica (en general) y la investigación sobre el problema (en particular) antes de ponerse a codificar como un poseso: como puede comprobarse aquí y en muchas otras fuentes, reconociendo la aplicabilidad del concepto de secuencia de De Bruijn no habría hecho falta tirar ni una sola línea de código para saber que la respuesta correcta es 10003.


Referencia musical: Uno de mis grupos favoritos de la segunda mitad de la década de los ’70 fue la banda de Steve Miller, músico recientemente incorporado al Salón de la Fama del Rock’n’Roll que desarrolló prácticamente toda su carrera en San Francisco. El tema “Take the Money and Run” fue el primer single de uno de sus discos más exitosos, “Fly Like an Eagle” (1976). Pero es probablemente el tercer éxito, el que le da el nombre al disco, el que más perdura en la memoria hoy en día; la crítica social de su letra siempre me recuerda que California (y especialmente el norte) es desde hace muchísimo tiempo una región netamente “progre”.

Octavio Hernandez

Desarrollador y consultor en tecnologías .NET. Microsoft C# MVP entre 2004 y 2010.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *