Katakan padaku bagaimana cara menjatuhkannya

29

Sebagai ilmuwan komputer, Anda mungkin sudah terbiasa dengan daftar operasi dasar pop dan push . Ini adalah operasi sederhana yang mengubah daftar elemen. Namun, pernahkah Anda mendengar tentang kegagalan operasi ? (seperti di flip- flop )? Sederhana saja. Dengan diberi nomor n , balikkan elemen n pertama dari daftar. Ini sebuah contoh:

>>> a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> a.flop(4)
[4, 3, 2, 1, 5, 6, 7, 8, 9, 10]

Yang keren tentang operasi gagal, adalah Anda dapat menggunakannya melakukan beberapa hal keren ke daftar, seperti menyortirnya . Kita akan melakukan sesuatu yang mirip dengan jepit:

Diberikan daftar bilangan bulat, "Tetangga itu". Dengan kata lain, sortir sehingga setiap elemen duplikat muncul secara berurutan.

Ini bisa dilakukan dengan jepit! Misalnya, ambil daftar berikut:

>>> a = [3, 2, 1, 4, 3, 3, 2]
>>> a.flop(4)
[4, 1, 2, 3, 3, 3, 2]
>>> a.flop(3)
[2, 1, 4, 3, 3, 3, 2]
>>> a.flop(6)
[3, 3, 3, 4, 1, 2, 2]

Ini membawa kita ke definisi tantangan hari ini:

Diberikan daftar bilangan bulat, hasilkan setiap set jepit yang akan menghasilkan daftar bertetangga.

Menggunakan daftar terakhir sebagai contoh, Anda harus menampilkan:

4
3
6

karena membalik daftar dengan 4, kemudian oleh 3, maka dengan 6 akan menghasilkan daftar tetangga. Ingatlah bahwa Anda tidak perlu mencetak daftar flor yang sesingkat mungkin yang bertetangga dengan daftar. Jika Anda telah mencetak:

4
4
4
3
1
1
6
2
2

sebagai gantinya, ini masih akan menjadi output yang valid. Namun, Anda mungkin tidak akan pernah menampilkan angka yang lebih besar dari panjang daftar. Ini karena untuk daftar a = [1, 2, 3], panggilan a.flop(4)tidak masuk akal.

Berikut ini beberapa contohnya:

#Input:
[2, 6, 0, 3, 1, 5, 5, 0, 5, 1]

#Output
[3, 7, 8, 6, 9]


#Input
[1, 2]

#Output
<any list of integers under 3, including an empty list>


#Input
[2, 6, 0, 2, 1, 4, 5, 1, 3, 2, 1, 5, 6, 4, 4, 1, 4, 6, 6, 0]

#Output
[3, 19, 17, 7, 2, 4, 11, 15, 2, 7, 13, 4, 14, 2]


#Input
[1, 1, 1, 1, 2, 2, 2, -1, 4]

#Output
[]


#Input
[4, 4, 8, 8, 15, 16, 16, 23, 23, 42, 42, 15]

#Output
[12, 7]

Ingatlah bahwa dalam masing-masing contoh ini, output yang diberikan hanyalah salah satu output yang valid. Seperti yang saya katakan sebelumnya, setiap set jepit yang bertetangga dengan daftar yang diberikan adalah output yang valid . Anda dapat menggunakan skrip python ini untuk memverifikasi apakah daftar jepit yang diberikan benar dalam daftar.

Anda dapat mengambil input dan output dalam format apa pun yang masuk akal. Misalnya, argumen fungsi / nilai pengembalian, STDIN / STDOUT, membaca / menulis file dll. Semuanya valid. Seperti biasa, ini adalah , jadi buatlah program sesingkat mungkin, dan bersenang-senanglah! :)

