Suggestion for orientation fixing

[awsdert]

Already posted this on the YT vid but I'll repeat it here anyways.

For fixing orientation you 1st want to determine the longest or shortest section of the shape, doesn't matter what way it's rotated at this point, you just set that section as the central axis. Next you find the opposite (so if set longest as central then now you want shortest) and set that as the next axis to orientate around. Now you do the basic √(A² * B²) to find the shortest or longest hypotenuse between those 2 lengths and set that as "up" or "down". You should have a fixed orientation at this point, if not then some more calculations based on the remaining length are needed but that you should be able to work out yourself.

As for the probable number of unique shapes, start with W * H * D of the total area available for orienting in and then apply whatever formula it was for calculating the number of variants in sequences of length N like 2=2(XY,YX) & 3=6(XYZ, XZY, YXZ, YZX, ZXY, ZYX), that will give you a suitable amount of shapes to potentially store.

Finally you can speed up the search for same by just using a list of offsets to that pre-allocated array, the offsets will be for the start of the shapes containing the same number of cubes and a length of said array. From there I have no further ideas for optimal searching.

[mamoniot]

Fixing orientation can be done more simply by taking the bit array representation, pad it to a cube, creating all 24 rotations of it, translate each to a fixed corner, interpreting each bit array as a number, and then going with the smallest number. This method can be implemented as a constant number of bitshifts and at most 24 comparison operations (though there is probably a method of prematurely ruling out a bunch of orientations before operating on them).

For example, in 2d with only 2 shapes, you can consider these two orientations of an L shape:

100     110
100 and 010
110     010

and interpret them as numbers 100100110 and 110010010, and consider the larger number, 110010010, to be the "canonical" orientation of an L shape.

[georgedorn]

Finally you can speed up the search for same by just using a list of offsets to that pre-allocated array, the offsets will be for the start of the shapes containing the same number of cubes and a length of said array. From there I have no further ideas for optimal searching.

Searches within a Python set() are constant time. It's not the same as comparing the needle to every item in the haystack.

Fixing orientation can be done more simply by taking the bit array representation, pad it to a cube, creating all 24 rotations of it, translate each to a fixed corner, interpreting each bit array as a number, and then going with the smallest number.

The fastest speedup thus far is to store all of the rotations of a newly-found unique polycube, rather than rotating every candidate 24x and looking for each. Any rotation-independent hashable representation will need to out-do not rotating a candidate at all while also cutting down the number of rotations for a found unique polycube below 24x.

[awsdert]

Well mine doesn't actually rotate the object, just defines what order to compare the cells in by using traits the various orientations of each shape would share in a unique enough way to fixate the relative order so for example a calculated orientation could result in separate references being set to different lists like this

getx = getabsz
gety = getabsx
getz = getabsy

The comparison would then not care about the underlying orientation because it's just reading the cells in the same relative order. Additionally I suspect that formula for N numbers to arrange would likely get the same counts anyways, I personally refuse to use python and am working on a more time consuming project anyways so I'll leave testing that theory to you lot.

[camel-cdr]

I think the original implementation used a depth first search without the need of a hash table: http://kevingong.com/Polyominoes/ParallelPoly.html

The idea is to generate the objects using these inner/outer numbered cells, which allows you to generate all polysquares (and cubes), including rotational and transitional equivalent ones. But you can filter out all the rotational equivalent ones by rejecting every shape where the root element isn't the left most square at the bottom of the polysquare:

So now you have an algorithm that allows you to visit every polysquare ones, without needing to store them. This method can be expanded to polycubes.

I'm not sure how the accounted for the rotational equivalent ones, I can see two approaches working:

1. Just have different counters for rotational symetric polysquares/cubes , this would result in a larger search space

2. fix the orientation of non-rotational symmetric polysquares/cubes using a method as described in this thread above, and hash every rotational symmetric polysquare, to canonicalize those.

the paper suggests that

[...] However, the cost of checking for symmetry probably outweighs the potential gain in speed. In fact, as is evidenced by Lunnon's results, and proven theoretically, the number of polyominoes with no symmetry divided by the number of polyominoes approaches 1 as the size of polyominoes grows larger.

This seems to suggest that 2. is the way to go, as we wouldn't expect to many entries, and drastically reduce the search space at the start.

Edit: I'm not sure if you can only explore the canonicalized form of the rotational symmetric polysquares. I assumed that this is the case in the above, so I crossed the parts out for now.

Also: Note that the current approach of generating successors and storing them in a hash table can't feasibly work to get close to the world record as we are already dealing with 59795121480 polycubes for n=16, that is >59 Gb if we'd only need a single byte to store a polycube in a hash table.

[awsdert]

Well I don't know if your method really is the best but I can say with certainty that I like my method better. It's easy to understand that a shape in any orientation will occupy the same volume of space, so using the dimensions of that space to get the fixed perspective to start comparing in is much easier than trying to rotate it until it matches one that already exists. Sure when it drops down to programming level hash tables are probably of use, but it still likely helps cause the desired collisions by fixing the perspective.