carpet implementation in Go

On carpets and fractals

July 2018, GoGraz, Lukas Prokop

Motivation

Video “Carpets, Genetics, and the Pi Fractal”
Blogpost “The Pi Fractal”

Hodkinson's "Carpets, Genetics, and the Pi Fractal" video

In essence, I watched jrhodkinson’s “Carpets, Genetics, and the Pi Fractal” talk and was amazed by the beauty. So I implemented it.

Goals

Implementation in Go
MIT license
Public API
Easy way to define your own rules
Easy way to generate fractals/carpets/…

The theory

In mathematics, a fractal is an abstract object used to describe and simulate naturally occurring objects. Artificially created fractals commonly exhibit similar patterns at increasingly small scales. It is also known as expanding symmetry or evolving symmetry.

A carpet seems to be a plane, square fractal.

String rewriting systems

Rules

0 → 0
1 → 01

Replaces 01101 with 00101001 (1 iteration) or 00000010000010000001 (5 iterations)

String rewriting systems

Rules

gr → h
et → ll
i → o⎵ 
ng → world

Replaces greeting with hello world

Thue programming language

It is a meta-language that can be used to define or recognize Type-0 languages from the Chomsky hierarchy

—Wikipedia: Thue (programming language)

A Turing tarpit (or Turing tar-pit) is any programming language or computer interface that allows for flexibility in function but is difficult to learn and use because it offers little or no support for common tasks.

Thue is a Turing tar pit

Thue programming language

lhs1 ::= rhs1
lhs2 ::= rhs2
::=
initialstring

Here we 2 substitution rules in the rulebase, a single production symbol as delimiter followed by the initial state.

::= is pronounced can be.
::= can never be the lhs.
::: is an input stream.
~ is the output stream.

a::=~Hello World!
::=
a

1_::=1++
0_::=1

01++::=10
11++::=1++0

_0::=_
_1++::=10

::=

_1111111111_

_1111111111_ → _1111111111++ → _111111111++0 → _11111111++00 → … → _1++000000000 → 10000000000

What is that?

Conway's Game of Life

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.

—Wikipedia: Conway's Game of Life

live, < 2 live neighbors → dead
live, 2 | 3 live neighbors → live
live, > 3 live neighbors → dead
dead, 3 live neighbors → live

Conway's Game of Life

via Wikipedia: Puffer train

Rule 110

Let an arbitrary binary string be given. Consider a triple (left neighbor, center, right neighbor) for each digit.

current	111	110	101	100	011	010	001	000
next	0	1	1	0	1	1	1	0

BTW, 01101110₂ = 110₁₀.

~2000: Matthew Cook showed Rule 110 is turing-complete.

Rule 110

