Реализация клеточного автомата на N языках

cellmachine.cpp

#include <functional>
#include <iostream>
#include <set>

// грязный хак для FnRule
struct Board;

typedef std::set<std::pair<uint8_t, uint8_t> > Cell;
typedef std::function<bool (Board &, uint8_t, uint8_t)> FnRule;

struct Board {
    uint8_t width;
    uint8_t height;
    Cell cell;

    Board(uint8_t width, uint8_t height): width(width), height(height) {}

    bool get(int16_t x, int16_t y) const {
        if (x < 0 || y < 0 || x > width || y > height) {
            return false;
        } else {
            // нужен флаг -std=c++20 или c++2a
            return cell.contains({x, y});
        }
    }

    void set(uint8_t x, uint8_t y) {
        cell.insert({x, y});
    }

    void next(FnRule rule) {
        Cell new_cell;
        for (uint8_t y = 0; y < height; y++) {
            for (uint8_t x = 0; x < width; x++) {
                // не можем передать get, т.к. он не static, ну а ссылку на всю структуру -- пожалуйста!
                if (rule(*this, x, y)) {
                    new_cell.insert({x, y});
                }
            }
        }
        cell = new_cell;
    }

    friend std::ostream & operator << (std::ostream &os, const Board &board) {
        for (uint8_t y = 0; y < board.height; y++) {
            for (uint8_t x = 0; x < board.width; x++) {
                os << (board.get(x, y) ? '#' : '.');
            }
            if (y != board.height - 1) {
                os << std::endl;
            }
        }
        return os;
    }
};

int main() {
    // конфигурация
    const std::vector<std::pair<uint8_t, uint8_t>> extra_cells = {
        {50, 0}, {0, 50}, {99, 50}, {50, 99}
    };
    const uint32_t iterations = 100;
    const uint8_t size = 100;

    // инициализируем доску
    Board board(size, size);
    for (uint8_t i = 0; i < size; i++) {
        board.set(i, i);
        board.set(size - i - 1, i);
    }
    for (auto xy : extra_cells) {
        board.set(xy.first, xy.second);
    }

    // работаем
    std::cout << (int)size << ';' << (int)size << ';' << iterations << std::endl << board << std::endl;
    for (uint32_t i = 1; i < iterations; i++) {
        board.next([](Board &b, uint8_t x, uint8_t y) {
            return b.get(x - 1, y - 1) ^ b.get(x + 1, y - 1) ^ b.get(x - 1, y + 1) ^ b.get(x + 1, y + 1);
        });
        std::cout << board << std::endl;
    }
}

cellmachine.hs

import Data.Set hiding (filter, map)
import Data.List (intercalate)

data Board = Board { width :: Int, height :: Int, cell :: Set (Int, Int) }

instance Show Board where
  show b = intercalate "\n" [[toChar $ member (x, y) c | x <- [0..w]] | y <- [0..h]]
    where toChar x = if x then '#' else '.'
          (w, h, c) = unpack b

get :: Board -> (Int, Int) -> Bool
get b (x, y)
  | x < 0 || y < 0 || x > w || y > h = False
  | otherwise = member (x, y) c
    where (w, h, c) = unpack b

set :: Board -> (Int, Int) -> Board
set b xy = board w h $ insert xy c
    where (w, h, c) = unpack b

next :: (Board -> (Int, Int) -> Bool) -> Board -> Board
next r b = board w h $ convert new_state
  where new_state = [[(r b (x, y), (x, y)) | x <- [0..w]] | y <- [0..h]]
        convert = fromList . map snd . filter ((== True) . fst) . concat
        (w, h, _) = unpack b

board :: Int -> Int -> Set (Int, Int) -> Board
board w h c = Board { width = w, height = h, cell = c }

unpack :: Board -> (Int, Int, Set (Int, Int))
unpack (Board w h c) = (w, h, c)

rule :: Board -> (Int, Int) -> Bool
rule b (x, y) = (k /= l) /= (m /= n)
  where k = get b (x - 1, y - 1)
        l = get b (x + 1, y - 1)
        m = get b (x - 1, y + 1)
        n = get b (x + 1, y + 1)

iter :: String -> Int -> Board -> String
iter l 0 b = l
iter l i b = iter (l ++ "\n" ++ show b) (i - 1) (next rule b)

main :: IO ()
main =
  putStrLn $ info ++ (iter "" iterations $ board size size cell)
    where diagonals = [(x, x) | x <- [0..size]] ++ [(size - x, x) | x <- [0..size]]
          cell = fromList $ diagonals ++ [(50, 0), (0, 50), (99, 50), (50, 99)]
          info = (show (size + 1)) ++ ";" ++ (show (size + 1)) ++ ";" ++ (show iterations)
          iterations = 100
          size = 100 - 1