DJMcMayhem
sumber
3
Saya mendengarnya sebagai fl (oating point) op (eration).
Weijun Zhou
3
@ WeijunZhou Itu adalah ukuran kecepatan komputasi, untuk menghitung operasi yang dilakukan oleh perangkat keras. en.wikipedia.org/wiki/FLOPS
iPhoenix
3
Apakah kiriman harus bersifat deterministik atau dapatkah saya pseudo-secara acak gagal sampai array dikelompokkan?
Dennis
3
Apakah zero flop diperbolehkan muncul di output?
Laikoni
4
Terkait . NB setiap jawaban untuk pertanyaan itu akan menjadi jawaban untuk yang satu ini, tetapi karena disortir adalah kondisi yang lebih kuat daripada "bertetangga", dimungkinkan untuk tidak bermain golf sehingga ini mungkin bukan duplikat (meskipun fakta bahwa satu-satunya jawab sejauh ini macam tidak menggembirakan).
Peter Taylor

Jawaban:

7

Haskell , 98 71 byte

h.r
h(x:s)|(a,b)<-span(/=x)s=l b:l s:h(b++r a)
h e=e
r=reverse
l=length

Cobalah online!

Penjelasan

Untuk daftar panjangnya n, metode ini menghasilkan 2*njepit. Ia bekerja dengan melihat elemen terakhir dari daftar, mencari elemen yang sama dalam daftar sebelumnya dan membalikkannya ke posisi kedua ke posisi terakhir. Kemudian daftar dengan elemen terakhir yang dihapus secara rekursif "bertetangga".

Untuk daftar [1,2,3,1,2]algoritma bekerja seperti ini:

[1,2,3,1,2]  flip longest prefix that ends in 2: flop 2
[2,1,3,1,2]  bring first element to second to last position: flop n-1 = flop 4
[1,3,1,2,2]  recursively work on n-1 list
[1,3,1,2]    there is no other 2: flop 0
[1,3,1,2]    flop n-1 = flop 3
[1,3,1,2]    recurse
[1,3,1]      flop 1
[1,3,1]      flop 2
[3,1,1]      recurse
[3,1]        flop 0
[3,1]        flop 1
 ...

Semua ini menghasilkan jepit [2,4,0,3,1,2,0,1,0,0]dan daftar tetangga [3,1,1,2,2].

Laikoni
sumber
6

Bahasa Wolfram (Mathematica) , 71 byte

