
"""simple docstring"""



from heapq import heappop, heappush

import numpy as np






def 	__snake_case  (    SCREAMING_SNAKE_CASE:					np.ndarray     ,  SCREAMING_SNAKE_CASE:					tuple[int, int]     ,  SCREAMING_SNAKE_CASE:					tuple[int, int]     ,  SCREAMING_SNAKE_CASE:					bool     ,  ):
							_lowerCAmelCase	,		_lowerCAmelCase  	=			grid.shape
							_lowerCAmelCase  	=			[-1, 1, 0, 0]
							_lowerCAmelCase  	=			[0, 0, -1, 1]
							if allow_diagonal:
														dx += [-1, -1, 1, 1]
														dy += [-1, 1, -1, 1]

							_lowerCAmelCase	,		_lowerCAmelCase  	=			[(0, source)], set()
							_lowerCAmelCase  	=			np.full((rows, cols)     ,  np.inf						)
							_lowerCAmelCase  	=			0
							_lowerCAmelCase  	=			np.empty((rows, cols)     ,  dtype=SCREAMING_SNAKE_CASE						)
							_lowerCAmelCase  	=			None

							while queue:
														((_lowerCAmelCase)	,		(_lowerCAmelCase))  	=			heappop(SCREAMING_SNAKE_CASE						)
														if (x, y) in visited:
																					continue
														visited.add((x, y)						)

														if (x, y) == destination:
																					_lowerCAmelCase  	=			[]
																					while (x, y) != source:
																												path.append((x, y)						)
																												_lowerCAmelCase	,		_lowerCAmelCase  	=			predecessors[x, y]
																					path.append(SCREAMING_SNAKE_CASE						)  # add the source manually
																					path.reverse()
																					return matrix[destination], path

														for i in range(len(SCREAMING_SNAKE_CASE						)						):
																					_lowerCAmelCase	,		_lowerCAmelCase  	=			x + dx[i], y + dy[i]
																					if 0 <= nx < rows and 0 <= ny < cols:
																												_lowerCAmelCase  	=			grid[nx][ny]
																												if next_node == 1 and matrix[nx, ny] > dist + 1:
																																			heappush(SCREAMING_SNAKE_CASE     ,  (dist + 1, (nx, ny))						)
																																			_lowerCAmelCase  	=			dist + 1
																																			_lowerCAmelCase  	=			(x, y)

							return np.inf, []


if __name__ == "__main__":
	import doctest

	doctest.testmod()








"""simple docstring"""



import unittest

import numpy as np
import torch

