


from __future__ import annotations

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

UpperCAmelCase_   :				Optional[Any]						      =TypeVar('T')
UpperCAmelCase_   :				Any						      =TypeVar('U')
class 				SCREAMING_SNAKE_CASE__						(       Generic[T, U]    ):
      def __init__( self       : List[Any]  ,							SCREAMING_SNAKE_CASE__       : T | None  ,							SCREAMING_SNAKE_CASE__       : U | None  )	->    Optional[int]:
             a_      :	List[Any]							=						key
             a_      :	Union[str, Any]							=						val
             a_      :	DoubleLinkedListNode[T, U] | None							=						None
             a_      :	DoubleLinkedListNode[T, U] | None							=						None

      def __repr__( self       : int  )	->    Any:
             return (
                 F"""Node: key: {self.key}, val: {self.val}, """
                 F"""has next: {bool(self.next  )}, has prev: {bool(self.prev  )}"""
             )
class 				SCREAMING_SNAKE_CASE__						(       Generic[T, U]    ):
      def __init__( self       : Optional[Any]  )	->    List[str]:
             a_      :	DoubleLinkedListNode[T, U]							=						DoubleLinkedListNode(UpperCAmelCase__  ,							UpperCAmelCase__  )
             a_      :	DoubleLinkedListNode[T, U]							=						DoubleLinkedListNode(UpperCAmelCase__  ,							UpperCAmelCase__  )
             a_      :	Any							=						self.rear, self.head
      def __repr__( self       : str  )	->    Tuple:
             a_      :	Optional[int]							=						['''DoubleLinkedList''']
             a_      :	str							=						self.head
             while node.next is not None:
                    rep.append(str(UpperCAmelCase__  )  )
                    a_      :	Union[str, Any]							=						node.next
             rep.append(str(self.rear  )  )
             return ",\n    ".join(UpperCAmelCase__  )
      def  SCREAMING_SNAKE_CASE							( self       : Dict  ,							SCREAMING_SNAKE_CASE__       : DoubleLinkedListNode[T, U]  )	->    Union[str, Any]:
             a_      :	Optional[Any]							=						self.rear.prev

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

             a_      :	Tuple							=						node
             a_      :	Union[str, Any]							=						previous
             a_      :	List[str]							=						node
             a_      :	Tuple							=						self.rear

      def  SCREAMING_SNAKE_CASE							( self       : Tuple  ,							SCREAMING_SNAKE_CASE__       : DoubleLinkedListNode[T, U]  )	->    Union[str, Any]:

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

             a_      :	Union[str, Any]							=						node.next
             a_      :	Dict							=						node.prev
             a_      :	List[str]							=						None
             a_      :	Optional[Any]							=						None
             return node
class 				SCREAMING_SNAKE_CASE__						(       Generic[T, U]    ):
      snake_case__       :  dict[Callable[[T], U], LRUCache[T, U]]       =		{}
      def __init__( self       : Dict  ,							SCREAMING_SNAKE_CASE__       : int  )	->    Tuple:
             a_      :	DoubleLinkedList[T, U]							=						DoubleLinkedList()
             a_      :	List[Any]							=						capacity
             a_      :	Tuple							=						0
             a_      :	Union[str, Any]							=						0
             a_      :	List[str]							=						0
             a_      :	dict[T, DoubleLinkedListNode[T, U]]							=						{}
      def __repr__( self       : Tuple  )	->    Tuple:
             return (
                 F"""CacheInfo(hits={self.hits}, misses={self.miss}, """
                 F"""capacity={self.capacity}, current size={self.num_keys})"""
             )
      def __contains__( self       : Dict  ,							SCREAMING_SNAKE_CASE__       : T  )	->    str:
             return key in self.cache
      def  SCREAMING_SNAKE_CASE							( self       : Optional[Any]  ,							SCREAMING_SNAKE_CASE__       : T  )	->    Union[str, Any]:
             # Note: pythonic interface would throw KeyError rather than return None

             if key in self.cache:
                    self.hits += 1
                    a_      :	DoubleLinkedListNode[T, U]							=						self.cache[key]
                    a_      :	Optional[int]							=						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  SCREAMING_SNAKE_CASE							( self       : List[str]  ,							SCREAMING_SNAKE_CASE__       : T  ,							SCREAMING_SNAKE_CASE__       : U  )	->    List[str]:

             if key not in self.cache:
                    if self.num_keys >= self.capacity:
                           # delete first node (oldest) when over capacity
                           a_      :	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
                    a_      :	Dict							=						DoubleLinkedListNode(UpperCAmelCase__  ,							UpperCAmelCase__  )
                    self.list.add(self.cache[key]  )
                    self.num_keys += 1

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

      @classmethod
      def  SCREAMING_SNAKE_CASE							( cls       : Dict  ,							SCREAMING_SNAKE_CASE__       : int = 1_2_8  )	->    List[str]:

             def cache_decorator_inner(SCREAMING_SNAKE_CASE__       : Callable[[T], U]  ) -> Callable[..., U]:
                    def cache_decorator_wrapper(*SCREAMING_SNAKE_CASE__       : T  ) -> U:
                           if func not in cls.decorator_function_to_instance_map:
                                  a_      :	str							=						LRUCache(UpperCAmelCase__  )

                           a_      :	str							=						cls.decorator_function_to_instance_map[func].get(args[0]  )
                           if result is None:
                                  a_      :	List[str]							=						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()






