Tentang Seri
Saya akan menjalankan serangkaian tantangan kode-golf berputar di sekitar tema keacakan. Ini pada dasarnya akan menjadi Lapangan Golf 9-Lubang , tetapi tersebar di beberapa pertanyaan. Anda dapat berpartisipasi dalam setiap tantangan secara individual seolah-olah itu adalah pertanyaan normal.
Namun, saya akan mempertahankan papan peringkat di semua tantangan. Serial ini akan membahas lebih dari 9 tantangan (untuk saat ini), satu diposting setiap beberapa hari. Setiap pengguna yang berpartisipasi dalam 9 tantangan memenuhi syarat untuk memenangkan seluruh seri. Skor keseluruhan mereka adalah jumlah dari kiriman terpendek mereka pada setiap tantangan (jadi jika Anda menjawab tantangan dua kali, hanya jawaban yang lebih baik yang dihitung untuk skor tersebut). Jika ada yang memegang posisi teratas di papan peringkat keseluruhan ini selama 28 hari, saya akan memberi mereka hadiah 500 rep .
Meskipun saya memiliki banyak ide untuk seri ini, tantangan di masa depan belum ditetapkan. Jika Anda memiliki saran, beri tahu saya di pos kotak pasir yang relevan .
Lubang 1: Kocok Array
Tugas pertama cukup sederhana: diberi array integer yang tidak kosong, kocok secara acak. Ada beberapa aturan:
- Setiap permutasi yang mungkin harus dikembalikan dengan probabilitas yang sama (sehingga shuffle harus memiliki distribusi yang seragam). Anda dapat memeriksa apakah algoritme Anda seragam / tidak memihak dengan mengimplementasikannya dalam JavaScript pada Will it Shuffle , yang akan menghasilkan matriks bias - hasilnya akan terlihat sama seragamnya dengan Fisher-Yates bawaannya atau urutkan (urutan acak) .
- Anda tidak boleh menggunakan metode bawaan atau pihak ketiga untuk mengocok array atau menghasilkan permutasi acak (atau menghitung semua permutasi). Secara khusus, satu-satunya fungsi acak bawaan yang dapat Anda gunakan adalah mendapatkan satu nomor acak sekaligus . Anda dapat mengasumsikan bahwa setiap metode bilangan acak bawaan berjalan di O (1) dan sangat seragam selama interval yang diminta (dalam pengertian matematika - Anda dapat mengabaikan detail representasi titik mengambang di sini). Jika bahasa Anda memungkinkan Anda memperoleh daftar angka acak m sekaligus, Anda dapat menggunakan fasilitas ini, asalkan angka-angka m independen satu sama lain, dan Anda menghitungnya sebagai O (m).
- Implementasi Anda tidak boleh melebihi kompleksitas waktu O (N) , di mana N adalah ukuran array yang akan dikocok. Misalnya, Anda tidak dapat "mengurutkan berdasarkan angka acak".
- Anda dapat mengocok array di tempat, atau membuat array baru (dalam hal ini array lama dapat diubah sesuka Anda).
Anda dapat menulis program atau fungsi lengkap dan mengambil input melalui STDIN, argumen baris perintah, argumen fungsi atau prompt dan menghasilkan output melalui nilai balik atau dengan mencetak ke STDOUT (atau alternatif terdekat). Jika Anda menulis fungsi yang mengocok array di tempatnya, Anda tidak perlu mengembalikannya tentu saja (asalkan bahasa Anda memungkinkan Anda mengakses array yang diubah setelah fungsi kembali).
Input dan output mungkin dalam format string atau daftar yang mudah digunakan, tetapi harus mendukung bilangan bulat sewenang-wenang dalam rentang -2 31 ≤ x <2 31 . Pada prinsipnya, kode Anda harus bekerja untuk array hingga panjang 2 31 , meskipun ini tidak harus sesuai dengan memori Anda atau selesai dalam jumlah waktu yang wajar. (Saya hanya tidak ingin melihat batas ukuran sewenang-wenang untuk loop hardcode atau sesuatu.)
Ini adalah kode golf, jadi pengiriman terpendek (dalam byte) menang.
Papan peringkat
Cuplikan berikut akan menghasilkan papan peringkat di semua tantangan seri.
Untuk memastikan jawaban Anda muncul, mulailah setiap jawaban dengan tajuk utama, menggunakan templat Penurunan harga berikut:
# Language Name, N bytes
di mana N
ukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Contohnya:
# Ruby, <s>104</s> <s>101</s> 96 bytes
(Bahasa saat ini tidak ditampilkan, tetapi cuplikan memang membutuhkan dan menguraikannya, dan saya dapat menambahkan leaderboard berdasarkan bahasa di masa mendatang.)
/* 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)
(alasan untuk pembatasan waktu) atau hanya.shuffle()
(alasan untuk pembatasan bawaan), yang saya pikir jauh lebih pintar daripada harus menerapkan Fisher-Yates atau yang lainnya pendekatan.shuffle(array)
bukannewArray=shuffle(array)
?Jawaban:
Dyalog APL,
2524 bytePertama untuk solusi 25 karakter:
i{⊃a[⍺⍵]←a[⍵⍺]}¨?i←⌽⍳⍴a←⎕
Setelah beberapa transformasi kesetaraan di atas:
kita dapat menyingkirkan tugas
i←
dan menyimpan karakter:{⊃a[⍺⍵]←a[⍵⍺]}¨∘?⍨⌽⍳⍴a←⎕
sumber
80386 kode mesin,
4424 byteHexdump kode:
Terima kasih kepada FUZxxl, yang menyarankan untuk menggunakan
rdrand
instruksi ini.Berikut adalah kode sumbernya (dapat dikompilasi oleh Visual Studio):
Namun implementasi Fisher-Yates yang lain. Sebagian besar golf dicapai dengan melewati parameter dalam register.
sumber
rdrand
untuk omong kosong dan cekikikan.Jawa, 88
101Acak Fisher-Yates dasar melakukan trik. Saya merasa itu akan digunakan cukup umum di sini, karena cepat dan mudah diimplementasikan. Ada beberapa loop / tugas yang menjejalkan di sini, tapi jujur tidak terlalu banyak bermain golf; itu hanya singkat secara alami.
Dengan beberapa jeda baris:
Ini mengocok di tempat, memodifikasi array asli
s[]
. Program uji:sumber
Math.random()
memiliki ukuran yang merupakan kekuatan dua, jadi ini tidak memenuhi spesifikasi.Python 2, 86 byte
Ini adalah fungsi yang mengocok array di tempatnya tanpa mengembalikannya, menggunakan implementasi langsung dari shuffle Fisher-Yates . Mendapatkan nomor acak dari Python mahal ...
Terima kasih kepada @xnor dan @colevk untuk kiatnya.
sumber
while i:i-=1;...
?while
cenderung lebih pendek daripadafor
untuk hal semacam ini ...i=len(L)
dan meletakkan decrement di awal while loop.J,
4544 karakterIni yang sulit.
Berikut ini penjelasannya:
# y
: The penghitungan dariy
, yaitu, jumlah elemen dalamy
.?@# y
: Nomor acak yang didistribusikan secara seragam dari rentang1
ke(#y)-1
.x { y
: Item dariy
at indexx
.(<<<x) { y
: Semua item kecuali item pada indeksx
dalamy
.x , y
:y
ditambahkan kex
.x ({ , <^:3@[ { ]) y
: Item di indexx
iny
, lalu semua item lainnya.(?@# ({ , <^:3@[ { ]) ]) y
Acak dariy
, lalu semua item lainnya.x {. y
: Pertamax
item yang diambil dariy
.x }. y
:x
Item pertama turun dariy
.x ({. , }.) y
: Pertamax
item diambil dariy
, maka yang pertamax
item turun dariy
x ({. , (?@# ({ , <^:3@[ { ]) ])@}.) y
: Pertamax
item diambil dariy
, maka yang pertamax
item dariy
olahan seperti pada nomor 7.x ({. , ?@#@}. ({ , <^:3@[ { ]) }.) y
: Hal yang sama dengan drop yang ditarik untuk menyelamatkan satu karakter.u/ y
:u
disisipkan di antara itemy
.< y
:y
kotak .<"0 y
: Setiap item dalamy
kotak .i. y
: integer dari0
key - 1
.i.@# y
: integer dari0
ke(#y) - 1
.(<"0@i.@# , <) y
: Integer dari0
ke(#y) - 1
setiap kotak dan kemudiany
dalam satu kotak. Ini diperlukan karena array dalam J adalah seragam. Sebuah kotak menyembunyikan bentuk isinya.x u&v y
: seperti(v x) u (v y)
.> y
:y
dibuka , yaitu, tanpa kotaknya.x ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&> y
frasa dari angka 12 diterapkan pada argumennya yang tidak dikotak.({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/ y
frasa dari nomor 21 disisipkan di antara item dariy
.({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/@(<"0@i.@# , <) y
frasa dari nomor 22 diterapkan pada hasil frasa dari nomor 18, atau, permutasi yang seragam dari itemy
.sumber
<@<@<@[
itu juga merupakan misteri ... Menunggu penjelasan. :)from
({
). Dan saya sangat suka&>/
trik untuk memanipulasi daftar. Saya yakin saya bisa menggunakannya beberapa kali sebelumnya.Pyth, 25 byte
Uji di sini.
Namun implementasi Fisher-Yates yang lain. Pada dasarnya sama dengan solusi python @ Sp3000, hanya di pyth.
Terima kasih kepada @Jakube untuk trik swapping
sumber
Perl,
685644Seperti banyak solusi lain, ini menggunakan algoritma Fisher-Yates .
Menggunakan komentar nutki , 12 karakter disimpan dengan menggunakan
$_
alih-alih$i
dan melakukan operasi dalam indeks array.44:
56:
Ini codegolf pertamaku.
sumber
@_[...]
sebagai nilai seperti itu. Dapat bermain golf lebih jauhsub f{@_[$_,$j]=@_[$j=rand$_,--$_]for 1..@_}
.C,
636160 byteHanya implementasi langsung dari Fischer-Yates yang mengurutkan array yang diberikan pada tempatnya. Mengkompilasi dan menghubungkan dengan sangat baik dengan kompiler studio visual (vs2013, belum menguji versi lain) dan Intel Compiler. Tanda tangan fungsi tampak bagus
s(int array[], int length)
. Saya terkesan secara sah dengan mengalahkan Python dan Ruby.Asumsi
srand()
ini dipanggil dan rand () diimplementasikan dengan benar, tetapi saya percaya aturan ini memungkinkan untuk itu:Versi yang diformat dengan baik:
sumber
s(a,m)*a{
, tapi saya tidak yakin dan tidak ingin menguji juga. Anda mungkin ingin melakukan-xor
swap, seperti dia[i]^=a[m]^=a[i]^=a[m]
. Ini juga menghindari keharusan untuk menyatakant
.i==m
.s(a,m)int*a
untuk studio visual dan kompiler intel. Tidak memiliki gcc atau dentang yang diinstal untuk menguji, tetapi saya menganggap mereka juga akan mengeluh.t=a[i]
, Anda kemudian dapat memindahkani=rand()%m--
pernyataan di dalam sebagai indeks array.Oktaf,
8877 byteNamun implementasi Fisher-Yates yang lain ... Harus cukup mudah jika saya menambahkan garis pengembalian dan spasi yang biasa:
Kata kunci "akhir" benar-benar membunuh skor golf di sini, sayangnya.Hai, saya bisa menggunakan "end" daripada "endfor" dan "endfunction"!sumber
numel
bukanlenght
. Sebagai bonus, program Anda juga akan bekerja dengan array 2-D alias matriks;)Java 8, 77
Ini adalah lambda mengambil
int[]
dan mengembalikan kekosongan. Upaya pertama saya sepertinya tidak terlalu menarik, jadi saya memutuskan untuk mengeluarkannya dengan melemparkan pengecualian.Program uji:
sumber
Math.random()
?Golflua, 37
Bagaimana cara menjalankan Golflua?
Input diberikan sebagai tabel dalam variabel X. Tabel diacak di tempatnya.
Contoh penggunaan:
sumber
R, 79 byte
Ini adalah implementasi langsung dari shuffle Fisher-Yates. Fungsi R
sample
menggambar sampel acak sederhana dengan ukuran tertentu dari vektor yang diberikan dengan probabilitas yang sama. Di sini kita menggambar sampel acak ukuran 1 pada setiap iterasi dari bilangan bulati
, ...,n
. Sebagaimana dinyatakan dalam pertanyaan, ini dapat dianggap sebagai O (1), jadi dalam semua implementasi ini harus O (N).sumber
Matlab, 67
Juga menerapkan Fisher-Yates.
Saya pikir itu terlalu buruk saya tidak bisa menggunakan
randperm
fungsi Matlab . Tetapi setelah beberapa mengutak-atik, saya pikir saya mungkin melihat sumberrandperm
untuk melihat bagaimana hal itu dilakukan, dan saya heran melihat bahwa hanya ada satu baris:[~,p] = sort(rand(1,n))
=)sumber
Perl, 44
Perl lainnya dalam 44 karakter. Contoh penggunaan:
sumber
Mathematica,
82 90 8393 byteCatatan: Variasi ini shuffle Fisher-Yates sebenarnya adalah solusi Martin Büttner, dengan beberapa kode pengurang oleh alephalpha.
s
adalah array input. Tidak ada yang mewah-smancy, tetapi terkadang hal-hal sederhana adalah yang paling sulit dipahami.sumber
Do
sini. Itu lebih pendek dariWhile
.Ruby, 57 byte
Input (sebagai fungsi lambda):
Keluaran:
sumber
TI-BASIC, 46 byte
Sumber untuk jumlah byte
sumber
End
.K, 31 karakter
Tidak sesingkat yang saya pasang sebelumnya (yang didiskualifikasi) ... oh well.
Ini adalah shuffle Fisher-Yates dasar. Ini dibangun dengan banyak bantuan dari milis Kona .
sumber
JavaScript (ES6), 66
Fungsi ini mengocok array di tempatnya. Ini juga mengembalikan array produk sampingan yang BUKAN output yang dikocok dan tidak harus dipertimbangkan.
sumber
MATL , 16 byte
Cobalah online!
Fisher-Yates dalam MATL. Hampir sepertiga dari program ini dikhususkan untuk surat itu
H
, yang sesuai dengan fungsi clipboard di MATL.Pada dasarnya,
H
simpan barang-barang yang tidak digunakan dari input, sementara tumpukan melacak daftar acak.sumber
Japt, 12
Cobalah!
-10 (sekitar setengah;) terima kasih kepada @Shaggy!
Saya ingin mencoba bahasa golf, dan penerjemah Japt memiliki dokumentasi yang baik dan cara untuk mencoba berbagai hal di browser.
Di bawah ini adalah strategi yang saya ambil:
sumber
Javascript ES6, 69
Ini Fisher – Yates.
PS: Dapat diuji di Firefox
sumber
Pyth, 27 byte
Uji di sini
Ini adalah implementasi dari shuffle Fisher-Yates tambahan, disebutkan kedua di sini .
sumber
Haskell, 170
Solusi Fisher-Yates lain yang terinspirasi oleh algoritma di https://wiki.haskell.org/Random_shuffle .
s
adalah fungsi yang memiliki tanda tangan:IOArray Int a -> IO [a]
sumber
CJam - 30
Cobalah di http://cjam.aditsu.net/
Input contoh:
[10 20 30 40 50]
Contoh output:
3020401050
(tambahkan ap
di akhir kode untuk pencetakan cantik)Jika kode diizinkan untuk mengambil input dari tumpukan (seperti fungsi), maka 2 karakter pertama dapat dihapus, mengurangi ukuran menjadi 28.Penjelasan:
Kode lebih panjang daripada yang saya harapkan, karena kurangnya operator "swap" untuk array
(akan diimplementasikan kemudian: p)
sumber
_
adalah O (N) (di dalam lingkaran O (N)). Sayangnya, saya tidak melihat cara untuk mengatasi itu di CJam.t
yang membunuhnya, karena tidak dapat mengubah daftar dan sekarang harus membuat salinan.t
, saya ingin memperbaikinya di versi mendatang ..JavaScript (ES 6), 61
Anda dapat mengujinya di sini hanya dengan menambahkan baris yang mengatakan
shuffle = S
(khusus Firefox).sumber
STATA, 161
Mengharapkan input sebagai angka yang dipisahkan ruang. Saya bisa menghapus header dan nomor observasi dari output jika Anda mau, tetapi jika tidak, ini lebih pendek.
sumber
_n
ini?Java, 93 byte
Contoh penggunaan: http://ideone.com/RqSMnZ
sumber
SQF, 91 byte
sumber
%x
dengan%i
.Perl, 41 byte
Cobalah online!
sumber