Schnelle Topswops-Berechnung

11

Von AZSPCS :

Angenommen, Sie haben ein Deck mit n Karten. Jede Karte enthält eine Zahl von 1 bis n, und jede Zahl erscheint auf genau einer Karte. Sie sehen sich die Zahl auf der obersten Karte an - sagen wir, es ist k - und kehren dann die Reihenfolge der obersten k Karten um. Sie setzen diesen Vorgang fort - lesen Sie die oberste Zahl und kehren Sie dann die entsprechende Anzahl von Karten um - bis die oberste Karte 1 ist.

Schreiben Sie das schnellste Programm, um die Anzahl der Umkehrungen für ein bestimmtes Deck zu berechnen. Beachten Sie, dass Sie Ihren Code nicht veröffentlichen dürfen, wenn Sie am Wettbewerb teilnehmen (und ich meinen Code daher noch nicht veröffentlichen werde).

code-challenge fastest-code Alexandru
quelle
Was ist das Eingabe- / Ausgabemodell? Irgendwelche Sprachbeschränkungen? Wie bestimmen Sie, wie schnell jeder Eintrag ist?
aaaaaaaaaaa
Es könnte einen dedizierten Stack-Austausch für Azspcs geben;)
Eelvex
Dürfen wir also Lösungen posten oder nicht?
AShelly
Ja. Der Wettbewerb ist beendet.
Alexandru
Der Link zu azspcs verweist auf eine Seite, die nicht in Ordnung ist. Und es scheint ein Meta-Tag zu sein, das das Rätsel nicht beschreibt. Das Tag sollte möglicherweise entfernt werden.
Benutzer unbekannt

Antworten:

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}

Sie übergeben es dem Deck, wie folgt:

f([3, 2, 1]) // 1
f([2, 3, 1]) // 2
f([1, 2, 3]) // 0
Ry-
quelle
Du bist also der Gewinner! :)
Benutzer unbekannt
3

Scala: (Dies ist kein Golf - oder?)

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)

Komplette Anwendung mit Testfall und Stoppuhr, einschließlich des Mischens des Decks:

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)
}

Anzahl: 1000 Größe: 100 Dauer: 1614 ms Maschine: Single Pentium M 2Ghz

Benutzer unbekannt
quelle
2

Python, 84 Zeichen

Golfen sowieso ... Ich benutze die Zahlen 0 bis n-1. Angenommen, das Array ist in einer Variablen x gespeichert, benötige ich 84 Zeichen Python.

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

Die Leistung ist jedoch aufgrund von Speichermissbrauch ziemlich schlecht.

Standby
quelle
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++;
  }
}

deckist ein Zeiger auf ein Integer-Array, das die Decks darstellt. nist die Anzahl der Karten. Offensichtlich ist die Speichersicherheit die Aufgabe des Anrufers.

Es nähert sich wahrscheinlich dem schnellsten Algorithmus auf neueren Computern und in einer Hochsprache. Nur mit Tricks auf Asm-Level konnte es schneller gemacht werden, aber auch mit ihnen nicht schwer.

Peter - Setzen Sie Monica wieder ein
quelle