code: # This Python program implements an optimal binary search tree (abbreviated BST)
  # building dynamic programming algorithm that delivers O(n^2) performance.
  #
  # The goal of the optimal BST problem is to build a low-cost BST for a
  # given set of nodes, each with its own key and frequency. The frequency
  # of the node is defined as how many time the node is being searched.
  # The search cost of binary search tree is given by this formula:
  #
  # cost(1, n) = sum{i = 1 to n}((depth(node_i) + 1) * node_i_freq)
  #
  # where n is number of nodes in the BST. The characteristic of low-cost
  # BSTs is having a faster overall search time than other implementations.
  # The reason for their fast search time is that the nodes with high
  # frequencies will be placed near the root of the tree while the nodes
  # with low frequencies will be placed near the leaves of the tree thus
  # reducing search time in the most frequent instances.
  import sys
  from random import randint
  
  
  
  
  class 					UpperCamelCase	:
  
  
  
  
  					def __init__( self :					Optional[Any]      ,_lowerCAmelCase :					Tuple      ,_lowerCAmelCase :					List[Any]						):
  
  
  							"""simple docstring"""
  
  
  
  
  							__snake_case		       =     key
  							__snake_case		       =     freq
  
  
  
  
  
  
  
  					def __str__( self :					Union[str, Any]						):
  
  
  							"""simple docstring"""
  
  
  
  
  							return F"""Node(key={self.key}, freq={self.freq})"""
  
  
  
  
  def 							_lowerCamelCase(				__snake_case						,						__snake_case						,						__snake_case						,						__snake_case						,						__snake_case						,						__snake_case	)  ->   List[Any]:
  
  
  
  
  
  
  
  		if i > j or i < 0 or j > len(_A	) - 1:
  				return
  
  		__snake_case		       =     root[i][j]
  		if parent == -1:  # root does not have a parent
  				print(f"""{key[node]} is the root of the binary search tree."""	)
  		elif is_left:
  				print(f"""{key[node]} is the left child of key {parent}."""	)
  		else:
  				print(f"""{key[node]} is the right child of key {parent}."""	)
  
  		print_binary_search_tree(_A						,						_A						,						_A						,						node - 1						,						key[node]						,						_A	)
  		print_binary_search_tree(_A						,						_A						,						node + 1						,						_A						,						key[node]						,						_A	)
  
  
  
  def 							_lowerCamelCase(				__snake_case	)  ->   Tuple:
  		nodes.sort(key=lambda __snake_case	: node.key	)
  
  		__snake_case		       =     len(_A	)
  
  		__snake_case		       =     [nodes[i].key for i in range(_A	)]
  		__snake_case		       =     [nodes[i].freq for i in range(_A	)]
  
  		# This 2D array stores the overall tree cost (which's as minimized as possible);
  		# for a single key, cost is equal to frequency of the key.
  		__snake_case		       =     [[freqs[i] if i == j else 0 for j in range(_A	)] for i in range(_A	)]
  		# sum[i][j] stores the sum of key frequencies between i and j inclusive in nodes
  		# array
  		__snake_case		       =     [[freqs[i] if i == j else 0 for j in range(_A	)] for i in range(_A	)]
  		# stores tree roots that will be used later for constructing binary search tree
  		__snake_case		       =     [[i if i == j else 0 for j in range(_A	)] for i in range(_A	)]
  
  		for interval_length in range(2						,						n + 1	):
  				for i in range(n - interval_length + 1	):
  						__snake_case		       =     i + interval_length - 1
  
  						__snake_case		       =     sys.maxsize  # set the value to "infinity"
  						__snake_case		       =     total[i][j - 1] + freqs[j]
  
  						# Apply Knuth's optimization
  						# Loop without optimization: for r in range(i, j + 1):
  						for r in range(root[i][j - 1]						,						root[i + 1][j] + 1	):  # r is a temporal root
  								__snake_case		       =     dp[i][r - 1] if r != i else 0  # optimal cost for left subtree
  								__snake_case		       =     dp[r + 1][j] if r != j else 0  # optimal cost for right subtree
  								__snake_case		       =     left + total[i][j] + right
  
  								if dp[i][j] > cost:
  										__snake_case		       =     cost
  										__snake_case		       =     r
  
  		print("Binary search tree nodes:"	)
  		for node in nodes:
  				print(_A	)
  
  		print(f"""\nThe cost of optimal BST for given tree nodes is {dp[0][n - 1]}."""	)
  		print_binary_search_tree(_A						,						_A						,						0						,						n - 1						,						-1						,						_A	)
  
  
  
  def 							_lowerCamelCase(				)  ->   Optional[Any]:
  		__snake_case		       =     [Node(_A						,						randint(1						,						50	)	) for i in range(10						,						0						,						-1	)]
  		find_optimal_binary_search_tree(_A	)
  
  
  if __name__ == "__main__":
  		main()
  
  
  
  
  
  
