Hex-Chaos Compositions and Equivalence Classes of Packing Problems

Year: 2018 Authors: Gary R. Greenfield

Core claim

Up to equivalence, there are exactly thirteen types of hex-chaos compositions.

Topics

generative art, cellular automata, genetic algorithm, packing problems, equivalence classes

Domains

elementary group theory, combinatorics, discrete structures, generative art, visualization, minimalist artworks

Methods

binary-to-hex mapping, 1 + 1 genetic algorithm, equivalence classification

Media

grid cells, hexadecimal labels, color ramp

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2018 Conference Proceedings

Hex-Chaos Compositions and Equivalence Classes of Packing Problems

Gary R. Greenfield

University of Richmond, Virginia, USA; ggreenfi@richmond.edu

Abstract

We consider a generative art scheme that uses zero-one labelings of the edges of all the cells of a grid and chaotic one-dimensional cellular automata to assign hexadecimal digits to the cells of the grid. This allows us to color all the cells by mapping hex digits to colors. We invoke a genetic algorithm to maximize the number of occurrences of two hex digits thereby evolving what we call hex-chaos compositions. Using elementary group theory we prove, up to equivalence, there are thirteen different types of hex-chaos compositions.

Introduction

Let ${\mathcal{G}}_{m,n}$ denote the set of $m\times n$ grids whose cells are labeled with hexadecimal digits. If $\mathcal{X}=\{0,\dots ,9,a,\dots ,f\}$ , then ${\mathcal{G}}_{m,n}=\{\boxed{x_{r,c}}:x_{r,c}\in \mathcal{X},\text{ for }1\le r\le m,1\le c\le n\}$ . Each cell of a hex grid $X=\boxed{x_{r,c}}\in {\mathcal{G}}_{m,n}$ has four edges. Suppose the edges of all the cells are labelled using zeros and ones. Then a generic cell $x_{r,c}$ has top, left, bottom and right edge labels $h_{r,c},v_{r,c},h_{r+1,c}$ and $v_{r,c+1}$ . The horizontal edge labels determine an $(m+1)\times n$ matrix $H=(h_{p,q})$ , while the vertical edge labels determine an $m\times (n+1)$ matrix $V=(v_{s,t})$ . We say $X$ is a pullback if there exist $H$ and $V$ such that for all $r$ and $c$ , $x_{r,c}$ is equal to the conversion of the base two representation of the four digit binary number formed by concatenating the edge labels counterclockwise from the top to a hex digit i.e., $x_{r,c}$ equals the hex value of the decimal

In this case, we write $X=H\diamond V$ . We denote the set of $m\times n$ hex grids that are pullbacks by ${\mathcal{P}}_{m,n}$ . Evidently, the way to construct pullbacks is to interleave matrices of zeros and ones of the appropriate dimensions and then use the binary to hex conversion formula to determine the hex labels.

EXAMPLE 1. Let $m=4$ , $n=5$ . Set

Then interleaving gives

Greenfield

and using the binary to hex conversion formula gives the pullback

For visualization purposes we assign a color ramp of sixteen shades of blue to the hex values 0 through $f$ . To add visual interest to the construction we choose two hex values 0 \leq x_{1} < x_{2} \leq f and recolor them so they stay stand out. If we choose $x_1=5$ and $x_2=9$ and assign them the colors brown and yellow respectively, we obtain the visualization for the $X$ of Example 1 shown in Figure 1.

Figure 1: A visualization of the hex labeled grid in Example 1 obtained by mapping 5 to brown, 9 to yellow and all other hex labels to shades of blue.

Adding Chaos

