from json import dumps
from time import perf_counter
from array import array
import requests


class Session:
    def __init__(self, session: int):
        base_url = "https://cc.the-morpheus.de/"
        self.__challenge = base_url + f'challenges/{session}/'
        self.__solution = base_url + f'solutions/{session}/'

    def get(self):
        with requests.session() as session:
            return session.get(self.__challenge)

    def post(self, data=None, json=None):
        with requests.session() as session:
            return session.post(self.__solution, data=data, json=json)


class Node:
    def __init__(self, value, index):
        self.left_child: Node = None
        self.right_child: Node = None
        self.value = value
        self.index = index


class Tree:
    def __init__(self):
        self.root: Node = None

    def insert(self, value, index):
        if self.root is None:
            self.root = Node(value, index)
        else:
            self._insert(value, index, self.root)

    def _insert(self, value, index, node: Node):
        if value < node.value:
            if node.left_child is None:
                node.left_child = Node(value, index)

            self._insert(value, index, node.left_child)

        if value > node.value:
            if node.right_child is None:
                node.right_child = Node(value, index)

            self._insert(value, index, node.right_child)

    def exists(self, value) -> bool:
        if self.root is None:
            return False

        return self._exists(value, self.root)

    def _exists(self, value, node: Node) -> bool:
        if value == node.value:
            return True

        if value < node.value:
            if node.left_child is None:
                return False

            return self._exists(value, node.left_child)

        if value > node.value:
            if node.right_child is None:
                return False

            return self._exists(value, node.right_child)

    def get_index(self, value):
        if self.root is None:
            return None

        return self._get_index(value, self.root)

    def _get_index(self, value, node: Node):
        if value == node.value:
            return node.index

        if value < node.value:
            if node.left_child is None:
                return None

            return self._get_index(value, node.left_child)

        if value > node.value:
            if node.right_child is None:
                return None

            return self._get_index(value, node.right_child)

    def sort(self) -> []:
        if self.root is None:
            yield (-1, -1)
        yield from self._sort(self.root)

    def _sort(self, node: Node) -> []:
        if node.left is not None:
            yield from self._sort(node.left)

        yield (node.value, node.index)

        if node.right is not None:
            yield from self._sort(node.right)


class Solver:
    @staticmethod
    def solve_with_tree(numbers, target):
        candidate: int = target // 2 if target % 2 == 0 else -1
        my_tree = Tree()

        for index, number in enumerate(numbers):
            if number > target:
                continue

            if number == candidate:
                return [index, index]

            if my_tree.exists(target - number):
                return [my_tree.get_index(target - number), index]

            if not my_tree.exists(number):
                my_tree.insert(number, index)

        return [-1, -1]

    @staticmethod
    def solve_with_array(numbers, target):
        table = array('i', [-1 for _ in range(target + 1)])
        candidate: int = target // 2 if target % 2 == 0 else -1

        for index, number in enumerate(numbers):
            if number > target:
                continue
            if number == candidate:
                return [index, index]
            diff = table[target - number]
            if diff >= 0 and numbers[diff] + number == target:
                return [diff, index]
            if table[number] < 0:
                table[number] = index

        return [-1, -1]

    @staticmethod
    def solve_with_list(numbers, target):
        table = [-1 for _ in range(target + 1)]
        candidate: int = target // 2 if target % 2 == 0 else -1

        for index, number in enumerate(numbers):
            if number > target:
                continue
            if number == candidate:
                return [index, index]
            diff = table[target - number]
            if diff >= 0 and numbers[diff] + number == target:
                return [diff, index]
            if table[number] < 0:
                table[number] = index

        return [-1, -1]

    @staticmethod
    def solve_with_dictionary(numbers, target):
        table = {}
        candidate = target // 2 if target % 2 == 0 else -1
        for index, number in enumerate(numbers):
            if number > target:
                continue

            if number == candidate:
                return [index, index]

            if (target - number) in table:
                return [table[target - number], index]

            if number not in table:
                table[number] = index

        return [-1, -1]


def solver(session: Session):
    json_get = session.get().json()
    k = json_get['k']
    lst = json_get['list']

    t = perf_counter()
    ret_tree = Solver.solve_with_tree(lst, k)
    elapsed_time_tree = perf_counter() - t

    t = perf_counter()
    ret_list = Solver.solve_with_list(lst, k)
    elapsed_time_list = perf_counter() - t

    t = perf_counter()
    ret_dictionary = Solver.solve_with_dictionary(lst, k)
    elapsed_time_dictionary = perf_counter() - t

    t = perf_counter()
    ret_array = Solver.solve_with_array(lst, k)
    elapsed_time_array = perf_counter() - t

    if ret_list == ret_dictionary == ret_array == ret_tree:
        param = dumps({"token": ret_dictionary})
        response = session.post(data=param)
        if response.text != "Success":
            raise ValueError("Inkorrekte Lösung")

        print(f'{response.text:10}: {ret_dictionary}')
        print(f'Dictionary: {elapsed_time_dictionary * 1000:06.5f} ms')
        print(f'List:       {elapsed_time_list * 1000:06.5f} ms')
        print(f'Array:      {elapsed_time_array * 1000:06.5f} ms')
        print(f'Tree:       {elapsed_time_tree * 1000:06.5f} ms')
    else:
        raise ValueError("Werte stimmen nicht überein!")


mySession = Session(7)
while True:
    solver(mySession)
    print()