MBrendecke

The Morpheus Tutorials - Coding Challange 7 - PY

Aug 22nd, 2018
667
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 6.60 KB | None | 0 0
  1. from json import dumps
  2. from time import perf_counter
  3. from array import array
  4. import requests
  5.  
  6.  
  7. class Session:
  8.     def __init__(self, session: int):
  9.         base_url = "https://cc.the-morpheus.de/"
  10.         self.__challenge = base_url + f'challenges/{session}/'
  11.         self.__solution = base_url + f'solutions/{session}/'
  12.  
  13.     def get(self):
  14.         with requests.session() as session:
  15.             return session.get(self.__challenge)
  16.  
  17.     def post(self, data=None, json=None):
  18.         with requests.session() as session:
  19.             return session.post(self.__solution, data=data, json=json)
  20.  
  21.  
  22. class Node:
  23.     def __init__(self, value, index):
  24.         self.left_child: Node = None
  25.         self.right_child: Node = None
  26.         self.value = value
  27.         self.index = index
  28.  
  29.  
  30. class Tree:
  31.     def __init__(self):
  32.         self.root: Node = None
  33.  
  34.     def insert(self, value, index):
  35.         if self.root is None:
  36.             self.root = Node(value, index)
  37.         else:
  38.             self._insert(value, index, self.root)
  39.  
  40.     def _insert(self, value, index, node: Node):
  41.         if value < node.value:
  42.             if node.left_child is None:
  43.                 node.left_child = Node(value, index)
  44.  
  45.             self._insert(value, index, node.left_child)
  46.  
  47.         if value > node.value:
  48.             if node.right_child is None:
  49.                 node.right_child = Node(value, index)
  50.  
  51.             self._insert(value, index, node.right_child)
  52.  
  53.     def exists(self, value) -> bool:
  54.         if self.root is None:
  55.             return False
  56.  
  57.         return self._exists(value, self.root)
  58.  
  59.     def _exists(self, value, node: Node) -> bool:
  60.         if value == node.value:
  61.             return True
  62.  
  63.         if value < node.value:
  64.             if node.left_child is None:
  65.                 return False
  66.  
  67.             return self._exists(value, node.left_child)
  68.  
  69.         if value > node.value:
  70.             if node.right_child is None:
  71.                 return False
  72.  
  73.             return self._exists(value, node.right_child)
  74.  
  75.     def get_index(self, value):
  76.         if self.root is None:
  77.             return None
  78.  
  79.         return self._get_index(value, self.root)
  80.  
  81.     def _get_index(self, value, node: Node):
  82.         if value == node.value:
  83.             return node.index
  84.  
  85.         if value < node.value:
  86.             if node.left_child is None:
  87.                 return None
  88.  
  89.             return self._get_index(value, node.left_child)
  90.  
  91.         if value > node.value:
  92.             if node.right_child is None:
  93.                 return None
  94.  
  95.             return self._get_index(value, node.right_child)
  96.  
  97.     def sort(self) -> []:
  98.         if self.root is None:
  99.             yield (-1, -1)
  100.         yield from self._sort(self.root)
  101.  
  102.     def _sort(self, node: Node) -> []:
  103.         if node.left is not None:
  104.             yield from self._sort(node.left)
  105.  
  106.         yield (node.value, node.index)
  107.  
  108.         if node.right is not None:
  109.             yield from self._sort(node.right)
  110.  
  111.  
  112. class Solver:
  113.     @staticmethod
  114.     def solve_with_tree(numbers, target):
  115.         candidate: int = target // 2 if target % 2 == 0 else -1
  116.         my_tree = Tree()
  117.  
  118.         for index, number in enumerate(numbers):
  119.             if number > target:
  120.                 continue
  121.  
  122.             if number == candidate:
  123.                 return [index, index]
  124.  
  125.             if my_tree.exists(target - number):
  126.                 return [my_tree.get_index(target - number), index]
  127.  
  128.             if not my_tree.exists(number):
  129.                 my_tree.insert(number, index)
  130.  
  131.         return [-1, -1]
  132.  
  133.     @staticmethod
  134.     def solve_with_array(numbers, target):
  135.         table = array('i', [-1 for _ in range(target + 1)])
  136.         candidate: int = target // 2 if target % 2 == 0 else -1
  137.  
  138.         for index, number in enumerate(numbers):
  139.             if number > target:
  140.                 continue
  141.             if number == candidate:
  142.                 return [index, index]
  143.             diff = table[target - number]
  144.             if diff >= 0 and numbers[diff] + number == target:
  145.                 return [diff, index]
  146.             if table[number] < 0:
  147.                 table[number] = index
  148.  
  149.         return [-1, -1]
  150.  
  151.     @staticmethod
  152.     def solve_with_list(numbers, target):
  153.         table = [-1 for _ in range(target + 1)]
  154.         candidate: int = target // 2 if target % 2 == 0 else -1
  155.  
  156.         for index, number in enumerate(numbers):
  157.             if number > target:
  158.                 continue
  159.             if number == candidate:
  160.                 return [index, index]
  161.             diff = table[target - number]
  162.             if diff >= 0 and numbers[diff] + number == target:
  163.                 return [diff, index]
  164.             if table[number] < 0:
  165.                 table[number] = index
  166.  
  167.         return [-1, -1]
  168.  
  169.     @staticmethod
  170.     def solve_with_dictionary(numbers, target):
  171.         table = {}
  172.         candidate = target // 2 if target % 2 == 0 else -1
  173.         for index, number in enumerate(numbers):
  174.             if number > target:
  175.                 continue
  176.  
  177.             if number == candidate:
  178.                 return [index, index]
  179.  
  180.             if (target - number) in table:
  181.                 return [table[target - number], index]
  182.  
  183.             if number not in table:
  184.                 table[number] = index
  185.  
  186.         return [-1, -1]
  187.  
  188.  
  189. def solver(session: Session):
  190.     json_get = session.get().json()
  191.     k = json_get['k']
  192.     lst = json_get['list']
  193.  
  194.     t = perf_counter()
  195.     ret_tree = Solver.solve_with_tree(lst, k)
  196.     elapsed_time_tree = perf_counter() - t
  197.  
  198.     t = perf_counter()
  199.     ret_list = Solver.solve_with_list(lst, k)
  200.     elapsed_time_list = perf_counter() - t
  201.  
  202.     t = perf_counter()
  203.     ret_dictionary = Solver.solve_with_dictionary(lst, k)
  204.     elapsed_time_dictionary = perf_counter() - t
  205.  
  206.     t = perf_counter()
  207.     ret_array = Solver.solve_with_array(lst, k)
  208.     elapsed_time_array = perf_counter() - t
  209.  
  210.     if ret_list == ret_dictionary == ret_array == ret_tree:
  211.         param = dumps({"token": ret_dictionary})
  212.         response = session.post(data=param)
  213.         if response.text != "Success":
  214.             raise ValueError("Inkorrekte Lösung")
  215.  
  216.         print(f'{response.text:10}: {ret_dictionary}')
  217.         print(f'Dictionary: {elapsed_time_dictionary * 1000:06.5f} ms')
  218.         print(f'List:       {elapsed_time_list * 1000:06.5f} ms')
  219.         print(f'Array:      {elapsed_time_array * 1000:06.5f} ms')
  220.         print(f'Tree:       {elapsed_time_tree * 1000:06.5f} ms')
  221.     else:
  222.         raise ValueError("Werte stimmen nicht überein!")
  223.  
  224.  
  225. mySession = Session(7)
  226. while True:
  227.     solver(mySession)
  228.     print()
Advertisement
Add Comment
Please, Sign In to add comment