




from __future__ import annotations

import time

lowerCAmelCase_					    = list[tuple[int, int]]

lowerCAmelCase_					    = [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
]

lowerCAmelCase_					    = [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right






class  _lowerCAmelCase     :

      def __init__(   self      ,				__UpperCAmelCase      ,				__UpperCAmelCase      ,				__UpperCAmelCase      ,				__UpperCAmelCase      ,				__UpperCAmelCase		):
        lowerCAmelCase__				:  Union[str, Any]		       =     pos_x
        lowerCAmelCase__				:  Optional[int]		       =     pos_y
        lowerCAmelCase__				:  Union[str, Any]		       =     (pos_y, pos_x)
        lowerCAmelCase__				:  List[str]		       =     goal_x
        lowerCAmelCase__				:  Tuple		       =     goal_y
        lowerCAmelCase__				:  str		       =     parent






class  _lowerCAmelCase     :

      def __init__(   self      ,				__UpperCAmelCase      ,				__UpperCAmelCase		):
        lowerCAmelCase__				:  Optional[int]		       =     Node(start[1]      ,				start[0]      ,				goal[1]      ,				goal[0]      ,				__UpperCAmelCase		)
        lowerCAmelCase__				:  Any		       =     Node(goal[1]      ,				goal[0]      ,				goal[1]      ,				goal[0]      ,				__UpperCAmelCase		)

        lowerCAmelCase__				:  Tuple		       =     [self.start]
        lowerCAmelCase__				:  Union[str, Any]		       =     False

      def 	__magic_name__(   self		):
        while self.node_queue:
          lowerCAmelCase__				:  List[str]		       =     self.node_queue.pop(0		)

          if current_node.pos == self.target.pos:
            lowerCAmelCase__				:  Any		       =     True
            return self.retrace_path(__UpperCAmelCase		)

          lowerCAmelCase__				:  Optional[Any]		       =     self.get_successors(__UpperCAmelCase		)

          for node in successors:
            self.node_queue.append(__UpperCAmelCase		)

        if not self.reached:
          return [self.start.pos]
        return None

      def 	__magic_name__(   self      ,				__UpperCAmelCase		):
        lowerCAmelCase__				:  Dict		       =     []
        for action in delta:
          lowerCAmelCase__				:  List[str]		       =     parent.pos_x + action[1]
          lowerCAmelCase__				:  Tuple		       =     parent.pos_y + action[0]
          if not (0 <= pos_x <= len(grid[0]		) - 1 and 0 <= pos_y <= len(__UpperCAmelCase		) - 1):
            continue

          if grid[pos_y][pos_x] != 0:
            continue

          successors.append(
              Node(__UpperCAmelCase      ,				__UpperCAmelCase      ,				self.target.pos_y      ,				self.target.pos_x      ,				__UpperCAmelCase		)		)
        return successors







      def 	__magic_name__(   self      ,				__UpperCAmelCase		):
        lowerCAmelCase__				:  Union[str, Any]		       =     node
        lowerCAmelCase__				:  Any		       =     []
        while current_node is not None:
          path.append((current_node.pos_y, current_node.pos_x)		)
          lowerCAmelCase__				:  Tuple		       =     current_node.parent
        path.reverse()
        return path






class  _lowerCAmelCase     :

      def __init__(   self      ,				__UpperCAmelCase      ,				__UpperCAmelCase		):
        lowerCAmelCase__				:  int		       =     BreadthFirstSearch(__UpperCAmelCase      ,				__UpperCAmelCase		)
        lowerCAmelCase__				:  str		       =     BreadthFirstSearch(__UpperCAmelCase      ,				__UpperCAmelCase		)
        lowerCAmelCase__				:  int		       =     False

      def 	__magic_name__(   self		):
        while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
          lowerCAmelCase__				:  List[str]		       =     self.fwd_bfs.node_queue.pop(0		)
          lowerCAmelCase__				:  Tuple		       =     self.bwd_bfs.node_queue.pop(0		)

          if current_bwd_node.pos == current_fwd_node.pos:
            lowerCAmelCase__				:  Optional[int]		       =     True
            return self.retrace_bidirectional_path(
                __UpperCAmelCase      ,				__UpperCAmelCase		)

          lowerCAmelCase__				:  Union[str, Any]		       =     current_bwd_node
          lowerCAmelCase__				:  Any		       =     current_fwd_node

          lowerCAmelCase__				:  Tuple		       =     {
              self.fwd_bfs: self.fwd_bfs.get_successors(__UpperCAmelCase		),
              self.bwd_bfs: self.bwd_bfs.get_successors(__UpperCAmelCase		),
          }

          for bfs in [self.fwd_bfs, self.bwd_bfs]:
            for node in successors[bfs]:
              bfs.node_queue.append(__UpperCAmelCase		)

        if not self.reached:
          return [self.fwd_bfs.start.pos]
        return None







      def 	__magic_name__(   self      ,				__UpperCAmelCase      ,				__UpperCAmelCase		):
        lowerCAmelCase__				:  Union[str, Any]		       =     self.fwd_bfs.retrace_path(__UpperCAmelCase		)
        lowerCAmelCase__				:  Any		       =     self.bwd_bfs.retrace_path(__UpperCAmelCase		)
        bwd_path.pop()
        bwd_path.reverse()
        lowerCAmelCase__				:  Dict		       =     fwd_path + bwd_path
        return path


if __name__ == "__main__":
     # all coordinates are given in format [y,x]
     import doctest

     doctest.testmod()
     lowerCAmelCase_					    = (0, 0)
     lowerCAmelCase_					    = (len(grid) - 1, len(grid[0]) - 1)
     for elem in grid:
          print(elem)

     lowerCAmelCase_					    = time.time()
     lowerCAmelCase_					    = BreadthFirstSearch(init, goal)
     lowerCAmelCase_					    = bfs.search()
     lowerCAmelCase_					    = time.time() - start_bfs_time

     print("""Unidirectional BFS computation time : """, bfs_time)

     lowerCAmelCase_					    = time.time()
     lowerCAmelCase_					    = BidirectionalBreadthFirstSearch(init, goal)
     lowerCAmelCase_					    = bd_bfs.search()
     lowerCAmelCase_					    = time.time() - start_bd_bfs_time

     print("""Bidirectional BFS computation time : """, bd_bfs_time)







from collections import Counter
from timeit import timeit



def      __lowerCAmelCase			(					UpperCamelCase = ""	,      )     ->	bool:
  return sum(c % 2 for c in Counter(input_str.replace(''' '''	,      ''''''      ).lower()      ).values()      ) < 2



def      __lowerCAmelCase			(					UpperCamelCase = ""      )     ->	bool:
  if len(UpperCamelCase      ) == 0:
    return True
  lowerCAmelCase__				:  str		       =     input_str.replace(''' '''	,      ''''''      ).lower()
  # character_freq_dict: Stores the frequency of every character in the input string
  lowerCAmelCase__				:  dict[str, int]		       =     {}

  for character in lower_case_input_str:
    lowerCAmelCase__				:  int		       =     character_freq_dict.get(UpperCamelCase	,      0      ) + 1
  lowerCAmelCase__				:  Any		       =     0

  for character_count in character_freq_dict.values():
    if character_count % 2:
      odd_char += 1
  if odd_char > 1:
    return False
  return True



def      __lowerCAmelCase			(					UpperCamelCase = ""      )     ->	None:
  print('''\nFor string = '''	,      UpperCamelCase	,      ''':'''      )
  print(
      '''> can_string_be_rearranged_as_palindrome_counter()'''	,      '''\tans ='''	,      can_string_be_rearranged_as_palindrome_counter(UpperCamelCase      )	,      '''\ttime ='''	,      timeit(
          '''z.can_string_be_rearranged_as_palindrome_counter(z.check_str)'''	,      setup='''import __main__ as z'''	,      )	,      '''seconds'''	,      )
  print(
      '''> can_string_be_rearranged_as_palindrome()'''	,      '''\tans ='''	,      can_string_be_rearranged_as_palindrome(UpperCamelCase      )	,      '''\ttime ='''	,      timeit(
          '''z.can_string_be_rearranged_as_palindrome(z.check_str)'''	,      setup='''import __main__ as z'''	,      )	,      '''seconds'''	,      )


if __name__ == "__main__":
     lowerCAmelCase_					    = input(
         """Enter string to determine if it can be rearranged as a palindrome or not: """
     ).strip()
     benchmark(check_str)
     lowerCAmelCase_					    = can_string_be_rearranged_as_palindrome_counter(check_str)
     print(F"""{check_str} can {"" if status else "not "}be rearranged as a palindrome""")

