
from __future__ import annotations

from itertools import permutations
from random import randint
from timeit import repeat






def    lowerCamelCase__				(				):




			"""simple docstring"""


			lowerCAmelCase_						=	[randint(-1000    ,							1000				) for i in range(10				)]
			lowerCAmelCase_						=	randint(-5000    ,							5000				)
			return (arr, r)


_A   =     make_dataset()






def    lowerCamelCase__				(				__lowerCAmelCase  :  list[int]    ,							__lowerCAmelCase  :  int				):




			"""simple docstring"""


			for triplet in permutations(__lowerCAmelCase    ,							3				):
						if sum(__lowerCAmelCase				) == target:
									return tuple(sorted(__lowerCAmelCase				)				)
			return (0, 0, 0)






def    lowerCamelCase__				(				__lowerCAmelCase  :  list[int]    ,							__lowerCAmelCase  :  int				):




			"""simple docstring"""


			arr.sort()
			lowerCAmelCase_						=	len(__lowerCAmelCase				)
			for i in range(n - 1				):
						lowerCAmelCase_	,  lowerCAmelCase_						=	i + 1, n - 1
						while left < right:
									if arr[i] + arr[left] + arr[right] == target:
												return (arr[i], arr[left], arr[right])
									elif arr[i] + arr[left] + arr[right] < target:
												left += 1
									elif arr[i] + arr[left] + arr[right] > target:
												right -= 1
			return (0, 0, 0)






def    lowerCamelCase__				(				):




			"""simple docstring"""


			lowerCAmelCase_						=	"\nfrom __main__ import dataset, triplet_sum1, triplet_sum2\n"
			lowerCAmelCase_						=	"\ntriplet_sum1(*dataset)\n"
			lowerCAmelCase_						=	"\ntriplet_sum2(*dataset)\n"
			lowerCAmelCase_						=	repeat(setup=__lowerCAmelCase    ,							stmt=__lowerCAmelCase    ,							repeat=5    ,							number=10000				)
			lowerCAmelCase_						=	repeat(setup=__lowerCAmelCase    ,							stmt=__lowerCAmelCase    ,							repeat=5    ,							number=10000				)
			return (min(__lowerCAmelCase				), min(__lowerCAmelCase				))


if __name__ == "__main__":
			from doctest import testmod

			testmod()
			_A   =     solution_times()
			print(f"""The time for naive implementation is {times[0]}.""")
			print(f"""The time for optimized implementation is {times[1]}.""")





import functools






def    lowerCamelCase__				(				__lowerCAmelCase  :  str    ,							__lowerCAmelCase  :  str				):




			"""simple docstring"""


			lowerCAmelCase_						=	len(__lowerCAmelCase				)
			lowerCAmelCase_						=	len(__lowerCAmelCase				)

			@functools.cache
			def min_distance(__lowerCAmelCase  :  int    ,							__lowerCAmelCase  :  int				) -> int:
						# if first word index is overflow - delete all from the second word
						if indexa >= len_worda:
									return len_worda - indexa
						# if second word index is overflow - delete all from the first word
						if indexa >= len_worda:
									return len_worda - indexa
						lowerCAmelCase_						=	int(worda[indexa] != worda[indexa]				)  # current letters not identical
						return min(
						    1 + min_distance(indexa + 1    ,							__lowerCAmelCase				)    ,							1 + min_distance(__lowerCAmelCase    ,							indexa + 1				)    ,							diff + min_distance(indexa + 1    ,							indexa + 1				)    ,							)

			return min_distance(0    ,							0				)


if __name__ == "__main__":
			import doctest

			doctest.testmod()



