Membalik pancake

27

Dalam menyortir pancake , satu-satunya operasi yang diizinkan adalah membalik elemen dari beberapa awalan urutan. Atau, pikirkan tumpukan pancake: Kami memasukkan spatula di suatu tempat di tumpukan dan membalik semua pancake di atas spatula.

Sebagai contoh, urutan 6 5 4 1 2 3dapat diurutkan dengan pertama membalik 6elemen pertama (seluruh urutan), menghasilkan hasil antara 3 2 1 4 5 6, dan kemudian membalik 3elemen pertama , sampai pada 1 2 3 4 5 6.

Karena hanya ada satu operasi, seluruh proses penyortiran dapat dijelaskan oleh urutan bilangan bulat, di mana setiap bilangan bulat adalah jumlah elemen / pancake untuk menyertakan pr flip. Untuk contoh di atas, urutan pengurutannya adalah 6 3.

Contoh lain: 4 2 3 1bisa disortir dengan 4 2 3 2. Inilah hasil antara:

         4 2 3 1
flip 4:  1 3 2 4
flip 2:  3 1 2 4
flip 3:  2 1 3 4
flip 2:  1 2 3 4

Tugas:

Tulis program yang mengambil daftar bilangan bulat dan mencetak urutan penyortiran pancake yang valid.

Daftar untuk disortir dapat berupa daftar yang dipisahkan spasi dari stdin, atau argumen baris perintah. Cetak daftar itu bagaimanapun nyaman, asalkan terbaca.

Ini adalah codegolf!

Edit:

Seperti yang saya katakan di komentar, Anda tidak perlu mengoptimalkan output (menemukan urutan terpendek adalah NP-hard ). Namun , saya baru menyadari bahwa solusi yang murah adalah membuang angka acak sampai Anda mendapatkan hasil yang diinginkan (jenis bogosort [baru?]). Sejauh ini tidak ada jawaban yang telah melakukan ini, jadi saya sekarang menyatakan bahwa algoritma Anda tidak harus bergantung pada keacakan (pseudo-) .

Saat Anda semua menendang diri sendiri, inilah varian bogopancakeort di Ruby 2.0 (60 karakter), untuk digosokkan ke:

a=$*.map &:to_i
a=a[0,p(v=rand(a.size)+1)].reverse+a[v..-1]while a!=a.sort
daniero
sumber
1
Adakah urutan yang valid, atau haruskah urutannya minimal?
Peter Taylor
Tiny typo: contoh kedua menunjukkan 4 3 2 1bukan4 2 3 1
beary605
4
(Internet saya turun saat saya mencoba mengedit ini, jadi saya mempostingnya lagi) @PeterTaylor Saya tergoda untuk memasukkan semacam optimasi ke dalam ini, tetapi memilih untuk tidak melakukannya. Menemukan panjang urutan minimal sebenarnya NP-hard , sedangkan algoritma yang paling sederhana dan lurus dapat menemukan solusi yang paling panjangnya adalah 2n. Saya tidak benar-benar tahu bagaimana saya akan menilai ini sebagai tantangan kode / keluaran yang optimal, dan saya lebih suka codegolf biasa :)
daniero
Saya bertanya-tanya apakah ada yang akan memposting entri mereka dari tantangan ini .
grc
Apakah urutannya harus nilai yang berdekatan? Apakah 2 7 5 merupakan input yang valid?

Jawaban:

6

GolfScript, 34/21 karakter

(Terima kasih @PeterTaylor untuk memotong 4 karakter)

~].{,,{1$=}$\}2*${.2$?.p)p.@\-+}/,

Tes online

Versi yang lebih pendek, 21 karakter hanya berfungsi untuk daftar dengan item unik

~].${.2$?.p)p.@\-+}/,

Tes online

Kedua versi menghasilkan solusi sub-optimal.


Penjelasan untuk solusi yang lebih pendek:

