Sortir dasar, dengan bug yang mengganggu

28

Input Anda adalah daftar / urutan / vektor / array 5-255 bilangan bulat positif, tidak harus unik. Anda dapat mengasumsikan format input apa pun yang paling cocok, dan bahwa setiap bilangan bulat (serta jumlah bilangan bulat) dipilih secara acak secara acak dari kisaran 5-255.

Tujuannya adalah untuk menampilkan daftar yang sama, dalam format yang sama (atau setara), tetapi diurutkan ke dalam urutan peningkatan (tidak menurun). Latihan awal yang umum dalam mempelajari bahasa. Pengajuan untuk mencakup:

  1. Sebuah jawaban yang bekerja dengan benar dan mencapai tujuan; dan

  2. Jawaban kedua yang berisi bug yang mengganggu. Antara 1% dan 10% dari waktu, output harus berupa daftar dalam format yang benar dan mengandung elemen yang benar, tetapi dalam urutan yang salah (urutan apa pun kecuali disortir dengan benar). Sisa waktu, program harus bekerja dengan benar dan mencapai tujuan.

Kedua jawaban harus memiliki Levenshtein jarak satu; yaitu, kita dapat memperoleh satu dari yang lain dengan menghapus satu byte, atau menambahkan satu byte, atau mengubah satu byte.

Mencetak seperti biasa dalam kode-golf (berdasarkan pada jawaban yang lebih pendek dari dua jawaban Anda), dengan celah-celah yang biasa dilarang.

Bonus 10% (turun menjadi skor) jika bug yang mengganggu adalah independen-input, yaitu menggunakan input yang sama lagi tidak mereproduksi bug (kecuali antara 1% dan 10% dari waktu).

code-golf array-manipulation random integer Vadim Ponomarenko
sumber
9
Selamat datang di PPCG! Saya sarankan menghapus bonus, itu bukan latihan yang bagus.
Tn. Xcoder
2
Tidak jelas berapa probabilitas dari setiap panjang input yang mungkin.
user202729
12
Haruskah spesifikasi antara 1% dan 10% dari waktu terpenuhi untuk setiap input atau hanya keseluruhan untuk set input yang mungkin? Untuk beberapa input sepertinya [5,5,5]tidak mungkin menghasilkan urutan yang salah
Luis Mendo
4
Ada kehalusan tentang format IO standar kami . Jika kode kita mendefinisikan suatu fungsi, apakah boleh jika memiliki peluang untuk mendefinisikan fungsi secara konsisten buggy, sebagai lawan dari mendefinisikan fungsi yang memiliki kemungkinan buggy?
xnor
1
@VadimPonomarenko Di situs ini, orang-orang diizinkan untuk menyediakan fungsi serta program lengkap. xnor bertanya apakah diizinkan untuk memiliki fungsi yang, 1% hingga 10% dari waktu dibuat, adalah fungsi kereta yang akan selalu memiliki bug. Menjaga surat pertanyaan Anda jawabannya mungkin tidak , tetapi akan lebih menyenangkan jika ya .
wizzwizz4

Jawaban:

9

Python 3 , 36 byte

Versi bebas bug, 37 byte

lambda l:sorted(l,reverse=l[-9:]==[])

Cobalah online!

Versi yang menjengkelkan, 36 byte

lambda l:sorted(l,reverse=l[9:]==[])

Cobalah online!

Ini tergantung pada input dan karenanya tidak memenuhi syarat untuk bonus.
Ini memiliki probabilitas sekitar 2% untuk gagal. Gagal saat panjang input lebih rendah dari 10.

Dikombinasikan dengan jawaban LyricLy, ini menghasilkan 34 byte:

lambda l:sorted(l)[::l[9:]>[]or 1]
lambda l:sorted(l)[::l[9:]>[]or-1]
ovs
sumber
Saya tidak berpikir Anda membutuhkan ruang dalam versi bebas bug.
wizzwizz4
@ wizzwizz4 tanpa spasi or1akan ditafsirkan sebagai nama variabel dan memunculkan kesalahan sintaksis.
Ovs
9

05AB1E , 5 * 0,9 = 4,5 byte

Solusi kerja

