





'''simple docstring'''




import inspect
import unittest

import torch
import torch.nn as nn

from accelerate.hooks import (
    AlignDevicesHook,
    ModelHook,
    SequentialHook,
    add_hook_to_module,
    attach_align_device_hook,
    remove_hook_from_module,
    remove_hook_from_submodules,
)
from accelerate.test_utils import require_multi_gpu






class 				__snake_case     (					nn.Module							):





	def __init__(		self		)      ->		str:
		super().__init__()
		snake_case__	       =   nn.Linear(3      ,       4		)
		snake_case__	       =   nn.BatchNormad(4		)
		snake_case__	       =   nn.Linear(4      ,       5		)





	def   _snake_case   (		self      ,       UpperCamelCase_		)      ->		Tuple:
		return self.lineara(self.batchnorm(self.lineara(UpperCamelCase_		)		)		)






class 				__snake_case     (					__magic_name__							):





	def   _snake_case   (		self      ,       UpperCamelCase_      ,       *UpperCamelCase_      ,       **UpperCamelCase_		)      ->		str:
		return (args[0] + 1,) + args[1:], kwargs






class 				__snake_case     (					__magic_name__							):





	def   _snake_case   (		self      ,       UpperCamelCase_      ,       UpperCamelCase_		)      ->		Tuple:
		return output + 1