Following an idea first proposed by Cruz et al. [1], we now require the edge labels of our pullbacks to be the outputs of iterates of chaotic or eventually periodic one-dimensional cellular automata [3]. Thus, we let $H_0$ be an $(m+1)\times n$ matrix with randomly generated zeros and ones and $V_0$ be an $m\times (n+1)$ matrix of randomly generated zeros and ones. We assign one dimensional automata to the $m+1$ rows of $H_0$ and the $n+1$ columns of $V_0$ . We define $H_i$ and $V_i$ inductively by letting $H_{i+1}$ and $V_{i+1}$ be the matrices obtained by treating the rows of the $H_i$ matrix and the columns of the $V_i$ matrix as the inputs to the respective automata, yielding the rows of the $H_{i+1}$ matrix and the columns of the $V_{i+1}$ matrix as the outputs.

EXAMPLE 2. Let $m=4$ , $n=5$ . Choose Rule 30 for the rows and Rule 54 for the columns. Let

Then $H_{500}$ and $V_{500}$ are the matrices $H$ and $V$ that gave rise to the pullback grid $X$ of Example 1.

Hex-Chaos Compositions

Let $m=30$ , $n=40$ , and continue to use Rule 30 for rows and Rule 54 for columns. Towards the Cruz et al. goal of “harnessing chaos” we consider the following scheme for maximizing the number of occurrences of the two distinguished hex values $x_1$ and $x_2$ in the central region of a pullback hex grid. If $X_{500}$ is a pullback induced after 500 iterations starting from $H_0$ and $V_0$ (i.e., $X_{500}=H_{500}\diamond V_{500}$ ), let $c_i$ be the number

Hex-Chaos Compositions and Equivalence Classes of Packing Problems

of occurrences of $x_i$ in $X_{500}$, $w_i$ be the number of occurrences of $x_i$ in the centered $3/5m\times 3/5n$ subgrid of $X_{500}$ and $o_i=c_i-w_i$. Then the fitness of $X_{500}$ is defined to be

This function preferences pullbacks where the number of $x_1$‘s and $x_2$‘s are nearly equal, rewards pullbacks where occurrences of $x_1$ and $x_2$ are within the central window and penalizes pullbacks where occurrences of $x_1$ and $x_2$ are outside the central window.

We invoke a so-called $1+1$ genetic algorithm by forming $H_0^{\prime }$ and $V_0^{\prime }$ from $H_0$ and $V_0$ by changing either one entry of $H_0$, one entry of $V_0$ or one entry of both, and replacing $X_0$ by $X_0^{\prime }$ whenever $F(X_{500}^{\prime })\ge F(X_{500})$. This implements simple hill climbing such that the rows and columns of $H_0$ and $V_0$ are, via indirect feedback, forced to cooperate to maximize fitness. We let the algorithm run for 25,000 generations. That is, we make 25,000 attempts to improve fitness. Further details about the motivation, algorithm design and choice of parameter settings can be found in Greenfield [2].

Figure 2 shows three examples of hex-chaos compositions evolved using our evolutionary algorithm. From a distance they may look quite similar, but up close each one presents a different visual challenge to the viewer. Namely, what are the rules for the two distinguished colors? For example, for browns and yellows one finds: browns can be vertically or horizontally adjacent to each other, yellows cannot, and if brown and yellow are ever horizontally (respectively, vertically) adjacent then yellow must be on the left (respectively, on top). We leave it to the reader to infer the adjacency rules for the other two examples.

Packing Problems

Since we are trying to pack approximately an equal number of $x_1$‘s and $x_2$‘s into the central window, this raises the question of how many occurrences of $x_1$ and $x_2$ one can pack into an $m\times n$ pullback in general. Of course to consider such a question we will have to drop the assumption that the pullback is an iterate. Thus we wish to consider the problem of determining

where, for $x\in \mathcal{X}$ and $G\in \mathcal{G}$, ${\eta }_x(G)$ equals the number of occurrences of $x$ in $G$. This is a challenging problem. We offer the following examples whose proofs appear in Greenfield [2].

THEOREM 3. Let $x_1=5$, $x_2=f$. Then ${\Gamma }_{m,n}(5,f)$ equals $\lfloor mn/2\rfloor -1$ if $m$ is even and $n$ is odd, and $\lfloor mn/2\rfloor$ otherwise.

