Masalah Pancake Bakar

23

Tantangan ini terkait dengan Flipping Pancake .

Anda mungkin pernah mendengar tentang penyortiran pancake , di mana setumpuk pancake diurutkan berdasarkan ukuran dengan memasukkan spatula ke dalam tumpukan dan membalik semua pancake di atas spatula, sampai pancake diurutkan terkecil hingga terbesar di piring. Masalah pancake yang terbakar sedikit berbeda. Semua panekuk sekarang memiliki satu sisi yang terbakar, dan sisi yang terbakar dari masing-masing panekuk harus menghadap piring setelah penyortiran selesai.

Sebagai contoh, diberi tumpukan berikut (ukuran panekuk di sebelah kiri. 0Artinya sisi terbakar sebelah bawah dan 1berarti sisi sisi atas terbakar di sebelah kanan):

1 0
3 1
2 1

Anda dapat membalik seluruh tumpukan untuk mendapatkan 20 30 11, membalik dua teratas untuk mendapatkan 31 21 11dan membalik seluruh tumpukan lagi untuk mendapatkan 10 20 30, tumpukan pancake bakaran yang diurutkan. Urutan gerakan ini, flip 3, flip 2, flip 3, dapat direpresentasikan sebagai 3 2 3.

Tantangan

  • Dengan serangkaian ukuran pancake (tidak harus unik) dan orientasinya, menampilkan urutan penyortiran pancake bakaran yang valid, yaitu, urutan flips yang mengarah ke tumpukan pancake yang diurutkan dari yang terkecil hingga terbesar dengan sisi yang terbakar ke bawah.
  • Input dan output mungkin merupakan format waras dengan pemisah, tetapi harap tentukan format mana yang Anda gunakan dan nyatakan ujung mana dari format input Anda yang berada di atas tumpukan (TOS).
  • Membalikkan nol pancake diperbolehkan.
  • Mencampur pemisah dalam input / output diperbolehkan.

Uji kasus

Untuk semua kasus uji berikut, input adalah daftar dan output adalah string yang dipisahkan oleh spasi, dan TOS di sebelah kiri.

[[1, 0], [3, 1], [2, 1]]
"3 2 3"

[[5, 1], [3, 0], [4, 1], [2, 1], [1, 0]]
"5 3 4 1 3 2 1"

[[5, 1], [3, 0], [3, 0], [1, 1]]
"4 3 2 3"

Seperti biasa, jika ada yang tidak jelas atau salah, harap beri tahu saya di komentar. Semoga berhasil dan bermain golf dengan baik!

Sherlock9
sumber

Jawaban:

7

Python 2, 83

Input diharapkan menjadi daftar (ukuran, orientasi) tupel dengan puncak tumpukan di akhir. Outputnya adalah daftar ukuran untuk flip yang dipisahkan oleh berbagai jenis spasi.

a=input()
while a:i=a.index(max(a));print len(a)-i,a[i][1],len(a),i;a=a[i+1:]+a[:i]
feersum
sumber
2
Rupanya saya idiot.
Leaky Nun
Apakah 0dalam daftar output diperbolehkan?
Leaky Nun
19
@ LeakyNun Membalik 0 pancake sangat mungkin. Sebenarnya, saya sedang melakukannya sekarang.
feersum
@daniero Bagian atas tumpukan ada di sisi kanan.
Leaky Nun
@ LeakyNun oh maaf,
salahku
3

CJam (37 byte)

q~{__$W>#)_p/(W%\M*2,f.^+(1=p_,)pW%}h

Input adalah array dalam format CJam pada stdin; output adalah daftar panjang flip yang dipisahkan pada baris baru di stdout. Bagian atas tumpukan berada di indeks 0; 0menunjukkan sisi yang terbakar ke atas, dan 1menunjukkan sisi yang terbakar ke bawah.

Demo online

Pembedahan

Output selalu 3nmembalik panjang, di mana njumlah pancake. Pertama, kita membalikkan pancake tersisa terbesar ke atas; maka jika sisi bakarnya terbakar ke bawah kita balikkan satu pancake itu; dan kemudian kita balikkan ke bawah dan ulangi seolah-olah tumpukan pancake lebih pendek.

q~         e# Parse input into array
{          e# Loop...
  __$W>#)  e#   Find 1-based index of largest element in array
  _p       e#   Dup and print
  /(       e#   Split into chunks that long, and pull off the first
  W%       e#   Reverse the first chunk. Note that we don't flip the burnt/unburnt bit
  \M*      e#   Merge the remaining chunks into a single array
  2,f.^    e#   Flip *their* burnt/unburnt bits
  +        e#   Concatenate, prepending the first chunk
  (1=p     e#   Pull off the first (largest) element and print its burnt/unburnt bit
  _,)p     e#   Print the number of remaining elements plus 1 (to account for the largest)
  W%       e#   Reverse. Note that the first chunk has now been flipped twice, which is
           e#   why we have left its burnt/unburnt bit alone
}h         e# ... until we get down to an empty array
Peter Taylor
sumber
3

Ruby, 101 95 93 byte

Tidak terlalu golf, saya hanya ingin membuat varian bogo-sort. Ini adalah fungsi anonim yang mengambil array array dan mencetak membalik acak ke stdout sampai pancake diurutkan.

->a{(p r=-~rand(a.size)
a[0,r]=a[0,r].reverse.map{|x,b|[x,1-b]})while a!=a.sort||a.rassoc(1)}

Misalnya, Anda dapat menetapkan fdan mengatakannyaf.call [[1, 0], [3, 1], [2, 1]]

-5 byte dari @Jordan dengan penggunaan brilian rassoc
-2 byte dari @ Sherlock9

daniero
sumber
1
Anda dapat menyimpan beberapa byte dengan menggantinya a.all?{...}dengan !a.rassoc(1).
Jordan
@ Jordan Wow, itu benar-benar brilian! Saya tidak berpikir saya pernah berpikir untuk menggunakan ( r) assocsebelumnya, tetapi memikirkannya, itu mungkin berguna dalam banyak masalah di situs ini - saya merasa harus masuk dalam posting tips golf Ruby. Bagaimanapun, terima kasih :) Saya juga mampu membunuh byte lain meskipun penerapan hukum deMorgans dan mengganti untildengan while.
daniero
Karena bhanya pernah 0atau 1, 1-bjuga akan bekerja dan akan menghemat dua byte.
Sherlock9