# This code is adapted from OpenAI's release
# https://github.com/openai/human-eval/blob/master/human_eval/execution.py

import contextlib
import faulthandler
import io
import multiprocessing
import os
import platform
import signal
import tempfile







def  SCREAMING_SNAKE_CASE_		(    __A				:    List[Any]						,					__A				:    List[Any]						,					__A				:    List[Any]						,					__A				:    Optional[int]       )			->	Dict:

       """simple docstring"""

       a_      :	Optional[Any]							=						multiprocessing.Manager()
       a_      :	Tuple							=						manager.list()

       a_      :	Optional[int]							=						multiprocessing.Process(target=__A						,					args=(check_program, result, timeout)       )
       p.start()
       p.join(timeout=timeout + 1       )
       if p.is_alive():
              p.kill()

       if not result:
              result.append('timed out'       )

       return {
           "task_id": task_id,
           "passed": result[0] == "passed",
           "result": result[0],
           "completion_id": completion_id,
       }







def  SCREAMING_SNAKE_CASE_		(    __A				:    Tuple						,					__A				:    Optional[Any]						,					__A				:    Optional[Any]       )			->	Dict:

       """simple docstring"""

       with create_tempdir():
              # These system calls are needed when cleaning up tempdir.
              import os
              import shutil

              a_      :	Any							=						shutil.rmtree
              a_      :	List[str]							=						os.rmdir
              a_      :	List[Any]							=						os.chdir

              # Disable functionalities that can make destructive changes to the test.
              reliability_guard()

              # Run program.
              try:
                     a_      :	Any							=						{}
                     with swallow_io():
                            with time_limit(__A       ):
                                   exec(__A						,					__A       )
                     result.append('passed'       )
              except TimeoutException:
                     result.append('timed out'       )
              except BaseException as e:
                     result.append(F"""failed: {e}"""       )

              # Needed for cleaning up.
              a_      :	Tuple							=						rmtree
              a_      :	Any							=						rmdir
              a_      :	Optional[int]							=						chdir







@contextlib.contextmanager
def  SCREAMING_SNAKE_CASE_		(    __A				:    List[str]       )			->	str:

       """simple docstring"""

       def signal_handler(__A				:    List[str]						,					__A				:    Dict       ):
              raise TimeoutException('Timed out!'       )

       signal.setitimer(signal.ITIMER_REAL						,					__A       )
       signal.signal(signal.SIGALRM						,					__A       )
       try:
              yield
       finally:
              signal.setitimer(signal.ITIMER_REAL						,					0       )







@contextlib.contextmanager
def  SCREAMING_SNAKE_CASE_		(    )			->	Dict:

       """simple docstring"""

       a_      :	int							=						WriteOnlyStringIO()
       with contextlib.redirect_stdout(__A       ):
              with contextlib.redirect_stderr(__A       ):
                     with redirect_stdin(__A       ):
                            yield