{TLΩi

Cobalah online!

Penjelasan

{      # sort input
 TL    # push the range [1 ... 10]
   Ω   # pick a random number in the range
    i  # if true (equal to 1), do nothing

Solusi yang mengandung bug

Memberikan solusi yang salah 10% dari waktu (tidak bergantung pada input).

{TLΩiR

Cobalah online!

Penjelasan

Sama seperti solusi yang berfungsi, kecuali itu membalikkan daftar jika nomor yang diambil benar.

Emigna
sumber
Serius apa hei. Keluaran bahkan bukan kardinalitas yang tepat.
Joshua
@ Yosua Apa maksudmu?
Erik the Outgolfer
Cobalah secara online menunjukkan itu mengeluarkan daftar daftar.
Joshua
4
@ Yosua Tautan TiO menyertakan tajuk 100Fdan catatan kaki },yang membantu kami memvisualisasikan hasil fungsi yang dipanggil pada input beberapa kali. Ini menunjukkan kepada kita bahwa solusi yang bekerja selalu mengembalikan hasil yang benar, sementara yang disadap memiliki cacat keluaran.
Tn. Xcoder
Tolong, seseorang, jelaskan algoritmanya. Segera saya akan menerima pengajuan peringkat teratas (atau salah satu kiriman peringkat teratas). Saya tidak dapat menerima solusi yang tidak dapat saya mengerti.
Vadim Ponomarenko
7

Jelly , 7 * (100% - 10%) = 6,3 byte

Ṣ¹⁵X:¤¡

Cobalah online!

Versi kereta:

ṢẊ⁵X:¤¡

Cobalah online!

Di kedua tautan, ada test harness yang akan menjalankan kode 100 kali, setiap kali dengan daftar yang Anda berikan sebagai argumen, dan kemudian mengembalikan hasilnya.

Probabilitas setiap panjang input adalah:

0.1 - 0.1/(length!)

Jadi untuk panjang 1 ada probabilitas 0%, untuk panjang 2 5%, untuk panjang 3 8,83̅%, untuk panjang 4 9,583̅% dll hingga panjang ∞ yang memiliki probabilitas 10%.

Erik the Outgolfer
sumber
Seharusnya 0.1 - 0.1/(length!).
user202729
@ user202729 yakin
Erik the Outgolfer
Ṣ⁵X’¤¡dan Ṣ⁵X¤¡harus bekerja juga: versi kereta mengembalikan daftar yang tidak disortir <10% dari waktu, dan mengingat bahwa input dipilih secara acak acak, itu harus bekerja, simpan 2 byte.
user202729
Jika Anda tidak menyukai solusi itu, Anda dapat menghapus hanya ¹untuk menyimpan 1 byte (jumlah aturan hitungan byte = yang lebih pendek); juga ada overline menggabungkan asing setelah yang kedua 6di 6.6̅%.
user202729
@ user202729 Sayangnya itu tidak akan menjadi input-independen lagi, dan tidak, saya tidak bisa "hanya menghapus ¹" karena kemudian tidak akan mengurutkan sama sekali 10% dari waktu.
Erik the Outgolfer
6

Python 3, skor 58 57 - 10% = 51,3

Menyimpan satu byte berkat ovs.

Versi bebas bug, 57 byte

lambda m:sorted(m)[::random()>.1or 1]
from random import*

Cobalah online!

Versi disadap, 57 byte

lambda m:sorted(m)[::random()>.1or-1]
from random import*

Cobalah online!

Saya memutuskan untuk mencoba solusi yang menggunakan bonus. Itu tidak mengalahkan jawaban Python lainnya, tapi saya senang memikirkannya.

Lirik
sumber
5

C, 71 * 0,9 = 63,9 byte

Bebas serangga:

c(int*a,int*b){return*a-*b;}f(a,n)int*a;{if(rand()%1<9)qsort(a,n,4,c);}

Cobalah online!

Buggy:

c(int*a,int*b){return*a-*b;}f(a,n)int*a;{if(rand()%10<9)qsort(a,n,4,c);}

Cobalah online!

Steadybox
sumber
+1 untuk% 1 (oh, ayolah 6 lagi, Anda pasti bercanda)
Joshua
4

Groovy , 31 byte

Solusi yang disadap:

{a->a.sort()[a[9]?0..-1:-1..0]}

Solusi kerja:

{a->a.sort()[a[0]?0..-1:-1..0]}

Operator subskrip Groovy ( getAtmetode) mengembalikan null untuk daftar jika indeks lebih besar dari ukuran. Jadi jika ada elemen kesembilan ia akan tetap sama dengan daftar yang diurutkan, tetapi jika tidak (peluang 1,99203187%) itu akan terbalik. Namun akan selalu ada elemen pertama karena ukuran daftar selalu lebih besar dari atau sama dengan 5. Jadi 0 in a[0]bisa ditukar dengan 1, 2, 3 atau 4.

Hlaaftana
sumber
1
Selamat datang di situs dan posting pertama yang bagus!
caird coinheringaahing
3

Bahasa Wolfram (Mathematica) , 29 byte

Ini adalah 26,1 byte dengan bonus, tetapi saya tidak sepenuhnya yakin saya mendapatkan bonus; pada input yang sudah diurutkan, kedua versi selalu menghasilkan output yang diurutkan.

Versi bebas bug (29 byte)

If[RandomReal[]<0.,#,Sort@#]&

Cobalah online!

Versi yang mengganggu (30 byte)

If[RandomReal[]<0.1,#,Sort@#]&

Cobalah online!

Misha Lavrov
sumber
3

PHP, 70 byte

Versi bebas bug, 70 byte

<?unset($argv[0]);((rand(1,9)?"":r).sort)($argv);echo join(" ",$argv);

Cobalah online!

Versi disadap, 70 byte

<?unset($argv[0]);((rand(0,9)?"":r).sort)($argv);echo join(" ",$argv);

Cobalah online!

Versi yang disadap mengurutkan dalam urutan terbalik 10% dari waktu (berdasarkan generator nomor acak).

Jo.
sumber
tidak perlu untuk tag dengan -r(-2 byte). bergabung dengan garis bawah; itu harus setara (-2 byte). gunakan asortalih-alih sort(-1 byte).
Titus
... atau gunakan seluruh kata sebagai ganti awalan (atau tidak): unset($argv[0]);(rand(1,9)?sort:rsort)($argv);echo join(_,$argv);(juga 65 byte)
Titus
3

Python 2 , 26 byte

Buggy:

lambda l:l[9:]and l.sort()

Cobalah online!

Keluaran dengan memodifikasi daftar input . Urutkan daftar hanya jika panjangnya setidaknya 10. Versi non-kereta menggantikan 9dengan 0untuk selalu mengurutkan.

Kerja:

lambda l:l[0:]and l.sort()

Cobalah online!

Kita dapat memodifikasi fungsi untuk mengembalikan daftar dengan biaya 4 byte, untuk total 30 byte:

lambda l:l[9:]and l.sort()or l

Cobalah online!

25 byte dengan beberapa aturan:

[list,sorted][id(0)%17>0]

Cobalah online!

Keluaran fungsi literal yang baik mengurutkan atau identitas, menggunakan id(0)sebagai sumber acak. Ubah >ke >=untuk memperbaiki, atau 0ke ~0.

Tidak
sumber
3

Sekam , 6 byte

Versi kereta:

?OIV¦9

Cobalah online!

Versi yang benar:

?OIVK9

Cobalah online!

Penjelasan

Program-program ini sepenuhnya deterministik. Faktanya, Husk saat ini tidak memiliki dukungan sama sekali untuk angka acak.

?  V    If any element
    ¦9  is divisible by 9 (in buggy version),
    K9  is truthy when replaced by 9 (in correct version),
 O      sort the list,
  I     otherwise return it unchanged.

Saya mengklaim bahwa output dari program kereta tidak diurutkan dengan probabilitas antara 1% dan 2%. Diterangkan dengan N = 251 jumlah nilai elemen yang mungkin. Probabilitas bahwa daftar acak panjang L tidak mengandung kelipatan 9 adalah ((NK) / N) ^ L , di mana K adalah jumlah nilai yang dapat dibagi dengan 9 (dalam kasus kami K = 28 ). Probabilitas total adalah rata-rata untuk 5 ≤ L ≤ 255 , yaitu sekitar 1,98%. Beberapa dari daftar ini adalah positif palsu, karena sudah disortir. Probabilitas daftar acak panjang L yang akan diurutkan paling banyak ((N + N * (N-1) / 2) / N ^ 2) ^ ⌊L / 2⌋ : jika kita memecah daftar menjadi potongan-potongan panjang 2, masing-masingPotongan ⌊L / 2⌋ harus disortir. Probabilitas total daftar yang diurutkan dibatasi oleh rata-rata di atas untuk 5 ≤ L ≤ 255 , yaitu sekitar 0,30%. Dengan demikian probabilitas fungsi mengembalikan daftar yang tidak disortir adalah antara 1,67% dan 1,98%.

Zgarb
sumber
habis dibagi 9 memberi kira-kira 11% kemungkinan kegagalan. dan tidak menyortir tidak menjamin bahwa daftar tidak disortir.
Titus
1
@Itus saya membahas ini dalam analisis. Kegagalan untuk mengurutkan hanya terjadi jika daftar tidak mengandung elemen yang dapat dibagi dengan 9. Kemungkinan ini adalah sekitar 1,98%. Dan memang benar jika daftar sudah diurutkan, tidak melakukan apa-apa juga akan memberikan daftar diurutkan. Namun, probabilitas daftar yang sudah diurutkan paling banyak 0,30%, yang cukup rendah sehingga probabilitas total menghasilkan daftar yang tidak disortir di atas 1%.
Zgarb
true ... dan input yang diurutkan tidak mengubah bug.
Titus
Bisakah Anda menggunakan ↓9alih-alih V¦9, dan mempersingkatnya hanya 9untuk versi yang benar? Ini akan membuatnya selalu gagal pada input pendek dan selalu bekerja dengan benar pada input yang lebih panjang, tetapi karena panjang input mengikuti distribusi acak, itu masih harus menjadi jawaban yang valid
Leo
3

Bash , 26 byte

Versi yang benar

s=n
sort -${s:RANDOM%20<0}

Cobalah online! atau periksa probabilitasnya .

Versi disadap

s=n
sort -${s:RANDOM%20<1}

Cobalah online! atau periksa probabilitasnya .

Mengambil input sebagai angka yang dipisahkan oleh baris baru. Menggunakan variabel bawaan RANDOM, yang selalu mengembalikan nomor acak (semu) di kisaran 0 - 32767 . Menggunakan %20hasil dalam tingkat kegagalan sekitar 5% (terima kasih @Titus untuk mengklarifikasi masalah dengan %10).

Keacakan ini berarti tingkat kegagalan tidak tergantung pada input, tetapi ini mengharuskan array input mencakup setidaknya satu angka dengan lebih dari satu digit, karena output kegagalan diurutkan secara leksikografis.

Versi alternatif, 27 byte

((RANDOM+20))||cat&&sort -n

Versi bugged menggantikan +dengan a %. Cobalah online atau coba disadap .

Justin Mariner
sumber
penny picking: %10memiliki peluang lebih tinggi untuk kembali 0ke 7daripada 8atau 9, sehingga kemungkinan gagal di atas 10%;)
Titus
@Itus Terima kasih, saya lupa tentang fakta itu. Diperbarui untuk digunakan %20seperti jawaban Anda.
Justin Mariner
3

Pyth , skor 8 * 0,9 = 7.2

Cuplikan pertama (yang benar):

h.uSNT.S

Coba di sini!

Cuplikan kedua (disadap):

O.uSNT.S

Coba di sini!

Disimpan dua byte (dan skor 1,8) berkat isaacg !

Tuan Xcoder
sumber
Saya pikir 9 daripada 10 salinan baru akan baik-baik saja. Kemungkinan untuk .Smengembalikan input tidak berubah berarti bahwa dalam kasus (jarang) itu, peluang kami untuk mendapatkan jawaban yang salah turun dari 10% menjadi 0% - jadi rata-rata, masih dalam kisaran yang tepat. Tentu saja, 10 salinan juga baik-baik saja.
Misha Lavrov
@MishaLavrov Saya telah membuat kesalahan dalam penjelasan saya, sekarang diatasi. Saya katakan .Smungkin juga mengembalikan input itu sendiri (yang tidak akan menjadi masalah), tapi maksud saya .Smungkin juga mengembalikan daftar yang diurutkan .
Tn. Xcoder
Benar, itulah yang saya maksudkan juga.
Misha Lavrov
Gagasan yang sama, tetapi lebih pendek:O.uSNT.S
isaacg
2

JavaScript (ES6), 24 byte

Versi bebas bug (setidaknya untuk bilangan bulat dalam kisaran 0-2147483647, jadi apa pun dalam kisaran yang diberikan):

a=>a.sort((a,b)=>a-b>>0)

Versi kereta:

a=>a.sort((a,b)=>a-b>>1)

Bergantung pada a) algoritma pengurutan mesin dan b) daftar input yang berisi dua nilai dalam urutan yang salah yang berbeda dengan 1. (Jika probabilitas itu ternyata terlalu rendah maka 1dapat ditingkatkan, tetapi pada saat Anda mendapatkan untuk 8itu tidak akan mengurutkan apa pun dalam kisaran 5-255.)

Neil
sumber
2

PHP, 62 byte

terinspirasi oleh solusi Jo (dan saya baru memperhatikan: ini pelabuhan Justin Mariner ):

bekerja (macam naik):

unset($argv[0]);(r[rand()+20].sort)($argv);echo join(_,$argv);

buggy (kesempatan sekitar 5% untuk menurun):

unset($argv[0]);(r[rand()%20].sort)($argv);echo join(_,$argv);

Jalankan dengan -nr

Titus
sumber
2

Pushy , 9 byte - 10% = 8.1

Solusi yang Disadap:

g0TUn?};_