00000000000000000000000000000000000000000000000000000000000000000000000000000001
00000000000000000000000000000000000000000000000000000000000000000000000000000011
00000000000000000000000000000000000000000000000000000000000000000000000000000111
00000000000000000000000000000000000000000000000000000000000000000000000000001101
00000000000000000000000000000000000000000000000000000000000000000000000000011111
00000000000000000000000000000000000000000000000000000000000000000000000000110001
00000000000000000000000000000000000000000000000000000000000000000000000001110011
00000000000000000000000000000000000000000000000000000000000000000000000011010111
00000000000000000000000000000000000000000000000000000000000000000000000111111101
00000000000000000000000000000000000000000000000000000000000000000000001100000111
00000000000000000000000000000000000000000000000000000000000000000000011100001101
00000000000000000000000000000000000000000000000000000000000000000000110100011111
00000000000000000000000000000000000000000000000000000000000000000001111100110001
00000000000000000000000000000000000000000000000000000000000000000011000101110011
00000000000000000000000000000000000000000000000000000000000000000111001111010111
00000000000000000000000000000000000000000000000000000000000000001101011001111101
00000000000000000000000000000000000000000000000000000000000000011111111011000111
00000000000000000000000000000000000000000000000000000000000000110000001111001101
00000000000000000000000000000000000000000000000000000000000001110000011001011111
00000000000000000000000000000000000000000000000000000000000011010000111011110001
00000000000000000000000000000000000000000000000000000000000111110001101110010011
00000000000000000000000000000000000000000000000000000000001100010011111010110111
00000000000000000000000000000000000000000000000000000000011100110110001111111101
00000000000000000000000000000000000000000000000000000000110101111110011000000111
00000000000000000000000000000000000000000000000000000001111111000010111000001101
00000000000000000000000000000000000000000000000000000011000001000111101000011111
00000000000000000000000000000000000000000000000000000111000011001100111000110001
00000000000000000000000000000000000000000000000000001101000111011101101001110011
00000000000000000000000000000000000000000000000000011111001101110111111011010111
00000000000000000000000000000000000000000000000000110001011111011100001111111101
00000000000000000000000000000000000000000000000001110011110001110100011000000111
00000000000000000000000000000000000000000000000011010110010011011100111000001101
00000000000000000000000000000000000000000000000111111110110111110101101000011111
00000000000000000000000000000000000000000000001100000011111100011111111000110001
00000000000000000000000000000000000000000000011100000110000100110000001001110011
00000000000000000000000000000000000000000000110100001110001101110000011011010111
00000000000000000000000000000000000000000001111100011010011111010000111111111101
00000000000000000000000000000000000000000011000100111110110001110001100000000111
00000000000000000000000000000000000000000111001101100011110011010011100000001101
00000000000000000000000000000000000000001101011111100110010111110110100000011111
00000000000000000000000000000000000000011111110000101110111100011111100000110001
00000000000000000000000000000000000000110000010001111011100100110000100001110011
00000000000000000000000000000000000001110000110011001110101101110001100011010111
00000000000000000000000000000000000011010001110111011011111111010011100111111101
00000000000000000000000000000000000111110011011101111110000001110110101100000111
00000000000000000000000000000000001100010111110111000010000011011111111100001101
00000000000000000000000000000000011100111100011101000110000111110000000100011111
00000000000000000000000000000000110101100100110111001110001100010000001100110001
00000000000000000000000000000001111111101101111101011010011100110000011101110011
00000000000000000000000000000011000000111111000111111110110101110000110111010111
00000000000000000000000000000111000001100001001100000011111111010001111101111101
00000000000000000000000000001101000011100011011100000110000001110011000111000111
00000000000000000000000000011111000110100111110100001110000011010111001101001101
00000000000000000000000000110001001111101100011100011010000111111101011111011111
00000000000000000000000001110011011000111100110100111110001100000111110001110001
00000000000000000000000011010111111001100101111101100010011100001100010011010011
00000000000000000000000111111100001011101111000111100110110100011100110111110111
00000000000000000000001100000100011110111001001100101111111100110101111100011101
00000000000000000000011100001100110011101011011101111000000101111111000100110111
00000000000000000000110100011101110110111111110111001000001111000001001101111101
00000000000000000001111100110111011111100000011101011000011001000011011111000111
00000000000000000011000101111101110000100000110111111000111011000111110001001101
00000000000000000111001111000111010001100001111100001001101111001100010011011111
00000000000000001101011001001101110011100011000100011011111001011100110111110001
00000000000000011111111011011111010110100111001100111110001011110101111100010011
00000000000000110000001111110001111111101101011101100010011110011111000100110111
00000000000001110000011000010011000000111111110111100110110010110001001101111101
00000000000011010000111000110111000001100000011100101111110111110011011111000111
00000000000111110001101001111101000011100000110101111000011100010111110001001101
00000000001100010011111011000111000110100001111111001000110100111100010011011111
00000000011100110110001111001101001111100011000001011001111101100100110111110001
00000000110101111110011001011111011000100111000011111011000111101101111100010011
00000001111111000010111011110001111001101101000110001111001100111111000100110111
00000011000001000111101110010011001011111111001110011001011101100001001101111101
00000111000011001100111010110111011110000001011010111011110111100011011111000111
00001101000111011101101111111101110010000011111111101110011100100111110001001101
00011111001101110111111000000111010110000110000000111010110101101100010011011111
00110001011111011100001000001101111110001110000001101111111111111100110111110001
01110011110001110100011000011111000010011010000011111000000000000101111100010011
11010110010011011100111000110001000110111110000110001000000000001111000100110111

