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()
Comments