Cobalah online!

Solusi kerja:

g1TUn?};_

Cobalah online!

Kode yang disadap melakukan hal berikut:

g0TUn?};_

g          \ Sort the stack correctly
 0TU       \ Generate random(0, 10)
    n? ;   \ If this is zero:
      }    \    Cyclically shift the stack right once
        _  \ Print the result

Kode tetap hanya berubah 0menjadi 1. Seperti random(1, 10)tidak akan pernah terjadi 0, pernyataan if tidak akan pernah dieksekusi.

FlipTack
sumber
2

MATL , 7 * 0,9 = 6,3 6 * 0,9 = 5,4 byte

Versi kereta:

Gr.9<?S

Cobalah online!

Penjelasan:

G        % Grab input
 r       % Push a random number between 0 and 1
  .9     % Push 0.9
    <    % Check if the random number is smaller than 0.9
     ?   % If true
      S  % Sort input
         % Implicit output

Versi bebas bug:

Gr9<?S

Cobalah online!

Penjelasan:

G       % Grab input
 r      % Push a random number between 0 and 1
  9     % Push 9
   <    % Check if the random number is smaller than 9 (always true)
    ?   % If true
     S  % Sort the input
        % Implicit output
Stewie Griffin
sumber
1

Jq 1,5 , 42 byte

