
"""simple docstring"""






class 			_SCREAMING_SNAKE_CASE					:






			def __init__(					self       )			->     int:
						lowerCAmelCase_    :List[str]			     =  """"""
						lowerCAmelCase_    :List[Any]			     =  """"""
						lowerCAmelCase_    :Union[str, Any]			     =  []






			def  __lowerCAmelCase (					self       ,   __A       ,   __A       )			->     int:
						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]:
												lowerCAmelCase_    :List[Any]			     =  self.__min_dist_top_down_dp(m - 1       ,   n - 1       )
									else:
												lowerCAmelCase_    :int			     =  self.__min_dist_top_down_dp(__A       ,   n - 1       )
												lowerCAmelCase_    :Dict			     =  self.__min_dist_top_down_dp(m - 1       ,   __A       )
												lowerCAmelCase_    :Optional[int]			     =  self.__min_dist_top_down_dp(m - 1       ,   n - 1       )
												lowerCAmelCase_    :Tuple			     =  1 + min(__A       ,   __A       ,   __A       )

									return self.dp[m][n]






			def  __lowerCAmelCase (					self       ,   __A       ,   __A       )			->     int:
						lowerCAmelCase_    :List[str]			     =  worda
						lowerCAmelCase_    :int			     =  worda
						lowerCAmelCase_    :int			     =  [[-1 for _ in range(len(__A       )       )] for _ in range(len(__A       )       )]

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






			def  __lowerCAmelCase (					self       ,   __A       ,   __A       )			->     int:
						lowerCAmelCase_    :Optional[Any]			     =  worda
						lowerCAmelCase_    :Dict			     =  worda
						lowerCAmelCase_    :str			     =  len(__A       )
						lowerCAmelCase_    :Union[str, Any]			     =  len(__A       )
						lowerCAmelCase_    :List[str]			     =  [[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
															lowerCAmelCase_    :int			     =  j
												elif j == 0:  # second string is empty
															lowerCAmelCase_    :int			     =  i
												elif worda[i - 1] == worda[j - 1]:  # last characters are equal
															lowerCAmelCase_    :Union[str, Any]			     =  self.dp[i - 1][j - 1]
												else:
															lowerCAmelCase_    :Union[str, Any]			     =  self.dp[i][j - 1]
															lowerCAmelCase_    :Tuple			     =  self.dp[i - 1][j]
															lowerCAmelCase_    :Dict			     =  self.dp[i - 1][j - 1]
															lowerCAmelCase_    :Tuple			     =  1 + min(__A       ,   __A       ,   __A       )
						return self.dp[m][n]


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

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

				__UpperCAmelCase       =  input('Enter the first string: ').strip()
				__UpperCAmelCase       =  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 ***************')










"""simple docstring"""




lowercase_			     =  [4, 1, 7, 4, 2, 6, 4, 1, 5, 3, 7, 5]
lowercase_			     =  [3, 7, 7, 4, 2, 6, 4, 1, 5, 3, 7, 5]
lowercase_			     =  {
    0: "Sunday",
    1: "Monday",
    2: "Tuesday",
    3: "Wednesday",
    4: "Thursday",
    5: "Friday",
    6: "Saturday",
}

def        lowercase							(		lowerCAmelCase__ :     int    ,					lowerCAmelCase__ :     int    ,					lowerCAmelCase__ :     int			) ->      str:
		assert len(str(lowerCAmelCase__			)			) > 2, "year should be in YYYY format"
		assert 1 <= month <= 12, "month should be between 1 to 12"
		assert 1 <= day <= 31, "day should be between 1 to 31"

		# Doomsday algorithm:
		__a           =			year // 100
		__a           =			(5 * (century % 4) + 2) % 7
		__a           =			year % 100
		__a           =			centurian % 12
		__a           =			(
		    (centurian // 12) + centurian_m + (centurian_m // 4) + century_anchor
		) % 7
		__a           =			(
		    DOOMSDAY_NOT_LEAP[month - 1]
		    if (year % 4 != 0) or (centurian == 0 and (year % 400) == 0)
		    else DOOMSDAY_LEAP[month - 1]
		)
		__a           =			(dooms_day + day - day_anchor) % 7
		return WEEK_DAY_NAMES[week_day]


if __name__ == "__main__":
				import doctest

				doctest.testmod()






