Terapkan "Sort Lazy"

44

Saya seharusnya mengurutkan daftar angka, tapi saya sangat malas. Sangat sulit untuk mencari cara menukar semua angka di sekitar sampai semuanya dalam urutan meningkat, jadi saya datang dengan algoritma saya sendiri yang akan menjamin bahwa daftar baru diurutkan¹. Begini cara kerjanya:

Untuk daftar ukuran N , kita perlu iterasi N-1 . Pada setiap iterasi,

  • Periksa apakah nomor ke- N lebih kecil dari nomor ke-1. Jika ya, maka kedua angka ini sudah diurutkan, dan kita dapat melewati iterasi ini.

  • Jika tidak, maka Anda harus terus mengurangi angka N pertama hingga kedua angka ini berurutan.

Mari kita ambil contoh konkret. Katakanlah input tadi

10 5 7 6 1

Pada iterasi pertama, kami akan membandingkan 10 dan 5. 10 lebih besar dari 5, jadi kami menurunkannya hingga lebih kecil:

4 5 7 6 1

Sekarang kita membandingkan 5 dan 7. 5 lebih kecil dari 7, jadi kita tidak perlu melakukan apa pun pada iterasi ini. Jadi kita pergi ke yang berikutnya dan membandingkan 7 dan 6. 7 lebih besar dari 6, jadi kami mengurangi tiga angka pertama sampai lebih kecil dari 6, dan kami mendapatkan ini:

2 3 5 6 1

Sekarang kita membandingkan 6 dan 1. Sekali lagi, 6 lebih besar dari 1, jadi kita mengurangi empat angka pertama sampai lebih kecil dari 1, dan kita mendapatkan ini:

-4 -3 -1 0 1

Dan kita selesai! Sekarang daftar kami dalam urutan sempurna. Dan, untuk membuat segalanya lebih baik, kami hanya perlu mengulangi daftar N-1 kali, jadi algoritma ini mengurutkan daftar dalam waktu O (N-1) , yang saya cukup yakin adalah algoritma tercepat yang ada.²

Tantangan Anda untuk hari ini adalah mengimplementasikan Sort Malas ini. Program atau fungsi Anda akan diberi array bilangan bulat dalam format standar apa pun yang Anda suka, dan Anda harus melakukan sortir malas ini dan mengembalikan daftar " sortir " yang baru . Array tidak akan pernah kosong atau mengandung non-integer.

Berikut ini beberapa contohnya:

Input: 10 5 7 6 1
Output: -4 -3 -1 0 1

Input: 3 2 1
Output: -1 0 1

Input: 1 2 3
Output: 1 2 3

Input: 19
Output: 19

Input: 1 1 1 1 1 1 1 1 1 
Output: -7 -6 -5 -4 -3 -2 -1 0 1 

Input: 5 7 11 6 16 2 9 16 6 16
Output: -27 -25 -21 -20 -10 -9 -2 5 6 16

Input: -8 17 9 7
Output: -20 5 6 7

Seperti biasa, ini , jadi tulislah program sesingkat mungkin!


¹ Ini tidak berarti seperti apa artinya, tetapi secara teknis itu benar

² Saya benar-benar bercanda, tolong jangan benci saya

DJMcMayhem
sumber
6
Saya pikir Anda tidak malas jika Anda melakukannya dengan cara ini
Jörg Hülsermann
4
@ JörgHülsermann juga beberapa bilangan bulat terlalu berat ... tidak dalam mood untuk membawa berat seperti itu, lebih baik melepas hanya hal-hal terbaik
Erik the Outgolfer
21
<sarcasm>Algoritma pengurutan ini sebenarnya masih O(N^2)memiliki kompleksitas waktu karena Anda harus memeriksa semua item yang sebelumnya diakses pada daftar untuk mengurangi mereka. Saya sarankan menelusuri daftar mundur sebagai gantinya dan mengurangi hanya satu nomor per langkah yang diperlukan. Ini akan memberi Anda O(N)kompleksitas sejati ! </sarcasm>
Value Ink
1
@ ValueInk O(n^2)dalam hal akses memori, tetapi bukankah itu O(n)untuk perbandingan?
Cole Johnson
7
@ColeJohnson secara teknis ya, tetapi kompleksitas waktu perlu mempertimbangkan semua langkah dari algoritma. Anda masih harus mengulangi semua indeks sebelumnya pada setiap iterasi, sehingga masih keluar O(N^2).
Value Ink