Buggy

sort|if length%13<=0then reverse else. end

Bekerja (hapus =)

sort|if length%13<0then reverse else. end

Asumsikan panjang garis seragam dalam kisaran [5.255] sekitar 7% akan memicu bug

Cobalah online!

jq170727
sumber
1

J, 22,5 byte (25 byte - 10%)

dengan bug:

[:]`(1&A.)@.(0.1>?@0:)/:~

tanpa bug:

[:]`(0&A.)@.(0.1>?@0:)/:~

Cobalah online!

Jonah
sumber
1

R , 30 * .9 = 27 byte

(kereta)

function(l)sort(l,runif(1)<.1)

Cobalah online!

(tidak buggy)

function(l)sort(l,runif(1)<.0)

Versi kereta jenis decreasing=T10% dari waktu, pengambilan sampel dari distribusi seragam (0,1). Versi un-buggy selaludecreasing=F

Giuseppe
sumber
1

Rosda , 42 byte - 10% = 37,8

Bebas serangga:

{sort key={|i|currentTime|[_%20//19*0+i]}}

Buggy:

{sort key={|i|currentTime|[_%20//19*i+i]}}

Cobalah online!

Ini menggunakan currentTimefungsi untuk membuat angka acak. Tampaknya distribusi mereka sedikit berbeda antar mesin. Rasio 20//19dapat disesuaikan untuk mendapatkan hasil yang berbeda tanpa penalti byte (kecuali lebih kecil dari 99//98).

fergusq
sumber
1

Oktaf , 36 * 0,9 = 32,4 byte

Versi kereta:

@(x)sort(x)(shift(1:end,+(rand<.1)))

Cobalah online!

Versi bebas bug:

@(x)sort(x)(shift(1:end,+(rand<.0)))

Cobalah online!

Ini memilah vektor, lalu menggeser semua angka satu ke kanan jika angka acak kurang dari 0,1.

Stewie Griffin
sumber
Ya, Anda tentu saja benar :) Terima kasih :)
Stewie Griffin
1

Java 8, 45 34,2 ( 50 38 - 10%) byte

Versi normal:

a->{if(Math.random()>0.)a.sort(null);}

Penjelasan:

Coba di sini.

a->{                    // Method with ArrayList<Integer> parameter and no return-type
  if(Math.random()>0.)  //  If the random 0-1 double is larger than 0:
    a.sort(null);       //   Sort the input-List
}                       // End of method

Versi disadap ( 51 39 byte):

a->{if(Math.random()>0.1)a.sort(null);}

LD dari 1: 1ditambahkan.

Penjelasan:

Coba di sini.

a->{                     // Method with ArrayList<Integer> parameter and no return-type
  if(Math.random()>0.1)  //  If the random 0-1 double is larger than 0.1:
    a.sort(null);        //   Sort the input-List
}                        // End of method
Kevin Cruijssen
sumber
0

JavaScript, 25 * 0.9 = 22.5

new Date%25?x:x.sort()

input x

l4m2
sumber