If[(n=Tr[1^#])<1,{},{i=Last@Ordering@#,n,n-1,i-1}~Join~#0[#~Drop~{i}]]&

Cobalah online!

Bagaimana itu bekerja

Dengan panjang array n, menghasilkan urutan 4njepit yang mengurutkan array dalam urutan yang meningkat: khususnya, menempatkan elemen duplikat di samping satu sama lain.

Idenya adalah untuk mengurutkan array, kita memindahkan elemen terbesarnya ke akhir, dan kemudian mengurutkan n-1elemen pertama dari array. Untuk menghindari penerapan operasi gagal, kami memindahkan elemen terbesar ke ujung dengan cara yang tidak mengganggu elemen lainnya:

{3, 2, 1, 5, 3, 3, 2}    starting array, with largest element in position 4
{5, 1, 2, 3, 3, 3, 2}    flop 4 to put the largest element at the beginning
{2, 3, 3, 3, 2, 1, 5}    flop 7 to put the largest element at the end
{1, 2, 3, 3, 3, 2, 5}    flop 6 (7-1) to reverse the effect of flop 7 on other elements
{3, 2, 1, 3, 3, 2, 5}    flop 3 (4-1) to reverse the effect of flop 4 on other elements

Secara umum, jika elemen terbesar ada di posisinya i, urutan jepit yang memindahkannya ke ujung adalah i, n, n-1, i-1.

Misha Lavrov
sumber
Anda dapat memindahkan elemen terbesar ke ujung hanya dengan i, n. Mengapa demikian n-1, i-1? Tidak perlu untuk jenis yang stabil .
Peter Taylor
@PeterTaylor Saya tidak berpikir jawabannya benar-benar melakukan jepit, melainkan menghilangkan elemen terbesar setiap kali, dan output setara dengan operasi itu dalam hal jepit.
Neil
3

Jelly , 19 17 byte

ỤỤạ‘Ḣ
ỤÇÐƤĖµUż’ṚF

Urutkan daftar.

Cobalah online!

Dennis
sumber
Saya pikir ỤŒ¿’Æ!‘ṚĖµUż’ṚFjenis mundur karena Œ¿modulo L!.
Jonathan Allan
Untuk alasan apa pun, itu tidak berfungsi untuk kasus uji terakhir, yang mungkin berarti bahwa kode saya akan gagal untuk beberapa kasus tepi tidak jelas juga ...
Dennis
Dan memang gagal untuk input [4, 3, 2, 1, 3]. Gelandangan.
Dennis
Oh, boo; itu memalukan.
Jonathan Allan
Ụ>Ṫ$ƤSạỤĖµUż’ṚFhemat 2 byte dengan mengganti tautan helper.
mil
2

Bersihkan , 88 byte

Saya pikir mungkin ada yang lebih pendek dengan penjaga, tapi saya belum menemukannya.

import StdEnv
$[h:t]#(a,b)=span((<>)h)t
=map length[b,t]++ $(b++r a)
$e=e
r=reverse

$o r

Cobalah online!

Sebagai fungsi literal. Bekerja dengan cara yang sama seperti jawaban Haskell dari Laikoni , tetapi bermain golf sedikit berbeda, dan tentu saja juga dalam bahasa yang berbeda.

Suram
sumber
1

JavaScript, 150 byte

(a,f=n=>(a=[...a.slice(0, n).reverse(),...a.slice(n)],n),l=a.length,i=0)=>a.reduce(c=>[...c,f(a.indexOf(Math.max(...a.slice(0, l-i)))+1),f(l-i++)],[])

Cobalah online!

JavaScript, 151 byte

a=>{f=n=>(a=[...a.slice(0,n).reverse(),...a.slice(n)],n),r=[];for(i=a.length+1;--i>0;)r.push(f(a.indexOf(Math.max(...a.slice(0, i)))+1),f(i));return r}

Cobalah online!

Keduanya pada dasarnya mengurutkan array dengan membalikkan angka maks ke awal dan kemudian membalik ke belakang, mengulanginya dengan array yang tersisa. Yang pertama menggunakan mengurangi, yang kedua menggunakan for for.

Tidak Terkumpul:

array => {
  let flop = n => {
    array = [...array.slice(0, n).reverse(), ...array.slice(n)]; 
    return n;
  }
  let flops = [];
  for (let i = array.length + 1; --i > 0;) 
  {
    let maxIndex = array.indexOf(Math.max(...array.slice(0, i)));
    flops.push(flop(maxIndex + 1), flop(i));
  }
  return flops;
}
mdatsev
sumber
0

Perl 5.10 (atau lebih tinggi), 66 byte

Termasuk +3untuk -n The use 5.10.0untuk membawa bahasa ke level perl 5.10 dianggap gratis

#!/usr/bin/perl -n
use 5.10.0;
$'>=$&or$.=s/(\S+) \G(\S+)/$2 $1/*say"$. 2 $."while$.++,/\S+ /g

Jalankan dengan input sebagai satu baris pada STDIN:

flop.pl <<< "1 8 3 -5 6"

Urutkan daftar dengan berulang kali menemukan inversi apa pun, menjatuhkannya ke depan lalu menjatuhkan inversi dan membalikkan semuanya kembali ke posisi semula.

Sangatlah sulit untuk mendapatkan in the ballpark yang sama dengan python yang satu ini :-)

Ton Hospel
sumber
0

C (gcc) , 165 160 byte

  • Terima kasih kepada ceilingcat untuk menghemat lima byte.
m,j,t;f(A,l)int*A;{for(j=0;j+j<l;A[j]=A[l+~j],A[l+~j++]=t)t=A[j];}F(A,l)int*A;{for(;l;f(A,++m),printf("%d,%d,",m,l),f(A,l--))for(j=m=0;j<l;j++)m=A[j]>A[m]?j:m;}
Jonathan Frech
sumber
@ceilingcat Terima kasih.
Jonathan Frech