cellmachine.jl

mutable struct Cell
    cell :: Base.Set
    Cell() = new(Base.Set([]))
end

mutable struct Board
    width :: UInt8
    height :: UInt8
    cell :: Cell
    Board(width, height) = new(width, height, Cell())
end

function set(o :: Board, x, y)
    push!(o.cell.cell, [x, y])
end

function get(o :: Board, x, y)
    if x < 0 || y < 0 || x > o.width || y > o.height
        false
    else
        [x, y] in o.cell.cell
    end
end

function next(o :: Board, rule)
    new_cell = Cell()
    for y in 0:o.height - 1
        for x in 0:o.width - 1
            if rule(o, x, y)
                push!(new_cell.cell, [x, y])
            end
        end
    end
    o.cell = new_cell
end

function printb(o :: Board)
    result = ""
    for y in 0:o.height - 1
        for x in 0:o.width - 1
            if get(o, x, y)
                # julia, что это * за конкатенация?
                result *= "#"
            else
                result *= "."
            end
        end
        result *= "\n"
    end
    print(result)
end

function rule(o :: Board, x, y)
    # julia, что это ⊻ за xor?
    get(o, x - 1, y - 1) ⊻ get(o, x + 1, y - 1) ⊻ get(o, x - 1, y + 1) ⊻ get(o, x + 1, y + 1)
end


extra_cells = [[50, 0], [0, 50], [99, 50], [50, 99]]
iterations = 100
bsize = 100

board = Board(bsize, bsize)
for i in 0:(bsize - 1)
    set(board, i, i)
    set(board, bsize - i - 1, i)
end
for (x, y) in extra_cells
    set(board, x, y)
end

print(bsize, ";", bsize, ";", iterations, "\n")
printb(board)
for i in 1:(iterations - 1)
    next(board, rule)
    printb(board)
end

cellmachine.lua

extra_cells = {{50, 0}, {0, 50}, {99, 50}, {50, 99}}
iterations = 100
size = 100

board = {width = size, height = size, cell = {}}

function board.set(x, y)
    if not board.cell[y] then
        board.cell[y] = {}
    end
    board.cell[y][x] = 1
end

function board.get(x, y)
    if x < 0 or y < 0 or x > board.width or y > board.height then
        return 0
    else
        if board.cell[y] and board.cell[y][x] then
            return 1
        else
            return 0
        end
    end
end

function board.next(rule)
    local new_cell = {}
    for y = 0, board.height - 1, 1 do
        for x = 0, board.width - 1, 1 do
            if rule(board, x, y) == 1 then
                if not new_cell[y] then
                    new_cell[y] = {}
                end
                new_cell[y][x] = 1
            end
        end
    end
    board.cell = new_cell
end

function board.print()
    local result = ''
    for y = 0, board.height - 1, 1 do
        for x = 0, board.width - 1, 1 do
            if board.get(x, y) == 1 then
                result = result .. "#"
            else
                result = result .. "."
            end
        end
        if y ~= board.height - 1 then
            result = result .. "\n"
        end
    end
    print(result)
end

function rule(f, x, y)
    return f.get(x - 1, y - 1) ~ f.get(x + 1, y - 1) ~ f.get(x - 1, y + 1) ~ f.get(x + 1, y + 1)
end

for i = 0, board.width - 1, 1 do
    board.set(i, i)
    board.set(board.width - i - 1, i)
end
for i in pairs(extra_cells) do
    x = extra_cells[i][1]
    y = extra_cells[i][2]
    board.set(x, y)
end

print(size .. ';' .. size .. ';' .. iterations)
board.print()
for i = 1, iterations - 1, 1 do
    board.next(rule)
    board.print()
end

cellmachine.nim

import sets

type
  # int вместо uint8, чтобы не делать везде cast[uint8](...)
  Cell = HashSet[tuple[x: int, y: int]]
  Board = object
    width: int
    height: int
    cell: Cell

proc get(b: Board, x: int, y: int): bool =
  if x < 0 or y < 0 or x > b.width or y > b.height:
    result = false
  else:
    result = b.cell.contains((x, y))

proc set(b: var Board, x: int, y: int) =
  b.cell.incl((x: x, y: y))

proc next(b: var Board, rule: proc (b: Board, x: int, y: int): bool) =
  var new_cell: Cell
  for y in 0 ..< b.height:
    for x in 0 ..< b.width:
      if b.rule(x, y):
        new_cell.incl((x: x, y: y))
  b.cell = new_cell

