Wyzwanie z prostymi regułami, ale nietrywialnymi algorytmami. :-)

Zadanie

Weź dane wejściowe w postaci liczb całkowitych oddzielonych spacją:

N A B S

Gdzie N jest długością boku kwadratowej macierzy 2D wypełnionej unikalnymi liczbami (liczbami całkowitymi) między A i B włącznie. Dla każdego wiersza i kolumny w tej macierzy suma jest zawsze taka sama: S. (Innymi słowy, macierz jest półmagicznym kwadratem).

Uwaga:

Wszystkie liczby są dodatnie. Wyjątkiem jest A, które może wynosić 0.

Przykłady

Dla

3 1 10000 2015

poprawnym rozwiązaniem byłoby

Dla

8 1 300 500

poprawnym rozwiązaniem byłoby

Wydajność

Dane wyjściowe powinny być tabelą ASCII. Przykład dla pierwszego przykładu powyżej:

 384  159 1472
1174  499  342
 457 1357  201

Wyrównane do prawej liczby całkowite wypełnione spacjami. Szerokość każdej kolumny to szerokość największej liczby całkowitej w tej kolumnie.

Punktacja

To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach. Obowiązują standardowe luki (szczególnie w przypadku wbudowanych rozwiązań tego problemu). Nie musisz się przejmować błędnymi lub w inny sposób niemożliwymi danymi wejściowymi (w tym liczbami ujemnymi). Podaj przykładowy wynik w swojej odpowiedzi (obowiązkowy) dla drugiego przykładu powyżej.

CJam, 119 91 bajtów

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?

Jest to możliwe do udowodnienia, niedeterministyczne podejście.

Na moim pulpicie drugi przypadek testowy zazwyczaj kończy się w mniej niż 10 minut.

Pierwsza sprawa kończy się natychmiast. Wypróbuj online w interpretatorze CJam .

Przykładowy przebieg

$ 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

Pomysł

Bez ograniczeń czasowych możemy po prostu losowo generować kwadraty, aż do znalezienia prawidłowego kwadratu. To podejście opiera się na tym pomyśle, dodając dwie optymalizacje:

• Zamiast pseudolosowego generowania kwadratu o długości boku N , generujemy kwadraty o długości boku N-1 , dodajemy jedną kolumnę, aby utworzyć prostokąt N × (N-1), którego rzędy mają sumę S , a następnie jeden wiersz, aby utworzyć kwadrat o długość boku N , których słupy mają sumy S .

  Ponieważ suma elementów wszystkich kolumn będzie NS a suma elementów pierwszych N-1 rzędami wynosi (n-1), S , ostatni wiersz również sumy S .

  Jednak ten proces może generować nieprawidłową macierz, ponieważ nie ma gwarancji, że wszystkie elementy ostatniego wiersza i kolumny będą unikalne lub mieszczą się w zakresie [A ... B] .

• Wybieranie losowo kwadratu unikatowych liczb całkowitych w [A ... B] i długości boku N-1 równomiernie zajęłoby dużo czasu. W jakiś sposób musimy nadać priorytet kwadratom, które mają większą szansę na uzyskanie prawidłowego kwadratu o długości boku N po zastosowaniu procesu opisanego w poprzednim punkcie.

  Biorąc pod uwagę, że każdy wiersz i kolumnę musi mieć sumy S , jej elementy mają średnio S / N . Zatem wybranie większej liczby elementów zbliżonych do tej średniej powinno zwiększyć nasze szanse.

  Dla każdego I w [A ... B] pseudolosowo wybieramy liczbę zmiennoprzecinkową od 0 do (I - S / N) ² + 1 i sortujemy elementy [A ... B] według wybranych liczb zmiennoprzecinkowych. Zachowujemy pierwsze N ² liczby i umieszczamy je w kolejności czytania w kwadracie.

  Zakładając idealnie równomierny rozkład wszystkich liczb rzeczywistych między 0 a (I - S / N) ² + 1 na każdym etapie, wszystkie kwadraty mają niezerowe prawdopodobieństwo wybrania, co oznacza, że ​​proces ostatecznie się zakończy.

Kod

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.