




"""simple docstring"""

from __future__ import annotations

a							      =     list[list[int]]

# assigning initial values to the grid
a							      =     [
    [3, 0, 6, 5, 0, 8, 4, 0, 0],
    [5, 2, 0, 0, 0, 0, 0, 0, 0],
    [0, 8, 7, 0, 0, 0, 0, 3, 1],
    [0, 0, 3, 0, 1, 0, 0, 8, 0],
    [9, 0, 0, 8, 6, 3, 0, 0, 5],
    [0, 5, 0, 0, 9, 0, 6, 0, 0],
    [1, 3, 0, 0, 0, 0, 2, 5, 0],
    [0, 0, 0, 0, 0, 0, 0, 7, 4],
    [0, 0, 5, 2, 0, 6, 3, 0, 0],
]

# a grid with no solution
a							      =     [
    [5, 0, 6, 5, 0, 8, 4, 0, 3],
    [5, 2, 0, 0, 0, 0, 0, 0, 2],
    [1, 8, 7, 0, 0, 0, 0, 3, 1],
    [0, 0, 3, 0, 1, 0, 0, 8, 0],
    [9, 0, 0, 8, 6, 3, 0, 0, 5],
    [0, 5, 0, 0, 9, 0, 6, 0, 0],
    [1, 3, 0, 0, 0, 0, 2, 5, 0],
    [0, 0, 0, 0, 0, 0, 0, 7, 4],
    [0, 0, 5, 2, 0, 6, 3, 0, 0],
]






def 		_snake_case	(   _snake_case				:   Matrix							,    _snake_case				:   int							,    _snake_case				:   int							,    _snake_case				:   int				)       ->   bool:






      '''simple docstring'''


      for i in range(9				):
            if grid[row][i] == n or grid[i][column] == n:
                  return False

      for i in range(3				):
            for j in range(3				):
                  if grid[(row - row % 3) + i][(column - column % 3) + j] == n:
                        return False

      return True






def 		_snake_case	(   _snake_case				:   Matrix				)       ->   tuple[int, int] | None:






      '''simple docstring'''


      for i in range(9				):
            for j in range(9				):
                  if grid[i][j] == 0:
                        return i, j
      return None






def 		_snake_case	(   _snake_case				:   Matrix				)       ->   Matrix | None:






      '''simple docstring'''


      if location := find_empty_location(_snake_case				):
            _A  ,       _A     =  location
      else:
            # If the location is ``None``, then the grid is solved.
            return grid

      for digit in range(1							,    10				):
            if is_safe(_snake_case							,    _snake_case							,    _snake_case							,    _snake_case				):
                  _A     =  digit

                  if sudoku(_snake_case				) is not None:
                        return grid

                  _A     =  0

      return None






def 		_snake_case	(   _snake_case				:   Matrix				)       ->   None:






      '''simple docstring'''


      for row in grid:
            for cell in row:
                  print(_snake_case							,    end=' '				)
            print()


if __name__ == "__main__":
       # make a copy of grid so that you can compare with the unmodified grid
       for example_grid in (initial_grid, no_solution):
              print('''\nExample grid:\n''' + '''=''' * 20)
              print_solution(example_grid)
              print('''\nExample grid solution:''')
              a							      =     sudoku(example_grid)
              if solution is not None:
                     print_solution(solution)
              else:
                     print('''Cannot find a solution.''')








import collections
import tempfile
import unittest

import numpy as np

from transformers.testing_utils import (
    is_pt_flax_cross_test,
    require_flax,
    require_torch,
    require_vision,
    slow,
    torch_device,
)
from transformers.utils import is_flax_available, is_torch_available, is_vision_available

from ...test_modeling_flax_common import floats_tensor, ids_tensor, random_attention_mask
from ..bert.test_modeling_flax_bert import FlaxBertModelTester
from ..clip.test_modeling_flax_clip import FlaxCLIPVisionModelTester
from ..vit.test_modeling_flax_vit import FlaxViTModelTester


if is_flax_available():
    from transformers import (
        FlaxBertModel,
        FlaxCLIPVisionModel,
        FlaxVisionTextDualEncoderModel,
        FlaxViTModel,
        VisionTextDualEncoderConfig,
        VisionTextDualEncoderProcessor,
    )
    from transformers.modeling_flax_pytorch_utils import (
        convert_pytorch_state_dict_to_flax,
        load_flax_weights_in_pytorch_model,
    )


