




from __future__ import annotations

import time

a         =      list[tuple[int, int]]

a         =      [
    [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],
]

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





class     lowercase_	:



 '''simple docstring'''

 def __init__(			self	:	str   ,							_UpperCAmelCase	:	int   ,							_UpperCAmelCase	:	int   ,							_UpperCAmelCase	:	int   ,							_UpperCAmelCase	:	int   ,							_UpperCAmelCase	:	Node | None		):
       _A        =       pos_x
       _A        =       pos_y
       _A        =       (pos_y, pos_x)
       _A        =       goal_x
       _A        =       goal_y
       _A        =       parent





class     lowercase_	:



 '''simple docstring'''

 def __init__(			self	:	Dict   ,							_UpperCAmelCase	:	tuple[int, int]   ,							_UpperCAmelCase	:	tuple[int, int]		):
       _A        =       Node(start[1]   ,							start[0]   ,							goal[1]   ,							goal[0]   ,							_UpperCAmelCase		)
       _A        =       Node(goal[1]   ,							goal[0]   ,							goal[1]   ,							goal[0]   ,							_UpperCAmelCase		)

       _A        =       [self.start]
       _A        =       False

 def       lowerCAmelCase_							(			self	:	Any		):
       while self.node_queue:
             _A        =       self.node_queue.pop(0		)

             if current_node.pos == self.target.pos:
                   _A        =       True
                   return self.retrace_path(_UpperCAmelCase		)

             _A        =       self.get_successors(_UpperCAmelCase		)

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

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

 def       lowerCAmelCase_							(			self	:	Optional[int]   ,							_UpperCAmelCase	:	Node		):
       _A        =       []
       for action in delta:
             _A        =       parent.pos_x + action[1]
             _A        =       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       lowerCAmelCase_							(			self	:	int   ,							_UpperCAmelCase	:	Node | None		):
       _A        =       node
       _A        =       []
       while current_node is not None:
             path.append((current_node.pos_y, current_node.pos_x)		)
             _A        =       current_node.parent
       path.reverse()
       return path