from .utils_summarization import build_mask, compute_token_type_ids, process_story, truncate_or_pad
class        _SCREAMING_SNAKE_CASE  (  unittest.TestCase							):






				'''simple docstring'''



				def 				__lowerCamelCase	(					self	:			Any  )		->  Dict:







											"""simple docstring"""




											_lowerCAmelCase  	=			10


				def 				__lowerCamelCase	(					self	:			List[Any]  )		->  Optional[int]:







											"""simple docstring"""




											_lowerCAmelCase  	=			[1, 2, 3, 4]
											_lowerCAmelCase  	=			[1, 2, 3, 4, 0, 0, 0, 0, 0, 0]
											self.assertEqual(truncate_or_pad(UpperCAmelCase_				,     self.block_size				,     0  )				,     UpperCAmelCase_  )


				def 				__lowerCamelCase	(					self	:			Optional[int]  )		->  int:







											"""simple docstring"""




											_lowerCAmelCase  	=			[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
											_lowerCAmelCase  	=			[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
											self.assertEqual(truncate_or_pad(UpperCAmelCase_				,     self.block_size				,     0  )				,     UpperCAmelCase_  )


				def 				__lowerCamelCase	(					self	:			List[Any]  )		->  int:







											"""simple docstring"""




											_lowerCAmelCase  	=			[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
											_lowerCAmelCase  	=			[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
											self.assertEqual(truncate_or_pad(UpperCAmelCase_				,     self.block_size				,     0  )				,     UpperCAmelCase_  )


				def 				__lowerCamelCase	(					self	:			str  )		->  Optional[int]:







											"""simple docstring"""




											_lowerCAmelCase  	=			'It was the year of Our Lord one thousand seven hundred and\n        seventy-five.\n\nSpiritual revelations were conceded to England at that\n        favoured period, as at this.'
											_lowerCAmelCase	,		_lowerCAmelCase  	=			process_story(UpperCAmelCase_  )
											self.assertEqual(UpperCAmelCase_				,     []  )


				def 				__lowerCamelCase	(					self	:			Dict  )		->  Union[str, Any]:







											"""simple docstring"""




											_lowerCAmelCase  	=			''
											_lowerCAmelCase	,		_lowerCAmelCase  	=			process_story(UpperCAmelCase_  )
											self.assertEqual(UpperCAmelCase_				,     []  )
											self.assertEqual(UpperCAmelCase_				,     []  )


				def 				__lowerCamelCase	(					self	:			Optional[int]  )		->  List[str]:







											"""simple docstring"""




											_lowerCAmelCase  	=			(
											    'It was the year of Our Lord one thousand seven hundred and '
											    'seventy-five\n\nSpiritual revelations were conceded to England '
											    'at that favoured period, as at this.\n@highlight\n\nIt was the best of times'
											)
											_lowerCAmelCase	,		_lowerCAmelCase  	=			process_story(UpperCAmelCase_  )

											_lowerCAmelCase  	=			[
											    'It was the year of Our Lord one thousand seven hundred and seventy-five.',
											    'Spiritual revelations were conceded to England at that favoured period, as at this.',
											]
											self.assertEqual(UpperCAmelCase_				,     UpperCAmelCase_  )

											_lowerCAmelCase  	=			['It was the best of times.']
											self.assertEqual(UpperCAmelCase_				,     UpperCAmelCase_  )


				def 				__lowerCamelCase	(					self	:			List[str]  )		->  int:







											"""simple docstring"""




											_lowerCAmelCase  	=			torch.tensor([1, 2, 3, 4]  )
											_lowerCAmelCase  	=			torch.tensor([1, 1, 1, 1]  )
											np.testing.assert_array_equal(build_mask(UpperCAmelCase_				,     0  ).numpy()				,     expected.numpy()  )


				def 				__lowerCamelCase	(					self	:			int  )		->  str:







											"""simple docstring"""




											_lowerCAmelCase  	=			torch.tensor([1, 2, 3, 4, 23, 23, 23]  )
											_lowerCAmelCase  	=			torch.tensor([1, 1, 1, 1, 0, 0, 0]  )
											np.testing.assert_array_equal(build_mask(UpperCAmelCase_				,     23  ).numpy()				,     expected.numpy()  )


				def 				__lowerCamelCase	(					self	:			int  )		->  Union[str, Any]:







											"""simple docstring"""




											_lowerCAmelCase  	=			torch.tensor([8, 2, 3, 4, 1, 1, 1]  )
											_lowerCAmelCase  	=			torch.tensor([1, 1, 1, 1, 0, 0, 0]  )
											np.testing.assert_array_equal(build_mask(UpperCAmelCase_				,     1  ).numpy()				,     expected.numpy()  )







				def 				__lowerCamelCase	(					self	:			str  )		->  int:







											"""simple docstring"""




											_lowerCAmelCase  	=			101
											_lowerCAmelCase  	=			torch.tensor([[1, 2, 3, 4, 5, 6], [1, 2, 3, 101, 5, 6], [1, 101, 3, 4, 101, 6]]  )
											_lowerCAmelCase  	=			torch.tensor([[1, 1, 1, 1, 1, 1], [1, 1, 1, 0, 0, 0], [1, 0, 0, 0, 1, 1]]  )

											_lowerCAmelCase  	=			compute_token_type_ids(UpperCAmelCase_				,     UpperCAmelCase_  )
											np.testing.assert_array_equal(UpperCAmelCase_				,     UpperCAmelCase_  )






