



"""simple docstring"""





from timeit import timeit

lowerCamelCase       	=						{
    """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        a__     (				lowerCAmelCase__				):
      UpperCAmelCase_      			=							0
      UpperCAmelCase_      			=							len(lowerCAmelCase__				) - 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        a__     (				lowerCAmelCase__				):
      UpperCAmelCase_      			=							len(lowerCAmelCase__				) // 2
      UpperCAmelCase_      			=							len(lowerCAmelCase__				)

      # 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(lowerCAmelCase__				)				)
def        a__     (				lowerCAmelCase__				):
      if len(lowerCAmelCase__				) <= 2:
            return True
      if s[0] == s[len(lowerCAmelCase__				) - 1]:
            return is_palindrome_recursive(s[1:-1]				)
      else:
            return False
def        a__     (				lowerCAmelCase__				):
      return s == s[::-1]
def        a__     (				lowerCAmelCase__				):
      UpperCAmelCase_      			=							f"""all({name}(key) is value for key, value in test_data.items())"""
      UpperCAmelCase_      			=							f"""from __main__ import test_data, {name}"""
      UpperCAmelCase_      			=							500000
      UpperCAmelCase_      			=							timeit(stmt=lowerCAmelCase__     ,      setup=lowerCAmelCase__     ,      number=lowerCAmelCase__				)
      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 __future__ import annotations

from collections import namedtuple
from dataclasses import dataclass
@dataclass
class 				lowercase__       :







       '''simple docstring'''


       UpperCamelCase						=					42
       UpperCamelCase						=					None
       UpperCamelCase						=					None



lowerCamelCase       	=						namedtuple("""CoinsDistribResult""", """moves excess""")
def        a__     (				lowerCAmelCase__				):

      if root is None:
            return 0

      # Validation
      def count_nodes(lowerCAmelCase__				) -> int:
            if node is None:
                  return 0

            return count_nodes(node.left				) + count_nodes(node.right				) + 1

      def count_coins(lowerCAmelCase__				) -> int:
            if node is None:
                  return 0

            return count_coins(node.left				) + count_coins(node.right				) + node.data

      if count_nodes(lowerCAmelCase__				) != count_coins(lowerCAmelCase__				):
            raise ValueError("The nodes number should be same as the number of coins"				)

      # Main calculation
      def get_distrib(lowerCAmelCase__				) -> CoinsDistribResult:

            if node is None:
                  return CoinsDistribResult(0     ,      1				)

            UpperCAmelCase_			,   UpperCAmelCase_      			=							get_distrib(node.left				)
            UpperCAmelCase_			,   UpperCAmelCase_      			=							get_distrib(node.right				)

            UpperCAmelCase_      			=							1 - left_distrib_excess
            UpperCAmelCase_      			=							1 - right_distrib_excess

            UpperCAmelCase_      			=							(
                left_distrib_moves
                + right_distrib_moves
                + abs(lowerCAmelCase__				)
                + abs(lowerCAmelCase__				)
            )
            UpperCAmelCase_      			=							node.data - coins_to_left - coins_to_right

            return CoinsDistribResult(lowerCAmelCase__     ,      lowerCAmelCase__				)

      return get_distrib(lowerCAmelCase__				)[0]


if __name__ == "__main__":
  import doctest

  doctest.testmod()




