NAME
Math::PlanePath::LCornerTree -- cellular automaton growing at exposed corners
SYNOPSIS
use Math::PlanePath::LCornerTree;
my $path = Math::PlanePath::LCornerTree->new;
my ($x, $y) = $path->n_to_xy (123);DESCRIPTION
This is the pattern of a cellular automaton growing by 3 cells at exposed corners. Points are numbered anti-clockwise within their level. The default is four quadrants starting from four initial cells N=0 to N=3,
68 67 66 65 4
69 41 40 39 38 35 34 33 32 64 3
42 20 19 37 36 18 17 31 ... 2
43 21 8 7 6 5 16 30 1
44 45 9 1 0 4 28 29 <- Y=0
47 46 10 2 3 15 63 62 -1
48 22 11 12 13 14 27 61 -2
49 23 24 54 55 25 26 60 -3
70 50 51 52 53 56 57 58 59 75 -4
71 72 73 74 -5
^
-5 -4 -3 -2 -1 X=0 1 2 3 4The growth rule is a cell which is an exposed corner grows by the three cells surrounding that corner. So
depth=0 depth=1 depth=2 depth=3
d d d d d d d d
\| |/ \| |/
c c c c d-c c-d d-c c-d
\| |/ \| |/
b b b b c-b b b b-c d-c-b b b b-c-d
\| |/ \| |/ /| \| |/ |\
a a b-a a-b b-a a-b d d b-a a-b d d
-> -> ->
a a b-a a-b b-a a-b d d b-a a-b d d
/| |\ /| |\ /| |\ |/
b b b b c-b b b b-c d c-b b b b-c-d
/| |\ /| |\
c c c d-c c-d d-c c-d
/| |\ /| |\
d d d d d d d d"a" is the first cell in each quadrant and grows into the three "b" around each. Then for the "b" cells only the corner ones are exposed corners and they grow to the "c" cells. Those "c" cells are then all exposed corners and give a set of 36 "d" cells. Of those "d"s only the corners are exposed corners for the next "e" level.
Grouping the three children of each corner shows the pattern
+-----------------------+
| | | | |
| +-----+ | +-----+ |
| | | | | | |
|--| +-----+-----+ |--|
| | | | | | |
| +--| +--+--+ |--+ |
| | | | | | |
|-----+--+--+--+--+-----|
| | | | | | |
| +--| +--+--+ |--+ |
| | | | | | |
|--| +-----+-----+ |--|
| | | | | | |
| +-----+ | +-----+ |
| | | | |
+-----------------------+In general the number of cells gained in each level is
Nwidth = 4 * 3^count1bits(depth)So for example depth=3 binary "11" has 2 1-bits so cells=4*3^2=36. Adding such powers-of-3 up to a depth=2^k gives a power-of-4 total square area.
Each side part turns by 90 degrees at its corner, so the plane is filled in a self-similar style turning into each side quarter. This is an attractive way to fill the plane by a tree structure.
+----------------+
| | |
| ^ | ^ |
| \ | / |
| \ | / |
| | |
|-------+--------|
| | |
| ^ | \ |
| / | \ |
| / | v |
| / | |
+----------------+See also Math::PlanePath::LCornerReplicate for a digit-based approach to the replication.
Toothpicks
The points can be regarded as the centres of toothpicks oriented diagonally and growing at exposed endpoints.
.. ..
| \ /
2 | 6 5 parts=1 (per below) as toothpicks
| \ /
| .
| \ / \
1 | 3 2 4
| \ / \
| . ..
| / \
Y=0 | 0 1
| / \
+-------------
X=0 1 2Point N=0 is reckoned as a diagonal toothpick and the three N=1,2,3 grow from its exposed end. At the next level another three grow from the exposed end of N=2. Only an exposed end grows. If two toothpick ends touch then they don't grow.
The toothpicks are oriented on the leading diagonal for "even" points X=Y mod 2 and on the opposite diagonal for "odd" points X!=Y mod 2. A rotation by 45 degrees can be applied to make them horizontal and vertical instead.
One Quadrant
Option parts => '1' confines the pattern to the first quadrant. This is a single copy of the repeating part which is in each of the four quadrants of the full pattern.
parts => "1"
4 | 18 17
3 | 14 13 12 11 16
2 | 15 6 5 10
1 | 3 2 4 9
Y=0 | 0 1 7 8
+---------------------
X=0 1 2 3 4Half Plane
Option parts => '2' confines the tree to the upper half plane Y>=0, giving two symmetric parts above the X axis.
parts => "2"
36 35 34 33 4
37 27 26 25 24 21 20 19 18 32 3
28 12 11 23 22 10 9 17 2
29 13 6 5 4 3 8 16 1
30 31 7 1 0 2 14 15 <- Y=0
--------------------------------------
-5 -4 -3 -2 -1 X=0 1 2 3 4Three Parts
Option parts => '3' is three replications arranged in a corner down and left similar to the way the tree grows from a power-of-2 corner X=2^k,Y=2^k.
parts => "3"
55 54 50 49 4
56 43 42 41 40 28 27 26 25 48 3
44 19 18 39 29 14 13 24 2
45 20 10 9 5 4 12 23 1
46 47 11 2 0 3 21 22 <- Y=0
------------------+ 1 8 38 37 -1
| 6 7 17 36 -2
| 30 15 16 35
| 31 32 33 34 53
| 51 52
^
-5 -4 -3 -2 -1 X=0 1 2 3 4One Octant
Option parts => 'octant' confines the pattern to the first eighth of the plane. This is a single side of the eight-way symmetry in the full pattern.
parts => "octant"
7 | 35
6 | 21 34
5 | 16 20 33
4 | 11 15 31 32
3 | 9 10 14 30 29
2 | 4 8 12 13 19 28
1 | 2 3 7 22 17 18 27
Y=0 | 0 1 5 6 23 24 25 26
+--------------------------
X=0 1 2 3 4 5 6 7The points are numbered in the same sequence as the parts=1 quadrant, but with those above the X=Y diagonal omitted. This means each N on the X=Y diagonal is the last of the depth level.
Upper Octant
Option parts => 'octant_up' confines the pattern to the upper eighth of the first quadrant.
parts => "octant_up"
7 | 31 30 29 28 25 24 23 22
6 | 32 20 19 27 26 18 17
5 | 33 21 15 14 13 12
4 | 34 35 16 11 10
3 | 8 7 6 5
2 | 9 4 3
1 | 2 1
Y=0 | 0
+--------------------------
X=0 1 2 3 4 5 6 7The points are numbered in the same sequence as the parts=1 quadrant, but with those below the X=Y diagonal omitted. This means each N on the X=Y diagonal is the first of the depth level.
Wedge
Option parts => 'wedge' confines the pattern to a wedge made of two octants, Y>=X and Y>=-1-X.
parts => "wedge"
71 70 69 68 65 64 63 62 53 52 51 50 47 46 45 44 7
43 42 67 66 41 40 61 54 37 36 49 48 35 34 6
33 32 31 30 39 60 55 38 27 26 25 24 5
23 22 29 58 59 56 57 28 21 20 4
19 18 17 16 13 12 11 10 3
9 8 15 14 7 6 2
5 4 3 2 1
1 0 Y=0
-----------------------------------------------
-8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7The points are numbered in the same sequence as the full parts=4 pattern, but restricted to the wedge portion. This means each N on the right-hand X=Y diagonal is the first of the depth level and each N on the X=-1-Y left-hand diagonal is the last of the depth level.
In this arrangement even N falls on "even" X,Y points X=Y mod 2. Odd N falls on "odd" X,Y points X!=Y mod 2.
O E O E O E O E
O E O E O E
O E O E
O EThe odd/even is true of N=0 and N=1 and then for further points it's true due to the way the pattern repeats in 2^k depth levels.
-------------- \ Y=2*2^k-1
\ 3 / \ 1 / |
\ / 2 \ / / Y=2^k
-------- \ Y=2^k-1
\base/ |
\ / / Y=0The base part Y=0 to Y=2^k-1 repeats in block 1 and block 3. The middle block 2 is also a repeat, less 2 points on the diagonals, but the right half of the base is rotated +90 degrees and the left half of the base rotated -90 degrees to make the upside-down wedge.
parts=2 and parts=4 forms also have an even number of points in each row but they don't have N even on X,Y even the way the wedge does. That's because the numbering of parts=2 and parts=4 means each row begins on the "ragged" edge of the pattern which may be X,Y odd or even, whereas each wedge row begins on the X=Y diagonal which is always X,Y even.
Diagonal
Option parts => 'diagonal' confines the pattern to a diagonal half-plane X>=Y-1,
parts => "diagonal"
35 34 33 32 29 28 27 26 3
\ | | / \ | | /
16 15--31 30--14 13--25 2
\ | | /
9 8 7 6--12--24 1
\ | | / | \
2 1---5 22 23 Y=0
0 - 4 21 20 -1
\ | /
3--11--19 -2
\
10--18 -3
\
17 -4
^
-4 -3 -2 -1 X=0 1 2 3 4 5 6 7Diagonal One
Option parts => 'diagonal-1' is a diagonal starting from a single point and confined to a diagonal half-plane X>=Y,
parts => "diagonal"
41 40 39 38 35 34 33 32 4
\ | | / \ | | /
42--20 19--37 36--18 17--31 3
\ | | /
21--11 10 9 8--16--30 2
\ | | / | \
12---3 2---7 28 29 1
| /
0---1---6 27 26 <- Y=0
| \ | /
4 5 15--25 -1
| \
13 14--24 -2
| \
22 23 -3
^
-3 -2 -1 X=0 1 2 3 4In this pattern the edge points such as N=1,5,14 all have 3 children, so there's always 0, 1 or 3 children as per the full pattern. The square section beginning N=2 corresponds to the origin in the full pattern, so the initial single point here makes it one depth level later.
This pattern is OEIS A183148 half-plane of toothpick triplets by Omar Pol.
http://oeis.org/A183148
Turning the pattern +45 degrees and drawing toothpicks and per "Toothpicks" above gives
|
8
|
---8---.---7---
| | |
9 3 6
| | |
--10---.---2---.---1---.---5---
| | |
11 0 4
| | |
--------------------------------Ulam Warburton
Taking just the non-leaf nodes gives the pattern of the Ulam-Warburton cellular automaton oriented on the diagonal as per Math::PlanePath::UlamWarburtonQuarter and using 2x2 blocks for each cell.
parts=>1 non-leaf cells
...
| ** ** ** **
| ** ** ** **
| ** **
| ** **
| ** ** ** **
| ** ** ** **
| **
| **
| ** ** ** **
| ** ** ** **
| ** **
| ** **
| ** ** ** **
| ** ** ** **
| *
+----------------parts=4 gives the pattern of Math::PlanePath::UlamWarburton but again turned 45 degrees and in 2x2 blocks.
FUNCTIONS
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
$path = Math::PlanePath::LCornerTree->new ()$path = Math::PlanePath::LCornerTree->new (parts => $str)-
Create and return a new path object. The
partsoption (a string) can be"4" the default "3" "2" "1" "octant" "octant_up" "wedge"
Tree Methods
@n_children = $path->tree_n_children($n)-
Return the children of
$n, or an empty list if$nhas no children (including when$n < 0, ie. before the start of the path).For parts=1,2,3,4 each point has either 0 or 3 children. Such a tree is sometimes called a "3-tree". The children of a corner
$nare the three cells adjacent to it turned "on" at the next depth. A non-corner has no children.For parts=octant the points on the X=Y diagonal always have 2 children and the rest is 0 or 3 children.
OEIS
This cellular automaton is in Sloane's Online Encyclopedia of Integer Sequences as follows, and drawings by Omar Pol.
http://oeis.org/A160410 (etc)
parts=4 (the default)
A160410 total cells at given depth, tree_depth_to_n()
A161411 added cells at given depth, 4*3^count1bits(n)
http://www.polprimos.com/imagenespub/polca023.jpg
http://www.polprimos.com/imagenespub/polca024.jpg
parts=3
A160412 total cells at given depth, tree_depth_to_n()
A162349 added cells at given depth, 3*3^count1bits(n)
http://www.polprimos.com/imagenespub/polca013.jpg
http://www.polprimos.com/imagenespub/polca027.jpg
http://www.polprimos.com/imagenespub/polca029.jpg
parts=1
A130665 total cells at given depth, from depth=1 onwards
cumulative 3^count1bits, tree_depth_to_n(d+1)
A048883 added cells at given depth, 3^count1bits(n)
http://www.polprimos.com/imagenespub/polca011.jpg
http://www.polprimos.com/imagenespub/polca012.jpg
http://www.polprimos.com/imagenespub/polca014.jpg
parts=octant,octant_up
A162784 added cells at given depth, (3^count1bits(n) + 1)/2
parts=wedge
A151712 added cells at given depth, 3^count1bits(n) + 1
http://www.polprimos.com/imagenespub/polca032.jpg
parts=diagonal-1
A183148 total cells at given depth, tree_depth_to_n()
A183149 added cells at given depthSEE ALSO
Math::PlanePath, Math::PlanePath::LCornerReplicate, Math::PlanePath::UlamWarburton, Math::PlanePath::ToothpickTree
HOME PAGE
http://user42.tuxfamily.org/math-planepath/index.html
LICENSE
Copyright 2012, 2013 Kevin Ryde
This file is part of Math-PlanePath-Toothpick.
Math-PlanePath-Toothpick is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
Math-PlanePath-Toothpick is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with Math-PlanePath-Toothpick. If not, see <http://www.gnu.org/licenses/>.