Przegląd

W tym wyzwaniu Twoim zadaniem jest losowe wygenerowanie monotonicznej funkcji matematycznej między dwoma zestawami.

Wejście

Twoje dane wejściowe to dwie dodatnie liczby całkowite si n.

Po uzyskaniu tych danych wejściowych program wygeneruje losową funkcję matematyczną fz zestawu do . Innymi słowy, jest to „zasada”, który odbywa się w -tuple liczb całkowitych między a i zwraca jeden taki całkowitych. Ponadto powinien być monotoniczny w następującym znaczeniu. Jeśli i są dwie pary, takie, które obowiązują dla każdej współrzędnej , to .{0,1,...,s-1}n{0,1,...,s-1}fn0s-1fABnA[i] ≥ B[i]if(A) ≥ f(B)

Dokładny rozkład funkcji monotonicznych fnie ma znaczenia, o ile każda taka funkcja ma dodatnie prawdopodobieństwo wygenerowania (przy założeniu idealnego RNG).

Wynik

Twój wynik powinien być wyliczeniem danych wejściowych i wyjściowych f. Powinien zawierać wszystkie nliczby całkowite między 0iw s-1jakiejś kolejności, po których każdemu następują odpowiednie dane wyjściowe z f. Dokładny format wyjściowy jest elastyczny (w granicach rozsądku).

Przykłady

Dane wejściowe s = 3i n = 2mogą generować dane wyjściowe

(0, 0) 0
(0, 1) 1
(0, 2) 2
(1, 0) 0
(1, 1) 1
(1, 2) 2
(2, 0) 1
(2, 1) 1
(2, 2) 2

Zawiera wszystkie pary w zestawie {0, 1, 2}dokładnie raz, a po każdej z nich znajduje się jej f-value. Warunek monotoniczności jest również spełniony. Krotki podano tutaj w kolejności leksykograficznej, ale nie jest to konieczne.

Jako kolejny przykład s = 2i n = 4może produkować

(0, 0, 0, 0) 0
(0, 0, 0, 1) 0
(0, 0, 1, 0) 0
(0, 0, 1, 1) 0
(0, 1, 0, 0) 1
(0, 1, 0, 1) 1
(0, 1, 1, 0) 1
(0, 1, 1, 1) 1
(1, 0, 0, 0) 0
(1, 0, 0, 1) 1
(1, 0, 1, 0) 0
(1, 0, 1, 1) 1
(1, 1, 0, 0) 1
(1, 1, 0, 1) 1
(1, 1, 1, 0) 1
(1, 1, 1, 1) 1

Poniżej przedstawiono wszystkie możliwe dane wyjściowe dla s = 2i n = 2(aż do zmiany kolejności krotek); twój program powinien losowo wypisać jeden z nich:

(0,0) 0
(0,1) 0
(1,0) 0
(1,1) 0
-------
(0,0) 0
(0,1) 0
(1,0) 0
(1,1) 1
-------
(0,0) 0
(0,1) 0
(1,0) 1
(1,1) 1
-------
(0,0) 0
(0,1) 1
(1,0) 0
(1,1) 1
-------
(0,0) 0
(0,1) 1
(1,0) 1
(1,1) 1
-------
(0,0) 1
(0,1) 1
(1,0) 1
(1,1) 1

Zasady i punktacja

Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone. Preferowany jest kod z wyjaśnieniem.

Nie ma ograniczeń dotyczących złożoności czasu, ale dam premię w wysokości -15%, jeśli Twoje rozwiązanie zawsze gwarantuje ukończenie w określonym czasie (w zależności od nakładów i przy założeniu idealnego RNG działającego w stałym czasie) .

Pyth, 35 bajtów (38-15% = 31,45 dalej)

#I!sm><FhMds<MCeMd^JC,mOQK^UQvzK2JB

Demonstracja

Dane wejściowe mają format:

n
s

Dane wyjściowe mają format:

[[value, tuple], [value, tuple], ...]

Po prostu generuje losowe możliwości i je testuje.

Alternatywna 37-bajtowa wersja, która moim zdaniem kwalifikuje się do premii:

Of!sm><FhMds<MCeMd^T2mC,d^UQvz^UQ^Qvz

Demonstracja

Zaczyna się od wygenerowania wszystkich możliwych funkcji monotonicznych, a następnie generuje losowo jedną. Jest znacznie wolniejszy i osiąga szczyt 2,2.

CJam, 40 bajtów - 15% = 34 bajty

q~1$\m*\1$,m*{W$\.+2m*{:.<2b}%1&!},mR]zp

To podejście generuje wszystkie prawidłowe funkcje, a następnie włącza losowo. Czas pracy wynosi co najmniej O (s ^{2s n} ) , ale jest stały dla danego wejścia.

Wątpię, by to właśnie miał na myśli OP, ale gwarantuje, że zakończy się w określonym czasie (w zależności od nakładów [...]) i dlatego kwalifikuje się do premii.

Wypróbuj online w interpretatorze CJam .

Julia, 64 bajty (-15% = 54,4)

g(s,n)=(K=rand(0:s-1,ntuple(n,i->s));for i=1:n K=sort(K,i)end;K)

Nie golfowany:

function g(s,n)
  # Generates a random n-dimensional array with s per dimension
  # and all values being integers between 0 and s-1
  K=rand(0:s-1,ntuple(n,i->s))
  # Loop over the various dimensions
  for i=1:n
    # Sort in the current dimension
    K=sort(K,i)
  end
  return K
end

Uruchomi się to szybko, z jedynym możliwym problemem związanym z pamięcią dla wystarczająco dużych si an (g (10,10) musi wytworzyć tablicę 10 ^ 10, więc oczywiście zabraknie pamięci - nawet jeśli każda liczba jest jeden bajt, czyli 10 gigabajtów danych).

Dane wyjściowe są oparte na indeksowaniu 1, więc aby określić wynik dla danych wejściowych, należy dodać jeden do każdej wartości wejściowej. Na przykład, aby znaleźć f (1,2,6,0,3), musisz to zbadać K[2,3,7,1,4].