






'''simple docstring'''



from timeit import timeit

__UpperCamelCase   :							int         =   {
    """MALAYALAM""": True,
    """String""": False,
    """rotor""": True,
    """level""": True,
    """A""": True,
    """BB""": True,
    """ABC""": False,
    """amanaplanacanalpanama""": True,  # "a man a plan a canal panama"
}
# Ensure our test data is valid
assert all((key == key[::-1]) is value for key, value in test_data.items())



def  __UpperCAmelCase						(					SCREAMING_SNAKE_CASE__:						str     )	->      bool:

   """simple docstring"""
   __a					  =     0
   __a					  =     len(SCREAMING_SNAKE_CASE__     ) - 1
   while start_i < end_i:
      if s[start_i] == s[end_i]:
         start_i += 1
         end_i -= 1
      else:
         return False
   return True



def  __UpperCAmelCase						(					SCREAMING_SNAKE_CASE__:						str     )	->      bool:

   """simple docstring"""
   __a					  =     len(SCREAMING_SNAKE_CASE__     ) // 2
   __a					  =     len(SCREAMING_SNAKE_CASE__     )

   # We need to traverse till half of the length of string
   # as we can get access of the i'th last element from
   # i'th index.
   # eg: [0,1,2,3,4,5] => 4th index can be accessed
   # with the help of 1st index (i==n-i-1)
   # where n is length of string
   return all(s[i] == s[n - i - 1] for i in range(SCREAMING_SNAKE_CASE__     )     )



def  __UpperCAmelCase						(					SCREAMING_SNAKE_CASE__:						str     )	->      bool:

   """simple docstring"""
   if len(SCREAMING_SNAKE_CASE__     ) <= 2:
      return True
   if s[0] == s[len(SCREAMING_SNAKE_CASE__     ) - 1]:
      return is_palindrome_recursive(s[1:-1]     )
   else:
      return False



def  __UpperCAmelCase						(					SCREAMING_SNAKE_CASE__:						str     )	->      bool:

   """simple docstring"""
   return s == s[::-1]



def  __UpperCAmelCase						(					SCREAMING_SNAKE_CASE__:						str     )	->      None:

   """simple docstring"""
   __a					  =     f"""all({name}(key) is value for key, value in test_data.items())"""
   __a					  =     f"""from __main__ import test_data, {name}"""
   __a					  =     500000
   __a					  =     timeit(stmt=SCREAMING_SNAKE_CASE__,       setup=SCREAMING_SNAKE_CASE__,       number=SCREAMING_SNAKE_CASE__     )
   print(f"""{name:<35} finished {number:,} runs in {result:.5f} seconds"""     )


if __name__ == "__main__":
 for key, value in test_data.items():
  assert is_palindrome(key) is is_palindrome_recursive(key)
  assert is_palindrome(key) is is_palindrome_slice(key)
  print(f"""{key:21} {value}""")
 print("""a man a plan a canal panama""")

 # finished 500,000 runs in 0.46793 seconds
 benchmark_function("""is_palindrome_slice""")
 # finished 500,000 runs in 0.85234 seconds
 benchmark_function("""is_palindrome""")
 # finished 500,000 runs in 1.32028 seconds
 benchmark_function("""is_palindrome_recursive""")
 # finished 500,000 runs in 2.08679 seconds
 benchmark_function("""is_palindrome_traversal""")







'''simple docstring'''



from queue import PriorityQueue
from typing import Any

import numpy as np



def  __UpperCAmelCase						(					SCREAMING_SNAKE_CASE__:						dict,       SCREAMING_SNAKE_CASE__:						str,       SCREAMING_SNAKE_CASE__:						set,       SCREAMING_SNAKE_CASE__:						set,       SCREAMING_SNAKE_CASE__:						dict,       SCREAMING_SNAKE_CASE__:						dict,       SCREAMING_SNAKE_CASE__:						PriorityQueue,       SCREAMING_SNAKE_CASE__:						dict,       SCREAMING_SNAKE_CASE__:						float | int,       )	->      float | int:

   """simple docstring"""
   for nxt, d in graph[v]:
      if nxt in visited_forward:
         continue
      __a					  =     cst_fwd.get(SCREAMING_SNAKE_CASE__,       np.inf     )
      __a					  =     cst_fwd[v] + d
      if new_cost_f < old_cost_f:
         queue.put((new_cost_f, nxt)     )
         __a					  =     new_cost_f
         __a					  =     v
      if nxt in visited_backward:
         if cst_fwd[v] + d + cst_bwd[nxt] < shortest_distance:
            __a					  =     cst_fwd[v] + d + cst_bwd[nxt]
   return shortest_distance



def  __UpperCAmelCase						(					SCREAMING_SNAKE_CASE__:						str,       SCREAMING_SNAKE_CASE__:						str,       SCREAMING_SNAKE_CASE__:						dict,       SCREAMING_SNAKE_CASE__:						dict     )	->      int:

   """simple docstring"""
   __a					  =     -1

   __a					  =     set()
   __a					  =     set()
   __a					  =     {source: 0}
   __a					  =     {destination: 0}
   __a					  =     {source: None}
   __a					  =     {destination: None}
   __a					  =     PriorityQueue()
   __a					  =     PriorityQueue()

   __a					  =     np.inf

   queue_forward.put((0, source)     )
   queue_backward.put((0, destination)     )

   if source == destination:
      return 0

   while not queue_forward.empty() and not queue_backward.empty():
      __a  ,      __a					  =     queue_forward.get()
      visited_forward.add(SCREAMING_SNAKE_CASE__     )

      __a  ,      __a					  =     queue_backward.get()
      visited_backward.add(SCREAMING_SNAKE_CASE__     )

      __a					  =     pass_and_relaxation(
          SCREAMING_SNAKE_CASE__,       SCREAMING_SNAKE_CASE__,       SCREAMING_SNAKE_CASE__,       SCREAMING_SNAKE_CASE__,       SCREAMING_SNAKE_CASE__,       SCREAMING_SNAKE_CASE__,       SCREAMING_SNAKE_CASE__,       SCREAMING_SNAKE_CASE__,       SCREAMING_SNAKE_CASE__,       )

      __a					  =     pass_and_relaxation(
          SCREAMING_SNAKE_CASE__,       SCREAMING_SNAKE_CASE__,       SCREAMING_SNAKE_CASE__,       SCREAMING_SNAKE_CASE__,       SCREAMING_SNAKE_CASE__,       SCREAMING_SNAKE_CASE__,       SCREAMING_SNAKE_CASE__,       SCREAMING_SNAKE_CASE__,       SCREAMING_SNAKE_CASE__,       )

      if cst_fwd[v_fwd] + cst_bwd[v_bwd] >= shortest_distance:
         break

   if shortest_distance != np.inf:
      __a					  =     shortest_distance
   return shortest_path_distance


__UpperCamelCase   :							Dict         =   {
    """B""": [["""C""", 1]],
    """C""": [["""D""", 1]],
    """D""": [["""F""", 1]],
    """E""": [["""B""", 1], ["""G""", 2]],
    """F""": [],
    """G""": [["""F""", 1]],
}
__UpperCamelCase   :							int         =   {
    """B""": [["""E""", 1]],
    """C""": [["""B""", 1]],
    """D""": [["""C""", 1]],
    """F""": [["""D""", 1], ["""G""", 1]],
    """E""": [[None, np.inf]],
    """G""": [["""E""", 2]],
}

if __name__ == "__main__":
 import doctest

 doctest.testmod()