Un desafío con reglas simples pero algoritmos no triviales. :-)

Tarea

Tome la entrada en forma de enteros separados por espacios:

N A B S

Donde N es la longitud lateral de una matriz cuadrada 2D llena de números únicos (enteros) entre A y B inclusive. Para cada fila y columna en esta matriz, la suma es siempre la misma: S. (En otras palabras, la matriz es un cuadrado semi-mágico).

Nota:

Todos los números son positivos. La excepción es A, que puede ser 0.

Ejemplos

por

3 1 10000 2015

una solución válida sería

por

8 1 300 500

una solución válida sería

Salida

Su salida debe ser una tabla ASCII. Ejemplo para el primer ejemplo anterior:

 384  159 1472
1174  499  342
 457 1357  201

Enteros alineados a la derecha rellenados por espacios. El ancho de cada columna es el ancho del entero más grande en esa columna.

Tanteo

Este es el código de golf , por lo que gana el código más corto en bytes. Se aplican las lagunas estándar (especialmente las incorporadas para resolver este problema). No tiene que preocuparse por entradas incorrectas o imposibles (incluidos números negativos). Proporcione un resultado de muestra en su respuesta (obligatorio) para el segundo ejemplo anterior.

CJam, 119 91 bytes

q~:M;),>:R;(:L{{R{ML)d/-Y#)mr}$L/L<2{{M1$:+-+}%z}*:U:+__O|=R*-}gU{:s_:,:e>f{Se[}}%zSf*N*}M?

Este es un enfoque probablemente correcto, no determinista.

En mi escritorio, el segundo caso de prueba generalmente termina en menos de 10 minutos.

El primer caso termina al instante. Pruébelo en línea en el intérprete de CJam .

Ejecución de la muestra

$ cjam grid.cjam <<< '8 1 300 500'
77  66  37 47  56  46 86  85
63 102  70 72  49  54 81   9
62  69  58 57  71  17 48 118
64  65  67 87  53  44 80  40
73  60  55 89  51  76 84  12
68  59  28 78  74  38 50 105
61  75  52 43 125  83 42  19
32   4 133 27  21 142 29 112

Idea

Sin límites de tiempo, podríamos generar cuadrados al azar hasta encontrar un cuadrado válido. Este enfoque se basa en esa idea, agregando dos optimizaciones:

• En lugar de generar pseudoaleatoriamente un cuadrado de longitud lateral N , generamos cuadrados de longitud lateral N-1 , agregamos una columna para formar un rectángulo N × (N-1) cuyas filas tienen la suma S , luego una fila para formar un cuadrado de longitud del lado N cuyas columnas tienen suma S .

  Como la suma de los elementos de todas las columnas será NS y la suma de los elementos de las primeras N-1 filas es (N-1) S , la última fila también tiene suma S .

  Sin embargo, este proceso puede generar una matriz no válida, ya que no hay garantía de que todos los elementos de la última fila y columna sean únicos o estén en el rango [A ... B] .

• Elegir un cuadrado de enteros únicos en [A ... B] y la longitud del lado N-1 de manera uniforme al azar tomaría demasiado tiempo. De alguna manera, debemos priorizar los cuadrados que tienen una mayor probabilidad de resultar en un cuadrado válido de longitud de lado N después de aplicar el proceso detallado en el punto anterior.

  Dado que cada fila y columna tiene que tener una suma de S , sus elementos tienen un promedio de S / N . Por lo tanto, elegir más elementos cercanos a ese promedio debería aumentar nuestras posibilidades.

  Para cada yo en [A ... B] , seleccionamos pseudoaleatoriamente un flotador entre 0 y (I - S / N) ² + 1 y clasificamos los elementos de [A ... B] por los flotadores seleccionados. Mantenemos los primeros números N ² y los colocamos en orden de lectura en un cuadrado.

  Suponiendo una distribución perfectamente uniforme de todos los números reales entre 0 y (I - S / N) ² + 1 en cada paso, todos los cuadrados tienen una probabilidad distinta de cero de ser elegidos, lo que significa que el proceso terminará eventualmente.

Código

q~          e# Read all input from STDIN and evaluate it.
:M;         e# Save "S" in M and discard it from the stack.
),>:R;      e# Transform "A B" into [A ... B], save in R and discard.
(:L         e# Save "N - 1" in L and keep it on the stack.
{           e# If L is non-zero:
  {         e#   Do:
    R{      e#     For each I in R:
      ML)d/ e#       Compute M/Double(L+1).
      -Y#   e#       Subtract the result from I and square the difference.
      )mr   e#       Add 1 and pick a non-negative Double below the result.
    }$      e#     Sort the values of I according to the picks.
    L/      e#     Split the shuffled R into chunks of length L.
    L<      e#     Keep only the first L chunks.
    2{      e#     Do twice:
      {     e#       For each row of the  L x L array.
        M1$ e#       Push M and a copy of the row.
        :+- e#       Add the integers of the row and subtract their sum from M.
        +   e#       Append the difference to the row.
      }%    e#
      z     e#       Transpose rows and columns.
    }*      e#
    :U:+    e#     Save the result in U and concatenate its rows.
    __O|    e#     Push two copies. Deduplicate the second copy.
    =R*     e#     Push R if all elements are unique, an empty array otherwise.
    -       e#     Remove the result's elements from U's elements.
  }g        e#   If the resulting array is non-empty, repeat the loop.
  U{        e#   For each row in U:
    :s      e#     Convert its integers into strings.
    _:,     e#     Copy and replace each string with its length.
    :e>     e#     Compute the maximum length.
    f{      e#     For each integer, push the maximum length; then
      Se[   e#       Left-pad the integer with spaces to that length.
    }       e#
  }%        e#
  z         e#   Transpose rows with columns.
  Sf*N*     e#   Join columns by spaces, rows by linefeeds.
}M?         e# Else, push M.