3

Yet another installment of the weekly code-bowling game as the previous incarnation is over a week old and fairly well explored by now. As a refresher:

Code-Bowling is a challenge for writing the most obscure, unoptimized, horrific and bastardized code possible. Basically, the exact opposite of Code-Golf.

The Challenge:

Create a program that takes a sequence of numbers, and determines if they are in an ascending order.

Example:

$ ./myprogram 1 2 7 10 14
true

$ ./myprogram 7 2 0 1
false

Rules:

There really are none. It can be a console application, it can be a webpage, it can be whatever. It just needs to be a stand-alone program that accepts numbers and returns numbers. The format and methods are 100% up to you.

So have fun, and let's see the bastardized solutions you can come up with!

3
  • Hrmm. I can do this in best case O(n!) or worse. Easily. Jan 30, 2011 at 22:59
  • Hum, I think my solution is worst case O(n!). Not sure where I got n^2 from. I think I thought 1+2+3+4+... instead of 1*2*3*4*... but I'm digressing. Let's see your solution, then?
    – YSN
    Jan 30, 2011 at 23:09
  • 1
    codegolf.stackexchange.com, an SE site for code golf and similar programming challenges, is in private beta for three more days. Once it enters public beta, I strongly encourage you to post this type of question on that site.
    – Jon Purdy
    Jan 30, 2011 at 23:34

7 Answers 7

2

This uses something I call "Parent Sort". For list greater than size 1, you have to ask Mom or Dad about each pair of numbers. It's interesting because there's a chance that Mom might have you go ask Dad, and there's a bigger chance that Dad will have you go ask Mom. Could run forever assuming infinite stack capabilities.

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;
}
1
#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;
};
1

This solution has worst-case performance O(n!) and works by generating all possible permutations of the list, and then calculating a number (see the function 'value') that has it's minimum for sequential lists (ascending or descending).

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

Here's a quick one. Interestingly, it should still be pretty efficient, since it only iterates over the terms once. It can only work on numbers between 0 and 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";

It works by inverting the string (1 2 5 4 becomes 1 2 0 4 3, in other words, the number in the sequence becomes the key in the result, and the position in the sequence becomes the value. Then all we need to check is that 1 is in position 1.

And along the same lines (same theory, just set-theory operations):

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

This solution isn't unoptimised, but it is obscure, horrific, and bastardised...

/* 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

This (ab)uses the C compiler as it's runtime environment, or can be invoked with the following shell script for prettier output (relies on the above being in 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/'
0

First time I used dynamic programing to make things worse It has time and space complexity of 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;
    }
0

Yay, Python!

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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