class 				__snake_case     (					unittest.TestCase							):





	def   _snake_case   (		self		)      ->		str:
		snake_case__	       =   ModelForTest()
		snake_case__	       =   ModelHook()

		add_hook_to_module(UpperCamelCase_      ,       UpperCamelCase_		)
		self.assertEqual(test_model._hf_hook      ,       UpperCamelCase_		)
		self.assertTrue(hasattr(UpperCamelCase_      ,       '_old_forward'		)		)

		# Check adding the hook did not change the name or the signature
		self.assertEqual(test_model.forward.__name__      ,       'forward'		)
		self.assertListEqual(list(inspect.signature(test_model.forward		).parameters		)      ,       ['x']		)

		remove_hook_from_module(UpperCamelCase_		)
		self.assertFalse(hasattr(UpperCamelCase_      ,       '_hf_hook'		)		)
		self.assertFalse(hasattr(UpperCamelCase_      ,       '_old_forward'		)		)





	def   _snake_case   (		self		)      ->		Dict:
		snake_case__	       =   ModelForTest()
		snake_case__	       =   ModelHook()

		add_hook_to_module(UpperCamelCase_      ,       UpperCamelCase_		)
		add_hook_to_module(UpperCamelCase_      ,       UpperCamelCase_      ,       append=UpperCamelCase_		)

		self.assertEqual(isinstance(test_model._hf_hook      ,       UpperCamelCase_		)      ,       UpperCamelCase_		)
		self.assertEqual(len(test_model._hf_hook.hooks		)      ,       2		)
		self.assertTrue(hasattr(UpperCamelCase_      ,       '_old_forward'		)		)

		# Check adding the hook did not change the name or the signature
		self.assertEqual(test_model.forward.__name__      ,       'forward'		)
		self.assertListEqual(list(inspect.signature(test_model.forward		).parameters		)      ,       ['x']		)

		remove_hook_from_module(UpperCamelCase_		)
		self.assertFalse(hasattr(UpperCamelCase_      ,       '_hf_hook'		)		)
		self.assertFalse(hasattr(UpperCamelCase_      ,       '_old_forward'		)		)





	def   _snake_case   (		self		)      ->		Dict:
		snake_case__	       =   ModelForTest()
		snake_case__	       =   torch.randn(2      ,       3		)
		snake_case__	       =   test_model(x + 1		)
		snake_case__	       =   test_model(x + 2		)

		snake_case__	       =   PreForwardHook()
		add_hook_to_module(UpperCamelCase_      ,       UpperCamelCase_		)
		snake_case__	       =   test_model(UpperCamelCase_		)
		self.assertTrue(torch.allclose(UpperCamelCase_      ,       UpperCamelCase_      ,       atol=1E-5		)		)

		# Attaching a hook to a model when it already has one replaces, does not chain
		snake_case__	       =   PreForwardHook()
		add_hook_to_module(UpperCamelCase_      ,       UpperCamelCase_		)
		snake_case__	       =   test_model(UpperCamelCase_		)
		self.assertTrue(torch.allclose(UpperCamelCase_      ,       UpperCamelCase_      ,       atol=1E-5		)		)

		# You need to use the sequential hook to chain two or more hooks
		snake_case__	       =   SequentialHook(PreForwardHook()      ,       PreForwardHook()		)
		add_hook_to_module(UpperCamelCase_      ,       UpperCamelCase_		)

		snake_case__	       =   test_model(UpperCamelCase_		)
		assert torch.allclose(UpperCamelCase_      ,       UpperCamelCase_      ,       atol=1E-5		)





	def   _snake_case   (		self		)      ->		List[Any]:
		snake_case__	       =   ModelForTest()
		snake_case__	       =   torch.randn(2      ,       3		)
		snake_case__	       =   test_model(UpperCamelCase_		)

		snake_case__	       =   PostForwardHook()
		add_hook_to_module(UpperCamelCase_      ,       UpperCamelCase_		)
		snake_case__	       =   test_model(UpperCamelCase_		)
		self.assertTrue(torch.allclose(UpperCamelCase_      ,       output + 1      ,       atol=1E-5		)		)

		# Attaching a hook to a model when it already has one replaces, does not chain
		snake_case__	       =   PostForwardHook()
		add_hook_to_module(UpperCamelCase_      ,       UpperCamelCase_		)
		snake_case__	       =   test_model(UpperCamelCase_		)
		self.assertTrue(torch.allclose(UpperCamelCase_      ,       output + 1      ,       atol=1E-5		)		)

		# You need to use the sequential hook to chain two or more hooks
		snake_case__	       =   SequentialHook(PostForwardHook()      ,       PostForwardHook()		)
		add_hook_to_module(UpperCamelCase_      ,       UpperCamelCase_		)

		snake_case__	       =   test_model(UpperCamelCase_		)
		assert torch.allclose(UpperCamelCase_      ,       output + 2      ,       atol=1E-5		)





	def   _snake_case   (		self		)      ->		Tuple:
		snake_case__	       =   ModelForTest()
		snake_case__	       =   torch.randn(2      ,       3		)
		snake_case__	       =   test_model(UpperCamelCase_		)

		snake_case__	       =   PostForwardHook()
		add_hook_to_module(UpperCamelCase_      ,       UpperCamelCase_		)
		snake_case__	       =   test_model(UpperCamelCase_		)
		self.assertTrue(torch.allclose(UpperCamelCase_      ,       output + 1		)		)
		self.assertTrue(outputa.requires_grad		)

		snake_case__	       =   True
		snake_case__	       =   test_model(UpperCamelCase_		)
		self.assertFalse(outputa.requires_grad		)





	@require_multi_gpu
	def   _snake_case   (		self		)      ->		Union[str, Any]:
		snake_case__	       =   ModelForTest()
		# Everything is on CPU
		self.assertEqual(model.lineara.weight.device      ,       torch.device('cpu'		)		)
		self.assertEqual(model.batchnorm.weight.device      ,       torch.device('cpu'		)		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('cpu'		)		)

		# This will move each submodule on different devices
		add_hook_to_module(model.lineara      ,       AlignDevicesHook(execution_device=0		)		)
		add_hook_to_module(model.batchnorm      ,       AlignDevicesHook(execution_device=0		)		)
		add_hook_to_module(model.lineara      ,       AlignDevicesHook(execution_device=1		)		)

		self.assertEqual(model.lineara.weight.device      ,       torch.device(0		)		)
		self.assertEqual(model.batchnorm.weight.device      ,       torch.device(0		)		)
		self.assertEqual(model.batchnorm.running_mean.device      ,       torch.device(0		)		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device(1		)		)

		# We can still make a forward pass. The input does not need to be on any particular device
		snake_case__	       =   torch.randn(2      ,       3		)
		snake_case__	       =   model(UpperCamelCase_		)
		self.assertEqual(output.device      ,       torch.device(1		)		)

		# We can add a general hook to put back output on same device as input.
		add_hook_to_module(UpperCamelCase_      ,       AlignDevicesHook(io_same_device=UpperCamelCase_		)		)
		snake_case__	       =   torch.randn(2      ,       3		).to(0		)
		snake_case__	       =   model(UpperCamelCase_		)
		self.assertEqual(output.device      ,       torch.device(0		)		)





	def   _snake_case   (		self		)      ->		Tuple:
		snake_case__	       =   ModelForTest()

		# Everything is on CPU
		self.assertEqual(model.lineara.weight.device      ,       torch.device('cpu'		)		)
		self.assertEqual(model.batchnorm.weight.device      ,       torch.device('cpu'		)		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('cpu'		)		)

		# This will move each submodule on different devices
		snake_case__	       =   {'execution_device': 0 if torch.cuda.is_available() else 'cpu', 'offload': True}

		add_hook_to_module(model.lineara      ,       AlignDevicesHook(**UpperCamelCase_		)		)
		add_hook_to_module(model.batchnorm      ,       AlignDevicesHook(**UpperCamelCase_		)		)
		add_hook_to_module(model.lineara      ,       AlignDevicesHook(**UpperCamelCase_		)		)

		# Parameters have been offloaded, so on the meta device
		self.assertEqual(model.lineara.weight.device      ,       torch.device('meta'		)		)
		self.assertEqual(model.batchnorm.weight.device      ,       torch.device('meta'		)		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('meta'		)		)
		# Buffers are not included in the offload by default, so are on the execution device
		snake_case__	       =   torch.device(hook_kwargs['execution_device']		)
		self.assertEqual(model.batchnorm.running_mean.device      ,       UpperCamelCase_		)

		snake_case__	       =   torch.randn(2      ,       3		)
		snake_case__	       =   model(UpperCamelCase_		)
		self.assertEqual(output.device      ,       UpperCamelCase_		)

		# Removing hooks loads back the weights in the model.
		remove_hook_from_module(model.lineara		)
		remove_hook_from_module(model.batchnorm		)
		remove_hook_from_module(model.lineara		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('cpu'		)		)
		self.assertEqual(model.batchnorm.weight.device      ,       torch.device('cpu'		)		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('cpu'		)		)

		# Now test with buffers included in the offload
		snake_case__	       =   {
		    'execution_device': 0 if torch.cuda.is_available() else 'cpu',
		    'offload': True,
		    'offload_buffers': True,
		}

		add_hook_to_module(model.lineara      ,       AlignDevicesHook(**UpperCamelCase_		)		)
		add_hook_to_module(model.batchnorm      ,       AlignDevicesHook(**UpperCamelCase_		)		)
		add_hook_to_module(model.lineara      ,       AlignDevicesHook(**UpperCamelCase_		)		)

		# Parameters have been offloaded, so on the meta device, buffers included
		self.assertEqual(model.lineara.weight.device      ,       torch.device('meta'		)		)
		self.assertEqual(model.batchnorm.weight.device      ,       torch.device('meta'		)		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('meta'		)		)
		self.assertEqual(model.batchnorm.running_mean.device      ,       torch.device('meta'		)		)

		snake_case__	       =   torch.randn(2      ,       3		)
		snake_case__	       =   model(UpperCamelCase_		)
		self.assertEqual(output.device      ,       UpperCamelCase_		)

		# Removing hooks loads back the weights in the model.
		remove_hook_from_module(model.lineara		)
		remove_hook_from_module(model.batchnorm		)
		remove_hook_from_module(model.lineara		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('cpu'		)		)
		self.assertEqual(model.batchnorm.weight.device      ,       torch.device('cpu'		)		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('cpu'		)		)





	def   _snake_case   (		self		)      ->		Any:
		snake_case__	       =   ModelForTest()

		# Everything is on CPU
		self.assertEqual(model.lineara.weight.device      ,       torch.device('cpu'		)		)
		self.assertEqual(model.batchnorm.weight.device      ,       torch.device('cpu'		)		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('cpu'		)		)

		# This will move each submodule on different devices
		snake_case__	       =   0 if torch.cuda.is_available() else 'cpu'
		attach_align_device_hook(UpperCamelCase_      ,       execution_device=UpperCamelCase_      ,       offload=UpperCamelCase_		)

		# Parameters have been offloaded, so on the meta device
		self.assertEqual(model.lineara.weight.device      ,       torch.device('meta'		)		)
		self.assertEqual(model.batchnorm.weight.device      ,       torch.device('meta'		)		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('meta'		)		)
		# Buffers are not included in the offload by default, so are on the execution device
		snake_case__	       =   torch.device(UpperCamelCase_		)
		self.assertEqual(model.batchnorm.running_mean.device      ,       UpperCamelCase_		)

		snake_case__	       =   torch.randn(2      ,       3		)
		snake_case__	       =   model(UpperCamelCase_		)
		self.assertEqual(output.device      ,       UpperCamelCase_		)

		# Removing hooks loads back the weights in the model.
		remove_hook_from_submodules(UpperCamelCase_		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('cpu'		)		)
		self.assertEqual(model.batchnorm.weight.device      ,       torch.device('cpu'		)		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('cpu'		)		)

		# Now test with buffers included in the offload
		attach_align_device_hook(UpperCamelCase_      ,       execution_device=UpperCamelCase_      ,       offload=UpperCamelCase_      ,       offload_buffers=UpperCamelCase_		)

		# Parameters have been offloaded, so on the meta device, buffers included
		self.assertEqual(model.lineara.weight.device      ,       torch.device('meta'		)		)
		self.assertEqual(model.batchnorm.weight.device      ,       torch.device('meta'		)		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('meta'		)		)
		self.assertEqual(model.batchnorm.running_mean.device      ,       torch.device('meta'		)		)

		snake_case__	       =   torch.randn(2      ,       3		)
		snake_case__	       =   model(UpperCamelCase_		)
		self.assertEqual(output.device      ,       UpperCamelCase_		)

		# Removing hooks loads back the weights in the model.
		remove_hook_from_submodules(UpperCamelCase_		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('cpu'		)		)
		self.assertEqual(model.batchnorm.weight.device      ,       torch.device('cpu'		)		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('cpu'		)		)





	def   _snake_case   (		self		)      ->		Dict:
		snake_case__	       =   ModelForTest()

		# Everything is on CPU
		self.assertEqual(model.lineara.weight.device      ,       torch.device('cpu'		)		)
		self.assertEqual(model.batchnorm.weight.device      ,       torch.device('cpu'		)		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('cpu'		)		)

		# This will move each submodule on different devices
		snake_case__	       =   0 if torch.cuda.is_available() else 'cpu'
		attach_align_device_hook(
		    UpperCamelCase_      ,       execution_device=UpperCamelCase_      ,       offload=UpperCamelCase_      ,       weights_map=model.state_dict()		)

		# Parameters have been offloaded, so on the meta device
		self.assertEqual(model.lineara.weight.device      ,       torch.device('meta'		)		)
		self.assertEqual(model.batchnorm.weight.device      ,       torch.device('meta'		)		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('meta'		)		)
		# Buffers are not included in the offload by default, so are on the execution device
		snake_case__	       =   torch.device(UpperCamelCase_		)
		self.assertEqual(model.batchnorm.running_mean.device      ,       UpperCamelCase_		)

		snake_case__	       =   torch.randn(2      ,       3		)
		snake_case__	       =   model(UpperCamelCase_		)
		self.assertEqual(output.device      ,       UpperCamelCase_		)

		# Removing hooks loads back the weights in the model.
		remove_hook_from_submodules(UpperCamelCase_		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('cpu'		)		)
		self.assertEqual(model.batchnorm.weight.device      ,       torch.device('cpu'		)		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('cpu'		)		)

		# Now test with buffers included in the offload
		attach_align_device_hook(
		    UpperCamelCase_      ,       execution_device=UpperCamelCase_      ,       offload=UpperCamelCase_      ,       weights_map=model.state_dict()      ,       offload_buffers=UpperCamelCase_      ,       )

		# Parameters have been offloaded, so on the meta device, buffers included
		self.assertEqual(model.lineara.weight.device      ,       torch.device('meta'		)		)
		self.assertEqual(model.batchnorm.weight.device      ,       torch.device('meta'		)		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('meta'		)		)
		self.assertEqual(model.batchnorm.running_mean.device      ,       torch.device('meta'		)		)

		snake_case__	       =   torch.randn(2      ,       3		)
		snake_case__	       =   model(UpperCamelCase_		)
		self.assertEqual(output.device      ,       UpperCamelCase_		)

		# Removing hooks loads back the weights in the model.
		remove_hook_from_submodules(UpperCamelCase_		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('cpu'		)		)
		self.assertEqual(model.batchnorm.weight.device      ,       torch.device('cpu'		)		)
		self.assertEqual(model.lineara.weight.device      ,       torch.device('cpu'		)		)










'''simple docstring'''




from __future__ import annotations

import math




def 						__lowerCamelCase			(	UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_							)   ->int:

	if depth < 0:
		raise ValueError('Depth cannot be less than 0'							)

	if not scores:
		raise ValueError('Scores cannot be empty'							)

	if depth == height:
		return scores[node_index]

	return (
	    max(
	        minimax(depth + 1					,				node_index * 2					,				UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_							)					,				minimax(depth + 1					,				node_index * 2 + 1					,				UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_							)					,				)
	    if is_max
	    else min(
	        minimax(depth + 1					,				node_index * 2					,				UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_							)					,				minimax(depth + 1					,				node_index * 2 + 1					,				UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_							)					,				)
	)




def 						__lowerCamelCase			(	)   ->None:
	snake_case__	       =   [90, 23, 6, 33, 21, 65, 1_23, 3_44_23]
	snake_case__	       =   math.log(len(UpperCAmelCase_							)					,				2							)
	print(f'''Optimal value : {minimax(0					,				0					,				UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_							)}'''							)


if __name__ == "__main__":
			import doctest

			doctest.testmod()
			main()



