


"""simple docstring"""




import torch
from torch import nn







class lowerCAmelCase_						(			nn.Module	):

 '''simple docstring'''

 def __init__(     self		,				_UpperCAmelCase		,				_UpperCAmelCase		,				_UpperCAmelCase		,				_UpperCAmelCase		,				_UpperCAmelCase=1		,				_UpperCAmelCase=False ):
       super().__init__()

       snake_case_	=				n_token
       snake_case_	=				d_embed
       snake_case_	=				d_proj

       snake_case_	=				cutoffs + [n_token]
       snake_case_	=				[0] + self.cutoffs
       snake_case_	=				div_val

       snake_case_	=				self.cutoffs[0]
       snake_case_	=				len(self.cutoffs ) - 1
       snake_case_	=				self.shortlist_size + self.n_clusters

       if self.n_clusters > 0:
             snake_case_	=				nn.Parameter(torch.zeros(self.n_clusters		,				self.d_embed ) )
             snake_case_	=				nn.Parameter(torch.zeros(self.n_clusters ) )

       snake_case_	=				nn.ModuleList()
       snake_case_	=				nn.ParameterList()

       if div_val == 1:
             for i in range(len(self.cutoffs ) ):
                   if d_proj != d_embed:
                         self.out_projs.append(nn.Parameter(torch.FloatTensor(_UpperCAmelCase		,				_UpperCAmelCase ) ) )
                   else:
                         self.out_projs.append(_UpperCAmelCase )

             self.out_layers.append(nn.Linear(_UpperCAmelCase		,				_UpperCAmelCase ) )
       else:
             for i in range(len(self.cutoffs ) ):
                   snake_case_	=				self.cutoff_ends[i], self.cutoff_ends[i + 1]
                   snake_case_	=				d_embed // (div_val**i)

                   self.out_projs.append(nn.Parameter(torch.FloatTensor(_UpperCAmelCase		,				_UpperCAmelCase ) ) )

                   self.out_layers.append(nn.Linear(_UpperCAmelCase		,				r_idx - l_idx ) )

       snake_case_	=				keep_order



 def 						UpperCamelCase__					(     self		,				_UpperCAmelCase		,				_UpperCAmelCase		,				_UpperCAmelCase		,				_UpperCAmelCase ):
       if proj is None:
             snake_case_	=				nn.functional.linear(_UpperCAmelCase		,				_UpperCAmelCase		,				bias=_UpperCAmelCase )
       else:
             # if CUDA_MAJOR <= 9 and CUDA_MINOR <= 1:
             snake_case_	=				nn.functional.linear(_UpperCAmelCase		,				proj.t().contiguous() )
             snake_case_	=				nn.functional.linear(_UpperCAmelCase		,				_UpperCAmelCase		,				bias=_UpperCAmelCase )
             # else:
             #     logit = torch.einsum('bd,de,ev->bv', (hidden, proj, weight.t()))
             #     if bias is not None:
             #         logit = logit + bias

       return logit



 def 						UpperCamelCase__					(     self		,				_UpperCAmelCase		,				_UpperCAmelCase=None		,				_UpperCAmelCase=False ):

       if labels is not None:
             # Shift so that tokens < n predict n
             snake_case_	=				hidden[..., :-1, :].contiguous()
             snake_case_	=				labels[..., 1:].contiguous()
             snake_case_	=				hidden.view(-1		,				hidden.size(-1 ) )
             snake_case_	=				labels.view(-1 )
             if hidden.size(0 ) != labels.size(0 ):
                   raise RuntimeError('''Input and labels should have the same size in the batch dimension.''' )
       else:
             snake_case_	=				hidden.view(-1		,				hidden.size(-1 ) )

       if self.n_clusters == 0:
             snake_case_	=				self._compute_logit(_UpperCAmelCase		,				self.out_layers[0].weight		,				self.out_layers[0].bias		,				self.out_projs[0] )
             if labels is not None:
                   snake_case_	=				labels != -1_00
                   snake_case_	=				torch.zeros_like(_UpperCAmelCase		,				dtype=hidden.dtype		,				device=hidden.device )
                   snake_case_	=				(
                       -nn.functional.log_softmax(_UpperCAmelCase		,				dim=-1 )[mask].gather(1		,				labels[mask].unsqueeze(1 ) ).squeeze(1 )
                   )
             else:
                   snake_case_	=				nn.functional.log_softmax(_UpperCAmelCase		,				dim=-1 )
       else:
             # construct weights and biases
             snake_case_	=				[], []
             for i in range(len(self.cutoffs ) ):
                   if self.div_val == 1:
                         snake_case_	=				self.cutoff_ends[i], self.cutoff_ends[i + 1]
                         snake_case_	=				self.out_layers[0].weight[l_idx:r_idx]
                         snake_case_	=				self.out_layers[0].bias[l_idx:r_idx]
                   else:
                         snake_case_	=				self.out_layers[i].weight
                         snake_case_	=				self.out_layers[i].bias

                   if i == 0:
                         snake_case_	=				torch.cat([weight_i, self.cluster_weight]		,				dim=0 )
                         snake_case_	=				torch.cat([bias_i, self.cluster_bias]		,				dim=0 )

                   weights.append(_UpperCAmelCase )
                   biases.append(_UpperCAmelCase )

             snake_case_	=				weights[0], biases[0], self.out_projs[0]

             snake_case_	=				self._compute_logit(_UpperCAmelCase		,				_UpperCAmelCase		,				_UpperCAmelCase		,				_UpperCAmelCase )
             snake_case_	=				nn.functional.log_softmax(_UpperCAmelCase		,				dim=1 )

             if labels is None:
                   snake_case_	=				hidden.new_empty((head_logit.size(0 ), self.n_token) )
             else:
                   snake_case_	=				torch.zeros_like(_UpperCAmelCase		,				dtype=hidden.dtype		,				device=hidden.device )

             snake_case_	=				0
             snake_case_	=				[0] + self.cutoffs
             for i in range(len(_UpperCAmelCase ) - 1 ):
                   snake_case_	=				cutoff_values[i], cutoff_values[i + 1]

                   if labels is not None:
                         snake_case_	=				(labels >= l_idx) & (labels < r_idx)
                         snake_case_	=				mask_i.nonzero().squeeze()

                         if indices_i.numel() == 0:
                               continue

                         snake_case_	=				labels.index_select(0		,				_UpperCAmelCase ) - l_idx
                         snake_case_	=				head_logprob.index_select(0		,				_UpperCAmelCase )
                         snake_case_	=				hidden.index_select(0		,				_UpperCAmelCase )
                   else:
                         snake_case_	=				hidden

                   if i == 0:
                         if labels is not None:
                               snake_case_	=				head_logprob_i.gather(1		,				target_i[:, None] ).squeeze(1 )
                         else:
                               snake_case_	=				head_logprob[:, : self.cutoffs[0]]
                   else:
                         snake_case_	=				weights[i], biases[i], self.out_projs[i]

                         snake_case_	=				self._compute_logit(_UpperCAmelCase		,				_UpperCAmelCase		,				_UpperCAmelCase		,				_UpperCAmelCase )
                         snake_case_	=				nn.functional.log_softmax(_UpperCAmelCase		,				dim=1 )
                         snake_case_	=				self.cutoffs[0] + i - 1  # No probability for the head cluster
                         if labels is not None:
                               snake_case_	=				head_logprob_i[:, cluster_prob_idx] + tail_logprob_i.gather(
                                   1		,				target_i[:, None] ).squeeze(1 )
                         else:
                               snake_case_	=				head_logprob[:, cluster_prob_idx, None] + tail_logprob_i
                               snake_case_	=				logprob_i

                   if labels is not None:
                         if (hasattr(self		,				'''keep_order''' ) and self.keep_order) or keep_order:
                               out.index_copy_(0		,				_UpperCAmelCase		,				-logprob_i )
                         else:
                               out[offset : offset + logprob_i.size(0 )].copy_(-logprob_i )
                         offset += logprob_i.size(0 )

       return out





 def 						UpperCamelCase__					(     self		,				_UpperCAmelCase ):
       if self.n_clusters == 0:
             snake_case_	=				self._compute_logit(_UpperCAmelCase		,				self.out_layers[0].weight		,				self.out_layers[0].bias		,				self.out_projs[0] )
             return nn.functional.log_softmax(_UpperCAmelCase		,				dim=-1 )
       else:
             # construct weights and biases
             snake_case_	=				[], []
             for i in range(len(self.cutoffs ) ):
                   if self.div_val == 1:
                         snake_case_	=				self.cutoff_ends[i], self.cutoff_ends[i + 1]
                         snake_case_	=				self.out_layers[0].weight[l_idx:r_idx]
                         snake_case_	=				self.out_layers[0].bias[l_idx:r_idx]
                   else:
                         snake_case_	=				self.out_layers[i].weight
                         snake_case_	=				self.out_layers[i].bias

                   if i == 0:
                         snake_case_	=				torch.cat([weight_i, self.cluster_weight]		,				dim=0 )
                         snake_case_	=				torch.cat([bias_i, self.cluster_bias]		,				dim=0 )

                   weights.append(_UpperCAmelCase )
                   biases.append(_UpperCAmelCase )

             snake_case_	=				weights[0], biases[0], self.out_projs[0]
             snake_case_	=				self._compute_logit(_UpperCAmelCase		,				_UpperCAmelCase		,				_UpperCAmelCase		,				_UpperCAmelCase )

             snake_case_	=				hidden.new_empty((head_logit.size(0 ), self.n_token) )
             snake_case_	=				nn.functional.log_softmax(_UpperCAmelCase		,				dim=1 )

             snake_case_	=				[0] + self.cutoffs
             for i in range(len(_UpperCAmelCase ) - 1 ):
                   snake_case_	=				cutoff_values[i], cutoff_values[i + 1]

                   if i == 0:
                         snake_case_	=				head_logprob[:, : self.cutoffs[0]]
                   else:
                         snake_case_	=				weights[i], biases[i], self.out_projs[i]

                         snake_case_	=				self._compute_logit(_UpperCAmelCase		,				_UpperCAmelCase		,				_UpperCAmelCase		,				_UpperCAmelCase )
                         snake_case_	=				nn.functional.log_softmax(_UpperCAmelCase		,				dim=1 )

                         snake_case_	=				head_logprob[:, -i] + tail_logprob_i
                         snake_case_	=				logprob_i

             return out



