El problema del cuadrado con numeritos

Me topé con un problema irresistible, descripto en inglés en este post. No me haría ninguna gracia tener que resolverlo en una entrevista de trabajo, como fue el caso de aquel blogger: mi primer intento, en la tranquilidad de mi casa, fue lento y torpe. Pero es de esos problemas que, una vez leido el enunciado, no se pueden ignorar: si sos programador y mínimamente te gusta tu profesión, deberás resolverlo. Sugiero que lo lean allá, sin ver soluciones, y... ya sabrán que hacer.

Spoiler Alert

La solución en C del blogger me pareció inteserante por lo concisa, lo mismo la de algunos comentaristas de ese blog, que utilizaron diferentes lenguajes. Cuándo no, la mía es en Scala. Con Scala se puede apuntar a una solución concisa por su poder expresivo, pero no quise descuidar otro aspecto: que el código capture la intención. Es una solución funcional, y con objetos (uso un par de clases). Este es el resultado:

case class Pos(i:Int, j:Int)
{
  def shiftIn = Pos(i - 1, j - 1)
}

case class Square(n:Int)
{
  val highest = (n * n) - 1
  val farEdge = n - 1
  private def isEdge(x:Int) = x == 0 || x == farEdge
  private def isEdge(p:Pos):Boolean = isEdge(p.i) || isEdge(p.j)
  private def isTopOrRight(p:Pos) = p.i == 0 || p.j == farEdge
  private def linearOffset(p:Pos) = if(isTopOrRight(p)) p.j + p.i else (farEdge * 2) + (farEdge - p.j) + (farEdge - p.i)
  private def calc(p:Pos):Int = if(isEdge(p)) highest - linearOffset(p) else Square(n - 2).calc(p.shiftIn)

  def calc(i:Int, j:Int):Int = calc(Pos(i,j))
}

Square es un cuadrado de n celdas de lado. Pos es una posición (i, j). Definimos valores para ayudar en la claridad del código: highest es el valor más alto del cuadrado (que estaría en la celda superior izquierda). farEdge es el índice al "borde lejano"... o sea, el borde horizontal cercano es la fila 0, y el lejano la fila farEdge; igual con los bordes verticales (columnas 0 y farEdge).
Los métodos privados conceptualizan los detalles de la implementación. El método calc, en palabras se describiría así:

Si la posición solicitada corresponde a un borde del cuadrado, tomar el valor más alto del cuadrado y restarle un offset lineal deesa posición respecto al contorno del cuadrado.

Si no, intentar con el cuadrado interno al actual.

El método isEdge nos dice si la posición indicada cae en un borde del cuadrado, es decir, que la fila o la columna sea 0 o sea farEdge.
Lo del offset lineal surge de observar, en el planteo del problema, una característica de todos los "anillos" cuadrados que forman la grilla, desde el borde exterior hasta la celda central (o cuadrado de 2 x 2): Desde la celda superior izquierda, que contiene el máximo valor del cuadrado, podemos recorrer el borde en sentido reloj, y son todos valores decrecientes de uno en uno. Si "enderezamos" ese borde, tenemos un vector donde la primera posición es la más alta. Pero como su contenido es tan obvio, no necesitamos representarlo en memoria. Dado un índice, podemos calcular fácilmente el valor que habría en tal posición: en la 0 está highest, en la 1 está highest - 1, y así. Entonces, la única dificultad es obtener ese offset lineal, el índice al vector imaginario, a partir de una posición bidimensional. Esto lo hace el método linearOffset. Pensándolo un poco, descubrimos que hay dos fórmulas: una aplica cuando la posición está sobre el borde superior o derecho, y la otra si está sobre el inferior o izquierdo.

Cuando la posición pedida no está en el borde del cuadrado actual, procedemos con el cuadrado inmediatamente interior. Este cuadrado interior tendrá 2 celdas menos de lado que el actual. Obsérvese que nunca nos importa si empezamos desde un cuadrado más externo al actual: un cuadrado de 3 x 3 es exactamente lo mismo ya sea que hayamos partido de 3 x 3, o que hayamos partido de uno de 7 x 7 bajando hasta 3 x 3. Por eso el problema se puede resolver en términos de anillos individuales: si no me sirve el actual, me lo saco de encima y reintento con el que sigue, como quien quita las capas de una cebolla.

Lo que tenemos que tener en cuenta al bajar al cuadrado inferior es ajustar la posición, porque esta fue informada como relativa al cuadrado actual. Lo que ahora es (1, 1), para el cuadrado inferior es (0, 0). Ese ajuste lo hace la clase Pos con el método shiftIn.