Wygeneruj funkcję monotoniczną

12

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) .

Zgarb
źródło
Może to pomóc, jeśli całkowicie wyliczysz wszystkie możliwe funkcje dla małego przypadku, takiego jak s = 2 n = 2. Musiałem przeczytać opis kilka razy, aby zrozumieć, jak losowość się pojawi.
Sparr,
@Sparr Dobry pomysł; edytowane.
Zgarb,
czy wymagane jest ograniczone środowisko wykonawcze? Rozważam rozwiązanie, które generuje funkcje losowe, dopóki nie znajdzie monotonicznego.
Sparr,
@Sparr Myślę, że dodam premię za ograniczony czas działania, więc takie rozwiązanie nie zostanie zdyskwalifikowane.
Zgarb,
@Zgarb - być może powinieneś zrobić dużą premię za rozwiązania, które są ograniczone i prawdopodobnie zakończą się w ciągu godziny.
Glen O

Odpowiedzi:

4

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.

isaacg
źródło
Dobry przykład z wejściem 3, 2. Niestety nawet nie otrzymałem odpowiedzi 3, 3w internetowym executorze pyth. Czy istnieje taka niekończąca się pętla dla tej kombinacji ?!
bobbel
@bobbel Online wykonawca ma limit czasu. Próbuję to lokalnie.
isaacg,
@bobbel To nie tyle pętla infitie ma bardzo powolną. Działa również 2, 4, ale niewiele więcej.
isaacg
@ Bobbel Dodałem coś jeszcze wolniej.
isaacg
1

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 .

Dennis
źródło
1

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].

Glen O
źródło