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.
