
import gc
import threading
import time

import psutil
import torch




class 				_lowerCamelCase :





     """simple docstring"""







     def __init__(							self  )  ->   Optional[Any]:




           """simple docstring"""







           UpperCamelCase__    :   Optional[int]					=				psutil.Process()
           UpperCamelCase__    :   Tuple					=				False






     def    __SCREAMING_SNAKE_CASE			(							self  )  ->   Optional[int]:




           """simple docstring"""







           UpperCamelCase__    :   Union[str, Any]					=				-1

           while True:
                 UpperCamelCase__    :   Optional[int]					=				max(self.process.memory_info().rss						,						self.cpu_memory_peak  )

                 # can't sleep or will not catch the peak right (this comment is here on purpose)
                 if not self.peak_monitoring:
                       break






     def    __SCREAMING_SNAKE_CASE			(							self  )  ->   Optional[int]:




           """simple docstring"""







           UpperCamelCase__    :   str					=				True
           UpperCamelCase__    :   Dict					=				threading.Thread(target=self.peak_monitor  )
           UpperCamelCase__    :   List[str]					=				True
           self.thread.start()






     def    __SCREAMING_SNAKE_CASE			(							self  )  ->   str:




           """simple docstring"""







           UpperCamelCase__    :   Union[str, Any]					=				False
           self.thread.join()
           return self.cpu_memory_peak
lowerCamelCase      =PeakCPUMemory()


def 							SCREAMING_SNAKE_CASE_      (			):
      # Time
      UpperCamelCase__    :   Dict					=				{'''time''': time.time()}

      gc.collect()
      torch.cuda.empty_cache()

      # CPU mem
      UpperCamelCase__    :   Dict					=				psutil.Process().memory_info().rss
      cpu_peak_tracker.start()

      # GPU mem
      for i in range(torch.cuda.device_count()		):
            UpperCamelCase__    :   List[Any]					=				torch.cuda.memory_allocated(UpperCamelCase__		)
      torch.cuda.reset_peak_memory_stats()

      return measures


def 							SCREAMING_SNAKE_CASE_      (			UpperCamelCase__		):
      # Time
      UpperCamelCase__    :   List[Any]					=				{'''time''': time.time() - start_measures['''time''']}

      gc.collect()
      torch.cuda.empty_cache()

      # CPU mem
      UpperCamelCase__    :   List[Any]					=				(psutil.Process().memory_info().rss - start_measures['''cpu''']) / 2**2_0
      UpperCamelCase__    :   Optional[Any]					=				(cpu_peak_tracker.stop() - start_measures['''cpu''']) / 2**2_0

      # GPU mem
      for i in range(torch.cuda.device_count()		):
            UpperCamelCase__    :   Optional[Any]					=				(torch.cuda.memory_allocated(UpperCamelCase__		) - start_measures[str(UpperCamelCase__		)]) / 2**2_0
            UpperCamelCase__    :   Any					=				(torch.cuda.max_memory_allocated(UpperCamelCase__		) - start_measures[str(UpperCamelCase__		)]) / 2**2_0

      return measures


def 							SCREAMING_SNAKE_CASE_      (			UpperCamelCase__ ,		UpperCamelCase__		):
      print(f'''{description}:'''		)
      print(f'''- Time: {measures["time"]:.2f}s'''		)
      for i in range(torch.cuda.device_count()		):
            print(f'''- GPU {i} allocated: {measures[str(UpperCamelCase__		)]:.2f}MiB'''		)
            UpperCamelCase__    :   Any					=				measures[f'''{i}-peak''']
            print(f'''- GPU {i} peak: {peak:.2f}MiB'''		)
      print(f'''- CPU RAM allocated: {measures["cpu"]:.2f}MiB'''		)
      print(f'''- CPU RAM peak: {measures["cpu-peak"]:.2f}MiB'''		)




