创建一个应用程序来确定数字序列是否已排序

Question

每周的代码保龄球游戏的另一部分与前一个版本一样已经有一周多了，到目前为止已经得到了很好的探索。回顾一下：

Code-Bowling 是一项挑战 写出最晦涩、未经优化的内容， 可怕且混蛋的代码 可能的。基本上，准确的 与代码高尔夫相反。

挑战：

创建一个程序，接受一系列数字，并确定它们是否按升序排列。

示例：

$ ./myprogram 1 2 7 10 14
true

$ ./myprogram 7 2 0 1
false

规则：

确实没有。它可以是控制台应用程序，可以是网页，可以是任何东西。它只需要是一个接受数字并返回数字的独立程序。格式和方法100%由您决定。

所以玩得开心，让我们看看你能想出的混蛋解决方案！

Answer 1

这使用了我称之为“父排序”的东西。对于大于 1 的列表，您必须向妈妈或爸爸询问每对数字。这很有趣，因为妈妈有可能让你去问爸爸，而爸爸让你去问妈妈的可能性更大。假设无限的堆栈功能可以永远运行。

function askMom($num1, $num2) {
    $chance = mt_rand(0,2);
    if ($chance>1) {
        return askDad($num1, $num2);
    } else {
        return $num1 <= $num2;
    }
}
function askDad($num1, $num2) {
    $chance = mt_rand(0,4);
    if ($chance>1) {
        return askMom($num1, $num2);
    } else {
        return $num1 <= $num2;
    }
}

function parentSort(array $numbers) {
    for ($i = 0; $i < count($numbers)-1; $i++) {
        $chance = mt_rand(0,1);
        if ($chance) {
            if (askMom($numbers[$i], $numbers[$i+1])) {

            } else {
                return false;
            }
        } else {
            if (askDad($numbers[$i], $numbers[$i+1])) {

            } else {
                return false;
            }
        }
    }

    return true;
}

Answer 2

#include <stdlib.h>
#include <stdio.h>

int main(int argc, char** argv){
    int a, b;
    if (argc > 2){
        sscanf(argv[1], "%d", &a);
        sscanf(argv[2], "%d", &b);
        if (a<=b) 
            return main(argc-1, argv+1);
        printf("false");
        exit(0);
    };
    printf("true");
    return 0;
};

Answer 3

该解决方案的最坏情况性能为 O(n!)，其工作原理是生成列表的所有可能排列，然后计算一个数字（请参阅函数“值”），该数字具有顺序列表（升序或降序）的最小值。

def value(list):
    sum = 0
    for i in range(len(list)-1):
        sum = sum + (list[i]-list[i+1])**2.0
    return sum

def drop(lst, i):
     if i + 1 >= len(lst):
         return lst[:i]
     else:
         return lst[:i] + lst[i+1:]

class list_permute:
    def __init__(self, lst):
        self.lst = lst
        self.i = -1
        self.subiter = None
    def __iter__(self):
        return self
    def next(self):
        if len(self.lst) == 1:
            if self.i == -1:
                self.i = self.i + 1
                return self.lst
            else:
                raise StopIteration()

        if self.subiter != None:
            try:
                return [self.lst[self.i]] + self.subiter.next()
            except StopIteration:
                self.subiter = None

        if self.subiter == None:
            self.i = self.i + 1
            if self.i >= len(self.lst):
                raise StopIteration()
            else:
                self.subiter = list_permute(drop(self.lst, self.i))
            return self.next()

def test(list):
    given = value(list)
    for i in list_permute(list):
        if value(i) < given:
            return False

    # Test for false positive
    if list[0] > list[len(list)-1]:
        return False
    return True

list = []
print "Feed me your numbers (end with ^C)"
try:
    while True:
        try:
            list.append(int(raw_input()))
        except ValueError:
            print "NaN"
except (KeyboardInterrupt, EOFError):
    pass

print test(list)

Answer 4

这是一个快速的。有趣的是，它应该仍然非常有效，因为它只迭代这些术语一次。它只能处理 0 到 255 之间的数字...

