14
\$\begingroup\$

From AZSPCS:

Suppose you have a deck containing n cards. Each card contains a number from 1 to n, and each number appears on exactly one card. You look at the number on the top card -- let's says it's k -- and then reverse the order of the top k cards. You continue this procedure -- reading the top number and then reversing the corresponding number of cards -- until the top card is 1.

Write the fastest program to compute the number of reversals for a given deck. Note that if you are participating in the contest you are not allowed to post your code (and thus I will not post my code yet).

\$\endgroup\$
5
  • \$\begingroup\$ What is the input/output model? Any language restrictions? How will you determine how fast each entry is? \$\endgroup\$ Jan 28, 2011 at 2:24
  • \$\begingroup\$ There could be a dedicated stackexchange for azspcs ;) \$\endgroup\$
    – Eelvex
    Jan 30, 2011 at 23:22
  • \$\begingroup\$ So are we allowed to post solutions or not? \$\endgroup\$
    – AShelly
    Feb 9, 2011 at 16:25
  • \$\begingroup\$ Yes. The contest has finished. \$\endgroup\$
    – Alexandru
    Feb 13, 2011 at 11:42
  • \$\begingroup\$ The link to azspcs links to a page which is out of order. And it seems a meta-tag, which doesn't describe the puzzle. The tag should, perhaps, be removed. \$\endgroup\$ May 1, 2011 at 1:42

5 Answers 5

5
\$\begingroup\$

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}

You pass it the deck, like so:

f([3, 2, 1]) // 1
f([2, 3, 1]) // 2
f([1, 2, 3]) // 0
\$\endgroup\$
1
  • \$\begingroup\$ So you're the winner! :) \$\endgroup\$ May 1, 2011 at 1:33
3
\$\begingroup\$

Scala: (This isn't a golf - is it?)

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)

Complete application with testcase and stopwatch, including the shuffling of the 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)
}

count: 1000 size: 100 duration: 1614 msecs machine: Single Pentium M 2Ghz

\$\endgroup\$
3
\$\begingroup\$

Python, 84 Chars

Golfing anyway... I'm using the numbers 0 through n-1. Assuming the array is stored in a variable x, it takes me 84 chars of Python.

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

However, performance is pretty bad due to memory abuse.

\$\endgroup\$
1
\$\begingroup\$

Perl 5, 58 + 2 (-ap) = 60 bytes

++$\&&(@F[0..$F[0]-1]=reverse@F[0..$F[0]-1])while$F[0]-1}{

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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

deck is a pointer to an integer array representing the decks. n is the number of the cards. Obviously memory safety is the task of the caller.

It is probably nearing the fastest algorithm on recent computers and on a high-level language. Only with asm-level tricks could it be made faster, but not heavily even with them.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.