Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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()
Advertisement
Add Comment
Please, Sign In to add comment