Calcul rapide de Topswops

11

De AZSPCS :

Supposons que vous ayez un deck contenant n cartes. Chaque carte contient un numéro de 1 à n, et chaque numéro apparaît sur exactement une carte. Vous regardez le nombre sur la carte du haut - disons que c'est k - puis inversez l'ordre des k premières cartes. Vous continuez cette procédure - en lisant le premier numéro puis en inversant le nombre de cartes correspondant - jusqu'à ce que la première carte soit 1.

Écrivez le programme le plus rapide pour calculer le nombre de retournements pour un jeu donné. Notez que si vous participez au concours, vous n'êtes pas autorisé à publier votre code (et donc je ne publierai pas encore mon code).

code-challenge fastest-code Alexandru
la source
Quel est le modèle d'entrée / sortie? Des restrictions linguistiques? Comment déterminerez-vous la vitesse de chaque entrée?
aaaaaaaaaaaa
Il pourrait y avoir un échange de pile dédié pour azspcs;)
Eelvex
Alors, sommes-nous autorisés à publier des solutions ou non?
AShelly
Oui. Le concours est terminé.
Alexandru
Le lien vers azspcs renvoie à une page qui est en panne. Et cela semble être une méta-étiquette, qui ne décrit pas le puzzle. La balise devrait peut-être être supprimée.
utilisateur inconnu

Réponses:

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}

Vous passez le pont, comme ça:

f([3, 2, 1]) // 1
f([2, 3, 1]) // 2
f([1, 2, 3]) // 0
Ry-
la source
Vous êtes donc le gagnant! :)
utilisateur inconnu
3

Scala: (Ce n'est pas un golf - n'est-ce pas?)

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)

Application complète avec testcase et chronomètre, y compris le brassage du 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)
}

nombre: 1000 taille: 100 durée: 1614 ms machine: Pentium M 2Ghz simple

Utilisateur inconnu
la source
2

Python, 84 caractères

Golf quand même ... J'utilise les chiffres de 0 à n-1. En supposant que le tableau est stocké dans une variable x, cela me prend 84 caractères de Python.

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

Cependant, les performances sont assez mauvaises en raison d'un abus de mémoire.

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

deckest un pointeur sur un tableau entier représentant les ponts. nest le nombre de cartes. Évidemment, la sécurité de la mémoire est la tâche de l'appelant.

Il s'approche probablement de l'algorithme le plus rapide sur les ordinateurs récents et sur un langage de haut niveau. Ce n'est qu'avec des tours de niveau asm que cela pourrait être fait plus rapidement, mais pas lourdement, même avec eux.

peterh - Réintégrer Monica
la source