THEOREM 4. Let $x_1=0$, $x_2=f$. Then

The proofs construct $P$‘s for which ${\eta }_{x_1}(P)={\eta }_{x_2}(P)$. If we let

and define

this leads to the conjecture

Greenfield

Figure 2: Hex-chaos compositions. Top: $x_1=2$ (green), $x_2=5$ (brown). Middle: $x_1=5$ (brown), $x_2=9$ (yellow). Bottom: $x_1=5$ (brown), $x_2=f$ (black).

Hex-Chaos Compositions and Equivalence Classes of Packing Problems

CONJECTURE A. ${{\rm Y}}_{m,n}(x_1,x_2)={\Gamma }_{m,n}(x_1,x_2)$

Equivalently, if we denote the set of attained maximums by

we have

CONJECTURE B. ${\mathcal{M}}_{m,n}(x_1,x_2)\cap {\mathcal{E}}_{m,n}(x_1,x_2)\ne \varnothing$

Packing Problem Equivalences

For fixed $m$ and $n$, using the convention 0 \leq x_{1} < x_{2} \leq f, ostensibly there are 120 packing problems to consider. Our goal is to prove that there are really only thirteen such problems and thus, up to the equivalence relation defined below, only thirteen different kinds of hex-chaos compositions.

If $B=(b_{i,j})$ is $k\times \ell$ matrix of zeros and ones we define its complement $\chi (B)$ to be $J-B$ where $J$ is the $k\times \ell$ matrix all of whose entries are ones. Complements establish four bijections of ${\mathcal{P}}_{m,n}$ with itself, ${\chi }_I,{\chi }_R,{\chi }_C,{\chi }_B={\chi }_R\circ {\chi }_C={\chi }_C\circ {\chi }_R$ corresponding to the identity, complementing the row edges, complementing the column edges, and complementing both the row and column edges. That is,

These bijections induced hex label permutations ${\psi }_I,{\psi }_R,{\psi }_C,{\psi }_B$ that are wholly determined by what happens to the edges of a “generic” cell. At this juncture it is convenient to change notation and use edge labels that reflect the ordering used for binary to hex conversion. We have

whence running through the sixteen possibilities for the base two representation of $x$ as $(e_1{e}_2{e}_3{e}_4{)}_2$ establishes ${\psi }_R$ with $(e_1{e}_2{e}_3{e}_4{)}_2⟶((1-e_1)e_2(1-e_3)e_4{)}_2$ as

and, similarly, we obtain

If $M=(m_{i,j})$ is a $k\times \ell$ matrix we define the reflection of $M$ about the vertical axis $\nu (M)$ to be the $k\times \ell$ matrix $(n_{i,j})$ where $n_{i,j}=m_{i,(\ell +1)-j}$, and the reflection of $M$ about the horizontal axis $\mu (M)$ to be the $k\times \ell$ matrix $(u_{i,j})$ where $u_{i,j}=m_{(k+1)-i,j}$. These operations together with the matrix transpose operation $(M^t=(t_{i,j})$ where $t_{i,j}=m_{j,i}$) allow us to mimic the action of the dihedral group of order eight on an $m\times n$

249

pullback. We realize this group as four clockwise rotations of 0(90), 1(90), 2(90), and 3(90) degrees plus four reflections $h$, $v$, $d$ and $a$ about the horizontal, vertical, diagonal, and antidiagonal axes. We define