~]         # read input from stdin
.$         # produce a sorted copy from lowest to highest
{          # iterate over the sorted list
  .2$?     # grab the index of the element
  .p       # print the index
  )p       # increment and print the index
  .@\-+    # move the element to the front
}/
,          # leave the length of the list on the stack
           # this flips the reverse sorted list to become sorted

Ini menggunakan algoritma yang berbeda untuk sebagian besar yang diposting. Pada dasarnya itu mengambil elemen terkecil dari daftar, dan dengan dua membalik bergerak ke depan, menjaga urutan elemen lainnya.

Untuk memindahkan elemen ke-n ke depan:

1 2 3 4 5 6 7   # let's move the 3rd (0-based) element to the front
# flip the first 3 elements
3 2 1 4 5 6 7
# flip the first 3+1 elements
4 1 2 3 5 6 7

Itu mengulangi operasi ini untuk setiap elemen secara berurutan, dan berakhir dengan daftar diurutkan terbalik. Kemudian membalik seluruh daftar untuk membiarkannya sepenuhnya diurutkan.


Sebenarnya algoritma ini adalah variasi dari solusi Python 90-char (milik saya sendiri, tentu saja):

d=map(int,raw_input().split());i=0
while d:n=d.index(max(d));d.pop(n);print n+i,n-~i,;i+=1
Keriangan
sumber
2
Saya melihat Anda belum menemukan salah satu kebiasaan berguna GolfScript: Anda dapat menggunakan token apa pun sebagai variabel. Anda tidak menggunakan &di mana saja, sehingga Anda harus dapat menggantikan ssementara &dan menghapus spasi.
Peter Taylor
@PeterTaylor ya, saya bertanya-tanya mengapa Anda bisa menggunakan ^sebagai variabel dalam tantangan fibonacci;) Terima kasih atas tipnya!
Volatilitas
Untuk input 3 2 1saya mendapatkan 131211yang tidak benar.
Howard
@ Howard berhasil bekerja sekarang
Volatilitas
@Vatilitas. Perubahan terakhir agak terlalu banyak ;-) Misalnya daftar suka 2 1 1tidak bisa disortir lagi.
Howard
11

Python, 91 90 karakter

L=map(int,raw_input().split())
while L:i=L.index(max(L));print-~i,len(L),;L=L[:i:-1]+L[:i]

Balikkan pancake terbesar ke atas, lalu balikkan seluruh tumpukan. Angkat pancake terbesar dari bawah dan ulangi.

iadalah indeks pancake terbesar. L=L[:i:-1]+L[:i]membalik i+1pancake, membalik len(L)pancake, lalu menjatuhkan pancake terakhir.

Keith Randall
sumber
1
Saya pikir Anda hanya diizinkan untuk membalik. (Yaitu, saya tidak berpikir Anda bisa menjatuhkan pancake dari tumpukan). Apakah saya salah paham aturan? Hmm. masuk untuk membaca halaman wiki lagi Bagaimanapun, pekerjaan yang bagus :) Kurang dari 100 karakter cukup menakjubkan bagi saya!
WendiKidd
@WendiKidd Sebenarnya, maksudnya adalah setelah membalik yang terbesar ke bawah, dia hanya mengabaikannya dan menganggap dirinya dengan pancake di atasnya.
AJMansfield
@AJMansfield Ah, saya mengerti! Terima kasih, itu masuk akal. Saya tidak dapat membaca kode (saya terlalu baru untuk Python) jadi saya salah mengerti penjelasannya :) Terima kasih!
WendiKidd
2
Cukup banyak evolusi dari apa yang saya tulis sebelumnya. Saya tidak berpikir untuk menghapus elemen karena pada awalnya saya harus memeriksa kebenaran dari output (yaitu daftar diurutkan sesudahnya?). Ngomong-ngomong: Saya percaya menghapus koma dari printwont membuat output tidak terbaca (1 byte disimpan :)
Bakuriu
@WendiKidd sebenarnya, pada pemeriksaan lebih lanjut, memang menghapus pancake; hanya perlu mencari tahu apa urutan flip, tidak benar-benar mengurutkan array.
AJMansfield
6

