fractals.sierpinski_carpet

The Sierpinski carpet is a plane fractal first described by Wacław Sierpiński in 1916. It is a two-dimensional generalisation of the Cantor set and a close relative of the Sierpinski triangle.

Construction

Start from a filled square. Divide it into a 3x3 grid of nine equal sub-squares and remove the central one. Then apply the same procedure recursively to each of the eight remaining sub-squares, forever.

A convenient way to decide whether a single cell of the 3**n x 3**n grid is filled (part of the carpet) or empty (a hole) is to look at the base-3 digits of its row and column indices: the cell is a hole if and only if, at some level, both the row digit and the column digit are equal to 1 (the centre of that 3x3 block).

This module builds the carpet purely with integer arithmetic, so every function is deterministic and can be verified with doctests – no plotting or turtle graphics required.

Reference: https://en.wikipedia.org/wiki/Sierpi%C5%84ski_carpet

Functions

count_filled_cells(→ int)	Return how many cells are filled in a carpet of the given depth.
generate_carpet(→ list[str])	Build the Sierpinski carpet of the given depth as a list of strings.
is_filled(→ bool)	Return True when the cell at (row, col) belongs to the carpet

Module Contents

fractals.sierpinski_carpet.count_filled_cells(depth: int) → int

Return how many cells are filled in a carpet of the given depth.

Each level keeps eight of the nine sub-squares, so the count is 8**depth. Verifying this closed form against a brute-force scan is a nice sanity check.

>>> [count_filled_cells(depth) for depth in range(4)]
[1, 8, 64, 512]
>>> all(
...     count_filled_cells(depth)
...     == sum(line.count("#") for line in generate_carpet(depth))
...     for depth in range(4)
... )
True

fractals.sierpinski_carpet.generate_carpet(depth: int, filled: str = '#', hole: str = ' ') → list[str]

Build the Sierpinski carpet of the given depth as a list of strings.

A depth of 0 is a single filled cell; each extra level multiplies the side length by three.

>>> generate_carpet(0)
['#']
>>> for line in generate_carpet(1):
...     print(line)
###
# #
###
>>> for line in generate_carpet(2, filled="X", hole="."):
...     print(line)
XXXXXXXXX
X.XX.XX.X
XXXXXXXXX
XXX...XXX
X.X...X.X
XXX...XXX
XXXXXXXXX
X.XX.XX.X
XXXXXXXXX
>>> generate_carpet(-1)
Traceback (most recent call last):
    ...
ValueError: depth must be non-negative, got -1

fractals.sierpinski_carpet.is_filled(row: int, col: int) → bool

Return True when the cell at (row, col) belongs to the carpet and False when it falls inside one of the removed central squares.

The result is independent of the fractal depth: a cell is a hole as soon as any pair of matching base-3 digits equals (1, 1).

>>> is_filled(0, 0)
True
>>> is_filled(1, 1)  # the very first central square is removed
False
>>> is_filled(4, 4)  # centre of the centre block -> still a hole
False
>>> is_filled(0, 4)
True
>>> [is_filled(1, col) for col in range(3)]
[True, False, True]

Negative coordinates make no sense for a grid index.

>>> is_filled(-1, 0)
Traceback (most recent call last):
    ...
ValueError: row and col must be non-negative, got (-1, 0)