O serii
Będę prowadził serię golfowych wyzwań związanych z przypadkowością. Będzie to w zasadzie 9-dołkowe pole golfowe , ale rozłożone na kilka pytań. Możesz brać udział w każdym wyzwaniu indywidualnie, jakby to było normalne pytanie.
Będę jednak utrzymywać tabelę wyników we wszystkich wyzwaniach. Serial obejmie 9 wyzwań (na razie), jedno publikowane co kilka dni. Każdy użytkownik, który bierze udział we wszystkich 9 wyzwaniach, może wygrać całą serię. Ich ogólny wynik to suma ich najkrótszych zgłoszeń na każde wyzwanie (więc jeśli odpowiesz dwukrotnie na wyzwanie, tylko lepsza odpowiedź jest liczona do wyniku). Jeśli ktokolwiek będzie zajmował najwyższe miejsce w ogólnej tabeli liderów przez 28 dni , przyznam mu nagrodę w wysokości 500 powtórzeń .
Chociaż mam szereg pomysłów w szeregu, przyszłe wyzwania nie są jeszcze ustalone. Jeśli masz jakieś sugestie, daj mi znać w odpowiednim poście z piaskownicą .
Hole 1: Shuffle an Array
Pierwsze zadanie jest dość proste: biorąc pod uwagę niepustą tablicę liczb całkowitych, losowo ją potasuj. Istnieje jednak kilka zasad:
- Każda możliwa permutacja musi zostać zwrócona z takim samym prawdopodobieństwem (dlatego losowanie powinno mieć jednolity rozkład). Możesz sprawdzić, czy twój algorytm jest jednorodny / bezstronny, implementując go w JavaScript w Will it Shuffle , co wytworzy matrycę tendencyjności - wynik powinien wyglądać tak jednolicie, jak wbudowane Fisher-Yates lub sortować (kolejność losowa) .
- Nie wolno używać żadnej wbudowanej lub innej firmy metody tasowania tablicy lub generowania losowej permutacji (lub wyliczenia wszystkich permutacji). W szczególności jedyną wbudowaną funkcją losową, której możesz użyć, jest uzyskanie pojedynczej liczby losowej na raz . Państwo może założyć, że każdy wbudowaną losowych przebiegów metoda numer w czasie O (1) i jest idealnie równomierne na wymaganym przedziale (w sensie matematycznym - można zignorować szczegóły reprezentacji zmiennoprzecinkowej tutaj). Jeśli twój język pozwala ci uzyskać listę m liczb losowych naraz, możesz skorzystać z tej funkcji, pod warunkiem, że m liczb jest od siebie niezależnych i policzysz je jako O (m).
- Implementacja nie może przekraczać złożoności czasowej O (N) , gdzie N jest rozmiarem tablicy, która ma być tasowana. Na przykład nie można „sortować według liczb losowych”.
- Możesz albo przetasować tablicę na miejscu, albo utworzyć nową tablicę (w takim przypadku stara tablica może zostać zmodyfikowana w dowolny sposób).
Możesz napisać pełny program lub funkcję i pobrać dane wejściowe za pomocą STDIN, argumentu wiersza poleceń, argumentu funkcji lub pytania i wygenerować dane wyjściowe za pomocą wartości zwracanej lub drukując do STDOUT (lub najbliższej alternatywy). Jeśli napiszesz funkcję, która przetasowuje tablicę w miejscu, nie musisz jej oczywiście zwracać (pod warunkiem, że Twój język pozwala na dostęp do zmodyfikowanej tablicy po powrocie funkcji).
Dane wejściowe i wyjściowe mogą być w dowolnym dogodnym formacie listy lub ciągu, ale muszą obsługiwać dowolne liczby całkowite z zakresu -2 31 ≤ x <2 31 . W zasadzie, Twój kod powinien działać dla tablic do długości 2 do 31 , choć niekoniecznie muszą zmieścić się w pamięci lub kompletne w rozsądnym czasie. (Po prostu nie chcę widzieć dowolnych limitów wielkości pętli kodu twardego itp.)
To jest kod golfowy, więc wygrywa najkrótsze przesłanie (w bajtach).
Tabela liderów
Poniższy fragment wygeneruje tabelę wyników we wszystkich wyzwaniach serii.
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).
/* Configuration */
var QUESTION_IDs = [45302, 45447, 46991, 49394, 51222, 66319, 89621, 120472]; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!.FjwQBrX2KXuFkv6p2lChi_RjzM19";
/* App */
var answers = [], page = 1, currentQ = -1;
function answersUrl(index) {
return "https://api.stackexchange.com/2.2/questions/" + QUESTION_IDs.join(";") + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}
function getAnswers() {
$.ajax({
url: answersUrl(page++),
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
answers.push.apply(answers, data.items);
if (data.has_more) getAnswers();
else process();
}
});
}
getAnswers();
var SIZE_REG = /\d+(?=[^\d&]*(?:<(?:s>((?!>).)*<\/s>|((?!>).)+>)[^\d&]*)*$)/;
var NUMBER_REG = /\d+/;
var LANGUAGE_REG = /^#*\s*([^\n,]+)(?=,)/;//
function shouldHaveHeading(a) {
var pass = false;
var lines = a.body_markdown.split("\n");
try {
pass |= /^#/.test(a.body_markdown);
pass |= ["-", "="]
.indexOf(lines[1][0]) > -1;
pass &= LANGUAGE_REG.test(a.body_markdown);
} catch (ex) {}
return pass;
}
function shouldHaveScore(a) {
var pass = false;
try {
pass |= SIZE_REG.test(a.body_markdown.split("\n")[0]);
} catch (ex) {}
if (!pass) console.log(a);
return pass;
}
function getAuthorName(a) {
return a.owner.display_name;
}
function getAuthorId(a) {
return a.owner.user_id;
}
function process() {
answers = answers.filter(shouldHaveScore)
.filter(shouldHaveHeading);
answers.sort(function (a, b) {
var aB = +(a.body_markdown.split("\n")[0].match(SIZE_REG) || [Infinity])[0],
bB = +(b.body_markdown.split("\n")[0].match(SIZE_REG) || [Infinity])[0];
return aB - bB
});
var users = {};
answers.forEach(function (a) {
var headline = a.body_markdown.split("\n")[0];
var question = QUESTION_IDs.indexOf(a.question_id);
var size = parseInt((headline.match(SIZE_REG)||[0])[0]);
var language = headline.match(LANGUAGE_REG)[1];
var user = getAuthorName(a);
var userId = getAuthorId(a);
if (!users[userId]) users[userId] = {name: user, nAnswer: 0, answers: []};
if (!users[userId].answers[question]) {
users[userId].answers[question] = {size: Infinity};
users[userId].nAnswer++;
}
if (users[userId].answers[question].size > size) {
users[userId].answers[question] = {size: size, link: a.share_link}
}
});
var sortedUsers = [];
for (var userId in users)
if (users.hasOwnProperty(userId)) {
var user = users[userId];
user.score = 0;
user.completedAll = true;
for (var i = 0; i < QUESTION_IDs.length; ++i) {
if (user.answers[i])
user.score += user.answers[i].size;
else
user.completedAll = false;
}
sortedUsers.push(user);
}
sortedUsers.sort(function (a, b) {
if (a.nAnswer > b.nAnswer) return -1;
if (b.nAnswer > a.nAnswer) return 1;
return a.score - b.score;
});
var place = 1;
for (var i = 0; i < sortedUsers.length; ++i) {
var user = sortedUsers[i];
var row = '<tr><td>'+ place++ +'.</td><td>'+user.name+'</td>';
for (var j = 0; j < QUESTION_IDs.length; ++j) {
var answer = user.answers[j];
if (answer)
row += '<td><a href="'+answer.link+'">'+answer.size+'</a></td>';
else
row += '<td class="missing"></td>';
}
row += '<td></td>';
if (user.completedAll)
row += '<td class="total">'+user.score+'</td>';
else
row += '<td class="total missing">'+user.score+'</td>';
row += '</tr>';
$("#users").append(row);
}
}
body { text-align: left !important}
#leaderboard {
width: 500px;
}
#answer-list {
padding: 10px;
width: 290px;
float: left;
}
#language-list {
padding: 10px;
width: 290px;
float: left;
}
table thead {
font-weight: bold;
}
table td {
padding: 5px;
}
td.total {
font-weight: bold;
text-align: right;
}
td.missing {
background: #bbbbbb;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="leaderboard">
<h2>Leaderboard</h2>
<p>
Missing scores are shown as grey cells. A grey total indicates that the user has not participated in all challenges and is not eligible for the overall victory yet.
</p>
<table class="_user-list">
<thead>
<tr><td></td><td>User</td>
<td><a href="https://codegolf.stackexchange.com/q/45302/8478">#1</a></td>
<td><a href="https://codegolf.stackexchange.com/q/45447/8478">#2</a></td>
<td><a href="https://codegolf.stackexchange.com/q/46991/8478">#3</a></td>
<td><a href="https://codegolf.stackexchange.com/q/49394/8478">#4</a></td>
<td><a href="https://codegolf.stackexchange.com/q/51222/8478">#5</a></td>
<td><a href="https://codegolf.stackexchange.com/q/66319/8478">#6</a></td>
<td><a href="https://codegolf.stackexchange.com/q/89621/8478">#7</a></td>
<td><a href="https://codegolf.stackexchange.com/q/120472/8478">#8</a></td>
<td></td><td>Total</td>
</tr>
</thead>
<tbody id="users">
</tbody>
</table>
</div>
<table style="display: none">
<tbody id="answer-template">
<tr><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
</tbody>
</table>
<table style="display: none">
<tbody id="language-template">
<tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
</tbody>
</table>
sortby(random)
(powodem ograniczenia czasowego) lub po prostu.shuffle()
(powodem ograniczenia wbudowanego), co moim zdaniem jest o wiele mniej sprytne niż konieczność implementacji Fisher-Yatesa lub innej podejście.shuffle(array)
zamiastnewArray=shuffle(array)
?Odpowiedzi:
Dyalog APL,
2524 bajtówPo pierwsze dla rozwiązania składającego się z 25 znaków:
i{⊃a[⍺⍵]←a[⍵⍺]}¨?i←⌽⍳⍴a←⎕
Po niektórych przekształceniach równoważności na powyższym:
możemy pozbyć się zadania
i←
i zapisać postać:{⊃a[⍺⍵]←a[⍵⍺]}¨∘?⍨⌽⍳⍴a←⎕
źródło
80386 kod maszynowy,
4424 bajtówHexdump kodu:
Dzięki FUZxxl, który zasugerował użycie
rdrand
instrukcji.Oto kod źródłowy (może zostać skompilowany przez Visual Studio):
Kolejna implementacja Fisher-Yates. Większość golfa została osiągnięta poprzez przekazanie parametrów do rejestrów.
źródło
rdrand
do gówna i chichotów.Java, 88
101Podstawowym tasowaniem jest Fisher-Yates. Mam wrażenie, że będzie tu używany dość często, ponieważ jest szybki i łatwy do wdrożenia. Jest tu trochę wkuwania pętli / zadań, ale tak naprawdę nie ma zbyt wiele do golfa; z natury jest krótki.
Z pewnymi podziałami linii:
To tasuje w miejscu, modyfikując oryginalną tablicę
s[]
. Program testowy:źródło
Math.random()
ma rozmiar, który jest potęgą dwóch, więc nie spełnia specyfikacji.Python 2, 86 bajtów
Jest to funkcja, która przetasowuje tablicę w miejscu bez zwracania jej, wykorzystując prostą implementację tasowania Fisher-Yates . Pobieranie losowych liczb z Pythona jest drogie ...
Dzięki @xnor i @colevk za wskazówki.
źródło
while i:i-=1;...
?while
zwykle krótsze niż wfor
przypadku takich rzeczy ...i=len(L)
i umieszczając zmniejszenie na początku pętli while.J,
4544 znakówTo było trudne.
Oto wyjaśnienie:
# y
: The tally ofy
, czyli liczba elementów wy
.?@# y
: Liczba losowa równomiernie rozmieszczona w zakresie od1
do(#y)-1
.x { y
: Pozycja zy
indeksux
.(<<<x) { y
: Wszystkie elementy oprócz pozycji o indeksiex
wy
.x , y
:y
dołączono dox
.x ({ , <^:3@[ { ]) y
: Pozycja w indeksiex
wy
, a następnie wszystkie inne pozycje.(?@# ({ , <^:3@[ { ]) ]) y
Losowo zy
, a następnie wszystkie inne przedmioty.x {. y
: Pierwszex
elementy zaczerpnięte zy
.x }. y
: Pierwszex
egzemplarze spadł zy
.x ({. , }.) y
: Pierwszex
elementy wzięte zy
, potem pierwszex
egzemplarze spadł zy
x ({. , (?@# ({ , <^:3@[ { ]) ])@}.) y
: Pierwszex
elementy wzięte zy
, a następnie pierwszex
elementyy
przetworzone jak w numerze 7.x ({. , ?@#@}. ({ , <^:3@[ { ]) }.) y
: To samo z kroplą wciągniętą, aby uratować jedną postać.u/ y
:u
wstawiony między pozycje zy
.< y
:y
zapakowane .<"0 y
: Każda pozycja wy
pudełku .i. y
: liczby całkowite od0
doy - 1
.i.@# y
: liczby całkowite od0
do(#y) - 1
.(<"0@i.@# , <) y
: Całkowite od0
do(#y) - 1
siebie ramkach , a następniey
w jednej obudowie. Jest to konieczne, ponieważ tablice w J są jednolite. Pudełko ukrywa kształt zawartości.x u&v y
: jak(v x) u (v y)
.> y
:y
otwarty , to znaczy bez pudełka.x ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&> y
fraza z liczby 12 zastosowana do jej nieopakowanych argumentów.({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/ y
zdanie z numeru 21 wstawione między pozycje zy
.({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/@(<"0@i.@# , <) y
zwrot z numeru 22 zastosowany do wyniku zdania z numeru 18 lub jednolita permutacja pozycji zy
.źródło
<@<@<@[
jest również tajemnicą ... Czekam na wyjaśnienia. :)from
({
) w pudełkach . I naprawdę podoba mi się&>/
sztuczka polegająca na manipulowaniu listą. Jestem pewien, że mogłem go użyć kilka razy wcześniej.Pyth, 25 bajtów
Sprawdź to tutaj.
Kolejna implementacja Fisher-Yates. Jest zasadniczo taki sam, jak @ Sp3000 rozwiązanie python, tylko w pyth.
Dzięki @Jakube za sztuczkę wymiany
źródło
Perl,
685644Podobnie jak wiele innych rozwiązań, wykorzystuje Fisher-Yates algorytm .
Za pomocą komentarza nutki zapisywanych jest 12 znaków przy użyciu
$_
zamiast$i
i wykonywania operacji na indeksach tablicowych.44:
56:
To jest mój pierwszy codegolf.
źródło
@_[...]
jako takiej wartości. Można zagrać w golfa dalejsub f{@_[$_,$j]=@_[$j=rand$_,--$_]for 1..@_}
.C,
636160 bajtówTylko prosta implementacja Fischera-Yatesa, która sortuje podaną tablicę na miejscu. Kompiluje i łączy się doskonale z kompilatorem Visual Studio (vs2013, nie testowałem innych wersji) i kompilatorem Intel. Ładnie wyglądająca sygnatura funkcji to
s(int array[], int length)
. Jestem pod wrażeniem, że pokonałem Pythona i Ruby.Zakłada się, że
srand()
jest wywoływany, a rand () jest poprawnie zaimplementowany, ale uważam, że ta reguła pozwala na to:Ładnie sformatowana wersja:
źródło
s(a,m)*a{
, ale nie jestem pewien i nie chcę też testować. Możesz zrobićxor
-swap, jak wa[i]^=a[m]^=a[i]^=a[m]
. Pozwala to również uniknąć konieczności deklarowaniat
.i==m
.s(a,m)int*a
studia wizualnego i kompilatora Intel. Nie instaluj gcc ani clang do testowania, ale zakładam, że będą również narzekać.t=a[i]
, możesz przenieśći=rand()%m--
instrukcję do wewnątrz jako indeks tablicy.Oktawa,
8877 bajtówYet another Fisher-Yates implementation... Should be fairly straightforward if I add the usual line returns and spacing:
The "end" keywords really kill the golf score here, unfortunately.Hey, I can use "end" instead of "endfor" and "endfunction"!źródło
numel
instead oflenght
. As a bonus your program would also work with 2-D arrays aka matrices ;)Java 8, 77
It's a lambda taking
int[]
and returning void. My first attempt seemed not very interesting, so I decided to have it exit by throwing an exception.Test program:
źródło
Math.random()
?Golflua, 37
How to run Golflua?
The input is provided as a table in the variable X. The table is shuffled in place.
Example usage:
źródło
R, 79 bytes
This is a straightforward implementation of the Fisher-Yates shuffle. The R function
sample
draws a simple random sample of a given size from a given vector with equal probability. Here we're drawing a random sample of size 1 at each iteration from the integersi
, ...,n
. As stated in the question, this can be assumed to be O(1), so in all this implementation should be O(N).źródło
Matlab, 67
Also implementing Fisher-Yates.
I thought it was too bad I could not use Matlab's
randperm
function. But after some fiddling around, I thought I may look at the source ofrandperm
to see how it is done, and I was astonished to see that there was just one line:[~,p] = sort(rand(1,n))
=)źródło
Perl, 44
Another perl in 44 characters. Example use:
źródło
Mathematica,
82 90 8393 bytesNote: This variation the Fisher-Yates shuffle is actually Martin Büttner's solution, with some code paring by alephalpha.
s
is the input array. Nothing fancy-smancy, but sometimes the simple things are the most elusive.źródło
Do
here. It's shorter thanWhile
.Ruby, 57 bytes
Input (as lambda function):
Output:
źródło
TI-BASIC, 46 bytes
Source for byte count
źródło
End
.K, 31 chars
Not quite as short as the one I put up before (which got disqualified)...oh well.
It's a basic Fisher-Yates shuffle. This was built with lots of help from the Kona mailing list.
źródło
JavaScript (ES6), 66
This function shuffles the array in place. It also returns a byproduct array that is NOT the shuffled output and must not be considered.
źródło
MATL, 16 bytes
Try it online!
Fisher-Yates in MATL. Almost a third of this program is devoted to the letter
H
, which corresponds to the clipboard function in MATL.Basically,
H
stores the unused items from the input, while the stack keeps track of the shuffled list.źródło
Japt, 12
Try it!
-10 (about half ;) thanks to @Shaggy!
I have been wanting to try out a golfing language, and the Japt interpreter had good documentation and a way to try things out in the browser.
Below is the strategy I took:
źródło
Javascript ES6, 69
It's Fisher–Yates.
PS: Can be tested in Firefox
źródło
Pyth, 27 bytes
Test it here
This is an implementation of the incremental Fisher-Yates shuffle, mentioned second here.
źródło
Haskell, 170
Another Fisher-Yates solution inspired by the algorithm at https://wiki.haskell.org/Random_shuffle.
s
is a function which has signature:IOArray Int a -> IO [a]
źródło
CJam - 30
Try it at http://cjam.aditsu.net/
Example input:
[10 20 30 40 50]
Example output:
3020401050
(add ap
at the end of the code for pretty printing)If the code is allowed to take the input from the stack (like a function), then the first 2 characters can be removed, reducing the size to 28.Explanation:
The code is longer than I hoped, due to the lack of a "swap" operator for arrays
(to be implemented later :p)
źródło
_
is O(N) (inside an O(N) loop). Unfortunately, I don't see a way to work around that in CJam.t
that kills it, as it can't mutate the list and now must create a copy.t
, I'd like to improve it in future versions..JavaScript (ES 6), 61
You can test it here by just adding a line that says
shuffle = S
(Firefox only).źródło
STATA, 161
Expects input as space separated numbers. I can remove the headers and observation numbers from the output if you would like, but otherwise this is shorter.
źródło
_n
in this?Java, 93 bytes
Example usage: http://ideone.com/RqSMnZ
źródło
SQF, 91 bytes
źródło
%x
with%i
.Perl, 41 bytes
Try it online!
źródło