11
\$\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\$
  • \$\begingroup\$ What is the input/output model? Any language restrictions? How will you determine how fast each entry is? \$\endgroup\$ – aaaaaaaaaaaa Jan 28 '11 at 2:24
  • \$\begingroup\$ There could be a dedicated stackexchange for azspcs ;) \$\endgroup\$ – Eelvex Jan 30 '11 at 23:22
  • \$\begingroup\$ So are we allowed to post solutions or not? \$\endgroup\$ – AShelly Feb 9 '11 at 16:25
  • \$\begingroup\$ Yes. The contest has finished. \$\endgroup\$ – Alexandru Feb 13 '11 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\$ – user unknown May 1 '11 at 1:42
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\$
  • \$\begingroup\$ So you're the winner! :) \$\endgroup\$ – user unknown May 1 '11 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\$
2
\$\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\$
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\$
0
\$\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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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