I made this problem up in my head, and I'm looking for a solution. I realized that it's a very interesting problem, and I'm way too dumb to solve it, so I'm asking for help.
Given a 'desired canvas', which is a grid of colors (let's say an 8 by 8, because it's easy to work with). And given a list of unique 'patterns', where a 'pattern' is grid of booleans with the same size as the 'desired canvas'.
We can define an 'instruction' with a pattern and a color. We can use an instruction to "paint" on a new canvas, where we start with a blank canvas, and we paint the pattern on the canvas, but only on the pixels where the pattern is True. We can do this with every instruction. An 'instruction set' is a list of instructions. The order of the instructions matter, because we can paint over pixels, resulting in a different canvas.
What is the smallest possible instruction set, that reproduces our desired canvas?
We know that, most likely there are more than one of those, but we only care about one, so it doesn't matter which one we get. It just has to be the smallest possible size.
To be always able to reproduce the 'desired canvas' with our patterns, let's say we always have some default patterns, each of them being just a single pixel for every position (for 8x8 that'd be 64).
This problem is easily solvable by just trying every possible combination of instructions, but that would be very slow.
Also, the algorithm has to be only fast for a single pattern group, what I mean by that is that we can parse the patterns into a structured format, and then we can use that format to solve the problem for multiple 'desired canvases' faster. Although, the parsing process shouldn't take too long.
It should work well with a large number of patterns, let's say 1000.
Things I found
Checking if the instruction set is correct by only looking at the patterns
We can check if the instruction set is correct by only looking at the patterns, and not the colors.
In this code I store the patterns and the colors in a list of bitmaps, where each bitmap is a 64 bit integer, and each bit represents a pixel. The first bit is the top left pixel, and the last bit is the bottom right pixel. Each bitmap in the
color_bitmaps represents positions of a different color.
def is_correct(color_bitmaps: list[int], pattern_order: list[int]):
occupied = 0
for pattern in pattern_order[::-1]:
bitmap = pattern & ~occupied
found = False
for color in color_bitmaps:
if color & bitmap == bitmap:
found = True
if not found:
occupied |= bitmap
return occupied == (1 << (64)) - 1
Because of this, it's easy to brute force the problem, because we can just try every possible combination of patterns, and check if it's correct. But this has a complexity of
O(n!) (if not worse), which is very slow.
Relationships between patterns
I found relationships between the patterns, which could make solving the problem easier.
Two patterns are unrelated if there are no intersections. This means that in the instruction set it DOES NOT matter whether these two are before or after one another, because they would result in the same canvas.
A and B patterns are in parent-child relationship if the intersection of A and B equals B. In that case A would be the parent and B would be the child. This means that A should be always before B in the instruction set, because if B is before A then the resulting canvas is the same if B wouldn't be there.
If two patterns have an intersection, and not in a parent-child relationship, they are in a overlapping relationship. This means that in the instruction set it DOES MATTER whether these two are before or after one another, because they would result in a different canvas.
What I tried
I tried brute forcing the problem, but that was too slow. I found some ways to make the range of possible solutions smaller, but still. I also tried to travel through the pattern tree, but it's more of a graph than a tree, because of the overlapping relationships.
I'm looking for a decent algorithm that can solve this problem. Also I thought of machine learning, but I don't know how to apply it to this problem, so if you know how to do that, guidance would be appreciated.
(( i used python for examples just because it's easy to understand, but i'm not limited to python ))