TESSELATION

J. Lederberg
January 20, 1965

Algorithm for filling shells, out -> in.

6 bits = 1 byte. Use one byte for set of corresponding positions on 6 edges.
Therefore, if n = order of the shell, the descriptive word will have n bytes.

The bytes are in order, ABCDEF, GHIJKL, MNOPOR, STUVWX, YZabcd, and +

1. Partition the shell count among the bytes. (A more efficient algor-
ithm might well extract some symmetries at this point but would complicate the
definition of dictionary order. The symmetry involved is reflection, since
MNOPQR can interchange with GHIJKL on shell 3, for example.)

But dictionary order does not directly follow this; viz. ABC < AD. This
should not be consequential in producing the canonical forms.

2. Consider first byte.

3. Consider possible arrangements of this byte:

 

 

Binary Octal Symmetries left
A 100000 40 /
AB 110000 50 /1 BHNTZC
AC 101000 50 /2 YBHNTCI
AD 100100 44 2 / SSBHNCIO
ABC 111000 70 /2 MMMBHCIOU
ABD 110100 64 none GGGGBCTIOvUa
ACE 101010 52 3 / AAAAAt+DDDDD
ABCD 111100 74 /4 dXRLFEJIJIJ
ABCE 111010 72 /2 XRLFKEPPP
ABDE 110110 66 /1 RLFQKEVV
ABCDE 111110 76 /4 LFWQKEb
ABCDEF 111111 77 6 / FCWOQKE
0 000000 00 6 /

After translation, the figure must be canonicated to compare it with the
original. If the latter is later in dictionary order, it is rejected.

To canonicate, set up a look-up table of the function that transforms any
6-bit number to the canonical byte, and execute accordingly for the first
byte. The zemaining bytes are then tested in sequence under the allowed
operations still remaining; the same for the next shell.

For masking one shell on the next: the first byte (ABCDEF) is unique and
masks on as many as 3 bytes (1, 2 and last). The last is rotated before
being masked,
TESSELLATIONS 1/19/65

Definition of canonical form,

1. Translate center of coordinates to give the minimum shell-count-vector,

2. (Translate) rotate and reflect to give minimum dictionary value of
the list of items, shell by shell.

The outermost shell corresponds to the most significant (leftmost)
item of the vector-

D-E-F G OF ~ TAN 29 1966
€ G-b-
PBRG a
AKA+DGJ
RhPeuK
QKITE
PON M

Notation: list of shells separated by , and with or without terminal + ,
Empty comma positions are possible at right-hand side of
list only.
Examples: (+) benzene
(A+) naphthalene
(AB+) phenalene

(ABC+) pyrene
(A, AD+) napthacene

Possible economies: do not implement now

If more than one alphabetic cycle is needed in a ring,use initial . to
set up rank

Commas between non-ascending characters could be dispensed with.
Leading A and strings of A,A,A could be more economically coded
Tessellations 1/19/65
Tactical decisions:

1, Partition the count to shell count vector, No interstitial o's
allowed. Largest shell allocates entire count to diameter.

2. Build shells from outside inwards, Retain record of symmetry res-
trictions for calculations on next inner shells.

3, Test for peripheral islandsas each shell is filled.
4— When figure is completed, test (and discard if indicated)

translation to smaller shell count vector
discontinuity by masking in and out across shells (breathing)

if translation leaves any ambiguity (shell count vector same)
test results of operations(translation,rotation and reflection)
for any result with lower value than propesitus.

5 eventually install search for enclaves

6 store list of results on disk!

In process, calculate and store appropriate masks unless the
procedure for calculating the mask is quite fast