





'''simple docstring'''



from __future__ import annotations

from PIL import Image

# Define glider example
__magic_name__   :						str    =			[
    [0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0, 0],
    [1, 1, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
]

# Define blinker example
__magic_name__   :						List[Any]    =			[[0, 1, 0], [0, 1, 0], [0, 1, 0]]




def 				snake_case_      (		SCREAMING_SNAKE_CASE__       ):







  '''simple docstring'''



  _snake_case     		=				[]
  for i in range(len(SCREAMING_SNAKE_CASE__       )       ):
    _snake_case     		=				[]
    for j in range(len(cells[i]       )       ):
      # Get the number of live neighbours
      _snake_case     		=				0
      if i > 0 and j > 0:
        neighbour_count += cells[i - 1][j - 1]
      if i > 0:
        neighbour_count += cells[i - 1][j]
      if i > 0 and j < len(cells[i]       ) - 1:
        neighbour_count += cells[i - 1][j + 1]
      if j > 0:
        neighbour_count += cells[i][j - 1]
      if j < len(cells[i]       ) - 1:
        neighbour_count += cells[i][j + 1]
      if i < len(SCREAMING_SNAKE_CASE__       ) - 1 and j > 0:
        neighbour_count += cells[i + 1][j - 1]
      if i < len(SCREAMING_SNAKE_CASE__       ) - 1:
        neighbour_count += cells[i + 1][j]
      if i < len(SCREAMING_SNAKE_CASE__       ) - 1 and j < len(cells[i]       ) - 1:
        neighbour_count += cells[i + 1][j + 1]

      # Rules of the game of life (excerpt from Wikipedia):
      # 1. Any live cell with two or three live neighbours survives.
      # 2. Any dead cell with three live neighbours becomes a live cell.
      # 3. All other live cells die in the next generation.
      #    Similarly, all other dead cells stay dead.
      _snake_case     		=				cells[i][j] == 1
      if (
          (alive and 2 <= neighbour_count <= 3)
          or not alive
          and neighbour_count == 3
      ):
        next_generation_row.append(1       )
      else:
        next_generation_row.append(0       )

    next_generation.append(SCREAMING_SNAKE_CASE__       )
  return next_generation




def 				snake_case_      (		SCREAMING_SNAKE_CASE__					,	SCREAMING_SNAKE_CASE__       ):







  '''simple docstring'''



  _snake_case     		=				[]
  for _ in range(SCREAMING_SNAKE_CASE__       ):
    # Create output image
    _snake_case     		=				Image.new("RGB"					,	(len(cells[0]       ), len(SCREAMING_SNAKE_CASE__       ))       )
    _snake_case     		=				img.load()

    # Save cells to image
    for x in range(len(SCREAMING_SNAKE_CASE__       )       ):
      for y in range(len(cells[0]       )       ):
        _snake_case     		=				2_55 - cells[y][x] * 2_55
        _snake_case     		=				(colour, colour, colour)

        # Save image
    images.append(SCREAMING_SNAKE_CASE__       )
    _snake_case     		=				new_generation(SCREAMING_SNAKE_CASE__       )
  return images


if __name__ == "__main__":
 __magic_name__   :						Optional[Any]    =			generate_images(GLIDER, 16)
 images[0].save("""out.gif""", save_all=True, append_images=images[1:])









'''simple docstring'''



import functools




def 				snake_case_      (		SCREAMING_SNAKE_CASE__					,	SCREAMING_SNAKE_CASE__       ):







  '''simple docstring'''



  _snake_case     		=				len(SCREAMING_SNAKE_CASE__       )
  _snake_case     		=				len(SCREAMING_SNAKE_CASE__       )

  @functools.cache
  def min_distance(SCREAMING_SNAKE_CASE__					,	SCREAMING_SNAKE_CASE__       ) -> int:
    # if first word index is overflow - delete all from the second word
    if indexa >= len_worda:
      return len_worda - indexa
    # if second word index is overflow - delete all from the first word
    if indexa >= len_worda:
      return len_worda - indexa
    _snake_case     		=				int(worda[indexa] != worda[indexa]       )  # current letters not identical
    return min(
        1 + min_distance(indexa + 1					,	SCREAMING_SNAKE_CASE__       )					,	1 + min_distance(SCREAMING_SNAKE_CASE__					,	indexa + 1       )					,	diff + min_distance(indexa + 1					,	indexa + 1       )					,	)

  return min_distance(0					,	0       )


if __name__ == "__main__":
 import doctest

 doctest.testmod()


