





from __future__ import annotations

from collections.abc import Callable
from typing import Generic, TypeVar

lowerCAmelCase_						   =    TypeVar("""T""")
lowerCAmelCase_						   =    TypeVar("""U""")



class        _lowerCAmelCase    (			Generic[T, U]							):


  '''simple docstring'''







  def __init__(      self      :					List[str]      ,				UpperCamelCase      :					T | None      ,				UpperCamelCase      :					U | None							):


    '''simple docstring'''





    _snake_case   :				Optional[Any]														=	key
    _snake_case   :				List[Any]														=	val
    _snake_case   :				DoubleLinkedListNode[T, U] | None														=	None
    _snake_case   :				DoubleLinkedListNode[T, U] | None														=	None







  def __repr__(      self      :					Union[str, Any]							):


    '''simple docstring'''





    return (
        f"""Node: key: {self.key}, val: {self.val}, """
        f"""has next: {bool(self.next							)}, has prev: {bool(self.prev							)}"""
    )




class        _lowerCAmelCase    (			Generic[T, U]							):


  '''simple docstring'''







  def __init__(      self      :					str							):


    '''simple docstring'''





    _snake_case   :				DoubleLinkedListNode[T, U]														=	DoubleLinkedListNode(UpperCamelCase      ,				UpperCamelCase							)
    _snake_case   :				DoubleLinkedListNode[T, U]														=	DoubleLinkedListNode(UpperCamelCase      ,				UpperCamelCase							)
    _snake_case							,					_snake_case   :				List[str]														=	self.rear, self.head







  def __repr__(      self      :					Optional[int]							):


    '''simple docstring'''





    _snake_case   :				List[str]														=	['DoubleLinkedList']
    _snake_case   :				Dict														=	self.head
    while node.next is not None:
      rep.append(str(UpperCamelCase							)							)
      _snake_case   :				Dict														=	node.next
    rep.append(str(self.rear							)							)
    return ",\n    ".join(UpperCamelCase							)







  def UpperCamelCase_ (      self      :					Dict      ,				UpperCamelCase      :					DoubleLinkedListNode[T, U]							):


    '''simple docstring'''





    _snake_case   :				str														=	self.rear.prev

    # All nodes other than self.head are guaranteed to have non-None previous
    assert previous is not None

    _snake_case   :				Tuple														=	node
    _snake_case   :				int														=	previous
    _snake_case   :				int														=	node
    _snake_case   :				int														=	self.rear







  def UpperCamelCase_ (      self      :					Union[str, Any]      ,				UpperCamelCase      :					DoubleLinkedListNode[T, U]							):


    '''simple docstring'''





    if node.prev is None or node.next is None:
      return None

    _snake_case   :				str														=	node.next
    _snake_case   :				List[str]														=	node.prev
    _snake_case   :				Union[str, Any]														=	None
    _snake_case   :				Optional[int]														=	None
    return node




class        _lowerCAmelCase    (			Generic[T, U]							):


  '''simple docstring'''
  a_							:       dict[Callable[[T], U], LRUCache[T, U]]      					={}







  def __init__(      self      :					List[Any]      ,				UpperCamelCase      :					int							):


    '''simple docstring'''





    _snake_case   :				DoubleLinkedList[T, U]														=	DoubleLinkedList()
    _snake_case   :				Dict														=	capacity
    _snake_case   :				Tuple														=	0
    _snake_case   :				Optional[Any]														=	0
    _snake_case   :				Optional[Any]														=	0
    _snake_case   :				dict[T, DoubleLinkedListNode[T, U]]														=	{}







  def __repr__(      self      :					Dict							):


    '''simple docstring'''





    return (
        f"""CacheInfo(hits={self.hits}, misses={self.miss}, """
        f"""capacity={self.capacity}, current size={self.num_keys})"""
    )







  def __contains__(      self      :					List[str]      ,				UpperCamelCase      :					T							):


    '''simple docstring'''





    return key in self.cache







  def UpperCamelCase_ (      self      :					Any      ,				UpperCamelCase      :					T							):


    '''simple docstring'''





    if key in self.cache:
      self.hits += 1
      _snake_case   :				DoubleLinkedListNode[T, U]														=	self.cache[key]
      _snake_case   :				Dict														=	self.list.remove(self.cache[key]							)
      assert node == value_node

      # node is guaranteed not None because it is in self.cache
      assert node is not None
      self.list.add(UpperCamelCase							)
      return node.val
    self.miss += 1
    return None







  def UpperCamelCase_ (      self      :					int      ,				UpperCamelCase      :					T      ,				UpperCamelCase      :					U							):


    '''simple docstring'''





    if key not in self.cache:
      if self.num_keys >= self.capacity:
        # delete first node (oldest) when over capacity
        _snake_case   :				Dict														=	self.list.head.next

        # guaranteed to have a non-None first node when num_keys > 0
        # explain to type checker via assertions
        assert first_node is not None
        assert first_node.key is not None
        assert (
            self.list.remove(UpperCamelCase							) is not None
        )  # node guaranteed to be in list assert node.key is not None

        del self.cache[first_node.key]
        self.num_keys -= 1
      _snake_case   :				Any														=	DoubleLinkedListNode(UpperCamelCase      ,				UpperCamelCase							)
      self.list.add(self.cache[key]							)
      self.num_keys += 1

    else:
      # bump node to the end of the list, update value
      _snake_case   :				Optional[Any]														=	self.list.remove(self.cache[key]							)
      assert node is not None  # node guaranteed to be in list
      _snake_case   :				Optional[Any]														=	value
      self.list.add(UpperCamelCase							)







  @classmethod
  def UpperCamelCase_ (      cls      :					str      ,				UpperCamelCase      :					int = 1_28							):


    '''simple docstring'''





    def cache_decorator_inner(UpperCamelCase      :					Callable[[T], U]							) -> Callable[..., U]:
      def cache_decorator_wrapper(*UpperCamelCase      :					T							) -> U:
        if func not in cls.decorator_function_to_instance_map:
          _snake_case   :				Union[str, Any]														=	LRUCache(UpperCamelCase							)

        _snake_case   :				Union[str, Any]														=	cls.decorator_function_to_instance_map[func].get(args[0]							)
        if result is None:
          _snake_case   :				Any														=	func(*UpperCamelCase							)
          cls.decorator_function_to_instance_map[func].put(args[0]      ,				UpperCamelCase							)
        return result

      def cache_info() -> LRUCache[T, U]:
        return cls.decorator_function_to_instance_map[func]

      setattr(UpperCamelCase      ,				'cache_info'      ,				UpperCamelCase							)  # noqa: B010

      return cache_decorator_wrapper

    return cache_decorator_inner