style_context: import math
  from dataclasses import dataclass
  from typing import List, Optional, Union
  
  import numpy as np
  import PIL
  import torch
  from transformers import CLIPTextModelWithProjection, CLIPTokenizer
  
  from ...models import PriorTransformer
  from ...pipelines import DiffusionPipeline
  from ...schedulers import HeunDiscreteScheduler
  from ...utils import (
      BaseOutput,
      is_accelerate_available,
      is_accelerate_version,
      logging,
      randn_tensor,
      replace_example_docstring,
  )
  from .renderer import ShapERenderer
  
  
  lowerCamelCase__           =				logging.get_logger(__name__)  # pylint: disable=invalid-name
  
  lowerCamelCase__           =				'\n    Examples:\n        ```py\n        >>> import torch\n        >>> from diffusers import DiffusionPipeline\n        >>> from diffusers.utils import export_to_gif\n\n        >>> device = torch.device("cuda" if torch.cuda.is_available() else "cpu")\n\n        >>> repo = "openai/shap-e"\n        >>> pipe = DiffusionPipeline.from_pretrained(repo, torch_dtype=torch.float16)\n        >>> pipe = pipe.to(device)\n\n        >>> guidance_scale = 15.0\n        >>> prompt = "a shark"\n\n        >>> images = pipe(\n        ...     prompt,\n        ...     guidance_scale=guidance_scale,\n        ...     num_inference_steps=64,\n        ...     frame_size=256,\n        ... ).images\n\n        >>> gif_path = export_to_gif(images[0], "shark_3d.gif")\n        ```\n'
  
  
  
  
  @dataclass
  class 					UpperCamelCase	(     snake_case__      ):
  					__UpperCamelCase						=   42
  
  
  
  
  class 					UpperCamelCase	(     snake_case__      ):
  
  
  
  
  					def __init__( self :					int      ,_lowerCAmelCase :					PriorTransformer      ,_lowerCAmelCase :					CLIPTextModelWithProjection      ,_lowerCAmelCase :					CLIPTokenizer      ,_lowerCAmelCase :					HeunDiscreteScheduler      ,_lowerCAmelCase :					ShapERenderer      ,):
  
  
  							"""simple docstring"""
  
  
  
  
  							super().__init__()
  
  							self.register_modules(
  							    prior=_lowerCAmelCase      ,text_encoder=_lowerCAmelCase      ,tokenizer=_lowerCAmelCase      ,scheduler=_lowerCAmelCase      ,renderer=_lowerCAmelCase      ,)
  
  
  
  
  					def 							UpperCamelCase_						( self :					Union[str, Any]      ,_lowerCAmelCase :					List[Any]      ,_lowerCAmelCase :					List[str]      ,_lowerCAmelCase :					List[str]      ,_lowerCAmelCase :					Tuple      ,_lowerCAmelCase :					Union[str, Any]      ,_lowerCAmelCase :					Optional[int]						):
  
  
  							"""simple docstring"""
  
  
  
  
  							if latents is None:
  									__snake_case		       =     randn_tensor(_lowerCAmelCase      ,generator=_lowerCAmelCase      ,device=_lowerCAmelCase      ,dtype=_lowerCAmelCase						)
  							else:
  									if latents.shape != shape:
  											raise ValueError(F"""Unexpected latents shape, got {latents.shape}, expected {shape}"""						)
  									__snake_case		       =     latents.to(_lowerCAmelCase						)
  
  							__snake_case		       =     latents * scheduler.init_noise_sigma
  							return latents
  
  
  
  
  					def 							UpperCamelCase_						( self :					str      ,_lowerCAmelCase :					Optional[Any]=0						):
  
  
  							"""simple docstring"""
  
  
  
  
  							if is_accelerate_available():
  									from accelerate import cpu_offload
  							else:
  									raise ImportError("Please install accelerate via `pip install accelerate`"						)
  
  							__snake_case		       =     torch.device(F"""cuda:{gpu_id}"""						)
  
  							__snake_case		       =     [self.text_encoder, self.prior]
  							for cpu_offloaded_model in models:
  									if cpu_offloaded_model is not None:
  											cpu_offload(_lowerCAmelCase      ,_lowerCAmelCase						)
  
  
  
  
  					def 							UpperCamelCase_						( self :					Optional[int]      ,_lowerCAmelCase :					List[str]=0						):
  
  
  							"""simple docstring"""
  
  
  
  
  							if is_accelerate_available() and is_accelerate_version(">="      ,"0.17.0.dev0"						):
  									from accelerate import cpu_offload_with_hook
  							else:
  									raise ImportError("`enable_model_cpu_offload` requires `accelerate v0.17.0` or higher."						)
  
  							__snake_case		       =     torch.device(F"""cuda:{gpu_id}"""						)
  
  							if self.device.type != "cpu":
  									self.to("cpu"      ,silence_dtype_warnings=_lowerCAmelCase						)
  									torch.cuda.empty_cache()  # otherwise we don't see the memory savings (but they probably exist)
  
  							__snake_case		       =     None
  							for cpu_offloaded_model in [self.text_encoder, self.prior, self.renderer]:
  									__snake_case       ,       __snake_case		       =     cpu_offload_with_hook(_lowerCAmelCase      ,_lowerCAmelCase      ,prev_module_hook=_lowerCAmelCase						)
  
  							if self.safety_checker is not None:
  									__snake_case       ,       __snake_case		       =     cpu_offload_with_hook(self.safety_checker      ,_lowerCAmelCase      ,prev_module_hook=_lowerCAmelCase						)
  
  							# We'll offload the last model manually.
  							__snake_case		       =     hook
  
  
  
  
  					@property
  					def 							UpperCamelCase_						( self :					Optional[int]						):
  
  
  							"""simple docstring"""
  
  
  
  
  							if self.device != torch.device("meta"						) or not hasattr(self.text_encoder      ,"_hf_hook"						):
  									return self.device
  							for module in self.text_encoder.modules():
  									if (
  									    hasattr(_lowerCAmelCase      ,"_hf_hook"						)
  									    and hasattr(module._hf_hook      ,"execution_device"						)
  									    and module._hf_hook.execution_device is not None
  									):
  											return torch.device(module._hf_hook.execution_device						)
  							return self.device
  
  
  
  
  					def 							UpperCamelCase_						( self :					Optional[Any]      ,_lowerCAmelCase :					Dict      ,_lowerCAmelCase :					int      ,_lowerCAmelCase :					int      ,_lowerCAmelCase :					List[Any]      ,):
  
  
  							"""simple docstring"""
  
  
  
  
  							len(_lowerCAmelCase						) if isinstance(_lowerCAmelCase      ,_lowerCAmelCase						) else 1
  
  							# YiYi Notes: set pad_token_id to be 0, not sure why I can't set in the config file
  							__snake_case		       =     0
  							# get prompt text embeddings
  							__snake_case		       =     self.tokenizer(
  							    _lowerCAmelCase      ,padding="max_length"      ,max_length=self.tokenizer.model_max_length      ,truncation=_lowerCAmelCase      ,return_tensors="pt"      ,)
  							__snake_case		       =     text_inputs.input_ids
  							__snake_case		       =     self.tokenizer(_lowerCAmelCase      ,padding="longest"      ,return_tensors="pt"						).input_ids
  
  							if untruncated_ids.shape[-1] >= text_input_ids.shape[-1] and not torch.equal(_lowerCAmelCase      ,_lowerCAmelCase						):
  									__snake_case		       =     self.tokenizer.batch_decode(untruncated_ids[:, self.tokenizer.model_max_length - 1 : -1]						)
  									logger.warning(
  									    "The following part of your input was truncated because CLIP can only handle sequences up to"
  									    F""" {self.tokenizer.model_max_length} tokens: {removed_text}"""						)
  
  							__snake_case		       =     self.text_encoder(text_input_ids.to(_lowerCAmelCase						)						)
  							__snake_case		       =     text_encoder_output.text_embeds
  
  							__snake_case		       =     prompt_embeds.repeat_interleave(_lowerCAmelCase      ,dim=0						)
  							# in Shap-E it normalize the prompt_embeds and then later rescale it
  							__snake_case		       =     prompt_embeds / torch.linalg.norm(_lowerCAmelCase      ,dim=-1      ,keepdim=_lowerCAmelCase						)
  
  							if do_classifier_free_guidance:
  									__snake_case		       =     torch.zeros_like(_lowerCAmelCase						)
  
  									# For classifier free guidance, we need to do two forward passes.
  									# Here we concatenate the unconditional and text embeddings into a single batch
  									# to avoid doing two forward passes
  									__snake_case		       =     torch.cat([negative_prompt_embeds, prompt_embeds]						)
  
  							# Rescale the features to have unit variance
  							__snake_case		       =     math.sqrt(prompt_embeds.shape[1]						) * prompt_embeds
  
  							return prompt_embeds
  
  
  
  
  
  
  
  					@torch.no_grad()
  					@replace_example_docstring(_lowerCAmelCase						)
  					def __call__( self :					int      ,_lowerCAmelCase :					str      ,_lowerCAmelCase :					int = 1      ,_lowerCAmelCase :					int = 25      ,_lowerCAmelCase :					Optional[Union[torch.Generator, List[torch.Generator]]] = None      ,_lowerCAmelCase :					Optional[torch.FloatTensor] = None      ,_lowerCAmelCase :					float = 4.0      ,_lowerCAmelCase :					int = 64      ,_lowerCAmelCase :					Optional[str] = "pil"      ,_lowerCAmelCase :					bool = True      ,):
  
  
  							"""simple docstring"""
  
  
  
  
  							if isinstance(_lowerCAmelCase      ,_lowerCAmelCase						):
  									__snake_case		       =     1
  							elif isinstance(_lowerCAmelCase      ,_lowerCAmelCase						):
  									__snake_case		       =     len(_lowerCAmelCase						)
  							else:
  									raise ValueError(F"""`prompt` has to be of type `str` or `list` but is {type(_lowerCAmelCase						)}"""						)
  
  							__snake_case		       =     self._execution_device
  
  							__snake_case		       =     batch_size * num_images_per_prompt
  
  							__snake_case		       =     guidance_scale > 1.0
  							__snake_case		       =     self._encode_prompt(_lowerCAmelCase      ,_lowerCAmelCase      ,_lowerCAmelCase      ,_lowerCAmelCase						)
  
  							# prior
  
  							self.scheduler.set_timesteps(_lowerCAmelCase      ,device=_lowerCAmelCase						)
  							__snake_case		       =     self.scheduler.timesteps
  
  							__snake_case		       =     self.prior.config.num_embeddings
  							__snake_case		       =     self.prior.config.embedding_dim
  
  							__snake_case		       =     self.prepare_latents(
  							    (batch_size, num_embeddings * embedding_dim)      ,prompt_embeds.dtype      ,_lowerCAmelCase      ,_lowerCAmelCase      ,_lowerCAmelCase      ,self.scheduler      ,)
  
  							# YiYi notes: for testing only to match ldm, we can directly create a latents with desired shape: batch_size, num_embeddings, embedding_dim
  							__snake_case		       =     latents.reshape(latents.shape[0]      ,_lowerCAmelCase      ,_lowerCAmelCase						)
  
  							for i, t in enumerate(self.progress_bar(_lowerCAmelCase						)						):
  									# expand the latents if we are doing classifier free guidance
  									__snake_case		       =     torch.cat([latents] * 2						) if do_classifier_free_guidance else latents
  									__snake_case		       =     self.scheduler.scale_model_input(_lowerCAmelCase      ,_lowerCAmelCase						)
  
  									__snake_case		       =     self.prior(
  									    _lowerCAmelCase      ,timestep=_lowerCAmelCase      ,proj_embedding=_lowerCAmelCase      ,).predicted_image_embedding
  
  									# remove the variance
  									__snake_case       ,       __snake_case		       =     noise_pred.split(
  									    scaled_model_input.shape[2]      ,dim=2						)  # batch_size, num_embeddings, embedding_dim
  
  									if do_classifier_free_guidance is not None:
  											__snake_case       ,       __snake_case		       =     noise_pred.chunk(2						)
  											__snake_case		       =     noise_pred_uncond + guidance_scale * (noise_pred - noise_pred_uncond)
  
  									__snake_case		       =     self.scheduler.step(
  									    _lowerCAmelCase      ,timestep=_lowerCAmelCase      ,sample=_lowerCAmelCase      ,).prev_sample
  
  							if output_type == "latent":
  									return ShapEPipelineOutput(images=_lowerCAmelCase						)
  
  							__snake_case		       =     []
  							for i, latent in enumerate(_lowerCAmelCase						):
  									__snake_case		       =     self.renderer.decode(
  									    latent[None, :]      ,_lowerCAmelCase      ,size=_lowerCAmelCase      ,ray_batch_size=4_096      ,n_coarse_samples=64      ,n_fine_samples=128      ,)
  									images.append(_lowerCAmelCase						)
  
  							__snake_case		       =     torch.stack(_lowerCAmelCase						)
  
  							if output_type not in ["np", "pil"]:
  									raise ValueError(F"""Only the output types `pil` and `np` are supported not output_type={output_type}"""						)
  
  							__snake_case		       =     images.cpu().numpy()
  
  							if output_type == "pil":
  									__snake_case		       =     [self.numpy_to_pil(_lowerCAmelCase						) for image in images]
  
  							# Offload last model to CPU
  							if hasattr(self      ,"final_offload_hook"						) and self.final_offload_hook is not None:
  									self.final_offload_hook.offload()
  
  							if not return_dict:
  									return (images,)
  
  							return ShapEPipelineOutput(images=_lowerCAmelCase						)
  
  
  
  
  
  