Vertailut

Sinulle annetaan olio, jonka sisällä on luvuista 1,2,\dots,n muodostuva lista. Tehtäväsi on päätellä listan sisältö. Et voi kuitenkaan kysyä oliolta suoraan, mikä luku on missäkin listan kohdassa.

Voit tehdä oliolle kyselyjä, joissa kysyt kahden listan luvun suuruusjärjestystä. Voit tehdä enintään n \lfloor \log_2 n \rfloor kyselyä, minkä jälkeen tiedossasi tulee olla listan sisältö. Tässä \lfloor \cdots \rfloor tarkoittaa pyöristystä alaspäin kokonaisluvuksi. Esimerkiksi kun n=6, voit tehdä enintään 6 \cdot \lfloor \log_2 6 \rfloor = 12 kyselyä.

Toteuta tiedostoon comparisons.py funktio find_list, jolle annetaan parametrina olio. Funktion tulee palauttaa listan sisältö. Olion metodi list_size antaa listan koon. Metodi smaller(a, b) palauttaa True tarkalleen silloin, kun kohdassa a oleva luku on pienempi kuin kohdassa b oleva luku.

Funktiota testataan erilaisissa tapauksissa, joissa n on välillä 1 \dots 20. Funktion tulee toimia tehokkaasti kaikissa näissä tapauksissa.

Tehtäväpohjassa on esimerkki luokan Comparator toteutuksesta. Voit testata koodiasi tämän luokan avulla, mutta palvelimella luokan sisäinen toteutus on erilainen. Saat käyttää tehtävän ratkaisussa vain tässä kuvattuja olion metodeja etkä saa yrittää selvittää olion sisältöä muulla tavalla.

import math

class Comparer:
    def __init__(self, numbers):
        self.numbers = numbers
        self.counter = 0
        n = len(self.numbers)
        self.bound = n * math.floor(math.log2(n))

    def list_size(self):
        return len(self.numbers)

    def smaller(self, a, b):
        self.counter += 1
        if self.counter > self.bound:
            raise RuntimeError("too many comparisons")
        return self.numbers[a] < self.numbers[b]

def find_list(comparer):
    # TODO

if __name__ == "__main__":
    comparer = Comparer([3, 1, 2, 4])
    numbers = find_list(comparer)
    print(numbers) # [3, 1, 2, 4]

    comparer = Comparer([1, 6, 2, 5, 3, 4])
    numbers = find_list(comparer)
    print(numbers) # [1, 6, 2, 5, 3, 4]