if __name__ == "__main__":
      import doctest

      doctest.testmod()











import math
import random
from typing import Any

from .hill_climbing import SearchProblem


def     lowerCamelCase_	(      lowerCAmelCase:	Tuple    ,							lowerCAmelCase:	bool = True    ,							lowerCAmelCase:	float = math.inf    ,							lowerCAmelCase:	float = -math.inf    ,							lowerCAmelCase:	float = math.inf    ,							lowerCAmelCase:	float = -math.inf    ,							lowerCAmelCase:	bool = False    ,							lowerCAmelCase:	float = 1_00    ,							lowerCAmelCase:	float = 0.0_1    ,							lowerCAmelCase:	float = 1    ,							)->		Any:
  _snake_case   :				int														=	False
  _snake_case   :				Any														=	search_prob
  _snake_case   :				Tuple														=	start_temperate
  _snake_case   :				Any														=	[]
  _snake_case   :				List[str]														=	0
  _snake_case   :				Optional[Any]														=	None

  while not search_end:
    _snake_case   :				List[Any]														=	current_state.score()
    if best_state is None or current_score > best_state.score():
      _snake_case   :				Dict														=	current_state
    scores.append(lowerCAmelCase				)
    iterations += 1
    _snake_case   :				Optional[int]														=	None
    _snake_case   :				Union[str, Any]														=	current_state.get_neighbors()
    while (
        next_state is None and neighbors
    ):  # till we do not find a neighbor that we can move to
      _snake_case   :				Dict														=	random.randint(0    ,							len(lowerCAmelCase				) - 1				)  # picking a random neighbor
      _snake_case   :				int														=	neighbors.pop(lowerCAmelCase				)
      _snake_case   :				Union[str, Any]														=	picked_neighbor.score() - current_score

      if (
          picked_neighbor.x > max_x
          or picked_neighbor.x < min_x
          or picked_neighbor.y > max_y
          or picked_neighbor.y < min_y
      ):
        continue  # neighbor outside our bounds

      if not find_max:
        _snake_case   :				Union[str, Any]														=	change * -1  # in case we are finding minimum
      if change > 0:  # improves the solution
        _snake_case   :				Union[str, Any]														=	picked_neighbor
      else:
        _snake_case   :				Optional[Any]														=	(math.e) ** (
            change / current_temp
        )  # probability generation function
        if random.random() < probability:  # random number within probability
          _snake_case   :				int														=	picked_neighbor
    _snake_case   :				List[Any]														=	current_temp - (current_temp * rate_of_decrease)

    if current_temp < threshold_temp or next_state is None:
      # temperature below threshold, or could not find a suitable neighbor
      _snake_case   :				List[str]														=	True
    else:
      _snake_case   :				Union[str, Any]														=	next_state

  if visualization:
    from matplotlib import pyplot as plt

    plt.plot(range(lowerCAmelCase				)    ,							lowerCAmelCase				)
    plt.xlabel('Iterations'				)
    plt.ylabel('Function values'				)
    plt.show()
  return best_state


if __name__ == "__main__":


      def     lowerCamelCase_	(      lowerCAmelCase:	Any    ,							lowerCAmelCase:	List[Any]				)->		List[Any]:
        return (x**2) + (y**2)

      # starting the problem with initial coordinates (12, 47)
      lowerCAmelCase_						   =    SearchProblem(x=12, y=47, step_size=1, function_to_optimize=test_fa)
      lowerCAmelCase_						   =    simulated_annealing(
          prob, find_max=False, max_x=100, min_x=5, max_y=50, 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()}"""
      )

      # starting the problem with initial coordinates (12, 47)
      lowerCAmelCase_						   =    SearchProblem(x=12, y=47, step_size=1, function_to_optimize=test_fa)
      lowerCAmelCase_						   =    simulated_annealing(
          prob, find_max=True, max_x=100, min_x=5, max_y=50, min_y=-5, visualization=True
      )
      print(
          """The maximum 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_	(      lowerCAmelCase:	Any    ,							lowerCAmelCase:	Dict				)->		Dict:
        return (3 * x**2) - (6 * y)

      lowerCAmelCase_						   =    SearchProblem(x=3, y=4, step_size=1, function_to_optimize=test_fa)
      lowerCAmelCase_						   =    simulated_annealing(prob, find_max=False, visualization=True)
      print(
          """The minimum score for f(x, y) = 3*x^2 - 6*y found via hill climbing: """
          F"""{local_min.score()}"""
      )

      lowerCAmelCase_						   =    SearchProblem(x=3, y=4, step_size=1, function_to_optimize=test_fa)
      lowerCAmelCase_						   =    simulated_annealing(prob, find_max=True, visualization=True)







      print(
          """The maximum score for f(x, y) = 3*x^2 - 6*y found via hill climbing: """
          F"""{local_min.score()}"""
      )