@contextlib.contextmanager
def  SCREAMING_SNAKE_CASE_		(    )			->	Optional[int]:

       """simple docstring"""

       with tempfile.TemporaryDirectory() as dirname:
              with chdir(__A       ):
                     yield dirname
class 				SCREAMING_SNAKE_CASE__						(       lowercase__    ):
      pass
class 				SCREAMING_SNAKE_CASE__						(       io.StringIO    ):
      def  SCREAMING_SNAKE_CASE							( self       : List[Any]  ,							*SCREAMING_SNAKE_CASE__       : List[str]  ,							**SCREAMING_SNAKE_CASE__       : List[Any]  )	->    int:
             raise OSError
      def  SCREAMING_SNAKE_CASE							( self       : Tuple  ,							*SCREAMING_SNAKE_CASE__       : Tuple  ,							**SCREAMING_SNAKE_CASE__       : Dict  )	->    List[str]:
             raise OSError
      def  SCREAMING_SNAKE_CASE							( self       : int  ,							*SCREAMING_SNAKE_CASE__       : Dict  ,							**SCREAMING_SNAKE_CASE__       : List[Any]  )	->    Optional[Any]:
             raise OSError

      def  SCREAMING_SNAKE_CASE							( self       : Any  ,							*SCREAMING_SNAKE_CASE__       : Union[str, Any]  ,							**SCREAMING_SNAKE_CASE__       : List[Any]  )	->    List[Any]:
             return False
class 				SCREAMING_SNAKE_CASE__						(       contextlib._RedirectStream    ):  # type: ignore
      snake_case__       :  Optional[int]       =		'''stdin'''







@contextlib.contextmanager
def  SCREAMING_SNAKE_CASE_		(    __A				:    Tuple       )			->	Union[str, Any]:

       """simple docstring"""

       if root == ".":
              yield
              return
       a_      :	str							=						os.getcwd()
       os.chdir(__A       )
       try:
              yield
       except BaseException as exc:
              raise exc
       finally:
              os.chdir(__A       )







def  SCREAMING_SNAKE_CASE_		(    __A				:    Dict=None       )			->	Dict:

       """simple docstring"""

       if maximum_memory_bytes is not None:
              import resource

              resource.setrlimit(resource.RLIMIT_AS						,					(maximum_memory_bytes, maximum_memory_bytes)       )
              resource.setrlimit(resource.RLIMIT_DATA						,					(maximum_memory_bytes, maximum_memory_bytes)       )
              if not platform.uname().system == "Darwin":
                     resource.setrlimit(resource.RLIMIT_STACK						,					(maximum_memory_bytes, maximum_memory_bytes)       )

       faulthandler.disable()

       import builtins

       a_      :	str							=						None
       a_      :	str							=						None

       import os

       a_      :	Optional[int]							=						'1'

       a_      :	Any							=						None
       a_      :	int							=						None
       a_      :	int							=						None
       a_      :	Tuple							=						None
       a_      :	Dict							=						None
       a_      :	Any							=						None
       a_      :	Dict							=						None
       a_      :	Dict							=						None
       a_      :	List[str]							=						None
       a_      :	Optional[Any]							=						None
       a_      :	Tuple							=						None
       a_      :	Union[str, Any]							=						None
       a_      :	Dict							=						None
       a_      :	Dict							=						None
       a_      :	int							=						None
       a_      :	str							=						None
       a_      :	Union[str, Any]							=						None
       a_      :	str							=						None
       a_      :	Optional[int]							=						None
       a_      :	List[Any]							=						None
       a_      :	Union[str, Any]							=						None
       a_      :	Dict							=						None
       a_      :	Tuple							=						None
       a_      :	List[str]							=						None
       a_      :	str							=						None
       a_      :	str							=						None
       a_      :	str							=						None

       import shutil

       a_      :	Dict							=						None
       a_      :	Tuple							=						None
       a_      :	str							=						None

       import subprocess

       a_      :	str							=						None  # type: ignore

       a_      :	List[Any]							=						None

       import sys

       a_      :	Optional[int]							=						None
       a_      :	int							=						None
       a_      :	Any							=						None
       a_      :	str							=						None
       a_      :	str							=						None


