The Strort Unsorting Machine untuk Tujuan Jahat

18

Pegolf malam yang baik!

Tantangan Anda adalah sepenuhnya membatalkan serangkaian angka.

Memasukkan

Tepatnya 100 bilangan bulat akan diumpankan ke program Anda. Program Anda dapat menerima input baik sebagai file, atau melalui stdin. Setiap integer akan dipisahkan oleh karakter baris baru.

Ke-100 bilangan bulat itu akan berkisar dari nilai minimal hingga maksimal dari bilangan bulat yang ditandatangani dalam bahasa pilihan Anda.

Tidak akan ada nilai duplikat. Nilai-nilai dapat dipesan, tidak disusun atau dipesan sebagian - program Anda harus dapat menangani setiap kasus.

Keluaran

Output harus masing-masing dari 100 bilangan bulat, benar-benar tidak disortir, masing-masing dipisahkan oleh karakter baris baru. Outputnya bisa melalui stdout, atau ke file.

Benar-benar Tidak Disortir berarti bahwa tidak ada nilai yang bersebelahan dengan nilai apa pun yang akan berdekatan jika daftar itu sepenuhnya diurutkan dalam urutan yang diurutkan.

Skor

1 poin per karakter, dan skor terendah menang. Ada bonus -100 untuk solusi apa pun tanpa menggunakan fungsi sortir bawaan atau pustaka. Ada bonus -20 untuk solusi apa pun yang menggunakan fungsi angka acak bawaan.

Saya telah mencoba mendefinisikan pertanyaan ini selengkap mungkin. Jika Anda memiliki pertanyaan, silakan tanyakan. Jika Anda memiliki komentar tentang bagaimana saya dapat melakukan yang lebih baik lain kali, beri tahu saya.

Depan!

lochok
sumber
Tepatnya ada 100 input integer, dan tidak ada nilai duplikat (lihat di bawah "Input")
lochok
Benar kamu, tidak menemukan itu.
Strigoides
2
Ini bukan duplikat seperti itu, tetapi tidak jauh berbeda dengan codegolf.stackexchange.com/questions/6487/…
Peter Taylor
Begitu banyak respons yang cerdas! Saya akan memilih jawaban terpendek pada 31 Oktober pukul 8: 10-Zulu
lochok

Jawaban:

9

GolfScript (skor 27 - 120 = -93)

~].,{{.2$<{\}*}*]}*.(;+2%n*

Catatan: itu $mereferensikan elemen pada stack. Ada penyortiran, tetapi dilakukan dengan semacam gelembung yang dikodekan secara manual.

Terima kasih kepada Howard, untuk -90 => -92; dan Ilmari, yang menginspirasi -92 => -93.

Peter Taylor
sumber
Terima kasih atas jawaban singkat seperti itu, tetapi (maafkan saya, karena saya tidak berbicara atau mengerti GolfScript) - bukankah ^ akan mendiskualifikasi dari bonus -100?
lochok
1
@lochok, fungsi sort bawaan adalah $- itu sebabnya saya sebutkan $di dalam program tidak macam (tergantung konteks). Mayoritas program (28 dari 42 karakter) mendefinisikan fungsi ^; versi pertama, menggunakan bawaan, hanya 14 karakter.
Peter Taylor
Ahh - benar. Terimakasih atas klarifikasinya!
lochok
1
Anda dapat menyimpan dua karakter dengan loop output sebagai berikut: 2/{~p}%n*.
Howard
1
2/zip~+n*dan .);\+2%n*juga melakukan trik untuk jumlah karakter yang sama dengan versi @ Howard. Sayangnya, saya belum berhasil menemukan sesuatu yang lebih pendek.
Ilmari Karonen
6

Python -26

(94-120): Baru, pendekatan kasar. Terus popping elemen terendah ke daftar baru untuk mendapatkan elemen diurutkan, lalu iterate:

t=l=[]
i=N=100
exec't=t+[input()];'*N+'l+=[t.pop(t.index(min(t)))];'*N+'print l[i%N];i+=3;'*N

Python -13

(107-120): Pendekatan pertama: Menghapus empat elemen terendah sekaligus, lalu cetak empat elemen ini dalam urutan lain:

exec'l=[]'+'+[input()]'*100
while l:
 a,b,c,d=eval('l.pop(l.index(min(l))),'*4)
 for e in[b,d,a,c]:print e
daniero
sumber
t=l=[]dan exec't+=[input()];'*100akan menyelamatkan Anda beberapa karakter
quasimodo
Anda juga dapat menggunakan satu execpernyataan untuk lebih dari satu putaran.
quasimodo
@quasimodo Saya mencoba sesuatu seperti itu, tetapi dengan t=l=[]t dan l menunjuk ke objek yang sama dan tidak berhasil. Melewatkan tanda kurung execitu bagus.
daniero
Anda bisa menggunakan t=t+[input()];, ini menciptakan objek baru setiap kali. Dan Anda bahkan dapat melakukan loop cetak dalam pernyataan exec: ';i+=1;print l[i*3%100]'*100.
quasimodo
Kamu benar lagi. Terima kasih! Juga menambahkan beberapa golf lainnya seperti menghapus %3dan menghindari pengulangan 100.
daniero
4

