





'''simple docstring'''







import math





class     _UpperCAmelCase							:
		def __init__(  self,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE			):



					'''simple docstring'''

					__lowerCAmelCase											=				x
					__lowerCAmelCase											=				y
					__lowerCAmelCase											=				step_size
					__lowerCAmelCase											=				function_to_optimize
		def   lowerCamelCase__			(  self			):



					'''simple docstring'''

					return self.function(self.x,self.y			)
		def   lowerCamelCase__			(  self			):



					'''simple docstring'''

					__lowerCAmelCase											=				self.step_size
					return [
					    SearchProblem(__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE,self.function			)
					    for x, y in (
					        (self.x - step_size, self.y - step_size),
					        (self.x - step_size, self.y),
					        (self.x - step_size, self.y + step_size),
					        (self.x, self.y - step_size),
					        (self.x, self.y + step_size),
					        (self.x + step_size, self.y - step_size),
					        (self.x + step_size, self.y),
					        (self.x + step_size, self.y + step_size),
					    )
					]
		def __hash__(  self			):



					'''simple docstring'''

					return hash(str(self			)			)
		def __eq__(  self,__SCREAMING_SNAKE_CASE			):



					'''simple docstring'''

					if isinstance(__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE			):
								return hash(str(self			)			) == hash(str(__SCREAMING_SNAKE_CASE			)			)
					return False







		def __str__(  self			):



					'''simple docstring'''

					return f'x: {self.x} y: {self.y}'





def    _lowerCAmelCase						(						lowercase					,	lowercase = True					,	lowercase = math.inf					,	lowercase = -math.inf					,	lowercase = math.inf					,	lowercase = -math.inf					,	lowercase = False					,	lowercase = 1_0000					,	)					->					SearchProblem:
			__lowerCAmelCase											=				search_prob
			__lowerCAmelCase											=				[]  # list to store the current score at each iteration
			__lowerCAmelCase											=				0
			__lowerCAmelCase											=				False
			__lowerCAmelCase											=				set()
			while not solution_found and iterations < max_iter:
						visited.add(lowercase	)
						iterations += 1
						__lowerCAmelCase											=				current_state.score()
						scores.append(lowercase	)
						__lowerCAmelCase											=				current_state.get_neighbors()
						__lowerCAmelCase											=				-math.inf
						__lowerCAmelCase											=				math.inf
						__lowerCAmelCase											=				None  # to hold the next best neighbor
						for neighbor in neighbors:
									if neighbor in visited:
												continue  # do not want to visit the same state again
									if (
									    neighbor.x > max_x
									    or neighbor.x < min_x
									    or neighbor.y > max_y
									    or neighbor.y < min_y
									):
												continue  # neighbor outside our bounds
									__lowerCAmelCase											=				neighbor.score() - current_score
									if find_max:  # finding max
												# going to direction with greatest ascent
												if change > max_change and change > 0:
															__lowerCAmelCase											=				change
															__lowerCAmelCase											=				neighbor
									else:  # finding min
												# to direction with greatest descent
												if change < min_change and change < 0:
															__lowerCAmelCase											=				change
															__lowerCAmelCase											=				neighbor
						if next_state is not None:
									# we found at least one neighbor which improved the current state
									__lowerCAmelCase											=				next_state
						else:
									# since we have no neighbor that improves the solution we stop the search
									__lowerCAmelCase											=				True

			if visualization:
						from matplotlib import pyplot as plt

						plt.plot(range(lowercase	)					,	lowercase	)
						plt.xlabel("""Iterations"""	)
						plt.ylabel("""Function values"""	)
						plt.show()

			return current_state


if __name__ == "__main__":
	import doctest

	doctest.testmod()





	def    _lowerCAmelCase						(						lowercase					,	lowercase	)					->					Tuple:
				return (x**2) + (y**2)

	# starting the problem with initial coordinates (3, 4)
	_a					: Tuple      =    SearchProblem(x=3, y=4, step_size=1, function_to_optimize=test_fa)
	_a					: Union[str, Any]      =    hill_climbing(prob, find_max=False)
	print(
	    """The minimum score for f(x, y) = x^2 + y^2 found via hill climbing: """
	    f'{local_min.score()}'
	)

	# starting the problem with initial coordinates (12, 47)
	_a					: Any      =    SearchProblem(x=1_2, y=4_7, step_size=1, function_to_optimize=test_fa)
	_a					: Dict      =    hill_climbing(
	    prob, find_max=False, max_x=1_0_0, min_x=5, max_y=5_0, min_y=-5, visualization=True
	)
	print(
	    """The minimum score for f(x, y) = x^2 + y^2 with the domain 100 > x > 5 """
	    f'and 50 > y > - 5 found via hill climbing: {local_min.score()}'
	)





	def    _lowerCAmelCase						(						lowercase					,	lowercase	)					->					List[str]:
				return (3 * x**2) - (6 * y)

	_a					: Tuple      =    SearchProblem(x=3, y=4, step_size=1, function_to_optimize=test_fa)
	_a					: Union[str, Any]      =    hill_climbing(prob, find_max=True)







	print(
	    """The maximum score for f(x, y) = x^2 + y^2 found via hill climbing: """
	    f'{local_min.score()}'
	)








'''simple docstring'''







def    _lowerCAmelCase						(						lowercase	)					->					int:
			__lowerCAmelCase											=				len(lowercase	)
			__lowerCAmelCase											=				[0] * length
			__lowerCAmelCase											=				[[False for i in range(lowercase	)] for j in range(lowercase	)]
			for i, c in enumerate(lowercase	):
						__lowerCAmelCase											=				i
						for j in range(i + 1	):
									if c == string[j] and (i - j < 2 or is_palindromic[j + 1][i - 1]):
												__lowerCAmelCase											=				True
												__lowerCAmelCase											=				min(lowercase					,	0 if j == 0 else (cut[j - 1] + 1)	)
						__lowerCAmelCase											=				mincut
			return cut[length - 1]


if __name__ == "__main__":
	_a					: int      =    input("""Enter the string: """).strip()
	_a					: Dict      =    find_minimum_partitions(s)
	print(f'Minimum number of partitions required for the \'{s}\' is {ans}')

