Bisakah Anda mengalahkan Bill Gates?

13

Penyortiran pancake adalah istilah sehari-hari untuk masalah matematika menyortir tumpukan pancake dalam urutan ukuran ketika spatula dapat dimasukkan pada sembarang titik di stack dan digunakan untuk membalik semua pancake di atasnya. Nomor pancake P (n) adalah jumlah minimum flips yang diperlukan untuk n pancake. 1

Pada tahun 1979, seorang Bill Gates muda dan Christos Papadimitriou, menulis sebuah makalah yang membuktikan batas atas P (n) = (5n + 5) / 3 . 2

Saya pikir aman untuk mengasumsikan bahwa Gates (dan / atau Papadimitriou) menulis sebuah program untuk melakukan penyortiran pancake menggunakan algoritma yang mereka kembangkan (mungkin lebih dari 1979). Karena Gates adalah seorang programmer yang terampil, mereka mungkin mencoba golf kode ini sebaik mungkin, tetapi ukuran kode sumber tidak tersedia untuk umum (AFAIK).

Tantangan:

Buat fungsi / program yang melakukan penyortiran pancake, di mana jumlah maksimum flips tidak melebihi batas yang ditemukan oleh Gates dan Papadimitriou. 3 Anda dapat memilih apakah ingin daftar naik atau turun, asalkan konsisten.

Anda dapat menganggap bahwa n <50 . Karena itu, Anda harus membatasi jumlah flip hingga (beberapa n-nilai yang dipilih secara acak ):

 n   P(n)
38   65
49   83
50   85

Output harus menjadi posisi spatula sebelum setiap flip. Output mungkin nol atau satu-diindeks, dan Anda dapat memilih jika Anda menghitung dari atas atau bawah.

Aturan tambahan:

  • Runtime harus bersifat deterministik
  • Tidak ada batasan waktu tetap, tetapi Anda harus dapat memberikan output untuk daftar dengan 50 elemen

Daftar tes:

Saya tidak dapat memberikan daftar yang paling sulit (jika demikian, saya akan menulis makalah, bukan tantangan), jadi saya akan memberikan beberapa daftar angka acak yang dapat Anda uji fungsi / program Anda. Saya mungkin menambahkan orang lain jika ternyata daftar ini di mana "mudah".

9, 63, 62, 75, 45, 78, 59, 75, 69, 3, 28, 94, 51, 10, 45, 93, 97, 80, 72, 36, 80, 88, 30, 93, 84, 80, 17, 31, 6, 80, 76, 91, 9, 76, 38, 33, 22, 15, 45, 46, 15, 98, 2, 56, 90, 27, 27, 26, 69, 25
...
74, 89, 57, 52, 70, 96, 16, 5, 77, 84, 54, 13, 90, 64, 31, 80, 3, 25, 13, 19, 13, 34, 1, 79, 35, 43, 4, 19, 82, 29, 48, 95, 97, 28, 45, 62, 64, 82, 70, 34, 38, 15, 51, 83, 21, 66, 4, 42, 74, 84
...
62, 73, 7, 90, 83, 18, 12, 35, 72, 71, 99, 67, 87, 62, 65, 70, 14, 72, 55, 92, 87, 3, 7, 4, 4, 95, 49, 25, 4, 18, 49, 39, 26, 1, 45, 64, 23, 66, 39, 17, 33, 24, 58, 72, 77, 46, 99, 71, 10, 21

Semoga Bill Gates dan Papadimitriou akan melihat tantangan ini, dan memberikan kode mereka, sehingga kami dapat menentukan apakah Anda memang mengalahkan mereka.

3 Batas atas yang lebih baik telah ditemukan, tetapi Anda tidak perlu mempedulikannya.

code-golf number sorting optimization stack Stewie Griffin
sumber
Terkait , tetapi bukan duplikat. Jawaban di sana tidak akan berfungsi di sini.
Stewie Griffin
Saya menggunakan BFS dalam solusi saya di sana saat itu, masih harus bekerja di sini (dengan sedikit memperbarui) untuk menemukan solusi dengan jumlah flips minimum.
mil
@miles jangan ragu untuk memposting Saya tidak membahas semua jawaban secara terperinci, tetapi kebanyakan hanya menggunakan pendekatan naif.
Stewie Griffin

Jawaban:

4

Python 2 (PyPy) , 238 235 222 byte

a=input();n=len(a);r=range(n);a=zip(a,r);a=map(sorted(a).index,a)+[n]
def s(u,m):
 if m<1:return[0]
 for k in r:
  v=u[k::-1]+u[k+1:]
  if sum(1<abs(v[i]-v[i+1])for i in r)<m:
   p=s(v,m-1)
   if p:return[k]+p
print s(a,5*n/3)

* (2 spasi = tab)

Cobalah online!

Menyimpan 13 byte meminjam metode untuk menentukan peringkat daftar .

DFS dengan heuristik sederhana yang memeriksa apakah flip memisahkan sepasang "pancake" yang berdekatan ketika disortir. Mengurutkannya dalam urutan menaik. Output 0-diindeks dari kiri di mana 0 membalik 2 pertama dan seterusnya. Jumlah gerakan yang digunakan adalah di (5/3)*n+1 < 5/3*(n+1)mana (18/11)*n < (5/3)*n+1 < 5/3*(n+1)dan (18/11)*nmerupakan batas atas yang lebih ketat ditemukan pada tahun 2009 .

mil
sumber