one dimensional Algorithm
The one-dimensional algorithm refers to a computational method that operates on a single dimension or a sequence of data points, typically represented as a one-dimensional array or list. These algorithms are often designed to optimize the processing of data in linear structures, such as strings, numbers, or other simple data types. They are commonly used in solving problems that require searching, sorting, or transforming data, and are the foundation of many fundamental algorithms in computer science.
One of the most well-known one-dimensional algorithms is the binary search algorithm, which efficiently searches for a target value within a sorted array by repeatedly dividing the search interval in half. Another example is the selection sort algorithm, which sorts an array by repeatedly finding the smallest or largest element from the unsorted part of the array and moving it to the sorted part. Other notable one-dimensional algorithms include linear search, insertion sort, and merge sort, among others. While these algorithms are relatively simple in concept, they form the basis for more complex multidimensional algorithms and are crucial for efficient data manipulation and processing in various applications.
"""
Return an image of 16 generations of one-dimensional cellular automata based on a given
ruleset number
https://mathworld.wolfram.com/ElementaryCellularAutomaton.html
"""
from typing import List
from PIL import Image
# Define the first generation of cells
# fmt: off
CELLS = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
# fmt: on
def format_ruleset(ruleset: int) -> List[int]:
"""
>>> format_ruleset(11100)
[0, 0, 0, 1, 1, 1, 0, 0]
>>> format_ruleset(0)
[0, 0, 0, 0, 0, 0, 0, 0]
>>> format_ruleset(11111111)
[1, 1, 1, 1, 1, 1, 1, 1]
"""
return [int(c) for c in f"{ruleset:08}"[:8]]
def new_generation(cells: List[List[int]], rule: List[int], time: int) -> List[int]:
population = len(cells[0]) # 31
next_generation = []
for i in range(population):
# Get the neighbors of each cell
left_neighbor = 0 if i == 0 else cells[time][i - 1] # special: leftmost cell
right_neighbor = 0 if i == population - 1 else cells[time][i + 1] # rightmost
# Define a new cell and add it to the new generation
situation = 7 - int(f"{left_neighbor}{cells[time][i]}{right_neighbor}", 2)
next_generation.append(rule[situation])
return next_generation
def generate_image(cells: List[List[int]]) -> Image.Image:
"""
Convert the cells into a greyscale PIL.Image.Image and return it to the caller.
>>> from random import random
>>> cells = [[random() for w in range(31)] for h in range(16)]
>>> img = generate_image(cells)
>>> isinstance(img, Image.Image)
True
>>> img.width, img.height
(31, 16)
"""
# Create the output image
img = Image.new("RGB", (len(cells[0]), len(cells)))
pixels = img.load()
# Generates image
for w in range(img.width):
for h in range(img.height):
color = 255 - int(255 * cells[h][w])
pixels[w, h] = (color, color, color)
return img
if __name__ == "__main__":
rule_num = bin(int(input("Rule:\n").strip()))[2:]
rule = format_ruleset(int(rule_num))
for time in range(16):
CELLS.append(new_generation(CELLS, rule, time))
img = generate_image(CELLS)
# Uncomment to save the image
# img.save(f"rule_{rule_num}.png")
img.show()
