Números en espiral

A veces, las entrevistas de trabajo van acompañadas de preguntas-prueba para evaluar la capacidad del entrevistado. Google es conocido por hacer ese tipo de preguntas; entre las más recientes hay una que me parce especialmente chocante: How many resumes does Google receive each year for software engineering?

Pero buena parte de las preguntas bien podrían entrar en la categoría de pasatiempos lógicos, aunque con la presión de una entrevista de trabajo, cabe suponer que se siente de una forma diferente.

Eso me ha recordado un problema para una entrevista de trabajo sobre el que me hablaron tiempo ha. En una hoja de cálculo, se nos dan un número de fila y de columna que determinan una casilla a la que llamaremos origen. La intención es numerar las casillas que la rodean de la forma siguiente. La casilla origen se numera con un uno, la de su derecha con un dos. A la de abajo de la dos se le asigna el número tres, la de la izquierda de la tres es la cuatro, la de la izquierda de la cuatro es la cinco. La de arriba de la cinco es la seis, sobre la seis va la siete, a la derecha de la siete la ocho, y así sucesivamente, en espiral, cada casilla tiene su número. Por ejemplo, si el origen estuviera en la fila 4833, columna 1938, los alrededores de esa tabla tendrían este aspecto:

	...	1936	1937	1938	1939	1940	...
...	...	...	...	...	...	...	...
4831	...	21	22	23	24	25	26
4832	...	20	7	8	9	10	27
4833	40	19	6	1	2	11	28
4834	39	18	5	4	3	12	29
4835	38	17	16	15	14	13	30
...	37	36	35	34	33	32	31

El problema consiste en determinar, dadas la fila y columna origen y una fila F y una columna C arbitrarias, qué número correspondería a la casilla en la fila F columna C.

Me contaban que uno de los entrevistados escribió un algoritmo para resolverlo usando el lenguaje de script de la hoja de cálculo, y que dicha persona se jactaba de que el tiempo de ejecución era O(n), siendo n el número que le correspondería a la casilla en cuestión.

¿Es posible hacerlo mejor que eso?

Sí, es posible. Deje el lector aquí de leer si quiere intentarlo por sí mismo. Si no, continúe tras la línea.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

---

Observemos una característica de las diagonales. La diagonal que empieza en uno y se extiende hacia arriba y a la derecha (resaltada en verde a continuación), consiste en los números 1², 3², 5², ... y la que empieza en cuatro y se extiende hacia abajo e izquierda (señalada en amarillo), consiste en los números 2², 4², 6², ...

	...	1936	1937	1938	1939	1940	...
...	...	...	...	...	...	...	...
4831	...	21	22	23	24	25	26
4832	...	20	7	8	9	10	27
4833	40	19	6	1	2	11	28
4834	39	18	5	4	3	12	29
4835	38	17	16	15	14	13	30
...	37	36	35	34	33	32	31

¿Es casual esa observación, o hay algún motivo para que sea así? Para responder esa pregunta, basta fijarse en todos los números entre el 1 y cada uno de los que se encuentran en esas diagonales. Por ejemplo, observemos el 1, 2, 3 y 4. Forman un cuadrado de lado dos, así que los números en cierto modo cuentan su área. Ahora observemos el 1, 2, 3, 4, 5, 6, 7, 8 y 9. Forman un cuadrado de lado 3. Los números entre el 1 y el 16 forman un cuadrado de lado 4. Para formar un cuadrado de lado 5 no tendríamos más que añadirle al de lado 4 los cuadrados numerados entre el 17 y el 25 inclusive, y eso es justo lo que ocurre. No es casualidad, pues. Existe una relación numérica.

Para perfilar mejor lo que será la fórmula final, hay que fijarse en qué efecto tienen la fila y la columna a la hora de determinar el cuadrado en el que cae la casilla objetivo. Observemos que los cuadrados con lado impar siempre tienen el elemento origen (el 1) justo en el centro, mientras que los de lado par lo tienen «casi» en el centro.

Si, para una casilla dada, conseguimos determinar un cuadrado que tenga el origen justo en el centro (para lo cual sólo consideraremos cuadrados de lado impar) y para el que esa casilla sea parte de su perímetro, tenemos ya casi todo el problema resuelto, porque inmediatamente conocemos todos los números que forman su perímetro. Por ejemplo, para la casilla en la fila 4833, columna 1940, queremos hallar el cuadrado formado por las casillas de la 1 a la 25, ya que es el que tiene el 11 en su perímetro y el 1 en el centro.

Para calcular ese cuadrado, necesitaremos más pasos. La resta entre el número de columna de la celda y la del origen determina la diferencia horizontal, y haciendo lo mismo con las filas obtenemos la diferencia vertical. Sus valores absolutos son las distancias horizontal y vertical, respectivamente. La mayor de esas distancias servirá para determinar el cuadrado que buscamos. Llamémosla d. Entonces, (2d+1)² es el área del cuadrado buscado. Los números de su perímetro están comprendidos entre el (2d-1)²+1 y el (2d+1)²; el número de su vértice inferior izquierdo es (2d)²+1 y los otros dos vértices no los necesitamos, pues podemos descontar desde el mayor en las horizontales y contar desde el menor en las verticales.

Al determinar cuál de las dos distancias era mayor, si la horizontal o la vertical, hemos averiguado de paso si el número cae en un lado horizontal o en uno vertical del cuadrado; los signos de las diferencias nos ayudarán a distinguir el lado concreto. Usando el vértice como base y la otra diferencia como desplazamiento, obtendremos nuestro número.

La fórmula resultante, en OpenOffice, es:

=SI(ABS(CELDA("COL") - {col_origen}) > ABS(CELDA("ROW") - {fila_origen});
    SI(CELDA("COL") < {col_origen};
        4*SUMA.CUADRADOS({col_origen} - CELDA("COL")) + 1
            + {fila_origen} - CELDA("ROW") + {col_origen} - CELDA("COL");
        SUMA.CUADRADOS(2*(CELDA("COL") - {col_origen}) - 1)
            + CELDA("ROW") - {fila_origen} + CELDA("COL") - {col_origen}
    );
    SI(CELDA("ROW") < {fila_origen};
        SUMA.CUADRADOS(2*({fila_origen} - CELDA("ROW")) + 1)
            + CELDA("COL") - {col_origen} + CELDA("ROW") - {fila_origen};
        4*SUMA.CUADRADOS(CELDA("ROW") - {fila_origen}) + 1
            + {col_origen} - CELDA("COL") + {fila_origen} - CELDA("ROW")
    )
)

Que es O(1) para números razonablemente normales y casi instantánea de calcular en OpenOffice. Para números muy grandes, que las hojas de cálculo normales no pueden manejar, entraría en juego la complejidad de la multiplicación, O(log² n) en el peor de los casos, pero nunca O(n).