Ruby 1.9 - 109 88 79 karakter

Versi yang jauh lebih ringkas berdasarkan pada solusi python Keith:

a=$*.map &:to_i;$*.map{p v=a.index(a.max)+1,a.size;a=a[v..-1].reverse+a[0,v-1]}

Versi asli:

a=$*.map &:to_i
a.size.downto(2){|l|[n=a.index(a[0,l].max)+1,l].map{|v|v>1&&n<l&&p(v);a[0,v]=a[0,v].reverse}}

Jika Anda tidak peduli dengan operasi palsu (membalikkan tumpukan ukuran 1, atau membalik tumpukan yang sama dua kali berturut-turut) Anda bisa membuatnya sedikit lebih pendek (96 karakter):

a=$*.map &:to_i
a.size.downto(2){|l|[a.index(a[0,l].max)+1,l].map{|v|p v;a[0,v]=a[0,v].reverse}}

Mengambil daftar yang tidak disortir sebagai argumen baris perintah. Contoh penggunaan:

>pc.rb 4 2 3 1
4
2
3
2
Paul Prestidge
sumber
6

GolfScript, 31 29 karakter

~].${1$?).p.2$.,p>-1%\@<+)}%,

Solusi GolfScript lainnya, juga dapat diuji secara online .

Versi sebelumnya:

~].$-1%{1$?).2$>-1%@2$<+.,\);}/

Bagaimana cara kerjanya: itu membalik item terbesar ke atas dan kemudian ke tempat terakhir dalam daftar. Karena sekarang berada di posisi yang benar, kami dapat menghapusnya dari daftar.

~]         # Convert STDIN (space separated numbers) to array
.$-1%      # Make a sorted copy (largest to smallest)
{          # Iterate over this copy
  1$?)     # Get index of item (i.e. largest item) in the remaining list,
           # due to ) the index starts with one
  .        # copy (i.e. index stays there for output)
  2$>      # take the rest of the list...
  -1%      # ... and reverse it 
  @2$<     # then take the beginning of the list
  +        # and join both. 
           # Note: these operations do both flips together, i.e.
           # flip the largest item to front and then reverse the complete stack
  .,       # Take the length of the list for output
  \);      # Remove last item from list
}/
Howard
sumber
4

Perl, 103 100 karakter

Mengharapkan input pada baris perintah.

for(@n=sort{$ARGV[$a]<=>$ARGV[$b]}0..$#ARGV;@n;say$i+1,$/,@n+1)
{$i=pop@n;$_=@n-$_-($_<=$i&&$i)for@n}

Solusi yang dicetaknya jelas kurang optimal. (Saya memiliki program dengan output yang jauh lebih baik sekitar 24 karakter yang lalu ....)

Logikanya agak menarik. Dimulai dengan katalog indeks setiap item, apakah itu dalam urutan. Kemudian beralih melalui katalog ini dari kanan ke kiri. Jadi menerapkan flip melibatkan penyesuaian indeks di bawah nilai cutoff, bukannya benar-benar memindahkan nilai. Setelah beberapa penyelesaian saya juga berhasil menyelamatkan beberapa karakter dengan melakukan kedua membalik per iterasi secara bersamaan.

kotak roti
sumber
3

Python 2 (254)

Pencarian BFS sederhana, beberapa hal digarisbawahi, mungkin bisa dikompresi lebih banyak tanpa mengubah gaya pencarian. Semoga ini menunjukkan mungkin bagaimana memulai bermain golf sedikit (terlalu banyak untuk di komentar sederhana).

Menggunakan:

python script.py 4 2 3 1

(2 spasi = tab)

import sys
t=tuple
i=t(map(int,sys.argv[1:]))
g=t(range(1,len(i)+1))
q=[i]
p={}
l={}
while q:
 c=q.pop(0)
 for m in g:
  n=c[:m][::-1]+c[m:]
  if n==g:
   s=[m]
   while c!=i:s+=[l[c]];c=p[c]
   print s[::-1]
   sys.exit()
  elif n not in p:q+=[n];p[n]=c;l[n]=m
mil
sumber
1
Anda dapat menggantinya sys.exit()dengan 1/0(dalam codegolf Anda tidak pernah peduli dengan apa yang dicetak di stderr ...).
Bakuriu
Tentu, saya bisa melakukan print s[::-1];1/0untuk mencukur beberapa karakter.
mil
BFS sangat menarik, tetapi menjalankannya dengan 4 2 3 1memberi 2 3 2 4, yang sebenarnya tidak valid.
daniero
1
@daniero Bagaimana output itu tidak valid? 4 2 3 1-> 2 4 3 1-> 3 4 2 1-> 4 3 2 1->1 2 3 4
Gareth
@ Gareth, aku tidak tahu! Dan saya bahkan memeriksanya dua kali .. Oh well, lupakan saja :) Solusi bagus, mil t.
daniero
3

