Dalam tantangan pengoptimalan ini, Anda akan menulis sebuah program yang mengurutkan satu array dengan hanya membandingkan elemen melalui meminta pengguna di stdout untuk memasukkan hasil perbandingan pada stdin.
Protokol di bawah ini berbasis garis, jadi setiap kali Anda mencetak ke stdout atau membaca dari stdin, diasumsikan bahwa baris baru akan mengikuti. Sepanjang pertanyaan di bawah ini diasumsikan bahwa pengguna (baca: program penilaian) memiliki sebuah array yang ingin disortir dalam array yang diindeks berbasis 0 yang disebut array
. Untuk alasan teknis, saya sarankan pembilasan setelah setiap cetak menjadi gagah.
- Sebagai langkah pertama Anda, program Anda harus membaca ukuran array
n
dari stdin. - Kemudian, sesering yang Anda inginkan, Anda dapat mencetak
a < b
ke stdout, dengan dua bilangan bulat0 <= a, b < n
. Maka pengguna akan masuk1
dalam stdin jikaarray[a] < array[b]
, dan0
sebaliknya. Akhirnya, setelah program Anda yakin itu telah dengan benar menyimpulkan urutan array, itu harus mencetak
a ...
ke stdout, di mana...
adalah daftar spasi yang dipisahkan bilangan bulat yang menunjukkan urutan. Jadi jika program Anda menghasilkana 3 0 1 4 2
itu berarti program Anda telah menyimpulkanarray[3] <= array[0] <= array[1] <= array[4] <= array[2]
Perhatikan bahwa program Anda tidak pernah tahu isinya
array
, dan tidak akan pernah tahu.
Anda hanya bisa meminta <
pada stdin untuk mengurutkan array. Anda bisa mendapatkan operasi perbandingan lainnya dengan persamaan ini:
a > b b < a
a <= b !(b < a)
a >= b !(a < b)
a != b (a < b) || (b < a)
a == b !(a < b) && !(b < a)
Akhirnya, karena program Anda berinteraksi dengan program penilaian di stdout, cetak informasi debug ke stderr.
Program Anda akan dinilai menggunakan program Python berikut:
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)
Anda menilai program Anda dengan mengetik python score.py yourprogram
. Penilaian dilakukan dengan meminta program Anda mengurutkan satu array acak dari setiap ukuran 0 hingga 100 dan menghitung jumlah perbandingan yang diminta oleh program Anda. Array acak ini dapat memiliki duplikat , algoritme Anda harus dapat menangani elemen yang sama. Jika ada duplikat, tidak ada persyaratan pada urutan elemen yang sama. Jadi jika arraynya [0, 0]
tidak masalah apakah Anda output a 0 1
atau a 1 0
.
Anda tidak dapat mengoptimalkan secara spesifik untuk array tertentu yang dihasilkan oleh program penilaian. Saya dapat mengubah benih RNG kapan saja. Jawaban yang menggunakan algoritme penyortiran bawaan diizinkan untuk diposting demi kepentingan, tetapi tidak bersaing.
Program dengan kemenangan skor terendah.
Jawaban:
Python, skor 23069
Ini menggunakan algoritma sorting penyisipan gabungan Ford-Johnson.
sumber
Python 3, skor 28462
Sortir cepat. Pivot adalah item paling kiri.
Skor diharapkan, karena:
Skor untuk setiap ukuran yang diuji:
sumber
Python 2 (non-bersaing), skor 23471
Skor untuk setiap ukuran yang diuji:
sumber
Python, skor 333300
Ini adalah contoh program, mengimplementasikan bentuk paling sederhana dari bubbleort, selalu melakukan
n*(n-1)
perbandingan per larik.Saya mencetak program ini dengan menyimpannya sebagai
sort.py
dan mengetikpython score.py python sort.py
.sumber
print
melihat seperti fungsi.