proc print(b: Board) =
  var result = ""
  for y in 0 ..< b.height:
    for x in 0 ..< b.width:
      if b.get(x, y):
        result.add("#")
      else:
        result.add(".")
    if y != b.height - 1:
      result.add("\n")
  echo(result)

proc rule(b: Board, x: int, y: int): bool =
  result = b.get(x - 1, y - 1) xor b.get(x + 1, y - 1) xor b.get(x - 1, y + 1) xor b.get(x + 1, y + 1)

let extra_cells = [(50, 0), (0, 50), (99, 50), (50, 99)]
let iterations = 100
let size = 100

var board = Board(width: size, height: size)
for i in 0 ..< size:
  board.set(i, i)
  board.set(size - i - 1, i)
for _, (x, y) in extra_cells:
  board.set(x, y)

echo(size, ';', size, ';', iterations)
board.print()

for i in 1 ..< iterations:
  board.next(rule)
  board.print()

cellmachine.py

from itertools import product


class Board:
    def __init__(self, w, h):
        self.width = w
        self.height = h
        self.cell = set()

    def get(self, x, y):
        if x < 0 or y < 0 or x > self.width or y > self.height:
            return False
        else:
            return (x, y) in self.cell

    def set(self, x, y):
        self.cell.add((x, y))

    def next(self, rule):
        new_cell = set()
        for x, y in product(range(0, self.width), range(0, self.height)):
            if rule(self.get, x, y):
                new_cell.add((x, y))
        self.cell = new_cell

    def __str__(self):
        result = ''
        for y in range(0, self.height):
            for x in range(0, self.width):
                result += '#' if self.get(x, y) else '.'
            if y != self.height - 1:
                result += '\n'
        return result

def rule(f, x, y):
    return f(x - 1, y - 1) ^ f(x + 1, y - 1) ^ f(x - 1, y + 1) ^ f(x + 1, y + 1)


if __name__ == '__main__':
    # конфигурация
    extra_cells = [(50, 0), (0, 50), (99, 50), (50, 99)]
    iterations = 100
    size = 100

    board = Board(size, size)
    for i in range(size):
        board.set(i, i)
        board.set(size - i - 1, i)
    for x, y in extra_cells:
        board.set(x, y)
    
    print(f'{size};{size};{iterations}\n{board}')
    for _ in range(1, iterations):
        board.next(rule)
        print(board)

cellmachine.rb

require 'set'

class Board
    def initialize(width, height)
        @width = width
        @height = height
        @cell = Set[]
    end

    def get(x, y)
        if x < 0 or y < 0 or x > @width or y > @width
            false
        else
            @cell === [x, y]
        end
    end

    def set(x, y)
        @cell.add([x, y])
    end

    def next(rule)
        new_cell = Set[]
        (0..@height - 1).each do |y|
            (0..@width - 1).each do |x|
                if rule.call(self, x, y)
                    new_cell.add([x, y])
                end
            end
        end
        @cell = new_cell
    end

    def to_s()
        result = ""
        (0..@height - 1).each do |y|
            (0..@width - 1).each do |x|
                if get(x, y)
                    result << "#"
                else
                    result << "."
                end
            end
            if y != @height
                result << "\n"
            end
        end
        result
    end
end

if __FILE__ == $0
    extra_cells = [[50, 0], [0, 50], [99, 50], [50, 99]]
    iterations = 100
    size = 100

    board = Board.new(size, size)

    (0..size - 1).each do |i|
        board.set(i, i)
        board.set(size - i - 1, i)
    end
    extra_cells.each { |x, y| board.set(x, y) }

    rule = lambda { |f, x, y| f.get(x - 1, y - 1) ^ f.get(x + 1, y - 1) ^ f.get(x - 1, y + 1) ^ f.get(x + 1, y + 1) }
    
    puts "#{size};#{size};#{iterations}"
    puts board.to_s()
    (1..iterations - 1).each do ||
        board.next(rule)
        puts board.to_s()
    end
end

cellmachine.rs

use std::collections::HashSet;
use std::fmt;
use std::u8;

// вспомогательный трейт
trait MainFunc {
    fn get(&self, x: i16, y: i16) -> bool;
    fn set(&mut self, x: u8, y: u8);
}

// описание нашей доски
struct Board {
    // формально это cells, но cell выглядит лучше
    cell: HashSet<(u8, u8)>,
    width: u8,
    height: u8,
}

// добавляем свою функцию для Board
impl MainFunc for Board {
    // активация ячейки
    fn set(&mut self, x: u8, y: u8) {
        self.cell.insert((x, y));
    }

    // получаем значение ячейки
    fn get(&self, x: i16, y: i16) -> bool {
        if x < u8::MIN as i16 || y < u8::MIN as i16 || x > self.width as i16 || y > self.height as i16 {
            false
        } else {
            self.cell.contains(&(x as u8, y as u8))
        }
    }
}

