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 s
i n
.
Po uzyskaniu tych danych wejściowych program wygeneruje losową funkcję matematyczną f
z 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}
f
n
0
s-1
f
A
B
n
A[i] ≥ B[i]
i
f(A) ≥ f(B)
Dokładny rozkład funkcji monotonicznych f
nie 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 n
liczby całkowite między 0
iw s-1
jakiejś 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 = 3
i n = 2
mogą 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 = 2
i n = 4
moż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 = 2
i 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) .
źródło
Odpowiedzi:
Pyth, 35 bajtów (38-15% = 31,45 dalej)
Demonstracja
Dane wejściowe mają format:
Dane wyjściowe mają format:
Po prostu generuje losowe możliwości i je testuje.
Alternatywna 37-bajtowa wersja, która moim zdaniem kwalifikuje się do premii:
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
.źródło
3, 2
. Niestety nawet nie otrzymałem odpowiedzi3, 3
w internetowym executorze pyth. Czy istnieje taka niekończąca się pętla dla tej kombinacji ?!2, 4
, ale niewiele więcej.CJam, 40 bajtów - 15% = 34 bajty
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 .
źródło
Julia, 64 bajty (-15% = 54,4)
Nie golfowany:
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]
.źródło