1
$\begingroup$

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.

The problem

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
                break
        if not found:
            return False
        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.

Unrelated

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.

Parent-child

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.

Overlapping

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.

End note

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 ))

$\endgroup$

1 Answer 1

1
$\begingroup$

Since each pattern brush potentially overwrites previous pixels, I would suggest you work your way backwards. Basically You start checking for which patterns intersected with the "considered pixels" all pixels have the same color. For each of the patterns call the solver recursively with an image where the pattern pixels are removed from "considered pixels".

This will still give you a lot of combinations though. So instead of going through all combinations, you could do an A* search where the number of "considered pixels" is the the distance.

Depending on how tricky and/or redundant the pattern are that may still be a lot of combinations that have to be tested.

$\endgroup$
1
  • $\begingroup$ Thanks for your response! I actually (more or less) solved this problem days ago, and it's my fault for not making an update. I actually came up with the same idea as your first paragraph, but I am not sure how you intend to use A*. I'll make an update on what my solution was. $\endgroup$ Aug 15, 2023 at 1:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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