Cálculo rápido de Topswops

11

De AZSPCS :

Supongamos que tienes una baraja que contiene n cartas. Cada tarjeta contiene un número del 1 al n, y cada número aparece exactamente en una tarjeta. Observa el número en la tarjeta superior, digamos que es k, y luego invierte el orden de las tarjetas k superiores. Continúa este procedimiento, leyendo el número superior y luego invirtiendo el número correspondiente de tarjetas, hasta que la tarjeta superior sea 1.

Escriba el programa más rápido para calcular el número de reversiones para un mazo dado. Tenga en cuenta que si participa en el concurso no puede publicar su código (y, por lo tanto, no lo publicaré aún).

code-challenge fastest-code Alexandru
fuente
¿Cuál es el modelo de entrada / salida? ¿Alguna restricción de idioma? ¿Cómo determinará qué tan rápido es cada entrada?
aaaaaaaaaaaa
Podría haber un intercambio de pila dedicado para azspcs;)
Eelvex
Entonces, ¿podemos publicar soluciones o no?
AShelly
Si. El concurso ha terminado.
Alexandru
El enlace a azspcs enlaza a una página que está fuera de servicio. Y parece una metaetiqueta, que no describe el rompecabezas. La etiqueta debería, quizás, ser eliminada.
usuario desconocido

Respuestas:

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}

Pasas el mazo, así:

f([3, 2, 1]) // 1
f([2, 3, 1]) // 2
f([1, 2, 3]) // 0
Ry-
fuente
¡Entonces eres el ganador! :)
usuario desconocido
3

Scala: (Esto no es un golf, ¿verdad?)

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)

Aplicación completa con caso de prueba y cronómetro, incluido el barajado de la cubierta:

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

recuento: 1000 tamaño: 100 duración: 1614 ms máquina: Single Pentium M 2Ghz

usuario desconocido
fuente
2

Python, 84 caracteres

Golfing de todos modos ... Estoy usando los números del 0 al n-1. Suponiendo que la matriz se almacena en una variable x, me lleva 84 caracteres de Python.

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

Sin embargo, el rendimiento es bastante malo debido al abuso de memoria.

boothby
fuente
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++;
  }
}

deckes un puntero a una matriz entera que representa los mazos. nEs el número de las cartas. Obviamente, la seguridad de la memoria es tarea de la persona que llama.

Probablemente se está acercando al algoritmo más rápido en computadoras recientes y en un lenguaje de alto nivel. Solo con trucos de nivel asm podría hacerse más rápido, pero no mucho incluso con ellos.

peterh - Restablece a Monica
fuente