Perhitungan Topswops cepat

11

Dari AZSPCS :

Misalkan Anda memiliki setumpuk yang berisi kartu n. Setiap kartu berisi angka dari 1 hingga n, dan setiap nomor muncul tepat pada satu kartu. Anda melihat nomor di kartu atas - katakan saja k - dan kemudian membalik urutan kartu k atas. Anda melanjutkan prosedur ini - membaca nomor atas dan kemudian membalikkan jumlah kartu yang sesuai - sampai kartu teratas adalah 1.

Tulis program tercepat untuk menghitung jumlah pembalikan untuk setumpuk yang diberikan. Perhatikan bahwa jika Anda berpartisipasi dalam kontes Anda tidak diperbolehkan memposting kode Anda (dan dengan demikian saya belum akan memposting kode saya).

code-challenge fastest-code Alexandru
sumber
Apa model input / output? Adakah batasan bahasa? Bagaimana Anda menentukan seberapa cepat setiap entri?
aaaaaaaaaaaa
Mungkin ada pertukaran stack khusus untuk azspcs;)
Eelvex
Jadi, apakah kita boleh mengirim solusi atau tidak?
AShelly
Iya. Kontes telah selesai.
Alexandru
Tautan ke azspcs menautkan ke halaman yang rusak. Dan itu sepertinya meta-tag, yang tidak menggambarkan teka-teki itu. Tag harus, mungkin, dihapus.
pengguna tidak diketahui

Jawaban:

5

JavaScript

function(d){for(t=0;x=(n=d[0])-1;t++)for(i=0;i<n/2;i++){m=d[x-i];d[x-i]=d[i];d[i]=m}return t}

Anda memberikannya, seperti:

f([3, 2, 1]) // 1
f([2, 3, 1]) // 2
f([1, 2, 3]) // 0
Ry-
sumber
Jadi kamu pemenangnya! :)
pengguna tidak diketahui
3

Scala: (Ini bukan golf - kan?)

def transform (l: List[Int], sofar: Int = 0) : Int =
  if (l(0) == 1) sofar else transform (l.take (l(0)).reverse ::: l.drop (l(0)), sofar + 1)

Aplikasi lengkap dengan testcase dan stopwatch, termasuk pengocokan Deck:

object DeckReverse extends Application {

  def transform (l: List[Int], sofar: Int = 0) : Int = 
    if (l(0) == 1) sofar else transform (l.take (l(0)).reverse ::: l.drop (l(0)), sofar + 1)

  def stopwatch (count: Int, size: Int) = {
    val li = (1 until size).toList 
    val r = util.Random 

    val start = System.currentTimeMillis ()
    (0 until count).foreach (_ => transform (r.shuffle (li)))
    val stop = System.currentTimeMillis ()

    println ("count: " + count + "\tsize: " + size + "\tduration: " + (stop - start) + " msecs") 
  }

  stopwatch (1000, 100)
}

hitung: 1000 ukuran: 100 durasi: 1614 msecs mesin: Single Pentium M 2Ghz

Pengguna tidak diketahui
sumber
2

Python, 84 Chars

Tetap main golf ... Saya menggunakan angka 0 hingga n-1. Dengan asumsi array disimpan dalam variabel x, dibutuhkan saya 84 karakter Python.

while x[0]:x[:x[0]+1]=x[x[0]::-1]

Namun, kinerjanya sangat buruk karena penyalahgunaan memori.

stan
sumber
0

C

int revno(int* deck, int n) {
  int k,j,r=0;
  for(;;) {
    k=*deck;
    if (k==1) {
      return r;
    }
    for (j=0; j<k/2; j++) {
      int tmp=deck[j];
      deck[j]=deck[k-j];
      deck[k-j]=tmp;
    }
    r++;
  }
}

deckadalah pointer ke array integer yang mewakili deck. nadalah jumlah kartu. Jelas keamanan memori adalah tugas si penelepon.

Mungkin mendekati algoritma tercepat pada komputer terbaru dan pada bahasa tingkat tinggi. Hanya dengan trik tingkat asm yang bisa dibuat lebih cepat, tetapi tidak dengan mereka.

peterh - Pasang kembali Monica
sumber