impl Board {
    // инициализатор доски
    fn new(width: u8, height: u8) -> Board {
        Board { cell: HashSet::new(), width, height }
    }

    // расчёт следующего состояния доски использую переданное правило
    fn next<F>(&mut self, rule: F)
    where F: Fn(&Board, i16, i16) -> bool
    {
        let mut new_cell = HashSet::new();
        for y in 0..self.height {
            for x in 0..self.width {
                // пересчитываем состояние клетки
                if rule(&self, x as i16, y as i16) {
                    new_cell.insert((x, y));
                }
            }
        }
        // новое состояние системы
        self.cell = new_cell;
    }
}

// имплементим вывод нашей доски
impl fmt::Display for Board {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut result = String::with_capacity((self.width as usize + 1) * self.height as usize);
        for y in 0..self.height as i16 {
            for x in 0..self.width as i16 {
                if self.get(x, y) {
                    // ячейка заполнена
                    result.push('#');
                } else {
                    // ячейка пуста
                    result.push('.');
                }
            }
            // автоматичесий перенос строки
            if y != self.height as i16 - 1 {
                result.push('\n');
            }
        }
        write!(f, "{}", result)
    }
}

fn main() {
    // конфигурация
    let extra_cells = vec![(50, 0), (0, 50), (99, 50), (50, 99)];
    let iterations = 100;
    let size = 100;

    // инициализируем доску
    let mut board = Board::new(size, size);
    for i in 0..size {
        board.set(i, i);
        board.set(size - i - 1, i);
    }
    for (x, y) in extra_cells {
        board.set(x, y);
    }

    // работаем!
    println!("{};{};{}\n{}", size, size, iterations, board);
    for _ in 1..size {
        board.next(|f, x, y| {
            f.get(x - 1, y - 1) ^ f.get(x + 1, y - 1) ^ f.get(x - 1, y + 1) ^ f.get(x + 1, y + 1)
        });
        println!("{}", board);
    }
}

gif2mp4.sh

#!/bin/bash
ffmpeg -i output.gif -s 500x500 -sws_flags neighbor -v warning -y output.mp4

Makefile

all: build_rust build_cpp build_nim
build_rust:
	@echo "> build rust code"
	@rustc -C opt-level=3 cellmachine.rs -o cellmachine_rs
build_cpp:
	@echo "> build c++ code"
	@g++ -O3 -std=c++2a cellmachine.cpp -o cellmachine_cpp
build_nim:
	@echo "> build nim"
	@nim compile -d:release -o:cellmachine_nim cellmachine.nim > /dev/null 2>&1
build_haskell:
	@echo "> build haskell"
	@ghc -o cellmachine_hs cellmachine.hs -dynamic -O > /dev/null 2>&1
	@$(RM) cellmachine cellmachine.{o,hi}
run: all
	@echo -en "\n> rust code"
	@time ./cellmachine_rs > output_rs.txt
	@echo -en "\n> c++ code"
	@time ./cellmachine_cpp > output_cpp.txt
	@echo -en "\n> python code"
	@time python cellmachine.py > output_py.txt 
	@echo -en "\n> ruby code"
	@time ruby cellmachine.rb > output_rb.txt
	@echo -en "\n> julia code"
	@time julia -O3 cellmachine.jl > output_jl.txt
	@echo -en "\n> lua code"
	@time lua cellmachine.lua > output_lua.txt
	@echo -en "\n> nim code"
	@time ./cellmachine_nim > output_nim.txt
	@echo -en "\n> haskell code"
	@time ./cellmachine_hs > output_hs.txt
visualize: build_rust
	@echo "> generate data"
	@./cellmachine_rs > output.txt
	@echo "> convert to gif"
	@python render_gif.py
	@echo "> convert to mp4"
	@sh ./gif2mp4.sh
clean:
	@echo "> cleaning"
	@$(RM) cellmachine_* *.{txt,gif,mp4}

render_gif.py

from PIL import Image
import numpy as np


def take_n(data, count):
    for i in range(0, len(data), count):
        yield data[i:i + count]


def to_image(block):
    w, h = len(block[0]) - 1, len(block)
    img = np.zeros((h, w), dtype=np.uint8)
    for y, line in enumerate(block):
        for x, item in enumerate(line):
            if item == '#':
                img[y, x] = 255
    return Image.fromarray(img)


if __name__ == '__main__':
    data = open('output.txt').readlines()
    _, height, _ = map(int, data[0].strip().split(';'))
    images = [to_image(block) for block in take_n(data[1:], height)]
    images[0].save('output.gif', save_all=True, append_images=images[1:], duration=100, loop=0)