Python2: 120

L=map(int,raw_input().split())
u=len(L)
while u:i=L.index(max(L[:u]))+1;L[:i]=L[i-1::-1];L[:u]=L[u-1::-1];print i,u;u-=1

Itu tidak efisien: ia tidak akan menemukan urutan penyortiran terbaik, dan urutan yang diberikan bahkan dapat berisi no-ops (yaitu hanya membalik elemen pertama), namun hasilnya valid.

Outputnya diberikan dalam bentuk:

n_1 n_2
n_3 n_4
n_5 n_6
...

Yang harus dibaca sebagai urutan membalik: n_1 n_2 n_3 n_4 n_5 n_6 .... Jika Anda ingin mendapatkan output seperti:

n_1 n_2 n_3 n_4 n_5 n_6 ...

Cukup tambahkan koma dalam printpernyataan.

Bakuriu
sumber
[:i][::-1]-> [i-1::-1], [:u][::-1]-> [u-1::-1], menghemat 2 karakter
Volatilitas
Bahkan, L[:i]=L[i-1::-1];L[:u]=[u-1::-1]simpan 3 karakter lagi
Volatilitas
@Vatilitas, Terima kasih atas tipsnya. Termasuk.
Bakuriu
3

Python - 282 karakter

import sys
s=sys.argv[1]
l=s.split()
p=[]
for c in l:
 p.append(int(c))
m=sys.maxint
n=0
while(n==(len(p)-1)):
 i=x=g=0
 for c in p:
  if c>g and c<m:
   g=c
   x=i
  i+=1
 m=g
 x+=1
 t=p[:x]
 b=p[x:]
 t=t[::-1]
 p=t+b
 a=len(p)-n;
 t=p[:a]
 b=p[a:]
 t=t[::-1]
 p=t+b
 print p
 n+=1

Golf kode pertama saya; Saya tidak punya ilusi bahwa saya akan menang , tetapi saya bersenang-senang. Memberi segalanya nama-nama satu karakter tentu membuatnya menakutkan untuk dibaca, izinkan saya memberi tahu Anda! Ini dijalankan dari baris perintah, contoh implementasi di bawah ini:

Python PancakeSort.py "4 2 3 1"
[1, 3, 2, 4]
[2, 1, 3, 4]
[1, 2, 3, 4]

Tidak ada yang khusus atau inventif tentang cara saya melakukan hal ini, tetapi FAQ menyarankan untuk memposting versi non-golf untuk pembaca yang tertarik, jadi saya melakukannya di bawah ini:

import sys

pancakesStr = sys.argv[1]
pancakesSplit = pancakesStr.split()
pancakesAr = []
for pancake in pancakesSplit:
    pancakesAr.append(int(pancake))

smallestSorted = sys.maxint
numSorts = 0

