8
In this optimization challenge you will write a program that sorts a single array by only comparing elements through asking the user on stdout to input comparison results on stdin.
The below protocol is line-based, so everytime you print to stdout or read from stdin it is assumed a newline follows. Throughout the question below it is assumed that the user (read: the scoring program) has an array it wants sorted in a 0-based indexed array called array
. For technical reasons I suggest flushing after every print to stout.
- As your first step your program must read the array size
n
from stdin. - Then, as often as you wish, you can print
a < b
to stdout, with two integers0 <= a, b < n
. Then the user will enter1
in stdin ifarray[a] < array[b]
, and0
otherwise. Finally, once your program is convinced it has correctly deduced the order of the array, it must print
a ...
to stdout, where...
is a space separated list of integers indicating the order. So if your program outputsa 3 0 1 4 2
it means your program has deducedarray[3] <= array[0] <= array[1] <= array[4] <= array[2]
Note that your program never knew the contents of
array
, and never will.
You can only ask for <
on stdin to sort the array. You can get other comparison operations by these equivalencies:
a > b b < a
a <= b !(b < a)
a >= b !(a < b)
a != b (a < b) || (b < a)
a == b !(a < b) && !(b < a)
Finally, since your program interacts with the scoring program on stdout, print debug information to stderr.
Your program will be scored using the following Python program:
from __future__ import print_function
from subprocess import Popen, PIPE
import sys, random
def sort_test(size):
array = [random.randrange(0, size) for _ in range(size)]
pipe = Popen(sys.argv[1:], stdin=PIPE, stdout=PIPE, bufsize=0, universal_newlines=True)
print(str(size), file=pipe.stdin); pipe.stdin.flush()
num_comparisons = 0
while True:
args = pipe.stdout.readline().strip().split()
if args and args[0] == "a":
answer_array = [array[int(n)] for n in args[1:]]
if list(sorted(array)) != answer_array:
raise RuntimeError("incorrect sort for size {}, array was {}".format(size, array))
return num_comparisons
elif len(args) == 3 and args[1] == "<":
a, b = int(args[0]), int(args[2])
print(int(array[a] < array[b]), file=pipe.stdin); pipe.stdin.flush()
num_comparisons += 1
else:
raise RuntimeError("unknown command")
random.seed(0)
total = 0
for i in range(101):
num_comparisons = sort_test(i)
print(i, num_comparisons)
total += num_comparisons
print("total", total)
You score your program by typing python score.py yourprogram
. The scoring is done by having your program sort one random array of each size 0 to 100 and counting the amount of comparisons your program asks for. These random arrays can have duplicates, your algorithm must be able to handle equal elements. In the event there are duplicates, there are no requirements on the order of the equal elements. So if the array is [0, 0]
it doesn't matter if you output a 0 1
or a 1 0
.
You may not optimize specifically for the particular arrays the scoring program generates. I may change the RNG seed at any point in time. Answers using built-in sorting algorithms are permitted to be posted for interest's sake, but are non-competing.
Program with lowest score wins.
1Which version of Python are you using? – Leaky Nun – 2016-07-20T14:23:14.330
How long did it take to run your scoring algorithm? – Leaky Nun – 2016-07-20T14:40:17.747
What assumptions can we make on the maximum size of the input array? – helloworld922 – 2016-07-21T00:29:33.207
@helloworld922 Theoretically, none - your answer should work for any size. But if it saves effort in a language like C supporting everything up to and include 100 elements is required. – orlp – 2016-07-21T00:44:04.773
It’s important to clarify the Python version used by the scoring program, because Python 2 and 3 generate different random sequences. Or perhaps it would be better if the randomness came from a well-specified deterministic source such as hashlib. – Anders Kaseorg – 2016-07-21T07:35:07.743