C: 11 (131 - 120)

Program membaca dari stdin dan melakukan semacam sisipan sederhana, setelah itu mencetak n bersama-sama dengan nomor n + 50, seperti banyak solusi lainnya.

main(){int*i,a[101],*j=a;while(scanf("%d",a)>0)for(i=++j;i-->a;)i[1]=*i>=*a?*i:*(i=a);while(a<(i=j-50))printf("%d\n%d\n",*i,*j--);}
quasimodo
sumber
3

Mathematica -56 44 4 (95-120) = -25

Edit :

Versi ini tidak bergantung pada fungsi bawaan untuk menyortir daftar, atau fungsi pengacakan.

Riffle[RotateLeft[#[[All, 2]], 2], #[[All, 1]]] &
[Partition[l //. {x___, a_, b_, y___} /; b < a :> {x, b, a, y}, 2]]
DavidC
sumber
Bukankah Sortfungsi sortir bawaan?
Peter Taylor
Anda benar! Saya melewatkan kendala tentang semacam.
DavidC
Saya membuat Sort linting tangan.
DavidC
3

J, -63 (57-120) karakter

Karena semua orang akan melalui rute semacam yang ditulis sendiri ...

,50(}.,.{.)($:@([-.m),~m=.]#~]=<./)^:(0<#),".[;._2[1!:1[3

Tidak menggunakan fungsi angka acak, atau jenis bawaan apa pun.

Menggunakan semacam seleksi rekursif sederhana untuk mengurutkan input.

Gareth
sumber
3

Ruby 1.9, -59

(61-120)

Pengulangan! Yang ini sebenarnya, tidak seperti upaya Ruby saya sebelumnya, batalkan daftar tanpa mempedulikan urutan aslinya.

p *(f=->l{l[1]&&f[l-m=l.minmax]+m||[]})[$<.map &:to_i].rotate

Upaya sebelumnya

Cute one-liner, sekarang menggunakan sortir bawaan untuk bekerja dengan baik:

$<.map(&:to_i).sort.each_slice(4){|a,b,c,d|p b,d,a,c}

Pertama - Tidak perlu membatalkan 4 nilai terakhir:

l=$<.map &:to_i
48.times{l-=p *l.minmax}
a,b,c,d=l
p b,d,a,c
daniero
sumber
1
Solusi -72 Anda mengasumsikan daftar mulai disortir, yang tidak terjadi.
histokrat
Ups. Sepertinya saya tidak membaca kembali pertanyaan dengan seksama ketika saya mengunjungi kembali pertanyaan ini. Akan mencoba memunculkan sesuatu yang lain.
daniero
@ histokrat yang seharusnya melakukannya.
daniero
1

Python 2: 90 char

n=100
s=sorted(int(raw_input())for i in range(n))
for i in range(n):print s[(4*i+4*i/n)%n]

upaya malas tetapi hanya untuk pemula

mil
sumber
1

Python 48 = (148 - 100)

from random import*
x=[input()for i in range(100)]
while any(abs(x[i]-x[i+1])>1 for i in range(99)):n=randint(1,99);x=x[n:]+x[:n]
for j in x:print j

Belum menguji ini karena tidak dijamin (atau mungkin) berjalan dalam jumlah waktu yang wajar, tetapi harus bekerja secara teori dengan waktu yang tak terbatas.

scleaver
sumber
1
x=map(input,['']*100)
ugoren
Dan saya pikir Anda bahkan tidak perlu tambahan [], hanya string karakter apa pun.
pekerjaan
1

Python 27 (147 - 100 - 20)

R=range
def S(L):
 for i in R(len(L)-1):
    if L[i]>L[i+1]:L[i:i+2]=[L[i+1],L[i]];S(L)
a=map(input,['']*100);S(a)
for i in R(100):print a[i/2+i%2*50]

Catatan: spasi sebelum if L[i]>...harus tab tetapi tampaknya muncul sebagai spasi di blok kode.

Mat
sumber
Dengan R=rangeAnda dapat menyimpan 5 karakter.
scleaver
a=map(input,['']*100)
ugoren
1

Perl 5: 95 - 120 = -25 karakter

Menghitung baris perintah berikut:

perl -ne '$n=$_;splice@n,(grep{$n[$_]>$n}0..@n),0,$n}{print for map{@n[$_,$#n/2+$_+1]}0..$#n/2'
Matthias
sumber
1

Ruby: -50 (70 karakter - 120)

Saya melakukan hal yang sama seperti banyak jawaban lain: menghapus secara maksimal maks dan min dari daftar input dan menambahkannya ke output. Namun, saya menyadari bahwa jika 2 angka di kedua sisi median itu berurutan, outputnya akan salah (karena 2 angka berurutan itu akan muncul bersamaan di akhir output). Untuk memperbaiki ini, saya memutar daftar "tidak disortir" tepat oleh 1 elemen:

n=$*.map &:to_i;u=[];50.times{u+=n.minmax;n-=u.last 2};p *u.rotate(-1)

Atau, untuk bekerja dengan banyak input sembarang (hanya menggunakan 4 karakter lagi):

n=$*.map &:to_i;u=[];(u+=n.minmax;n-=u.last 2)while n.any?;p *u.rotate(-1)

Catatan: Beberapa jawaban Ruby yang lebih sedikit telah diposkan, tetapi solusi itu tidak mengatasi masalah median (dan / atau mengasumsikan daftar input yang diurutkan).

Jonathan Hefner
sumber
1

J 37 - 100 = -63

({~?~@#)^:(+./@(1=|)@(2&(-/\))@/:)^:_

Tidak menggunakan penyortiran (meskipun menggunakan peringkat ke atas) Menggunakan angka acak.

Penjelasan:

({~?~@#)             NB. Randomizes the array
^: foobar ^:_        NB. as long as
foo =: +./@(1 = |)   NB. as any 1 == absolute value of
bar =: (2&(-/\))@/:  NB. differences between adjacent ranks
foobar =: foo@bar
jpjacobs
sumber
1

Brachylog , 22 byte - 120 = -98

ṇịᵐpX¬{p≤₁s₂.&s₂p}∧Xẉᵐ

Cobalah online!

TIO link hanya memiliki input delapan bilangan bulat, bukan seratus, karena ini sangat lambat sehingga tidak dapat menangani lagi dalam 60 detik. Alasan untuk ini adalah bahwa, antara lain, daripada menerapkan beberapa algoritma penyortiran sederhana tapi normal untuk bonus wajib, saya demi singkatnya menggunakan jumlah yang setara dengan bogosort deterministik: p≤₁backtracks melalui setiap permutasi input sampai menemukan satu yang tidak menurun. Walaupun alasan yang lebih besar mungkin adalah bahwa ia menggunakan tingkat yang sama dari brute force untuk menemukan output, dan bahwa itu menghitung ulang versi yang diurutkan setiap kali ... Saya berusaha mengujinya pada input aktual ukuran 100, tapi saya tidak yakin berapa hari lagi.

Versi keseluruhan yang lebih baik:

Brachylog , 14 byte - 20 = -6

p.¬{os₂.&s₂p}∧

Cobalah online!

Ini mengabaikan persyaratan I / O kuno untuk singkatnya, dan lalai untuk mengambil bonus -100 sehingga mungkin dapat diuji tanpa superkomputer (meskipun saat menulis ini, saya sudah menjalankannya hanya pada 20 item selama beberapa menit dan itu masih belum memberi saya apa-apa).

 .                The output is
p                 a permutation of
                  the input
  ¬{        }∧    such that it cannot be proven that
         s₂       a pair of adjacent values in
        &         the output
       .   p      is a permutation of
     s₂           a pair of adjacent values in
    o             the output sorted.
String yang tidak terkait
sumber
Meskipun ini bukan jawaban yang praktis, itu bisa berguna untuk memvalidasi output dari program lain, karena sebagian besar hanya menggambarkan kendala yang ditempatkan pada output.
String Tidak Terkait
0

Keempat (gforth) , 79 - 120 = -21 byte

: f 100 0 do dup i 2 mod 4 * 2 - i + i 99 = i 0 = - 3 * + cells + @ . cr loop ;

Cobalah online!

Abaikan persyaratan input kuno dan ambil input sebagai alamat di memori tempat nomor disimpan.

Penjelasan

Loop melalui semua angka dari 0 hingga 99. Untuk setiap angka (n):

  • Jika n adalah 0:
    • output nilai pada alamat array + 1
  • Lain jika n adalah 99:
    • output nilai pada alamat array + 98
  • Lain jika n ganjil:
    • output nilai pada alamat array + (n + 2)
  • Lain (n adalah genap):

    • output nilai pada alamat array + (n - 2)
  • Keluarkan baris baru

Penjelasan Kode

: f               \ start new word definition
  100 0 do        \ loop from 0 to 99
    dup           \ duplicate the array address
    i             \ place the loop index on the stack
    2 mod 4 * 2 - \ convert to 2 if it's odd and -2 if it's even
    i +           \ add the result to the the loop index
    i 99 =        \ if i = 99 place -1 on top of the stack, else place a 0
    i 0 =         \ i i = 0 place -1 on top of the stack, else place 0
    - 3 *         \ subtract previous two results from each other and multiply by 3
\ the above line is used to avoid writing if/then by instead using math to get 98 and 1
    +             \ add result to existing result from above
    cells         \ multiply by the size of a single integer in memory
    +             \ add to the array's starting address
    @ . cr        \ get the value at the calculated address, print it, then print a newline
  loop            \ end the loop
;                 \ end the word definition
reffu
sumber