Jawaban:

12

Jelly ,  14 12 11  9 byte

-2 byte berkat ETHproductions (gunakan angka minimum, «)

I’«0Ṛ+\Ṛ+

Tautan monadik yang mengambil dan mengembalikan daftar bilangan bulat.

Cobalah online! atau lihat test suite .

Saya benar-benar tidak berpikir ini cukup Malas ™!

Bagaimana?

I’«0Ṛ+\Ṛ+ - Link: list of integers, a              e.g. [ 8, 3, 3, 4, 6, 2]
I         - increments between consecutive items of a   [-5, 0, 1, 2,-4 ]
 ’        - decrement (vectorises)                      [-6,-1, 0, 1,-5 ]
   0      - literal 0
  «       - minimum of decremented increments and zero  [-6,-1, 0, 0,-5 ]
    Ṛ     - reverse                                     [-5, 0, 0,-1,-6 ]
      \   - cumulative reduce with:
     +    -   addition                                  [-5,-5,-5,-6,-12]
       Ṛ  - reverse                                     [-12,-6,-5,-5,-5]
        + - addition (with a)                           [-4,-3,-2,-1, 1, 2]
Jonathan Allan
sumber
12

Haskell , 40 byte

f(a:r)|h:t<-f r=h-max(r!!0-a)1:h:t
f x=x

Cobalah online!

Tidak
sumber
11
Bahasa malas sepertinya cocok untuk tantangan ini
mulai
8

JavaScript (ES6), 61 byte

a=>a.map((b,i)=>a=(b-=a[i+1])>0?a.map(c=>i--<0?c:c-b-1):a)&&a

Uji kasus

Arnauld
sumber
7

Jelly , 12 byte

I»1U
0ị;Ç_\U

Cobalah online!

Bagaimana itu bekerja

I»1U  Helper link. Argument: l (list of integers)
I     Compute the increments (difference between items) of l.
 »1   For each item n, take the maximum of n and 1.
   U  Reverse.

0ị;Ç_\U  Main link. Argument: l (list of integers)
   Ç     Call the helper link with argument l.
  ;      Concatenate this with