from __future__ import annotations

import time

UpperCAmelCase      =   list[tuple[int, int]]

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

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







class lowerCAmelCase_						:

 '''simple docstring'''

 def __init__(     self		,				_UpperCAmelCase		,				_UpperCAmelCase		,				_UpperCAmelCase		,				_UpperCAmelCase		,				_UpperCAmelCase ):
       snake_case_	=				pos_x
       snake_case_	=				pos_y
       snake_case_	=				(pos_y, pos_x)
       snake_case_	=				goal_x
       snake_case_	=				goal_y
       snake_case_	=				parent







class lowerCAmelCase_						:

 '''simple docstring'''

 def __init__(     self		,				_UpperCAmelCase		,				_UpperCAmelCase ):
       snake_case_	=				Node(start[1]		,				start[0]		,				goal[1]		,				goal[0]		,				_UpperCAmelCase )
       snake_case_	=				Node(goal[1]		,				goal[0]		,				goal[1]		,				goal[0]		,				_UpperCAmelCase )

       snake_case_	=				[self.start]
       snake_case_	=				False



 def 						UpperCamelCase__					(     self ):
       while self.node_queue:
             snake_case_	=				self.node_queue.pop(0 )

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

             snake_case_	=				self.get_successors(_UpperCAmelCase )

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

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



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







class lowerCAmelCase_						:

 '''simple docstring'''

 def __init__(     self		,				_UpperCAmelCase		,				_UpperCAmelCase ):
       snake_case_	=				BreadthFirstSearch(_UpperCAmelCase		,				_UpperCAmelCase )
       snake_case_	=				BreadthFirstSearch(_UpperCAmelCase		,				_UpperCAmelCase )
       snake_case_	=				False



 def 						UpperCamelCase__					(     self ):
       while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
             snake_case_	=				self.fwd_bfs.node_queue.pop(0 )
             snake_case_	=				self.bwd_bfs.node_queue.pop(0 )

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

             snake_case_	=				current_bwd_node
             snake_case_	=				current_fwd_node

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


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

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

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

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

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

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