class     lowercase_	:



 '''simple docstring'''

 def __init__(			self	:	Optional[Any]   ,							_UpperCAmelCase	:	List[str]   ,							_UpperCAmelCase	:	Dict		):
       _A        =       BreadthFirstSearch(_UpperCAmelCase   ,							_UpperCAmelCase		)
       _A        =       BreadthFirstSearch(_UpperCAmelCase   ,							_UpperCAmelCase		)
       _A        =       False

 def       lowerCAmelCase_							(			self	:	int		):
       while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
             _A        =       self.fwd_bfs.node_queue.pop(0		)
             _A        =       self.bwd_bfs.node_queue.pop(0		)

             if current_bwd_node.pos == current_fwd_node.pos:
                   _A        =       True
                   return self.retrace_bidirectional_path(
                       _UpperCAmelCase   ,							_UpperCAmelCase		)

             _A        =       current_bwd_node
             _A        =       current_fwd_node

             _A        =       {
                 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       lowerCAmelCase_							(			self	:	int   ,							_UpperCAmelCase	:	Node   ,							_UpperCAmelCase	:	Node		):
       _A        =       self.fwd_bfs.retrace_path(_UpperCAmelCase		)
       _A        =       self.bwd_bfs.retrace_path(_UpperCAmelCase		)
       bwd_path.pop()
       bwd_path.reverse()
       _A        =       fwd_path + bwd_path
       return path


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

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

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

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

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

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







"""simple docstring"""

from collections import deque





class     lowercase_	:



 '''simple docstring'''

 def __init__(			self	:	int   ,							_UpperCAmelCase	:	str   ,							_UpperCAmelCase	:	int   ,							_UpperCAmelCase	:	int		):
       _A        =       process_name  # process name
       _A        =       arrival_time  # arrival time of the process
       # completion time of finished process or last interrupted time
       _A        =       arrival_time
       _A        =       burst_time  # remaining burst time
       _A        =       0  # total time of the process wait in ready queue
       _A        =       0  # time from arrival time to completion time





class     lowercase_	:



 '''simple docstring'''

 def __init__(			self	:	Optional[Any]   ,							_UpperCAmelCase	:	int   ,							_UpperCAmelCase	:	list[int]   ,							_UpperCAmelCase	:	deque[Process]   ,							_UpperCAmelCase	:	int   ,							):
       # total number of mlfq's queues
       _A        =       number_of_queues
       # time slice of queues that round robin algorithm applied
       _A        =       time_slices
       # unfinished process is in this ready_queue
       _A        =       queue
       # current time
       _A        =       current_time
       # finished process is in this sequence queue
       _A        =       deque()

 def       lowerCAmelCase_							(			self	:	Dict		):
       _A        =       []
       for i in range(len(self.finish_queue		)		):
             sequence.append(self.finish_queue[i].process_name		)
       return sequence

 def       lowerCAmelCase_							(			self	:	Optional[int]   ,							_UpperCAmelCase	:	list[Process]		):
       _A        =       []
       for i in range(len(_UpperCAmelCase		)		):
             waiting_times.append(queue[i].waiting_time		)
       return waiting_times

 def       lowerCAmelCase_							(			self	:	Dict   ,							_UpperCAmelCase	:	list[Process]		):
       _A        =       []
       for i in range(len(_UpperCAmelCase		)		):
             turnaround_times.append(queue[i].turnaround_time		)
       return turnaround_times

 def       lowerCAmelCase_							(			self	:	Optional[int]   ,							_UpperCAmelCase	:	list[Process]		):
       _A        =       []
       for i in range(len(_UpperCAmelCase		)		):
             completion_times.append(queue[i].stop_time		)
       return completion_times

 def       lowerCAmelCase_							(			self	:	Dict   ,							_UpperCAmelCase	:	deque[Process]		):
       return [q.burst_time for q in queue]

 def       lowerCAmelCase_							(			self	:	Dict   ,							_UpperCAmelCase	:	Process		):
       process.waiting_time += self.current_time - process.stop_time
       return process.waiting_time

 def       lowerCAmelCase_							(			self	:	int   ,							_UpperCAmelCase	:	deque[Process]		):
       _A        =       deque()  # sequence deque of finished process
       while len(_UpperCAmelCase		) != 0:
             _A        =       ready_queue.popleft()  # current process

             # if process's arrival time is later than current time, update current time
             if self.current_time < cp.arrival_time:
                   self.current_time += cp.arrival_time

             # update waiting time of current process
             self.update_waiting_time(_UpperCAmelCase		)
             # update current time
             self.current_time += cp.burst_time
             # finish the process and set the process's burst-time 0
             _A        =       0
             # set the process's turnaround time because it is finished
             _A        =       self.current_time - cp.arrival_time
             # set the completion time
             _A        =       self.current_time
             # add the process to queue that has finished queue
             finished.append(_UpperCAmelCase		)

       self.finish_queue.extend(_UpperCAmelCase		)  # add finished process to finish queue
       # FCFS will finish all remaining processes
       return finished

 def       lowerCAmelCase_							(			self	:	Dict   ,							_UpperCAmelCase	:	deque[Process]   ,							_UpperCAmelCase	:	int		):
       _A        =       deque()  # sequence deque of terminated process
       # just for 1 cycle and unfinished processes will go back to queue
       for _ in range(len(_UpperCAmelCase		)		):
             _A        =       ready_queue.popleft()  # current process

             # if process's arrival time is later than current time, update current time
             if self.current_time < cp.arrival_time:
                   self.current_time += cp.arrival_time

             # update waiting time of unfinished processes
             self.update_waiting_time(_UpperCAmelCase		)
             # if the burst time of process is bigger than time-slice
             if cp.burst_time > time_slice:
                   # use CPU for only time-slice
                   self.current_time += time_slice
                   # update remaining burst time
                   cp.burst_time -= time_slice
                   # update end point time
                   _A        =       self.current_time
                   # locate the process behind the queue because it is not finished
                   ready_queue.append(_UpperCAmelCase		)
             else:
                   # use CPU for remaining burst time
                   self.current_time += cp.burst_time
                   # set burst time 0 because the process is finished
                   _A        =       0
                   # set the finish time
                   _A        =       self.current_time
                   # update the process' turnaround time because it is finished
                   _A        =       self.current_time - cp.arrival_time
                   # add the process to queue that has finished queue
                   finished.append(_UpperCAmelCase		)

       self.finish_queue.extend(_UpperCAmelCase		)  # add finished process to finish queue
       # return finished processes queue and remaining processes queue
       return finished, ready_queue



 def       lowerCAmelCase_							(			self	:	str		):

       #  all queues except last one have round_robin algorithm
       for i in range(self.number_of_queues - 1		):
             _A       ,   _A        =       self.round_robin(
                 self.ready_queue   ,							self.time_slices[i]		)
       #  the last queue has first_come_first_served algorithm
       self.first_come_first_served(self.ready_queue		)

       return self.finish_queue


if __name__ == "__main__":
       import doctest

       a         =      Process('''P1''', 0, 53)
       a         =      Process('''P2''', 0, 17)
       a         =      Process('''P3''', 0, 68)
       a         =      Process('''P4''', 0, 24)
       a         =      3
       a         =      [17, 25]
       a         =      deque([Pa, Pa, Pa, Pa])

       if len(time_slices) != number_of_queues - 1:
              raise SystemExit(0)

       doctest.testmod(extraglobs={'''queue''': deque([Pa, Pa, Pa, Pa])})

       a         =      Process('''P1''', 0, 53)
       a         =      Process('''P2''', 0, 17)
       a         =      Process('''P3''', 0, 68)
       a         =      Process('''P4''', 0, 24)
       a         =      3
       a         =      [17, 25]
       a         =      deque([Pa, Pa, Pa, Pa])
       a         =      MLFQ(number_of_queues, time_slices, queue, 0)
       a         =      mlfq.multi_level_feedback_queue()

       # print total waiting times of processes(P1, P2, P3, P4)
       print(
           F'''waiting time:\
        \t\t\t{MLFQ.calculate_waiting_time(mlfq, [Pa, Pa, Pa, Pa])}'''
       )
       # print completion times of processes(P1, P2, P3, P4)
       print(
           F'''completion time:\
        \t\t{MLFQ.calculate_completion_time(mlfq, [Pa, Pa, Pa, Pa])}'''
       )
       # print total turnaround times of processes(P1, P2, P3, P4)
       print(
           F'''turnaround time:\
        \t\t{MLFQ.calculate_turnaround_time(mlfq, [Pa, Pa, Pa, Pa])}'''
       )
       # print sequence of finished processes
       print(
           F'''sequence of finished processes:\
        {mlfq.calculate_sequence_of_finish_queue()}'''
       )

