bertie2
commented
1 year ago I think your onto something with the views, the hard part will be proving that the views are unique, i'm going to run a test with the n=12 data to check.
as for an efficient way to compare the views, I think we just need to come up with a quick to compute canonical direction and order for the vectors. so in your example:
polycube1_views -> [4, 1], [1, 1, 1, 2], [1, 0, 1, 0, 1, 0, 1, 1] polycube1_rotated_views -> [1, 4], [1, 0, 1, 0, 1, 1, 1], [1, 1, 1, 2]
something which ranks [4, 1] higher than [1, 4] for example.
and something that ranks [1, 0, 1, 0, 1, 0, 1, 1] higher than, [4, 1]
the problem I foresee is after doing all these checks to get the right order, is it any faster than the rot90? more testing to be done.
Playit3110
VladimirFokow
ana-096
From profiling the function
generate_polycubes, for larger values of n the time spent onrot90is a significant factor, with 45 of the 108 second runtime being spent in it for n=9 (see table at bottom of text).So far I've been thinking about a couple of potential solutions, but I haven't reach a point where either solution could be implemented:
Solution A - Writing a purpose-specific
rot90orall_rotationsNumpy appears to use index swapping to achieve 90 degree rotation of an array (definitely faster than a transformation matrix I would imagine), but it has significant overhead as it is written to work for n-dimensional arrays. In the case of polycubes, we know that the array we want to rotate is 3D, and that we want all 28 rotations. Writing a purpose specific version of this function could save on overhead time, but I think it would most likely need to be done in another language.
I haven't really been pursuing this as I don't know any low level or performant languages to try this in, and I think we won't save time with a pure python implementation.
Solution B - Representing the polycube as three 2-D views
This solution appeals to me far more than solution A, as it reduces either our comparisons between hashes, or our memory used on storing hashes (if we store rotations). As we conveniently have a boolean array aligned with the axes, I think we can represent any polycube with three, fast to calculate, 2-D views of the polycube:
For the simple L shaped (cropped) polycube with a length of 4 and 1 cube off the a side, the views would be represented this way:
[4, 1], [1, 1, 1, 2], [1, 0, 1, 0, 1, 0, 1, 1]We can avoid worrying about the order in which these appear by using collections.Counter or generally by treating it as an unsorted list. We could then compare the view to a rotated version of the polycube by ensuring that all entries match only once, hence finding that both polycubes are identical...
Unfortunately, though this works for comparing the two 1-D views of a polysquare with some additional checks, I haven't found a way to ensure these views match for polycubes after any of the 28 arbitrary rotations:
We can see from this that some rotations will give us outputs that are very hard to compare to the original polycube for equality.
Perhaps a solution to this is to rebuild the arbitrary polycube in a specific manner to always give the same output? I don't have a solution for this yet.
Profiling
cumtimeis the value we're worried about forrot90in this case, as looking at the source code for this function, it calls a number of other functions to achieve rotation by 90 degrees, withflipbeing the main point of concern.With optimisations from the PRs on the original repo (bertie2, georgedorn, and mine), the cProfile.run output looks like this for n=9: