Um desafio com regras simples, mas com algoritmos não triviais. :-)

Tarefa

Tome entrada na forma de números inteiros separados por espaço:

N A B S

Onde N é o comprimento lateral de uma matriz quadrada 2D preenchida com números únicos (números inteiros) entre A e B, inclusive. Para cada linha e coluna nessa matriz, a soma é sempre a mesma: S. (Em outras palavras, a matriz é um quadrado semi-mágico).

Nota:

Todos os números são positivos. A exceção é A, que pode ser 0.

Exemplos

Para

3 1 10000 2015

uma solução válida seria

Para

8 1 300 500

uma solução válida seria

Saída

Sua saída deve ser uma tabela ASCII. Exemplo para o primeiro exemplo acima:

 384  159 1472
1174  499  342
 457 1357  201

Inteiros alinhados à direita preenchidos por espaços. A largura de cada coluna é a largura do maior número inteiro nessa coluna.

Pontuação

Isso é código-golfe , então o código mais curto em bytes vence. As brechas padrão se aplicam (especialmente sobre os embutidos para resolver esse problema). Você não precisa se preocupar com entradas erradas ou impossíveis (incluindo números negativos). Forneça uma amostra de saída em sua resposta (obrigatória) para o segundo exemplo acima.

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?

Essa é uma abordagem comprovadamente correta e não determinística.

Na minha área de trabalho, o segundo caso de teste geralmente termina em menos de 10 minutos.

O primeiro caso termina instantaneamente. Experimente on-line no intérprete CJam .

Amostra de execução

$ 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

Idéia

Sem limites de tempo, poderíamos gerar quadrados aleatoriamente até encontrar um quadrado válido. Essa abordagem se baseia nessa ideia, adicionando duas otimizações:

• Em vez de gerar quadrado pseudo-aleatoriamente com comprimento lateral N , geramos quadrados com comprimento lateral N-1 , adicionamos uma coluna para formar um retângulo N × (N-1) cujas linhas possuem soma S , depois uma linha para formar um quadrado de comprimento do lado N cujas colunas têm soma S .

  Uma vez que a soma dos elementos de todas as colunas serão NS e a soma dos elementos dos primeiros N-1 linhas é (N-1) S , a última linha também tem soma S .

  No entanto, esse processo pode gerar uma matriz inválida, pois não há garantia de que todos os elementos da última linha e coluna sejam exclusivos ou caiam no intervalo [A ... B] .

• Escolher um quadrado de números inteiros únicos em [A ... B] e o comprimento lateral N-1 uniformemente aleatoriamente levaria muito tempo. De alguma forma, precisamos priorizar os quadrados com maior chance de resultar em um quadrado válido de comprimento lateral N após aplicar o processo detalhado no item anterior.

  Dado que cada linha e coluna tem que ter um valor de S , os seus elementos têm uma média de S / N . Assim, escolher mais elementos próximos dessa média deve aumentar nossas chances.

  Para cada I em [A ... B] , escolhemos pseudo-aleatoriamente um flutuador entre 0 e (I - S / N) ² + 1 e classificamos os elementos de [A ... B] pelos flutuadores escolhidos. Mantemos os primeiros números N ² e os colocamos em ordem de leitura em um quadrado.

  Assumindo uma distribuição perfeitamente uniforme de todos os números reais entre 0 e (I - S / N) ² + 1 em cada etapa, todos os quadrados têm uma probabilidade diferente de zero de serem selecionados, significando que o processo 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.