Visualization by considering y-axis as time. Initial state is a sequence of zeros with single one at the very end.

Hence, iteration 0 is the first row, iteration 1 is the second row, …

Mandelbrot set

Found by Adrien Douady (1935-2006), named after Benoit B. Mandelbrot (1924-2010).

Image by Wolfgang Beyer (CC BY-SA 3.0).

Mandelbrot set

Mathematical background:

\sum_{n = 1}^{\infty} \frac{1}{n} = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \dots = \infty

\sum_{n = 1}^{\infty} \frac{1}{n^{2}} = \frac{1}{1} + \frac{1}{4} + \frac{1}{9} + \dots = \frac{π^{2}}{6}

infinity → diverges. number → converges.

z = a + i b

$z \in ℂ$ . Complex numbers have a real part a and an imaginary part b. $a, b \in ℝ$ . i² = -1.

Mandelbrot set

To plot complex numbers, real and imaginary parts are the 1st and 2nd Cartesian coordinate respectively.

Let M be the Mandelbrot set.
Let c be any complex number.

z_{0} = 0, z_{n + 1} = z_{n}^{2} + c

c \in M \Leftrightarrow \underset{n \to \infty}{limsup} | z_{n + 1} | \leq 2

c = 1 → 0, 1, 2, 5, 26, … with limsup = ∞
c = −1 → 0, −1, 0, −1, 0, … with limsup = 0

Mandelbrot set

How to colorize (with our own threshold)

limsup is ≤2, colorize pixel c black.
limsup crosses 10⁴ after 10⁴ iterations, colorize c bright blue.
Otherwise, colorize pixel c dark blue.

We can make an arbitrary number of thresholds. This will yield beautiful images.

Mandelbrot set

Image by Wolfgang Beyer

Mandelbrot set

Image by Wolfgang Beyer

Mandelbrot set

Image by Wolfgang Beyer

Mandelbrot set

Self-similarity

In mathematics, a self-similar object is exactly or approximately similar to a part of itself (i.e. the whole has the same shape as one or more of the parts). Many objects in the real world, such as coastlines, are statistically self-similar: parts of them show the same statistical properties at many scales.

—Wikipedia: self-similarity

The Mandelbrot set is self-similar around Misiurewicz points.

Self-similarity

Self-similarity in the Mandelbrot set at the Feigenbaum point.

Self-similarity

The practice

My implementation

https://github.com/meisterluk/carpet

My implementation

Core functionality

Replace with Sierpinski triangle rule for white color
Replace with Sierpinski triangle rule for black color

The match pattern color is encoded in the filename. The replacement pattern is a PNG file.

My implementation

Command line options

usage: ./carpet

  rule-files-dir    :string   required   directory containing rules files
  #iterations       :int      required   number of iterations
  output-file.png   :string   required   output filepath (PNG)
  initial-color     :8hex     optional   initial color/state

The rule-files-dir is expected to contain a bunch of files with filename suffix .png and containing 8 hexadecimal digits in the filename. This defines the match color. The replacement is the content of the PNG file itself. See example/* folders.

My implementation

Initial approach

Create PNG for each iteration
Obivously very memory intense
Annoying to handle alternation between 2 images of current/previous iteration

My implementation

Second approach

Use map[[2]byte]bool
Annoying to handle all the memory allocations

Implementation

Final approach

Initialize full PNG image
Retrieve color of previous iteration from 'representative pixel'
Memory efficient, computational efficient
Formula to retrieve coordinates of representative of previous/current iteration is annoying