Verifying solution proposal for Mike's cube problem

39 Views Asked by At

Note: This is a toy problem, nothing important, so only spend time if you have to spare and want to discuss. In this video Mike from Computerphile states a problem: Find all unique (including under rotational symmetry), connected shapes of cubes in a 3D grid for n cubes.

Question: Do you think my following algorithm would work for finding a unique hashvalue for a shape, independent of it's rotation?

I'm having a guess at the problem here, don't have the time to code it up:

  1. Deterministically choose a rotation independent point of the shape , haven't considered this step too far, my guess is calculating the gravitational midpoint of the shape, as how ever you rotate the shape that point will always have the same angle and distance to all other points
  2. Then for each point (or cube) calculate the (distance,angle)-pair to the midpoint. Pretty sure we've maintained uniqueness for each shape in this representation. So let's get rid of the rotation problem:
  3. (Don't know how this translates into 3D but for 2D) All angles are then rotated into the 1st half of the 1st quadrant of the unit circle. Meaning rotated and flipped so the angle is between 0-45 degrees. First account for rotation (we get it into the 1st quadrant 0-90): e.g. an angle that's 15 degrees is rotated 0 degrees, a "symmetric" angle of 195 degrees is rotated 180 degrees to 15, 105 would be rotated 270 to 15, and 285 rotated 90 to 15. To account for flips (get it into 0-45) we take angle X between 45-90 and flip it: by calculating it's flipped value Y = 90 - X, e.g. 75 would be flipped to 15 degrees. Combining this an angle that needs both rotation and flip correction, e.g. 165 would first be rotated 270 degrees into 75 and then flipped into 15. Now this will collapse symmetric shapes into the same representation (assuming the cube ordering is the same, see step 4.) but I'm still pretty sure this representation is unique for non-symmetric shapes. This calculation is pretty since it's O(n) for each shape
  4. Make sure the cube ordering is the same by sorting the array of (distance, angle)-pairs primarily distance to the point and secondarily angle to the midpoint. This is also pretty cheap O(n * log(n))
  5. Now the array representation should be unique between disimilar shapes but identical for symmetric shapes, thus hash the array representation.

FYI: I posted it as a YouTube comment as well

Mentally rotated and flipped a couple of shapes in 2D to figure out if the algorithm seemed correct

0

There are 0 best solutions below