0ị       the 0th last item of the (1-indexed) l. (Can't use Ṫ because it modifies l)
    _\   Cumulatively reduce the result by subtraction.
      U  Reverse.

Ide dasar yang dimainkan adalah ini: Jika Anda membalikkan array input dan output, output hanyalah input dengan setiap delta 0 atau lebih besar diganti dengan -1. Sebagai contoh:

[10,  5,  7,  6,  1]   input
[ 1,  6,  7,  5, 10]   reverse
[   5,  1, -2,  5  ]   deltas
[  -1, -1, -2, -1  ]   min(deltas, -1)
[ 1, -1, -2, -1, -1]   reverse and concat the last item of the original
[ 1,  0, -2, -3, -4]   re-apply deltas
[-4, -3, -2,  0,  1]   reverse
Produksi ETH
sumber
5

k, 20 byte

{x-|+\0,1_0|1+-':|x}

Cobalah online.

Penjelasan:

{                  } /function, x is input
                 |x  /reverse x
              -':    /difference between every element
            1+       /add one to each difference
          0|         /make minimum difference be 0
      0,1_           /swap first difference with a 0
    +\               /cumulative sum
   |                 /reverse again
 x-                  /subtract from x
zgrep
sumber
4

Haskell, 56 byte

a#(x:y:z)=map(+min(y-x-1)0)(a++[x])#(y:z)
a#x=a++x
([]#)

Cobalah online!

Simpan bagian pertama dari daftar di parameter a. Pada setiap langkah, tambahkan elemen berikutnya xke akhir adan tingkatkan semua elemen dengan minimum (y-x-1)dan 0.

nimi
sumber
4

Python , 54 byte

f=lambda a,*r:r and[f(*r)[0]-max(r[0]-a,1)]+f(*r)or[a]

Cobalah online!

Mengambil input seperti splatted f(1,2,3). Menghasilkan daftar. Menggunakan waktu eksponensial.

Tidak
sumber
3

C #, 76 byte

a=>{for(int d=0,i=a.Length-1;i>0;a[--i]-=d)d=a[i-1]-d<a[i]?d:a[i-1]-a[i]+1;}

Ini mengubah daftar di tempat. Itu berjalan melalui daftar mundur dan menjaga total berjalan delta untuk diterapkan ke setiap nomor.

Makanan Tangan
sumber
2

JavaScript (ES6), 59 byte

f=([n,...a],p=a[0]-n)=>a+a?[(a=f(a))[0]-(p>1?p:1),...a]:[n]
Produksi ETH
sumber
Wow. Saya hendak menulis solusi JS, tetapi kemudian saya melihat ini. Saya tidak berpikir untuk menggunakan operator spread seperti itu di parameter
andrewarchi
Anda dapat berhenti f=untuk jawaban JS untuk menyimpan dua byte
andrewarchi
@andrewarchi Terima kasih, tetapi fungsi khusus ini perlu memanggil dirinya sendiri ( f(a)) sehingga masih membutuhkan nama.
ETHproduk
Saya lupa itu rekursif
andrewarchi
2

Brain-Flak , 153 byte

{(({})<>[({})])(({}({}))[({}[{}])])<>(([{}]({})))([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}{{}({}<>{}())((<>))}{}{}}{}<>{}([]){{}({}<>)<>([])}<>

Cobalah online!

Ini termasuk +1untuk -rbendera.

#While True
{

    #Push the last value left in the array minus the counter onto the alternate stack
    (({})<>[({})])

    #Put the counter back on top of the alternate stack
    (({}({}))[({}[{}])])

    #Toggle
    <>

    #Find the difference between the last two inputs left on the array
    (([{}]({})))

    #Greater than or equal to 0?
    ([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

    #If So:
    {

      #Pop the truthy/falsy value
      {}

      #Increment the counter by the difference between elements +1
      ({}<>{}())

      #Push two falsys
      ((<>))

    #Endwhile
    }

    #Pop the two falsys
    {}{}

#Endwhile
}

#Pop the falsy

{}

#Toggle back
<>

#Pop the counter

#Reverse the stack
{}
([]){{}({}<>)<>([])}<>
DJMcMayhem
sumber
2

R, 56 byte

function(s){s-c(rev(cumsum(rev(pmax(0,-diff(s)+1)))),0)}

aPaULT
sumber
1
penggunaan yang bagus diff, saya mencoba mencari cara untuk mendapatkan itu bekerja ... Ngomong-ngomong, Anda dapat menyingkirkan kawat gigi di sekitar fungsi tubuh untuk -2 byte, tetapi lebih baik lagi, Anda dapat menggunakan s=scan()alih-alih fungsi definisi untuk menyimpan beberapa byte lagi. Akan lebih bagus jika Anda menyertakan tautan ke Coba online sehingga orang lain dapat memverifikasi bahwa kode ini berfungsi untuk semua kasus uji.
Giuseppe
Jangan khawatir! kita semua mulai di suatu tempat :)
Giuseppe
1

JavaScript (ES6), 68 byte

a=>a.map((v,i)=>(d=v-o[i+1]+1)>1?o=o.map((v,j)=>j>i?v:v-d):0,o=a)&&o

Input dan output adalah array bilangan bulat.

Cuplikan Tes

f=
a=>a.map((v,i)=>(d=v-o[i+1]+1)>1?o=o.map((v,j)=>j>i?v:v-d):0,o=a)&&o
<input id=I oninput="O.value=f(this.value.split` `.map(x=>+x)).join` `">
<input id=O disabled>

Justin Mariner
sumber
1

JavaScript (ES6), 50 byte

f=a=>(b=[...a]).some((_,i)=>a[i]-->=a[i+1])?f(a):b

Penjelasan:

Ini adalah solusi rekursif, yang pertama mengkloning array, kemudian menurunkan semua nilai hingga elemen lebih besar atau sama dengan elemen berikutnya dalam array.

Fungsi ini memanggil dirinya sendiri selama elemen-elemennya rusak. Ketika elemen akhirnya diurutkan, klon dikembalikan. (Kami tidak dapat mengembalikan array itu sendiri, karena some()metode ini akan mengurangi semua elemennya, membuat semuanya menjadi -1.)

Kasus uji:

f=a=>(b=[...a]).some((_,i)=>a[i]-->=a[i+1])?f(a):b

console.log(f([10,5,7,6,1])+'');
console.log(f([1,1,1,1,1,1,1,1,1])+'');
console.log(f([5,7,11,6,16,2,9,16,6,16])+'');
console.log(f([19])+'');
console.log(f([-8,17,9,7])+'');
console.log(f([1,2,3,4,5,6,7])+'');

Rick Hitchcock
sumber
1

SWI-Prolog, 194 byte

:-use_module(library(clpfd)).
f([],[],_,_).
f([A|B],[M|N],P,D):-A#=M-D-E,A#<P,abs(M,S),T#=S+1,E in 0..T,label([E]),f(B,N,A,D+E).
l([],[]).
l(A,B):-reverse(Z,B),f([X|Y],Z,X+1,0),reverse(A,[X|Y]).

Mungkin dapat mencobanya online di sini: http://swish.swi-prolog.org/p/LazySort.pl

Anda bertanya l(L, [10,5,7,6,1]).yang mengatakan "selesaikan untuk L, di mana L adalah versi malas diurutkan dari daftar ini".

Dua fungsi tersebut adalah:

  • lazysorted (A, B) - menyatakan bahwa A adalah versi lazysorted dari B, jika keduanya daftar kosong, atau jika A dapat diperoleh dengan membalikkan B, memanggil fungsi penolong untuk berjalan dalam daftar dan melakukan pengurangan dengan akumulator. mendorong setiap nilai lebih rendah dari yang sebelumnya, dan membalikkan hasilnya kembali ke jalan yang benar.
  • fhelper cocok dengan dua daftar, nilai angka sebelumnya dalam daftar, dan akumulator perbedaan bergulir, dan memecahkan nilai baru dari posisi daftar saat ini menjadi nilai asli dikurangi akumulator perbedaan, secara opsional dikurangi nilai baru yang diperlukan untuk memaksa ini nilai di bawah angka sebelumnya dalam daftar, dan fharus menyelesaikan untuk ekor daftar secara rekursif dengan akumulator perbedaan sekarang meningkat.

Cuplikan layar kasus uji pada Swish:

gambar yang menunjukkan test case yang dijalankan pada Swish

TessellatingHeckler
sumber
0

JavaScript (ES6), 61 byte

a=>a.reduceRight((r,e)=>[e-(d=(c=e-r[0]+1)>d?c:d),...r],d=[])

Bukan solusi terpendek tapi saya tidak bisa melewatkan kesempatan untuk menggunakannya reduceRight.

Neil
sumber
0

C # (.NET Core) , 89 88 86 79 byte

  • Disimpan hanya 1 byte dengan pendekatan yang sedikit berbeda.
  • Menyimpan 2 byte lainnya dengan penyederhanaan fors.
  • Disimpan 7 byte berkat keterampilan golf yang luar biasa dari VisualMelon.
a=>{for(int i=0,j,k;++i<a.Length;)for(k=a[i-1]-a[j=i]+1;--j>=0;)a[j]-=k>0?k:0;}

Cobalah online!

Pertama foriterasi melalui array, lalu menghitung penurunan dan akhirnya elemen kedua formengurangi elemen jika perlu sampai iposisi th.

Apakah valid untuk hanya memodifikasi array asli daripada mengembalikan yang baru (masih terbiasa dengan aturan)?

Charlie
sumber
Ya, Memodifikasi array asli tidak masalah. :)
DJMcMayhem
4
@DJMcMayhem terima kasih, saya merasa terlalu malas untuk membuat yang baru. :)
Charlie