快速Topswops计算

Question

来自AZSPCS：

假设你有一副包含n张卡片的牌。每一张卡片包含一个从1到n的数字，每个数字都出现在一张卡片上。你看上面卡片上的数字--让我们说它是k --然后反转最上面k卡的顺序。您继续这个过程--读取最上面的数字，然后反转相应的卡数--直到上面的卡片是1。

编写最快的程序来计算给定甲板的反转次数。请注意，如果您正在参加竞赛，则不允许您发布代码(因此，我还不会发布我的代码)。

Answer 1

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}

你把它递给甲板，就像这样：

f([3, 2, 1]) // 1
f([2, 3, 1]) // 2
f([1, 2, 3]) // 0

Answer 2

Scala：(这不是高尔夫-是吗？)

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)

有测试箱和秒表的完整应用，包括甲板的洗牌：

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

计数: 1000大小: 100持续时间: 1614毫秒机器:单奔腾M_2 2Ghz

Answer 3

Python，84个字符

无论如何打高尔夫球..。我用的是数字0到n-1。假设数组存储在变量x中，则需要84个字符的Python。

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

但是，由于内存滥用，性能非常差。