class 				_lowerCamelCase :





     """simple docstring"""







     def __init__(							self  )  ->   Tuple:




           """simple docstring"""







           UpperCamelCase__    :   Union[str, Any]					=				''''''
           UpperCamelCase__    :   int					=				''''''
           UpperCamelCase__    :   Optional[int]					=				[]






     def    __SCREAMING_SNAKE_CASE			(							self						,						__SCREAMING_SNAKE_CASE						,						__SCREAMING_SNAKE_CASE  )  ->   int:




           """simple docstring"""







           if m == -1:
                 return n + 1
           elif n == -1:
                 return m + 1
           elif self.dp[m][n] > -1:
                 return self.dp[m][n]
           else:
                 if self.worda[m] == self.worda[n]:
                       UpperCamelCase__    :   Union[str, Any]					=				self.__min_dist_top_down_dp(m - 1						,						n - 1  )
                 else:
                       UpperCamelCase__    :   int					=				self.__min_dist_top_down_dp(__SCREAMING_SNAKE_CASE						,						n - 1  )
                       UpperCamelCase__    :   Tuple					=				self.__min_dist_top_down_dp(m - 1						,						__SCREAMING_SNAKE_CASE  )
                       UpperCamelCase__    :   Optional[Any]					=				self.__min_dist_top_down_dp(m - 1						,						n - 1  )
                       UpperCamelCase__    :   Optional[int]					=				1 + min(__SCREAMING_SNAKE_CASE						,						__SCREAMING_SNAKE_CASE						,						__SCREAMING_SNAKE_CASE  )

                 return self.dp[m][n]






     def    __SCREAMING_SNAKE_CASE			(							self						,						__SCREAMING_SNAKE_CASE						,						__SCREAMING_SNAKE_CASE  )  ->   int:




           """simple docstring"""







           UpperCamelCase__    :   Union[str, Any]					=				worda
           UpperCamelCase__    :   Any					=				worda
           UpperCamelCase__    :   List[str]					=				[[-1 for _ in range(len(__SCREAMING_SNAKE_CASE  )  )] for _ in range(len(__SCREAMING_SNAKE_CASE  )  )]

           return self.__min_dist_top_down_dp(len(__SCREAMING_SNAKE_CASE  ) - 1						,						len(__SCREAMING_SNAKE_CASE  ) - 1  )






     def    __SCREAMING_SNAKE_CASE			(							self						,						__SCREAMING_SNAKE_CASE						,						__SCREAMING_SNAKE_CASE  )  ->   int:




           """simple docstring"""







           UpperCamelCase__    :   int					=				worda
           UpperCamelCase__    :   List[str]					=				worda
           UpperCamelCase__    :   int					=				len(__SCREAMING_SNAKE_CASE  )
           UpperCamelCase__    :   Optional[Any]					=				len(__SCREAMING_SNAKE_CASE  )
           UpperCamelCase__    :   int					=				[[0 for _ in range(n + 1  )] for _ in range(m + 1  )]

           for i in range(m + 1  ):
                 for j in range(n + 1  ):
                       if i == 0:  # first string is empty
                             UpperCamelCase__    :   List[Any]					=				j
                       elif j == 0:  # second string is empty
                             UpperCamelCase__    :   Union[str, Any]					=				i
                       elif worda[i - 1] == worda[j - 1]:  # last characters are equal
                             UpperCamelCase__    :   List[Any]					=				self.dp[i - 1][j - 1]
                       else:
                             UpperCamelCase__    :   Union[str, Any]					=				self.dp[i][j - 1]
                             UpperCamelCase__    :   str					=				self.dp[i - 1][j]
                             UpperCamelCase__    :   Union[str, Any]					=				self.dp[i - 1][j - 1]
                             UpperCamelCase__    :   List[Any]					=				1 + min(__SCREAMING_SNAKE_CASE						,						__SCREAMING_SNAKE_CASE						,						__SCREAMING_SNAKE_CASE  )
           return self.dp[m][n]


if __name__ == "__main__":
    lowerCamelCase      =EditDistance()

    print("****************** Testing Edit Distance DP Algorithm ******************")
    print()

    lowerCamelCase      =input("Enter the first string: ").strip()
    lowerCamelCase      =input("Enter the second string: ").strip()

    print()
    print(F'''The minimum edit distance is: {solver.min_dist_top_down(Sa, Sa)}''')
    print(F'''The minimum edit distance is: {solver.min_dist_bottom_up(Sa, Sa)}''')
    print()
    print("*************** End of Testing Edit Distance DP Algorithm ***************")