array_shift($argv);
$str = str_repeat(chr(0), 256);
foreach ($argv as $key => $element) {
    $str[(int) $element] = chr($key + 1);
}
$str = str_replace(chr(0), '', $str);
$hex = unpack('H*', $str);
for ($i = 1; $i < strlen($str); $i++) {
    if (substr($hex[1], $i * 2 - 2, 2) != dechex($a)) {
        echo "False\n";
        die();
    }
}
echo "True\n";

它的工作原理是反转字符串（1 2 5 4 变为 1 2 0 4 3，换句话说，序列中的数字成为结果中的键，序列中的位置成为值然后我们需要检查的是 1 是否位于位置 1 中

。沿着同样的思路（相同的理论，只是集合论运算）：

array_shift($argv);
$vals = array_flip($argv);
ksort($vals);
echo array_values($vals) == range(0, count($vals) - 1) ? "True\n" : "False\n";

Answer 5

这个解决方案并不是未经优化的，但它是晦涩的、可怕的和混蛋的......

/* Either #define macros FIRST, SECOND, THIRD, etc. here, or do so on the
 * command line when "compiling" i.e.
 * $ gcc -D FIRST=1 -D SECOND=5 -D THIRD=42
 */

#define min(X, Y) ((X) < (Y) ? (X) : (Y))

#define pairsorted(X, Y) (min((X), (Y)) == (X) ? 1 : 0)

#if defined (FIRST) && defined (SECOND) && pairsorted(FIRST, SECOND)
#if defined (THIRD) && pairsorted(SECOND, THIRD)
#if defined (FOURTH) && pairsorted (THIRD, FOURTH)
#if defined (FIFTH) && pairsorted (FOURTH, FIFTH)
#error "Sorted!"
#elif !defined (FIFTH)
#error "Sorted!"
#else /* FIFTH is defined and < FOURTH */
#error "Not sorted!"
#endif /* FIFTH */

#elif !defined (FOURTH)
#error "Sorted!"
#else /* FOURTH is defined and < THIRD */
#error "Not sorted!"
#endif /* FOURTH */

#elif !defined (THIRD)
#error "Sorted!"
#else /* THIRD is defined and < SECOND */
#error "Not sorted!"
#endif /* THIRD */

#elif !defined (SECOND)
#error "Sorted!"
#else /* SECOND is defined and < FIRST */
#error "Not sorted!"
#endif /* SECOND */

#ifndef SECOND
#error "I need at least two values to compare"
#endif

这个（ab）使用C编译器作为它的运行时环境，或者可以使用以下shell脚本调用以获得更漂亮的输出（依赖于上面的内容）在sortedcpp.c中）：

#!/bin/bash

ORDINALS=(ZEROTH FIRST SECOND THIRD FOURTH FIFTH)
VALUES=(0 $@)

for i in 1 2 3 4 5; do
  if [ $i -le $# ]
    then
      flags="$flags -D ${ORDINALS[$i]}=${VALUES[$i]}"
  fi
done

output=`gcc $flags sortedcpp.c 2>&1`

echo $output | sed -e 's/sortedcpp.c:[0-9]*: error: #error \"\(.*\)\"/\1/'

Answer 6

我第一次使用动态规划让事情变得更糟
它的时间和空间复杂度为 O(n²)

    #include <stdio.h>
    int main (int argc, char **argv)
    {
      int is_ordered[1000][1000];
      int list[1000];
      int i,j;

      for(i = 1; i < argc; i++)
        sscanf(argv[i],"%d", &list[i-1]);

      for (i = 0; i < argc -2; i++)
      {
        if (list[i] < list[i+1])
          is_ordered[i][i+1] = 1;
        else
          is_ordered[i][i+1] = 0;
      }

      for (i = 2; i < argc -1; i++)
        for (j = 0; j < (argc - 1 - i); j++)
        {
          if (is_ordered[j+1][i+j] && is_ordered[j][i+j-1])
            is_ordered[j][j+i] = 1;
          else
            is_ordered[j][j+i] = 0;
        }

      if(is_ordered[0][argc-2])
        printf("True\n");
      else
        printf("False\n");
      return 0;
    }

Answer 7

耶，Python！

def IsSorted(lst):
    return sorted(lst) == lst