Number of possible boards without predefined templates
I am trying to come up with some kind of dynamic algorithm to solve the given problem:
We have a board with 5 rows and columns n
. Each field can be colored black or white (1 or 0).
Someone gave us up to 5 templates. The size of each picture is 3x3. For example. this could be a pattern:
...
.x. // We got 1 black field in the middle
...
Our task is to provide several colors of all possible boards that do not even contain one kind of any template .
My initial idea was to scan the entire board with window
a 5x2 size (5 rows and 2 columns), but I can't see any way to get it right.
source to share
I think your idea is correct and scanning with a 5x2 window is the correct approach.
I think the key is to keep track of the count for each content value of the last two columns. The score represents the total number of boards that end with these two columns.
There are 2 ^ (5 * 2) = 1024 content choices for these two columns.
Start by setting a quantity for each of these options: 1.
Then, for each new column, try all the ways to color it and check which ones are legal.
You can then compute an updated sample list for the window at the next position across.
When you're done scanning, you can simply add all the final counts to get the total number of positions.
OPTIMIZATION
For each new column, we will always find the same set of legal templates, so you can simply execute them once and then save the resulting list of positions to update.
In fact, updating is exactly equivalent to matrix multiplication, so you can use a fast exponential expression to compute a value for a very large n. (It's probably not worth it if n is only up to 3000, since the matrix will be large.)
WORKING EXAMPLE
Consider a simpler problem where we have 2 rows and n columns and are trying to count the number of ways to paint a board without a pattern with two horizontally adjacent 1. For this problem, we can use the same approach with only a 2 by 1 window.
There are 4 starting templates, each with a starting score of 1:
0 0 1 1
0 1 0 1
For each of these, we'll go over all the ways to add to the next column
eg. for column 1,0 consider:
10 00
this does not contain a template, so we add 1 to the output of 0,0.
10 01
this does not contain a template, so we add 1 to the output of 0.1.
11 00
this contains the template, so we continue.
11 01
this contains the template, so we continue.
So we found 0.1 adds a score from 1 to 0.0 and 1.0. Similarly, 1.0 adds an amount between 1 and 0.0 and 0.1. 1.1 adds an amount from 1 to 0.0 0.0 adds an amount from 1 to 0.0 and 0.1 and 1.0 and 1.1
So, in general, after one step, we have the following values:
0 count of 4
0
0 count of 2
1
1 count of 2
0
1 count of 1
1
So if n is 2, we add all these numbers to find 4 + 2 + 2 + 1 = 9 possible ways to color the board 2 by 2 without adjacent ones.
source to share