3

I normally have a very intuitive approach to an efficient algorithm. In essence, I know what the bottleneck is, and how I can improve the algorithm. However, I'm now stuck and I am in the need of some "inspiration".

The problem

The idea itself is very easy. I have a matrix of n x m booleans. I input another grid, also of n x m booleans. The question this algorithm has to solve is if the input shape can ever be matched on the output shape: this may be done by mirroring, rotating and moving the input shape around. I only need to know if the two shapes can be matched or not: the actual transformations do not matter.

Examples:

Target shape:

0 0 0
0 1 1 
0 0 0 

Input:

1 0 0
1 0 0
0 0 0

Clearly, this can be done. The transformation is simple:

1) Rotate counterclockwise:

0 1 1
0 0 0
0 0 0

2) Move down:

0 0 0
0 1 1
0 0 0 

A quick check can easily be done: count how many zeros or ones are in the input matrix. If this doesnt match the numbers of zeros and ones in the target shape, then the target shape cannot be made.

A more broader, general question would be what specific class of algorithm I'm looking for. It isn't really clear for me, though using my example I'd say that a carefully constructed pathfinding algorithm could work.

I also want to note that I am not a computer science student, programming is one of my hobbies. I do have proper understanding of "basic matrix manipulations" - maybe there is a wonderful "math trick" for this.

  • Are you interested in just checking whether two "shapes" can be matched, or do you want to find the actual transformation sequence to get from one to the other? If the latter, my first thought is pathfinding algorithms like A*, with a heuristic like "average distance between 1s". – Ixrec Jun 14 '15 at 21:39
  • No, I only need to check if the two shapes can be matched. I am not interested in the actual transformation (though that would make an interesting algorithm too!) – JBrouwer Jun 14 '15 at 22:02
1

You can simply "trim" the shapes (remove rows and columns full of 0) and then try the 8 rotations + reflections.

This also gives you another heuristic: after trim the size must be the same or a rotation

  • 1
    This would work, yes, you basically put a shape into one corner as much as possible. This is a good suggestion which would significantly speed this up. – JBrouwer Jun 15 '15 at 14:36
1

Additionally to what @miniBill already wrote: after trimming the shape (or "moving" the shape to the lower left edge inside your m x n matrix), interpret the result as a binary number. Now do the same with the other 7 rotations & reflections, which yields you 8 numbers. Pick the minimum from those 8 values and assign this number to your original matrix, lets call this number the "code number" of the matrix

That way, two matrixes contain the same shape if and only if they have the same code number. This will allow you to work very efficiently with shape sets, for example by utilizing a dictionary or a hashset to store matrixes you alreay have and others you want to test against that set.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.