${\zeta }_0(H\diamond V)$ $=H\diamond V$ ${\zeta }_1(H\diamond V)$ $=\nu (V^t)\diamond \nu (H^t)$ ${\zeta }_2(H\diamond V)$ $=(\mu \circ \nu )(H)\diamond (\mu \circ \nu )(V)$ ${\zeta }_3(H\diamond V)$ $=\mu (V^t)\diamond \mu (H^t)$ ${\zeta }_h(H\diamond V)$ $=\mu (H)\diamond \mu (V)$ ${\zeta }_v(H\diamond V)$ $=\nu (H)\diamond \nu (V)$ ${\zeta }_d(H\diamond V)$ $=V^t\diamond H^t$ ${\zeta }_a(H\diamond V)$ $=(\mu \circ \nu )(V^t)\diamond (\mu \circ \nu )(H^t)$

The four bijections that involve transposes map $m\times n$ pullbacks to $n\times m$ pullbacks. We let ${\pi }_{\ast }$ denote the induced hex label permutation for ${\zeta }_{\ast }$. We know ${\pi }_0={\psi }_I$ is the identity permutation. To determine the other induced permutations, we again use our generic cell mapping notation, but now we must recognize that the cell containing hex label $x_{i,j}$ is being moved before it is relabeled. If we write $\tau (M)$ for $M^t$ so the notation is consistent, then we can track label movement by making appropriate index calculations. For example, ${\zeta }_1((i,j))=(\nu \circ \tau )((i,j))=\nu ((j,i))=(j,(m+1)-i)$ tells us that the label in cell $(i,j)$ will be moved to cell $((n+1)-j,i)$ and relabeled according to the permutation ${\pi }_1$ shown below. Because we know we are recovering the dihedral group, we only calculate ${\zeta }_1$ and ${\zeta }_v$:

[ \left[\begin{array}[]{cccc}&e_{1}&\ e_{2}&x&e_{4}\ &&e_{3}\end{array}\right]\longrightarrow\left[\begin{array}[]{cccc}&e_{2}&\ e_{3}&\pi_{1}(x)&e_{1}\ &&e_{4}\end{array}\right],\left[\begin{array}[]{cccc}&e_{1}&\ e_{4}&\pi_{v}(x)&e_{2}\ &&e_{3}\end{array}\right] ]

gives

${\pi }_1$ =\left(\begin{array}[]{cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc}{c}&0&1&2&3&4&5&6&7&8&9&a&b&c&d&e&f\\ 0&2&4&6&8&a&c&e&1&3&5&7&9&b&d&f\end{array}\right), ${\pi }_v$ =\left(\begin{array}[]{cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc}{c}&0&1&2&3&4&5&6&7&8&9&a&b&c&d&e&f\\ 0&4&2&6&1&5&3&7&8&c&a&e&9&d&b&f\end{array}\right).

Writing the non-identity permutations as products of disjoint cycles provides

