O serii
Po pierwsze, możesz potraktować to jak każde inne wyzwanie związane z golfem i odpowiedzieć na nie, nie martwiąc się w ogóle serią. Istnieje jednak tabela wyników dla wszystkich wyzwań. Możesz znaleźć tabelę liderów wraz z kilkoma więcej informacji o serii w pierwszym poście .
Dziura 8: Przetasuj nieskończoną listę
Powinieneś napisać funkcję lub program, który pobiera nieskończoną listę jako dane wejściowe i zwraca losową wersję tej listy.
O nieskończonych wejściach / wyjściach
Istnieje kilka sposobów na uzyskanie danych wejściowych i uzyskanie wyników dla tego wyzwania:
- Możesz wziąć listę dodatnich liczb całkowitych lub ich ciąg reprezentujący albo ciąg znaków lub listę drukowalnych znaków ASCII (od 0x20 do 0x7E włącznie). Format wyjściowy musi być zgodny z formatem wejściowym. Odtąd będę odtąd określał dane jako „listę”, niezależnie od wybranej opcji.
- Możesz odczytać listę z nieskończonego standardowego strumienia wejściowego i zapisywać dane wyjściowe w sposób ciągły do nieskończonego standardowego strumienia wyjściowego. Rozwiązanie nie powinno zależeć od żadnej konkretnej wartości lub sekwencji wartości, aby zapewnić, że strumień wyjściowy jest regularnie zapisywany i opróżniany (np. Nie można po prostu zapisywać danych wyjściowych, gdy jest
5
na liście wejściowej). Oczywiście, jeśli czytasz ciąg reprezentujący listę, możesz poczekać, aż pojawi się separator listy. - W językach, które je obsługują, możesz napisać funkcję, która pobiera i zwraca leniwą nieskończoną listę lub ciąg znaków.
- W językach, które je obsługują, możesz zaimplementować nieskończony generator, który pobiera inny generator jako dane wejściowe.
- Alternatywnie możesz napisać funkcję, która nie przyjmuje argumentów i zwraca jedną wartość wyjściową za każdym razem, gdy jest wywoływana. W takim przypadku można założyć, że zdefiniowano funkcję, która nie przyjmuje żadnych argumentów i zwraca kolejną wartość wejściową za każdym razem, gdy jest wywoływana. Możesz dowolnie wybrać nazwę tej funkcji.
Możesz założyć, że twój program działa wiecznie i że nieskończona pamięć jest dostępna. (Można to rozwiązać za pomocą skończonej ilości pamięci, ale oznacza to, że możesz wyciec pamięć.)
O losowości
Dla każdej wartości v, która jest odczytywana w pozycji i nieskończonego sygnału wejściowego, musi istnieć dodatnie prawdopodobieństwo, że znajdzie się ona w dowolnej pozycji od i-9 do i + 9 nieskończonej mocy wyjściowej (chyba że ta pozycja byłaby ujemna ). Prawdopodobieństwa te nie muszą być takie same dla różnych pozycji wyjściowych ani nawet dla różnych pozycji wejściowych. W porządku, jeśli twoje rozwiązanie może również przetasować wartości do innej pozycji, która jest dalej.
Dlatego nie jest konieczne, aby twoje rozwiązanie mogło przetasować pierwszą wartość bardzo daleko w dół listy, lub aby mogło przetasować bardzo późną wartość do pierwszej pozycji, chociaż jest w porządku, jeśli tak, dopóki wszystkie pozycje 9 kroków od dane wejściowe są możliwe.
Na przykład, jeśli wziąłeś następujący ciąg jako dane wejściowe, ___
wskazuje wszystkie pozycje, które X
muszą być w stanie znaleźć się w wyniku:
___________________
abcdefghijklmnopqrstuvwxyzXabcdefghijklmnopqrstuvwxyz...
Jeśli w Twoim języku nie ma wbudowanego generatora liczb losowych lub nie chcesz go używać, możesz wziąć dodatkową wartość początkową jako dane wejściowe i zaimplementować własny odpowiedni RNG za pomocą tego parametru. Ta strona może być do tego pomocna.
Bez względu na faktyczną dystrybucję, z której korzysta twoje rozwiązanie, prawie na pewno wygeneruje następną wartość po skończonym (ale arbitralnym) czasie.
Dołącz krótkie wyjaśnienie, w jaki sposób Twoje wdrożenie spełnia te wymagania.
Punktacja
To jest golf golfowy , więc wygrywa najkrótsza ważna odpowiedź - mierzona w bajtach .
Tabela liderów
Pierwszy post z serii generuje tabelę wyników.
Aby mieć pewność, że Twoje odpowiedzi się pojawią, zacznij każdą odpowiedź od nagłówka, używając następującego szablonu Markdown:
# Language Name, N bytes
gdzie N
jest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:
# Ruby, <s>104</s> <s>101</s> 96 bytes
(Język nie jest obecnie wyświetlany, ale fragment go wymaga i analizuje, a w przyszłości mogę dodać tabelę wyników według języków).
źródło
Odpowiedzi:
Python 3 , 78 bajtów
Wypróbuj online!
Pobiera dane wejściowe ze STDIN (jeden na linię), drukuje do STDOUT.
Utrzymuje bufor
l
do 10 elementów. Bufor jest tasowany z każdym krokiem. Gdy jego długość wynosi 10, ostatni element jest drukowany i usuwany.Jeśli element zostanie wydrukowany zaraz po jego wstawieniu, przeskoczył przed 9 innymi elementami oczekującymi w buforze, więc wydaje się, że pozostało 9 miejsc. Element może czekać w buforze dowolnie długo, więc jego pozycja może przesunąć dowolną kwotę w prawo.
Wydaje się, że nie ma dobrego sposobu na tworzenie i usuwanie losowego elementu z listy. Tasowanie wydaje się przesadą. Jest o 2 bajty dłużej w użyciu
l.pop(randint(0,9))
(co oznacza, że lista ma 10 elementów).Nie ma nic lepszego
x=choice(l);l.remove(x)
. Język zpoprandom
podobnymimożna bardzo czysto zrobić
źródło
Befunge ( smak dziwaczny ), 4 bajty
,
odczytuje znak ze strumienia i wypycha go na stos.~
wyrzuca górną postać ze stosu (jeśli jest obecna) i drukuje ją.?
losuje, które polecenie zostanie wykonane jako następne. Tak więc algorytm jest następujący: „W nieskończonej pętli, z jednakowym prawdopodobieństwem albo popchnij znak, albo pop znak”. Myślę, że spełnia to wymagania: postać może zobaczyć dowolną liczbę znaków dodanych nad nią na stosie, dzięki czemu może przesuwać się dowolnie daleko w prawo, i może być drukowana, gdy stos jest dowolnie duży, więc może dowolnie przenieść się do lewo.źródło
>> document.getElementById("output").innerHTML = "a\0b"
>> document.getElementById("output").innerHTML
"ab"
C (gcc) , 94 bajty
Wypróbuj online!
Ok, link TIO nie ma większego sensu. Dla ułatwienia testowania stworzyłem następujący program C, który wypisze losowe znaki ascii lub powtórzy ciąg nieskończenie.
Ten program będzie nazywany
iro
.Poprawność programu
To, co tu robię, to wczytywanie
9
wartości do bufora. Następnie losowe indeksy są wybierane z tej tablicy i są wyprowadzane, a następnie zastępowane przez następny znak w strumieniu.źródło
SILOS , 149 bajtów
Wypróbuj online!
Zasadniczo ciągle pobiera dane wejściowe (w tłumaczu online za pomocą argumentów, ale w oficjalnym tłumaczu offline umożliwia pisanie w konsoli (nieskończenie)) w blokach po 15 na raz (30 pierwszy blok).
Ładuje dane wejściowe do tymczasowej kolejki i wybiera szczęśliwą 15 (losowo, ale nie równo równo pod względem prawdopodobieństwa lub dystrybucji).
Reszta pozostaje, gdy nowe dane wejściowe wypełniają kolejkę, pierwsze dane wejściowe mogą być tasowane do samego końca (w zasadzie myślę, że znaki mają normalny rozkład). Warto zauważyć, że ten program jest tylko dwa razy bardziej gadatliwy niż python i być może „bardziej golfowy” niż Java.
Aby lepiej zobaczyć wyniki, mam wersję niezgodną, która pobiera dane wejściowe jako ciąg znaków (jednak może przyjąć tylko około 8 000 znaków).
Wypróbuj online!
Dla zabawy, oto ten post wprowadzony przez wersję strunową.
źródło
Aceto , 24 bajty, niekonkurujące
Nie konkuruje, ponieważ musiałem naprawić błąd w tłumaczu.
Pobiera nieskończony strumień linii i generuje je w losowej kolejności. Każdy element ma szansę wystąpić w dowolnym losowym punkcie.
Zaczynamy od
?
w lewym dolnym rogu, który przesuwa nas w losowym kierunku. Jeśli to jest w dół lub w lewo, zostajemy odepchnięci w prawo.Jeśli przeniesiemy się w górę,
r
odszukamy wartość, potasujemy stos (Y
) iO
wskoczemy z powrotem do rigina.Jeśli zostaniemy przesunięci w prawo,
d
zwiększymy wartość najwyższego stosu, wypchniemy a0
i sprawdzimy równość (ponieważ czytamy ciągi, nigdy nie możemy mieć liczby całkowitej 0). Jeśli wartości są równe, oznacza to, że doszliśmy do końca stosu (z którego nie chcemy drukować). Możemy negować porównanie (!
) ip
rukuj tylko wtedy, gdy (`
) rzeczy nie były równe. Następnie wskakujemy również z powrotem naO
platformę.źródło
Rubinowy, 43 bajty
W mojej pierwotnej odpowiedzi użyto leniwej, nieskończonej listy, ale jest ona krótsza. No cóż.
źródło
MATL , 11 bajtów
Wypróbuj online!
Port histocrat za befunge odpowiedź .
Objaśnienie: (Podziękowania dla Luisa Mendo za -1 bajt)
Daje to prawie na pewno w skończonym czasie, i prawie na pewno wymaga tylko skończonej pamięci .
Dla kompletności, oto 15-bajtowa wersja, która przechowuje 10-elementowy bufor i generuje losowy element z tego:
Podoba mi się ta wersja dla bardzo idiomatycznych (o ile języki gry w golfa mogą być idiomatyczne)
tn...Yr&)
, która wyskakuje z listy losowy element i zwraca listę bez tego elementu. Jednak szczególna logistyka tego wyzwania dodaje wiele bajtów (wymaganew
do wyświetlenia,t9>?
aby sprawdzić, czy lista jest wystarczająco pełna ...).źródło
Alice , 7 bajtów
Wypróbuj online!
To powinno działać na nieskończonym wejściu z nieskończonym czasem i pamięcią, ale w praktyce nie jest to takie łatwe :)
Wyjaśnienie
Przy każdej iteracji 10 znaków jest odczytywanych z wejścia i tylko jeden trafia na wyjście, więc użycie pamięci wzrasta liniowo podczas wykonywania. Przy skończonym wejściu szybko osiąga EOF, z którego dziesięć -1 będzie wypychane na stos przy każdej iteracji. Próba wypisania -1 jako znaku nie ma żadnego efektu, ale jest mało prawdopodobne, aby wszystkie znaki wejścia zostały wydrukowane w rozsądnym czasie.
Pozycję i wyjścia można przyjąć dowolnym znakiem na wejściu do pozycji 10i , co jest zgodne z wyzwaniem wymagającym co najmniej zakresu od i-9 do i + 9 .
źródło
C, 214 bajtów
Jak to działa
Wypróbuj online (UNIX)
źródło
Vi
jest zamieniony zVj
miejscem, w którymj = RAND [ i-9, i+9 ]
należy spełnić kryteria pytaniav which is read at a position i of the infinite input, there must be a positive probability for it to end up in any of the positions i-9 to i+9 of the infinite output
05AB1E , 13 bajtów
Wypróbuj online! (zmodyfikowany, aby wziąć 20 elementów)
źródło
Bash , 17 bajtów
Wypróbuj online!
xargs stale pobiera 9 liter ze STDIN i wysyła je do losowego
nieskończoną listę można wygenerować przez:
który drukuje abcde .. z nieskończonymi czasami.
Test można wykonać:
źródło
xargs shuf -e
spełnia wymaganiaR, 70 bajtów
Zaczyna się od pustego wektora
x
. W nieskończonej pętli pobiera nową wartość ze STDIN, a następnie tasuje wektor. Następnie sprawdza, czy długość utworzonej listy wynosi 10 lub więcej. Jeśli tak, może rozpocząć drukowanie. W ten sposób wektor ma bufor 10 danych wejściowych, z których każdy jest tasowany podczas każdej iteracji. Możliwe jest więc wydrukowanie danych wejściowych 10 miejsc wcześniej i nieskończenie wiele miejsc później (zgodnie z rozkładem geometrycznym za pomocąp=1/10
). Gdy bufor jest wystarczająco długi, pierwszy element jest drukowany i usuwany z wektora.źródło
JavaScript, 78 bajtów
Używa tej samej metody co odpowiedź xnor.
źródło
Perl 5 , 39 bajtów
38 bajtów kodu +
-n
flaga.Wypróbuj online!
Dodaj każdy element do
@F
tablicy (zpush@F,$_
). Gdy@F
zawiera 10 elementów (a więcpush
zwraca liczbę elementów w tablicy9<push...
), losowy element jest usuwany i drukowany (splice@F,rand 10,1
aby usunąć element,print
aby go wydrukować).Wyjście zaczyna się dziać po odczytaniu 10. elementu. Dlatego każdy element może zacząć pojawiać się co najmniej 9 pozycji przed swoim pierwotnym i może być nieskończenie przesuwany w prawo.
źródło
SmileBASIC,
6158 bajtówKażdy znak nieskończonej listy jest dodawany na końcu bufora. Gdy długość bufora wynosi 11, losowy znak jest drukowany i usuwany.
Funkcja
R
generuje następny znak.źródło
Prolog, 70 bajtów
źródło