Dropsort , dirancang oleh David Morgan-Mar, adalah contoh dari "algoritma pengurutan" waktu-linear yang menghasilkan daftar yang, pada kenyataannya, diurutkan, tetapi hanya berisi beberapa elemen asli. Elemen apa pun yang tidak paling tidak sebesar maksimum elemen sebelumnya hanya dihapus dari daftar dan dibuang.
Dalam tugas ini, Anda akan diberikan daftar bilangan bulat sebagai input (STDIN atau argumen fungsi, Anda harus mendukung setidaknya kisaran bilangan bulat bertanda 8-bit.) Tugas Anda adalah untuk menjatuhkan mereka dan kemudian menampilkan elemen yang tersisa di memesan.
Anda dapat menganggap bahwa daftar ini tidak kosong.
Ini kode golf, jadi program tersingkat menang.
Uji Kasus
Input Output
1 2 5 4 3 7 1 2 5 7
10 -1 12 10 12
-7 -8 -5 0 -1 1 -7 -5 0 1
9 8 7 6 5 9
10 13 17 21 10 13 17 21
10 10 10 9 10 10 10 10 10
Papan peringkat
var QUESTION_ID=61808,OVERRIDE_USER=39022;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<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="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><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>
code-golf
array-manipulation
sorting
SuperJedi224
sumber
sumber
highest < current
? Atauhighest <= current
?highest (so far)<=current
.Jawaban:
APL, 9 byte
Ini adalah kereta fungsi monadik dengan diagram:
Versi non-kereta adalah
Ini pada dasarnya memeriksa apakah setiap elemen sama dengan berjalan maksimum.
Perhatikan bahwa solusi J Martin Büttner sama panjangnya dengan ini dan diposting pertama kali.
sumber
J,
109 byteVersi kerja dari ide CJam saya (dalam lebih sedikit byte). Misalnya:
Penjelasan
Pertama, kami mendapatkan maksimum setiap awalan, dengan:
(Di sini,
>.
adalah operator maksimum,/
melipat operator itu ke daftar, dan\
mendapatkan semua awalan input.)Lalu kami membandingkan daftar awal dengan yang maksimum untuk persamaan:
Dan akhirnya, kami memilih semua elemen tempat daftar hasil boolean ini memberi
1
:sumber
Haskell, 28
Fungsi anonim. Sebut saja seperti
Setara dengan rekursi
Diterjemahkan secara iteratif, kami beralih pada elemen-elemen, dan untuk setiap elemen yang kami lihat, kami menghapus yang lebih kecil dari sisa daftar yang kami iterasi. Terima kasih kepada Antisthenes untuk byte yang disimpan bersama
(x<)
.sumber
foldr(\x->(x:).filter(>=x))[]
, itu ternyata sama panjangnya.x:
memaksa Anda untuk menambahkan operator titik. Oh well ...O(n^2)
sekalipun. banyak perbandingan yang tidak dibutuhkan. ;-(Python 2, 49
sumber
max(a)
JavaScript (ES6), 29
Menyalahgunakan konversi tipe standar dalam javascript, array ke nomor:
sumber
Oktaf,
2719 bytesumber
Pyth, 12 byte
Verifikasi semua kasus uji sekaligus.
Bagaimana itu bekerja
sumber
Brachylog , 5 byte
Cobalah online!
Jelly , 5 byte
Cobalah online!
Penjelasan
Ini adalah situasi yang langka: saya bisa menggunakan algoritma yang (sejauh yang saya tahu dengan skim cepat) tidak ada yang menggunakan sejauh ini, dan entah bagaimana berakhir dengan panjang yang sama dalam dua bahasa golf yang sangat berbeda dengan sintaks yang sangat berbeda dan set builtin, dengan korespondensi 1-ke-1 antara program (perintahnya bahkan dalam urutan yang sama!). Jadi sepertinya lebih masuk akal untuk menggabungkan mereka - dengan cara, ini adalah program yang sama, dan saya menulisnya dalam kedua bahasa untuk melihat mana yang lebih pendek - daripada mengirimkannya secara terpisah.
Ide dasar di sini adalah bahwa tetes daftar adalah urutannya dengan pembalikan maksimum secara leksikografis. Anehnya, baik Brachylog maupun Jelly tidak memiliki builtin untuk menemukan maksimum dengan fungsi tertentu (Jelly memiliki builtin untuk mengembalikan semua maxima dengan fungsi tertentu, tetapi itu akan mengembalikan daftar tunggal yang berisi hasil daripada hasil itu sendiri, dan juga bahkan tidak lebih pendek daripada melakukannya dengan cara ini). Jadi sebagai gantinya, kami menghasilkan semua kemungkinan berikutnya, urutkan secara terbalik, ambil yang terakhir.
Alasan mengapa "reverse maksimum lexicographically maksimum" bekerja adalah bahwa output yang dipilih harus diakhiri (sehingga kebalikannya harus dimulai) dengan angka tertinggi dalam daftar input (mudah untuk melihat bahwa output dropsort akan selalu berakhir dengan itu), dan dengan demikian dapat tidak mengandung apapun setelah itu (karena mengambil urutan menjaga ketertiban). Ulangi secara induktif dan kita berakhir dengan definisi dropsort.
sumber
Mathematica, 26 Bytes
sumber
DeleteDuplicates
sepertinya tidak akan kembali{10, 10, 10, 10}
untuk input{10, 10, 10, 9, 10}
DeleteDuplicates
dengan dua argumen tampaknya menjadi filter sederhana.R,
2926 byteIni menciptakan objek fungsi yang menerima vektor
x
dan kembalix
setelah menghapus semua elemen tidak setidaknya sebesar maksimum kumulatifx
.Disimpan 3 byte berkat flodel!
sumber
K, 11 byte
Dalam aksi:
sumber
{x@&~<':x}
byte lebih pendek.3 4 2 2 5
.{x@&~<':x}/
, tapi itu panjangnya sama.Java, 82 byte
Inilah loop output sederhana. Itu hanya membuat maks
m
dan membandingkan setiap elemen.sumber
a->{int m=a[0]...
Perl, 33 byte
32 byte kode +
-p
Jika spasi tambahan dapat diterima dalam output, bisa 31 byte dengan menghapus
dan
?
. Menerima string (atau jumlah baris baru yang dipisahkan) melaluiSTDIN
:sumber
Python 3, 67
Kekuatan yang cukup kasar. Mengubahnya menjadi fungsi, karena saya melewatkan jawaban yang valid.
Versi tidak disatukan:
sumber
Haskell,
3837 byteDisimpan 1 byte berkat JArkinstall .
sumber
$
untuk dikurangi satu byte penuh!f(x:y:s)|x>y=f$x:s|1>0=x:f(y:s);f s=s
(Semi-colon digunakan karena komentar tidak mengizinkan baris baru)C # -
6864 atau132127 KarakterWhere
dalam hal ini adalah iterasi melalui daftar, dan untuk setiap elemenv
pada indeksi
dalam daftar, mengevaluasi ekspresi boolean. Jika ekspresi bernilai true, maka item ditambahkan ke hasilnya. Satu-satunya trik nyata untuk ekspresi boolean adalah bahwa sirkuit pendek C # atau evaluasi segera setelah kondisi bernilai true. Ini mencegahIndexOutOfRangeException
pengecualian, dan menyimpan elemen pertama dalam daftar.Jika input dan output harus berupa string (saya tidak tahu pasti, jadi saya akan menyerahkannya kepada OP dan Anda semua untuk memutuskan.)
Dekompresi yang sedikit memberi:
Dalam hal ini baris kedua dari fungsi menggunakan logika yang sama persis seperti di atas. The
Select
diperebutkan unsur-unsur daftar dan mengkonversi mereka keint
. Panggilan keToList
1 memaksa pilih untuk dievaluasi, dan mengubahvar
menjadiList<int>
pada waktu kompilasi, sehinggaWhere
beroperasi pada kumpulan bilangan bulat.Cobalah di C # Pad
Terima kasih kepada VisualMelon untuk membantu memangkas masing-masing 4 byte dan 5 byte. :)
1 daftar tutu?
sumber
int[]f(int[]b)
baik-baik saja, dan Anda dapat menggunakani<1
daripadai==0
mempersingkat yang memeriksa sedikit. Untuk versi string, Anda juga dapat meletakkan tanda kurung di sekitar argumen-tunggal dalam lambda (misalnya(d)=>int.Parse(d)
bisad=>int.Parse(d)
. Saya juga hanya menghitung 67 byte, bukan 68, dalam orignal Anda;)CJam, 15 byte
Cobalah online di juru bahasa CJam .
Bagaimana itu bekerja
sumber
PowerShell , 32 byte
Cobalah online!
Kurang bermain golf:
sumber
C: 73 byte
atau
C: 49 byte
(Jika header bea cukai dibuat untuk kompetisi codegolf diizinkan)
Masih tidak bisa mengalahkan CJam, tetapi setidaknya ini memungkinkan untuk mengalahkan beberapa bahasa lainnya.
sumber
Burlesque, 13 byte
Solusi 11 byte yang lolos uji kasus:
Coba online di sini .
Penjelasan:
Namun, versi ini hanya berfungsi dengan menggunakan fakta, bahwa tidak ada dua angka yang lebih kecil di antara dua angka. Kalau tidak, gunakan versi di bawah ini (yaitu 13B):
Versi yang lebih lama:
Coba online di sini. Penjelasan:
Jika Anda juga akan menurunkan angka yang sama, Anda bisa menggunakan
.>
alih-alih menggunakancm
. Juga, jika daftar hanya berisi angka positif yang dapat Anda gunakan0
atau-1
bukanJ-]
.sumber
Minkolang 0,9 , 18 byte
Coba di sini.
Penjelasan
sumber
Ruby,
4137 karakterContoh dijalankan:
sumber
-[p]
lebih pendek dari.compact
NARS2000 APL, 13 byte
NARS2000 adalah juru bahasa APL gratis untuk Windows; itu termasuk fitur multiset yang diakses oleh
⍦
operator.Ini adalah garpu monadik yang mengambil persimpangan multiset (
⍦∩
) dari input (+
) * dan daftar maksimum berjalan (⌈\
).Karena
⍦
bukan karakter APL standar dalam pengkodean APL APLIKASI satu byte, kita harus menggunakan UTF-8,⍦∩⌈
masing-masing membuat karakter tiga byte. Saya memilih+
bukannya⊢
menyimpan dua byte.NARS2000 mendukung garpu, yang dapat dibangun menjadi kereta tanpa tanda kurung, tetapi tidak seperti Dyalog, ia tidak mengizinkan penugasan ke suatu fungsi tanpa membungkus fungsi dalam tanda kurung.
*
+
adalah konjugat yang kompleks secara teknis, tetapi inputnya nyata.sumber
> <> dengan flag -v,
3631 + 2 = 33 byteMasukkan daftar pada tumpukan dengan -v sehingga elemen pertama dari daftar berada di bagian atas tumpukan. Ini akan mencetak daftar yang diurungkan dengan ruang tambahan.
Uji coba:
Sunting: disimpan 5 byte berkat Fongoid
sumber
:&\o" "&n:~& <
dan baris 2 sebagai~ >l?!;:&:&(?!^
Python,
1029994 +56 baris baru non-file-final =107105100 byte(Saya menggunakan tab untuk indentasi)
Bukan yang terbaik di luar sana, tapi ini adalah kesempatan pertama saya bermain golf kode. Tidak dapat menemukan cara untuk mengurutkan daftar secara inline tanpa mengalami bug yang berhubungan dengan penghapusan, jadi saya memindahkan elemen yang dipesan ke daftar sementara.
EDIT: list.append () lebih pendek daripada melakukannya dengan cara yang jelek
r + = [i] lebih pendek dari list.append (); terima kasih njzk2 !
sumber
Scala:
232126120 bytesumber
List[Int]
tidak memenuhi persyaratan, Anda harus mendapatkan input melalui STDIN atau sebagai argumen. Plus, itu membengkak jawaban Anda ... Mengapa tidak begitu sajadef dropSort(s:Seq[Int]):Seq[Int]
?Scala, 54 byte
Tidak Disatukan:
sumber
Tiny Lisp, 107 byte
( Bahasa ini hanya diterbitkan setelah pertanyaan ini, jadi jawaban ini berjalan keluar dari kompetisi. Bukan berarti itu punya kesempatan untuk menang. The bahasa kemudian berkembang lebih lanjut untuk memiliki lebih buildins dari yang saya digunakan di sini, tapi aku tinggal dengan versi awalnya saya terapkan pada tahun 2015. Jawaban ini masih bekerja dengan penerjemah resmi yang lebih baru , meskipun memberikan beberapa peringatan karena saya mendefinisikan parameter
a
yang membayangi buildin barua
(untuk menambahkan). Terima kasih kepada DLosc untuk tautan TIO. )(d r(q((m a)(i a(i(l(h a)m)(r m(t a))(c(h a)(r(h a)(t a))))()))))(d ds(q((b)(i b(c(h b)(r(h b)(t b)))()))))
Ini mendefinisikan fungsi
ds
(dan fungsi pembantu rekursifnyar
) yang mengurutkan argumennya, yang harus berupa daftar bilangan bulat.r
bukan fungsi ekor-rekursif, jadi untuk daftar yang sangat panjang ini mungkin mengalami stack overflow.Tidak Disatukan:
Berikut adalah beberapa contoh cara menggunakan ini (dengan kasus uji dari pertanyaan):
(Ya,
-7
bukan bilangan bulat integer, jadi kita harus mendefinisikan fungsi untuk mewakili mereka.) Output:sumber
r
, saya kira ..)ds
? Saya kira ini bisa dilakukan, akan menghemat byte lain. Saya kira saya memilihds
sebagai singkatan untuk drop sort.(d ds
dan mencocokkan)
pada akhirnya. Golf lain dimungkinkan jika Anda ingin menggunakan juru bahasa saya saat ini , tetapi jika Anda ingin tetap menggunakan spesifikasi dalam pertanyaan awal, itu juga tidak masalah. :)Jelly, 5 byte
Perhatikan bahwa tantangan mendahului pembuatan Jelly.
Cobalah online!
Bagaimana itu bekerja
sumber
Mathematica, 27 byte
sumber