Ruby’s model is provided more for convenience than correctness, and is inconsistent:
array + array is array concatenation, allowing duplicates, but array - array is set difference, removing duplicates: [1, 1] - [1] is [], not [1].
- is not the inverse of +, because it’s not the case that a + b - c == a for all Array instances a, b, and c: take [1] + [1] - [1].
array * fixnum is defined as iterated array concatenation, but fixnum * array is not defined at all.
For purely array-based operations, I would expect + and - to be inverses:
[1, 2] + [3, 1] == [1, 2, 3, 1]
[1, 2, 3, 1] - [3, 1] == [1, 2]
- would remove elements from the tail just as + added them. Similarly for * and /:
[1, 2] * 3 == [1, 2, 1, 2, 1, 2]
[1, 2, 1, 2, 1, 2] / 3 == [1, 2]
[5, 1, 2, 1, 2] / 2 == [1, 2]
/ would first discard elements from the left until a.size % b == 0. Why from the left? Well, I would expect an array modulus operator to satisfy the law:
a % b == a - (b * (a / b))
And that rule seems to work if you go through a few examples:
[1, 1] % 2 == [1, 1] - (2 * ([1, 1] / 2)) == [][5, 1, 1] % 2 == [5, 1, 1] - (2 * ([5, 1, 1] / 2)) == [5]
This is basically defining division as iterated subtraction.
There are a couple of consistent and reasonably intuitive interpretations of array ♦ array:
Cartesian product: [1, 2] ♦ [3, 4] == [1 ♦ 3, 1 ♦ 4, 2 ♦ 3, 2 ♦ 4]
Pairwise product: [1, 2] ♦ [3, 4] == [1 ♦ 3, 2 ♦ 4]
With a Cartesian product, the size of the result is the product of the size of the inputs. This is how list comprehensions and the list monad work in Haskell:
[x ♦ y | x <- [1, 2], y <- [3, 4]]
do
x <- [1, 2]
y <- [3, 4]
return (x ♦ y)
A pairwise product also makes sense, in that ([x1, y1, z1] * [x2, y2, z2]).reduce(:+) would be the dot product of the vectors [x1, y1, z1] and [x2, y2, z2]. Of course, you would need to define the result when the inputs are of different lengths; in Haskell, the zipWith function takes the shorter of the two input lists:
zipWith (♦) [1, 2] [3, 4, 5]
== zipWith (♦) [1, 2] [3, 4]
So the answer is that there are several possible interpretations, the choice of which is up to the designers of languages and libraries. As long as they’re self-consistent, none of them is strictly more “right” or “intuitive” than any other. The established convention in array languages is for array * array to refer to pairwise product, because this generalises well to higher dimensions of array, and from promoting scalars to arrays of appropriate dimension.
You can make use of the fact that when
BoxIsFilledWithCubes(c,x,y,z)
returns true, then it is not necessary to check in BoxIsFilledWithCubes(c,x+1,y,z) all those cubes in the coordinate range "(c,x,y,z)" again. You need only to check those cubes with the new x-coordinate c.x + (x+1). (Same is true for y+1, or z+1). More generally, by splitting up a box into two smaller boxes (for which you might already know if they are both filled with cubes, or not both filled), you can apply a divide-and-conquer technique here, which becomes faster than your original approach when you cache the intermediate results.
To accomplish this, you start implementing BoxIsFilledWithCubes(c,x,y,z) recursively, for example:
bool BoxIsFilledWithCubes(coord,lx,ly,lz)
{
if(lx==0|| ly==0 || lz==0)
return true;
if(lx==1 && ly==1 && lz==1)
return world.Contains(coord);
if(lx>=ly && lx>=lz) // if lx is the maximum of lx,ly,lz ....
return BoxIsFilledWithCubes(coord,lx/2,ly,lz)
&& BoxIsFilledWithCubes(coord.Offset(lx/2,0,0), lx-lx/2, ly, lz);
else if(ly>=lz && ly>=lx)
// ... analogously when ly or lz is the maximum
}
and then use memoization (like it is discussed here) to avoid any repeated calls to BoxIsFilledWithCubes with the same parameters. Note you will have to clear the memoization cache when you apply a change to your world container, like by world.RemoveRange. Nevertheless I guess this will make your program faster.
Best Answer
There are a few ways to do this.
In addition to the six 3x3 arrays containing the colors of the stickers, you could have a 3x3x3 array representing the solid cubies. (The interior cell of this array can be ignored.) The cells of the 3x3x3 array could then contain integers (or pointers to more detailed objects) describing the original location of each cubie. You just have to make sure you do the appropriate "rotation" of the 3x3x3 array each time you "rotate" the stickers.
Or you could just put everything in one 5x5x5 array. The central 3x3x3 array could represent the solid parts of the cube and the central 3x3 array of cells on each face of the 5x5x5 array could represent the stickers.
Another alternative: just a 3x3x3 array, in which each cell contains a pointer to a structure. The structure identifies the original location of the cubie and the colors and locations of the stickers on its faces. The structure also contains a modifiable integer that describes the orientation of the cubie: a particular value (say, 0) for the orientation the cubie "should" have in a fully-solved cube, and 23 other values representing the other possible orientations of the cubie after a sequence of rotations. You also need a function (which could be a simple table lookup) that says which orientation results from each possible quarter-turn applied to each possible orientation. You will also probably find use for a function that says, for each orientation, what face of the original (orientation 0) cubie is on the top, bottom, left, and so forth. To rotate a slice of the cube, you have to permute the contents of the moving cells, of course, but you also have to correctly modify the orientation of every cubie in the rotated slice (including the cubie in the center of the face for a face rotation, even though the location of the cubie does not move).