while(numSorts < (len(pancakesAr) - 1)):
    i = 0
    biggestIndex = 0
    biggest = 0
    for pancake in pancakesAr:
        if ((pancake > biggest) and (pancake < smallestSorted)):
            biggest = pancake
            biggestIndex = i
        i += 1

    smallestSorted = biggest  #you've found the next biggest to sort; save it off.
    biggestIndex += 1   #we want the biggestIndex to be in the top list, so +1.

    top = pancakesAr[:biggestIndex]
    bottom = pancakesAr[biggestIndex:]

    top = top[::-1] #reverse top to move highest unsorted number to first position (flip 1)
    pancakesAr = top + bottom   #reconstruct stack

    alreadySortedIndex = len(pancakesAr) - numSorts;

    top = pancakesAr[:alreadySortedIndex]
    bottom = pancakesAr[alreadySortedIndex:]

    top = top[::-1] #reverse new top to move highest unsorted number to the bottom position on the unsorted list (flip 2)
    pancakesAr = top + bottom   #reconstruct list

    print pancakesAr    #print after each flip

    numSorts += 1

print "Sort completed in " + str(numSorts) + " flips. Final stack: "
print pancakesAr

Algoritma dasar yang saya gunakan adalah yang disebutkan dalam artikel wiki yang tertaut dalam pertanyaan :

Algoritma penyortiran pancake paling sederhana membutuhkan paling banyak 2n − 3 membalik. Dalam algoritme ini, variasi pemilihan, kami membawa pancake terbesar yang belum diurutkan ke atas dengan satu flip, dan kemudian membawanya ke posisi akhir dengan satu lagi, kemudian ulangi ini untuk pancake yang tersisa.

WendiKidd
sumber
1
Beberapa tips untuk bermain golf: empat ruang untuk lekukan adalah sia-sia. Lebih baik: gunakan satu ruang; bahkan lebih baik: gabungkan tab dan spasi untuk mengurangi lebih banyak lagi.
John Dvorak
1
t=p[:x] t=t[::-1](16+ indentasi) dapat dikurangi menjadi t=p[:x][::-1](13), atau bahkan t=p[x-1::-1](12). Sebariskan semua yang Anda bisa:p=p[x-1::-1]+p[x:]
John Dvorak
Gunakan indeks negatif untuk menghitung dari belakang. len(a)-nmenjadi -n; p=p[-n-1::-1]+p[-n:]. Lebih lanjut golf dengan menggunakan operasi yang tepat:p=p[~n::-1]+p[-n:]
John Dvorak
1
Umm ... Anda seharusnya mencetak seluruh urutan flipping, bukan hanya hasil akhirnya.
John Dvorak
Apa yang dikatakan Jan Dvorak. Selamat datang di codegolf. Anda dapat dengan mudah memotong jumlah karakter menjadi setengah dengan beberapa langkah sederhana; beberapa dari mereka telah disebutkan. Juga, variabel perantara tidak baik. Pemahaman daftar bagus. Tetapi jika Anda menggunakan sys.argv Anda sebaiknya membiarkan setiap nomor input menjadi argumen, lalu map(int,sys.argv[1:])lakukan apa yang dilakukan 6 baris pertama Anda sekarang. i=x=g=0berfungsi, tetapi Anda harus memangkas jumlah variabel. Saya akan memberi Anda satu hal: Ini adalah satu-satunya entri python yang paling saya mengerti: D
daniero
3

C # - 264 259 252 237 karakter

Menggunakan algoritma paling sederhana dan menghasilkan output yang benar tanpa membalik berlebihan. Bisa mencukur 7 karakter jika saya mengizinkannya memasukkan 1 (non-flips) dalam output, tapi itu jelek.

Saya menggunakan gotountuk golf maksimum. Juga menyimpan beberapa karakter dengan membiarkannya melakukan non-flip (tetapi tidak mencetaknya).

Peningkatan terbaru: menjaga array input sebagai string alih-alih mengonversi ke int.

using System.Linq;class P{static void Main(string[]a){var n=a.ToList();for(int p
=n.Count;p>0;p--){int i=n.IndexOf(p+"")+1;if(i<p){f:if(i>1)System.Console.Write
(i);n=n.Take(i).Reverse().Concat(n.Skip(i)).ToList();if(i!=p){i=p;goto f;}}}}}

Tidak Terkumpul:

using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        var numbers = args.ToList();

        for (int pancake = numbers.Count; pancake > 0; pancake--)
        {
            int index = numbers.IndexOf(pancake+"") + 1;
            if (index < pancake)
            {
                flip:

                if (index > 1)
                    System.Console.Write(index);

                numbers = numbers.Take(index)
                                 .Reverse()
                                 .Concat(numbers.Skip(index))
                                 .ToList();

                if (index != pancake)
                {
                    index = pancake;
                    goto flip;
                }
            }
        }
    }
}

Inilah solusi awal saya, ungolfed (264 karakter golf):

using System.Linq;
using System;

class Program
{
    static void Main(string[] args)
    {
        var numbers = args.Select(int.Parse).ToList();

        Action<int> Flip = howMany =>
        {
            Console.Write(howMany);
            numbers = numbers.Take(howMany)
                             .Reverse()
                             .Concat(numbers.Skip(howMany))
                             .ToList();
        };

        for (int pancake = numbers.Count; pancake > 0; pancake--)
        {
            int index = numbers.IndexOf(pancake) + 1;
            if (index < pancake)
            {
                if (index > 1)
                    Flip(index);
                Flip(pancake);
            }
        }
    }
}
Igby Largeman
sumber
Tidak menangani urutan yang tidak berdekatan - memberikan hasil yang salah dengan input tersebut.
@ kapak: Saya tidak yakin apa yang Anda maksud. Bisakah Anda memberi saya contoh?
Igby Largeman
Diberikan input 1 22, hasilnya mengatakan untuk melakukan satu swap, yang akan menghasilkan 22 1. Saya pikir kode Anda mengharapkan urutan untuk memasukkan angka yang berdekatan (mis: 2 4 1 3), tetapi tidak mengharapkan input seperti ( 2 24 5 5 990).
@tetap: Memang, saya tidak berusaha untuk mendukung kesenjangan dalam urutan, karena itu tidak masuk akal. Gagasan semacam pancake adalah untuk menyortir setumpuk objek, bukan sekelompok angka acak. Jumlah yang terkait dengan setiap objek mengidentifikasi posisi yang tepat di tumpukan. Oleh karena itu angka akan selalu dimulai dengan 1 dan berdekatan.
Igby Largeman
Saya tidak yakin, karena pertanyaannya mengatakan "urutan", dan dalam matematika, {1, 22} adalah urutan yang valid, tetapi kedua contoh adalah angka yang berdekatan. Jadi saya meminta klarifikasi dari OP (lihat komentar pada pertanyaan). Saya pikir sebagian besar jawaban di sini akan menangani kesenjangan ok.
2

Haskell , 72 71 byte

h s|(a,x:b)<-span(<maximum s)s=map length[x:a,s]++h(reverse b++a)
h e=e

Cobalah online! Menemukan maksimum, membalikkannya ke belakang dan secara rekursif mengurutkan daftar yang tersisa.

Sunting: -1 byte berkat BMO

Laikoni
sumber
2

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, membalikkannya ke depan lalu membalikkan inversi dan membalikkan semuanya kembali ke posisi semula. Dan itu setara dengan bertukar inversi jadi saya tidak perlu membalikkan (yang canggung pada string karena akan membalikkan digit nilai yang dikonversi misalnya 12ke 21)

Ton Hospel
sumber
1

C # - 229

using System;using System.Linq;class P{static void Main(string[] a){
var n=a.ToList();Action<int>d=z=>{Console.Write(z+" ");n.Reverse(0,z);};
int c=n.Count;foreach(var s in n.OrderBy(x=>0-int.Parse(x))){
d(n.IndexOf(s)+1);d(c--);}}}

versi yang mudah dibaca

using System;
using System.Linq;
class P {
    static void Main(string[] a) {
        var n = a.ToList();
        Action<int> d = z => { Console.Write(z + " "); n.Reverse(0, z); };
        int c = n.Count;
        foreach (var s in n.OrderBy(x => 0 - int.Parse(x))) {
            d(n.IndexOf(s) + 1); d(c--);
        }
    }
}

sumber