megasort/main.py

from functools import partial
import random


class Cell(object):
    def __init__(self):
        self.is_set = False
        self.value = None

    def set(self, x):
        self.is_set = True
        self.value = x


class Merge(object):
    def __init__(self, xs, ys, on_complete):
        self.xs = xs[:]
        self.ys = ys[:]
        self.output = []
        self.on_complete = on_complete
        self.running = True

        self.settle()

    def touch(self):
        # print(f"Touching: {self}")
        if ask(self.xs[0], self.ys[0]):
            self.output.append(self.xs.pop(0))
        else:
            self.output.append(self.ys.pop(0))

        self.settle()

    def settle(self):
        if len(self.xs) == 0:
            self.output += self.ys
            self.ys = []
            self.complete()
            return

        if len(self.ys) == 0:
            self.output += self.xs
            self.xs = []
            self.complete()
            return

    def complete(self):
        self.on_complete(self.output)
        self.running = False

    def __repr__(self):
        return f"Merge({self.xs}, {self.ys}, {self.output})"


def _sort(xs, merges, on_complete):
    if len(xs) < 2:
        on_complete(xs[:])
        return

    half = len(xs) // 2
    fst = xs[:half]
    snd = xs[half:]
    sorted_fst = Cell()
    sorted_snd = Cell()

    def cb(setter, value):
        setter(value)
        if sorted_fst.is_set and sorted_snd.is_set:
            new_merge = Merge(sorted_fst.value, sorted_snd.value, on_complete)
            merges.append(new_merge)

    _sort(fst, merges, partial(cb, sorted_fst.set))
    _sort(snd, merges, partial(cb, sorted_snd.set))


def merge_sort(xs):
    merges = []
    result = Cell()
    _sort(xs, merges, result.set)

    while True:
        # replace in place
        for i in reversed(range(len(merges))):
            if not merges[i].running:
                merges.pop(i)

        if len(merges) == 0:
            break

        # print(f"Number of ongoing merges: {merges}")
        # print(f"Number of ongoing merges: {len(merges)}")
        random.shuffle(merges)
        for m in merges[:]:
            m.touch()

    assert result.is_set
    return result.value


TRUTHY = "y yes 1 t true aye left up top first p".split()
FALSEY = "n no 0 2 f false nay right down bottom second nil".split()


def ask(x, y):
    if random.choice([False, True]):
        yes_result = True
        a, b = x, y
    else:
        yes_result = False
        a, b = y, x

    while True:
        choice = input(f"Is {a} better than {b}? ")
        if choice in TRUTHY:
            return yes_result

        if choice in FALSEY:
            return not yes_result

        print(f"Huh? I didn't understand {choice}. Answer \"y\" or \"n\".")


def main():
    with open("input.txt", "rt") as f_in:
        lines_in = [i.strip() for i in f_in.read().split("\n") if i.strip()]

    random.shuffle(lines_in)
    results = merge_sort(lines_in)

    with open("output.txt", "wt") as f_out:
        f_out.write("\n".join(results))


if __name__ == '__main__':
    main()