Spiral order
Imagine the cube standing on its corner. It can be cut by planes. Each plane intersection with cube is a triangle or a hexagon. Sum of the coordinates at the intersection is the same for every point of this intersection. Let's call it a level.
Level 0 is trivial - it's just a vertex.
Level 1 contains three vertexes. It's spiral path contains two lines: one step to the right and one step to the bottom.
Level 2 contains six vertexes. Spiral path: two steps to the right, two steps to the bottom, one step to the top.
Level 3: three steps to the right, three steps to the bottom, two steps to the top, one step to the right.
In the cube 5x5x5 we have 1 corner vertex, 5 triangles then 4 hexagons and then 5 triangles again ending by the last corner vertex.
Here is the algorithm that prints coordinates of the first triangles in spiral order. The algorithm for hexagons can be written in the same manner.
Each level coordinates sum equals to the level.
Level 0: ( 0, 0, 0 )
Level 1: ( 1, 0, 0 ) - decrement value at 0 and increment value at 1 to get next vertex coordinates
( 0, 1, 0 ) - decrement 1 and increment 2 to get next coordinates
( 0, 0, 1 )
Level 2: ( 2, 0, 0 ) - dec 0, inc 1 to get next line
( 1, 1, 0 ) - dec 0, inc 1
( 0, 2, 0 ) - dec 1, inc 2
( 0, 1, 1 ) - dec 1, inc 2
( 0, 0, 2 ) - dec 2, inc 0
( 1, 0, 1 )
Level 3: ( 3, 0, 0 ) - dec 0, inc 1
( 2, 1, 0 ) - dec 0, inc 1
( 1, 2, 0 ) - dec 0, inc 1
( 0, 3, 0 ) - dec 1, inc 2
( 0, 2, 1 ) - dec 1, inc 2
( 0, 1, 2 ) - dec 1, inc 2
( 0, 0, 3 ) - dec 2, inc 0
( 1, 0, 2 ) - dec 2, inc 0
( 2, 0, 1 ) - dec 0, inc 1
( 1, 1, 1 )
Can you see the pattern?
Each level's pattern repeats several times.
Level 1: pattern 1 then pattern 2
Level 2: pattern 1 twice then pattern 2 twice, then pattern 3
Level 3: pattern 1 thrice then pattern 2 thrice, then pattern 3 twice, then pattern 1 again
So we get:
Level 1: 1, 1
Level 2: 2, 2, 1
Level 3: 3, 3, 2, 1
Level 4: 4, 4, 3, 2, 1
Level 5: 5, 5, 4, 3, 2, 1
Applying these patterns gives the correct spiral order.
import java.util.Arrays;
import java.util.Iterator;
public class CoordsPrinter {
public static final int COORDS_CNT = 3;
public static class CoordsIterator implements Iterator< int[] > {
private final int maxLevel;
private final int coords[];
private int currentLevel;
private int currentTurn;
private int currentStep;
private int currentEdge;
public CoordsIterator( int max ) {
this.maxLevel = max;
coords = new int[ COORDS_CNT ];
}
@Override
public boolean hasNext() {
return currentLevel <= maxLevel;
}
@Override
public int[] next() {
int ret[] = coords.clone();
int stepsQuantity = currentTurn == 0 ? currentLevel : currentTurn == currentLevel ? 2 : currentLevel - currentTurn + 1;
int nextEdge = currentEdge + 1;
if ( nextEdge == COORDS_CNT )
nextEdge = 0;
coords[ currentEdge ]--;
coords[ nextEdge ]++;
currentStep++;
if ( currentStep >= stepsQuantity ) {
currentTurn++;
currentStep = 0;
if ( currentTurn > currentLevel ) {
currentLevel++;
currentTurn = 0;
currentEdge = 0;
Arrays.fill( coords, 0 );
coords[ 0 ] = currentLevel;
} else
currentEdge = nextEdge;
}
return ret;
}
}
public static class CoordsIterable implements Iterable< int[] > {
private final int maxLevel;
public CoordsIterable( int max ) {
this.maxLevel = max;
}
@Override
public Iterator< int[] > iterator() {
return new CoordsIterator( maxLevel );
}
}
public static void main( String args[] ) {
for ( int coords[] : new CoordsIterable( 5 ) )
System.out.println( Arrays.toString( coords ) );
}
}
currentLevel determines the level of the triangle. currentTurn determines how many times we have changed the direction of spiral. currentStep determines how many steps we have passed at the current direction. currentEdge and nextEdge show the direction (we move from currentEdge to nextEdge).