if is_torch_available():
    import torch

    from transformers import VisionTextDualEncoderModel

if is_vision_available():
    from PIL import Image






def 				_UpperCAmelCase			(    A     ):




   '''simple docstring'''

   if isinstance(A				,							collections.abc.Iterable     ):
      return x
   return (x, x)

@require_flax
class     snake_case_		:






 '''simple docstring'''





 def  __UpperCAmelCase						(  self,		A_,		A_		)	->       Dict:
    pass

 def  __UpperCAmelCase						(  self		)	->       List[str]:
    pass

 def  __UpperCAmelCase						(  self		)	->       str:
    pass

 def  __UpperCAmelCase						(  self,		A_,		A_,		A_		)	->       Optional[int]:
    UpperCAmelCase__						=np.abs((a - b)		).max()
    self.assertLessEqual(A_,		A_,		f"""Difference between torch and flax is {diff} (>= {tol})."""		)

 def  __UpperCAmelCase						(  self,		A_,		A_,		A_,		A_,		A_=None,		**A_		)	->       List[str]:
    UpperCAmelCase__						=VisionTextDualEncoderConfig.from_vision_text_configs(A_,		A_		)

    UpperCAmelCase__						=FlaxVisionTextDualEncoderModel(A_		)

    UpperCAmelCase__						=model(input_ids=A_,		pixel_values=A_,		attention_mask=A_		)

    self.assertEqual(output["text_embeds"].shape,		(input_ids.shape[0], config.projection_dim)		)
    self.assertEqual(output["image_embeds"].shape,		(pixel_values.shape[0], config.projection_dim)		)

 def  __UpperCAmelCase						(  self,		A_,		A_,		A_,		A_,		A_=None,		**A_		)	->       List[Any]:
    UpperCAmelCase__			,							UpperCAmelCase__						=self.get_vision_text_model(A_,		A_		)
    UpperCAmelCase__						={"vision_model": vision_model, "text_model": text_model}
    UpperCAmelCase__						=FlaxVisionTextDualEncoderModel.from_vision_text_pretrained(**A_		)

    UpperCAmelCase__						=model(input_ids=A_,		pixel_values=A_,		attention_mask=A_		)

    self.assertEqual(output["text_embeds"].shape,		(input_ids.shape[0], model.config.projection_dim)		)
    self.assertEqual(output["image_embeds"].shape,		(pixel_values.shape[0], model.config.projection_dim)		)

 def  __UpperCAmelCase						(  self,		A_,		A_,		A_,		A_,		A_=None,		**A_		)	->       Any:
    UpperCAmelCase__			,							UpperCAmelCase__						=self.get_vision_text_model(A_,		A_		)
    UpperCAmelCase__						={"vision_model": vision_model, "text_model": text_model}
    UpperCAmelCase__						=FlaxVisionTextDualEncoderModel.from_vision_text_pretrained(**A_		)

    UpperCAmelCase__						=model(input_ids=A_,		pixel_values=A_,		attention_mask=A_		)
    UpperCAmelCase__						=output[0]

    with tempfile.TemporaryDirectory() as tmpdirname:
       model.save_pretrained(A_		)
       UpperCAmelCase__						=FlaxVisionTextDualEncoderModel.from_pretrained(A_		)

       UpperCAmelCase__						=model(input_ids=A_,		pixel_values=A_,		attention_mask=A_		)
       UpperCAmelCase__						=after_output[0]
       UpperCAmelCase__						=np.amax(np.abs(out_a - out_a		)		)
       self.assertLessEqual(A_,		1E-3		)

 def  __UpperCAmelCase						(  self,		A_,		A_,		A_,		A_,		A_=None,		**A_		)	->       List[Any]:
    UpperCAmelCase__			,							UpperCAmelCase__						=self.get_vision_text_model(A_,		A_		)
    UpperCAmelCase__						={"vision_model": vision_model, "text_model": text_model}
    UpperCAmelCase__						=FlaxVisionTextDualEncoderModel.from_vision_text_pretrained(**A_		)

    UpperCAmelCase__						=model(
        input_ids=A_,		pixel_values=A_,		attention_mask=A_,		output_attentions=A_		)

    UpperCAmelCase__						=output.vision_model_output.attentions
    self.assertEqual(len(A_		),		vision_config.num_hidden_layers		)

    # in ViT, the seq_len equals the number of patches + 1 (we add 1 for the [CLS] token)
    UpperCAmelCase__						=to_atuple(vision_model.config.image_size		)
    UpperCAmelCase__						=to_atuple(vision_model.config.patch_size		)
    UpperCAmelCase__						=(image_size[1] // patch_size[1]) * (image_size[0] // patch_size[0])
    UpperCAmelCase__						=num_patches + 1
    self.assertEqual(vision_attentions[0].shape[-3:],		(vision_config.num_attention_heads, seq_len, seq_len)		)

    UpperCAmelCase__						=output.text_model_output.attentions
    self.assertEqual(len(A_		),		text_config.num_hidden_layers		)

    self.assertEqual(
        text_attentions[0].shape[-3:],		(text_config.num_attention_heads, input_ids.shape[-1], input_ids.shape[-1]),		)

 def  __UpperCAmelCase						(  self,		A_,		A_,		A_		)	->       Union[str, Any]:
    pt_model.to(A_		)
    pt_model.eval()

    # prepare inputs
    UpperCAmelCase__						=inputs_dict
    UpperCAmelCase__						={k: torch.tensor(v.tolist()		) for k, v in flax_inputs.items()}

    with torch.no_grad():
       UpperCAmelCase__						=pt_model(**A_		).to_tuple()

    UpperCAmelCase__						=fx_model(**A_		).to_tuple()
    self.assertEqual(len(A_		),		len(A_		),		"Output lengths differ between Flax and PyTorch"		)
    for fx_output, pt_output in zip(fx_outputs[:4],		pt_outputs[:4]		):
       self.assert_almost_equals(A_,		pt_output.numpy(),		4E-2		)

    # PT -> Flax
    with tempfile.TemporaryDirectory() as tmpdirname:
       pt_model.save_pretrained(A_		)
       UpperCAmelCase__						=FlaxVisionTextDualEncoderModel.from_pretrained(A_,		from_pt=A_		)

    UpperCAmelCase__						=fx_model_loaded(**A_		).to_tuple()
    self.assertEqual(len(A_		),		len(A_		),		"Output lengths differ between Flax and PyTorch"		)
    for fx_output_loaded, pt_output in zip(fx_outputs_loaded[:4],		pt_outputs[:4]		):
       self.assert_almost_equals(A_,		pt_output.numpy(),		4E-2		)

    # Flax -> PT
    with tempfile.TemporaryDirectory() as tmpdirname:
       fx_model.save_pretrained(A_		)
       UpperCAmelCase__						=VisionTextDualEncoderModel.from_pretrained(A_,		from_flax=A_		)

    pt_model_loaded.to(A_		)
    pt_model_loaded.eval()

    with torch.no_grad():
       UpperCAmelCase__						=pt_model_loaded(**A_		).to_tuple()

    self.assertEqual(len(A_		),		len(A_		),		"Output lengths differ between Flax and PyTorch"		)
    for fx_output, pt_output_loaded in zip(fx_outputs[:4],		pt_outputs_loaded[:4]		):
       self.assert_almost_equals(A_,		pt_output_loaded.numpy(),		4E-2		)

 def  __UpperCAmelCase						(  self,		A_,		A_,		A_		)	->       Tuple:
    UpperCAmelCase__						=VisionTextDualEncoderConfig.from_vision_text_configs(A_,		A_		)

    UpperCAmelCase__						=VisionTextDualEncoderModel(A_		)
    UpperCAmelCase__						=FlaxVisionTextDualEncoderModel(A_		)

    UpperCAmelCase__						=convert_pytorch_state_dict_to_flax(pt_model.state_dict(),		A_		)
    UpperCAmelCase__						=fx_state

    self.check_pt_flax_equivalence(A_,		A_,		A_		)

 def  __UpperCAmelCase						(  self,		A_,		A_,		A_		)	->       Dict:
    UpperCAmelCase__						=VisionTextDualEncoderConfig.from_vision_text_configs(A_,		A_		)

    UpperCAmelCase__						=VisionTextDualEncoderModel(A_		)
    UpperCAmelCase__						=FlaxVisionTextDualEncoderModel(A_		)

    UpperCAmelCase__						=load_flax_weights_in_pytorch_model(A_,		fx_model.params		)

    self.check_pt_flax_equivalence(A_,		A_,		A_		)

 def  __UpperCAmelCase						(  self		)	->       Tuple:
    UpperCAmelCase__						=self.prepare_config_and_inputs()
    self.check_model_from_pretrained_configs(**A_		)

 def  __UpperCAmelCase						(  self		)	->       List[str]:
    UpperCAmelCase__						=self.prepare_config_and_inputs()
    self.check_vision_text_dual_encoder_from_pretrained(**A_		)

 def  __UpperCAmelCase						(  self		)	->       Dict:
    UpperCAmelCase__						=self.prepare_config_and_inputs()
    self.check_save_load(**A_		)

 def  __UpperCAmelCase						(  self		)	->       Optional[Any]:
    UpperCAmelCase__						=self.prepare_config_and_inputs()
    self.check_vision_text_output_attention(**A_		)

 @is_pt_flax_cross_test
 def  __UpperCAmelCase						(  self		)	->       Dict:
    UpperCAmelCase__						=self.prepare_config_and_inputs()
    UpperCAmelCase__						=config_inputs_dict.pop("vision_config"		)
    UpperCAmelCase__						=config_inputs_dict.pop("text_config"		)

    UpperCAmelCase__						=config_inputs_dict

    self.check_equivalence_pt_to_flax(A_,		A_,		A_		)
    self.check_equivalence_flax_to_pt(A_,		A_,		A_		)






 @slow
 def  __UpperCAmelCase						(  self		)	->       Optional[Any]:
    UpperCAmelCase__			,							UpperCAmelCase__						=self.get_pretrained_model_and_inputs()

    UpperCAmelCase__						=model_a(**A_		)
    UpperCAmelCase__						=outputs[0]

    with tempfile.TemporaryDirectory() as tmp_dirname:
       model_a.save_pretrained(A_		)
       UpperCAmelCase__						=FlaxVisionTextDualEncoderModel.from_pretrained(A_		)

       UpperCAmelCase__						=model_a(**A_		)
       UpperCAmelCase__						=after_outputs[0]
       UpperCAmelCase__						=np.amax(np.abs(out_a - out_a		)		)
       self.assertLessEqual(A_,		1E-5		)

@require_flax
class     snake_case_		(   a,		unittest.TestCase							):






 '''simple docstring'''





 def  __UpperCAmelCase						(  self		)	->       Optional[Any]:
    UpperCAmelCase__						=FlaxVisionTextDualEncoderModel.from_vision_text_pretrained(
        "hf-internal-testing/tiny-random-vit",		"hf-internal-testing/tiny-bert",		vision_from_pt=A_,		text_from_pt=A_,		)
    UpperCAmelCase__						=13
    UpperCAmelCase__						=floats_tensor(
        [
            batch_size,
            model.config.vision_config.num_channels,
            model.config.vision_config.image_size,
            model.config.vision_config.image_size,
        ]		)
    UpperCAmelCase__						=ids_tensor([batch_size, 4],		model.config.text_config.vocab_size		)
    UpperCAmelCase__						=random_attention_mask([batch_size, 4]		)
    UpperCAmelCase__						={"pixel_values": pixel_values, "input_ids": input_ids, "attention_mask": attention_mask}

    return model, inputs

 def  __UpperCAmelCase						(  self,		A_,		A_		)	->       Optional[int]:
    UpperCAmelCase__						=FlaxViTModel(A_		)
    UpperCAmelCase__						=FlaxBertModel(A_		)
    return vision_model, text_model






 def  __UpperCAmelCase						(  self		)	->       int:
    UpperCAmelCase__						=FlaxViTModelTester(self		)
    UpperCAmelCase__						=FlaxBertModelTester(self		)
    UpperCAmelCase__						=vit_model_tester.prepare_config_and_inputs()
    UpperCAmelCase__						=bert_model_tester.prepare_config_and_inputs()

    UpperCAmelCase__			,							UpperCAmelCase__						=vision_config_and_inputs

    UpperCAmelCase__			,							UpperCAmelCase__			,							UpperCAmelCase__			,							UpperCAmelCase__						=text_config_and_inputs

    # make sure that cross attention layers are added
    return {
        "text_config": text_config,
        "vision_config": vision_config,
        "pixel_values": pixel_values,
        "attention_mask": attention_mask,
        "input_ids": input_ids,
        "token_type_ids": token_type_ids,
    }

@require_torch
class     snake_case_		(   a,		unittest.TestCase							):






 '''simple docstring'''





 def  __UpperCAmelCase						(  self		)	->       str:
    UpperCAmelCase__						=FlaxVisionTextDualEncoderModel.from_vision_text_pretrained(
        "hf-internal-testing/tiny-random-clip",		"hf-internal-testing/tiny-bert",		vision_from_pt=A_,		text_from_pt=A_,		)
    UpperCAmelCase__						=13
    UpperCAmelCase__						=floats_tensor(
        [
            batch_size,
            model.config.vision_config.num_channels,
            model.config.vision_config.image_size,
            model.config.vision_config.image_size,
        ]		)
    UpperCAmelCase__						=ids_tensor([batch_size, 4],		model.config.text_config.vocab_size		)
    UpperCAmelCase__						=random_attention_mask([batch_size, 4]		)
    UpperCAmelCase__						={"pixel_values": pixel_values, "input_ids": input_ids, "attention_mask": attention_mask}

    return model, inputs

 def  __UpperCAmelCase						(  self,		A_,		A_		)	->       Tuple:
    UpperCAmelCase__						=FlaxCLIPVisionModel(A_		)
    UpperCAmelCase__						=FlaxBertModel(A_		)
    return vision_model, text_model






 def  __UpperCAmelCase						(  self		)	->       Optional[Any]:
    UpperCAmelCase__						=FlaxCLIPVisionModelTester(self		)
    UpperCAmelCase__						=FlaxBertModelTester(self		)
    UpperCAmelCase__						=clip_model_tester.prepare_config_and_inputs()
    UpperCAmelCase__						=bert_model_tester.prepare_config_and_inputs()

    UpperCAmelCase__			,							UpperCAmelCase__						=vision_config_and_inputs

    UpperCAmelCase__			,							UpperCAmelCase__			,							UpperCAmelCase__			,							UpperCAmelCase__						=text_config_and_inputs

    # make sure that cross attention layers are added
    return {
        "text_config": text_config,
        "vision_config": vision_config,
        "pixel_values": pixel_values,
        "attention_mask": attention_mask,
        "input_ids": input_ids,
        "token_type_ids": token_type_ids,
    }

@require_flax
@require_vision
class     snake_case_		(   unittest.TestCase							):






 '''simple docstring'''





 @slow
 def  __UpperCAmelCase						(  self		)	->       Union[str, Any]:
    UpperCAmelCase__						=FlaxVisionTextDualEncoderModel.from_pretrained("clip-italian/clip-italian",		logit_scale_init_value=1.0		)
    UpperCAmelCase__						=VisionTextDualEncoderProcessor.from_pretrained("clip-italian/clip-italian"		)

    UpperCAmelCase__						=Image.open("./tests/fixtures/tests_samples/COCO/000000039769.png"		)
    UpperCAmelCase__						=processor(
        text=["una foto di un gatto", "una foto di un cane"],		images=A_,		padding=A_,		return_tensors="np"		)

    UpperCAmelCase__						=model(**A_		)

    # verify the logits
    self.assertEqual(outputs.logits_per_image.shape,		(inputs.pixel_values.shape[0], inputs.input_ids.shape[0])		)
    self.assertEqual(
        outputs.logits_per_text.shape,		(inputs.input_ids.shape[0], inputs.pixel_values.shape[0]),		)

    UpperCAmelCase__						=np.array([[1.2_28_47_27, 0.3_10_41_22]]		)

    self.assertTrue(np.allclose(outputs.logits_per_image,		A_,		atol=1E-3		)		)