${\psi }_R$ $=(0a)(1b)(28)(39)(4e)(5f)(6c)(7d)$ ${\psi }_C$ $=(05)(14)(27)(36)(8d)(9c)(af)(be)$ ${\psi }_B$ $=(0f)(1e)(2d)(3c)(4b)(5a)(69)(78)$ ${\pi }_1$ $=(0)(1248)(36c9)(5a)(7edb)(f)$ ${\pi }_2$ $=(0)(14)(28)(3c)(5)((69)(7d)(a)(be)(f)$ ${\pi }_3$ $=(0)(1842)(39c6)(5a)(7bde)(f)$ ${\pi }_h$ $=(0)(1)(28)(39)(4)(5)(6c)(7d)(a)(b)(e)(f)$ ${\pi }_v$ $=(0)(14)(2)(36)(5)(7)(8)(9c)(a)(be)(d)(f)$ ${\pi }_d$ $=(0)(12)(3)(48)(5a)(69)(7b)(c)(de)(f)$ ${\pi }_a$ $=(0)(18)(24)(3c)(5a)(6)(7e)(9)(bd)(f)$

The permutations ${\psi }_R$ and ${\psi }_C$ generate a subgroup of $S_{16}$ isomorphic to the Klein four group using the familiar relations

${\psi }_R^2,{\psi }_C^2,{\psi }_R{\psi }_C={\psi }_C{\psi }_R,$

Hex-Chaos Compositions and Equivalence Classes of Packing Problems

while the permutations ${\pi }_1$ and ${\pi }_{\nu }$ generate a subgroup of $S_{16}$ isomorphic to the dihedral group of order eight using the familiar relations

(Note that ${\pi }_1{\pi }_v={\pi }_d$ , ${\pi }_1^2{\pi }_v={\pi }_h$ and ${\pi }_1^3{\pi }_v={\pi }_a$ .) However, the subgroup of $S_{16}$ of order thirty two that these four permutations generate is not an internal direct product of the subgroup < \pi_1,\pi_v> of order eight with the subgroup < \psi_R,\psi_C> of order four because even though

we also have

To organize the calculation of equivalence classes of packing problems, we use a $4\times 8$ table showing how each of the thirty two permutations in

acts on an instance $(x_1,x_2)$ — by letting the permutation act on each entry — in such a way that the first four columns show $m\times n$ equivalences and the last four show $n\times m$ equivalences. An example illustrates how this works.

Even though for the purpose of equivalence the pairs should show the smaller value first, the ordering of the pairs in the table is useful. For example the $(f,7)$ in the ${\psi }_B$ row and ${\pi }_3$ column tells us that the mapping from ${\mathcal{P}}_{m,n}$ to ${\mathcal{P}}_{n,m}$ which takes $H\circ K$ to $({\zeta }_3\circ {\chi }_B)(H\circ K)$ will relocate all the 0’s and 1’s while simultaneously relabeling them as $f$ ‘s and 7’s, respectively, because $({\pi }_3\circ {\psi }_B)(0)=f$ and $({\pi }_3\circ {\psi }_B)(1)=7$ . This, in turn, tells us ${\Gamma }_{m,n}(0,1)={\Gamma }_{n,m}(7,f)$ or equivalently, if we can solve the $(0,1)$ packing problem for all problem instances then we can solve the $(7,f)$ packing problem for all problem instances. Thus, if we denote the equivalence class of packing problems for $(x_1,x_2)$ by $[(x_1,x_2)]$ , then the table reveals

Space prohibits showing the calculations for all thirteen equivalence classes. Instead, we show that the equivalence classes are not all the same size by providing

which yields

Greenfield

and

which gives

Table 1 lists the thirteen equivalence classes and their cardinalities. The choice of representative is lexicographical and classes are ordered lexicographically. With reference to Figure 2, we note that (2,5) belongs to $[(0,7))$ , (5,9) belongs to $[(0,3)]$ and $(5,f)$ belongs to $[(0,5)]$ . With reference to Theorem 3, $(5,f)$ belongs to $[(0,5)]$ .

Table 1: Equivalence Classes of Hex-Chaos Compositions.

Summary and Conclusions

We have described a generative art scheme incorporating chaotic one-dimensional cellular automata and hex labelings of the cells of a grid in order to evolve minimalist artworks called hex-chaos compositions. We then showed how this led to a suite of 120 packing problems which, thanks to some elementary group theory, could be organized into thirteen equivalence classes, thereby revealing there were exactly thirteen different types of hex-chaos compositions and presenting us with thirteen challenging packing problems to solve. To date we have solved seven of these problems.

References

[1] C. Cruz, M. Kirley, and J. Karakiewicz. “Generation and exploration of architectural form using a composite cellular automata.” Third Australasian Conference, ACALCI 2017, Geelong VIC, Australia, January 31 - February 2, 2017, Proceedings, M. Wagner et al. (eds.), LNAI 10142, Springer International Publishing, Cham, Switzerland, 2017, pp. 99-110. [2] G. Greenfield. “Interleaved cellular automata, evolved art and packing problems.” 2018 IEEE CEC Conference Proceedings, to appear. [3] S. Wolfram. “Universality and complexity in cellular automata.” Phys. D Nonlinear Phenomena, vol. 10, no. 1, 1984, pp. 1-35.