How to make this algorithm of pattern finding?

Go To StackoverFlow.com

2

I have a matrix and I need to find a pattern inside this matrix. Matrix is:

1 0 0 1 1 1 0 0 0 1
0 0 0 1 1 0 1 0 0 1
0 1 1 1 0 0 0 1 0 1
1 0 1 0 0 1 1 0 1 0
1 1 1 0 0 0 1 1 0 1
0 1 0 0 1 1 0 1 0 1
1 1 1 0 0 0 1 0 0 1
1 0 0 1 0 1 1 1 0 1

Rules:

  1. We choose one number from every row.
  2. The next choosen number from second row must be an opposite of the precedent.
  3. Positions of the numbers choosed by the 1 and 2 rules, must be a precise pattern.

So the question would be:

Find the best pattern that respect the 3 rules. Example from the matrix shown:

  1. Choosed a number: 0(2) //what is in "()" represents the position of the value..position start from 1 to 10 on rows.
  2. 1(4)
  3. For the positions 2 and 4 to be a pattern must support rules 1 and 2 for the rest of the matrix.

So we go further on the 3rd row and we check 2nd position:1. We go 4th row, we check 4th position:0. Seems to respect the rules. There are opposite numbers on 2nd and 4th position, so we continue: 5th row, 2nd position:, and so on, but you will see on 7th row 2nd position:1 and 8th row 4th position:1; so the pattern of positions 2-4 is not good.

How could I make an algorithm based on these rules?

2012-04-04 06:53
by Dany's
You already 'made' the algorithm. I don't understand why you don't just code up your list of instructions in your favourite programming language and get on with it. If you get stuck, or if you think your algorithm is sub-optimal (in some sense) post again with your code and we'll provide some help - High Performance Mark 2012-04-04 07:50


1

Maybe this will help (motivated by the comment to your question). This is a C++ sort of answer. This answer assumes 0 is always the number you pick, but you can easily edit this to allow 1 to be first.

int firstPos, secondPos;

for(int i = 0; i < 10; ++i)
    if(matrix[0][i] == 0)
        firstPos = i;

for(int i = 0; i < 10; ++i)
    if(matrix[0][i] == 1)
        secondPos= i;

bool success = true;

for(int i = 0; i < 10/2; ++i)
    if(matrix[2*i][firstPos] == matrix[2*i][secondPos])
        success == false;

if(success)
    cout << "success" << endl;
else 
    cout << "failure" << endl;
2012-04-04 08:30
by Mike T


0

I would define a pattern by index of the first item (F) and index of the second item (S). I'll also assume that indices begin with 0 (instead of 1 as in your example). Both F and S can take a value between 0 and 9. Solution is simple. Have a double nested loop that runs F and S from 0 to 9, and in third innermost loop just verify that current F and S form a pattern.

2012-04-04 11:21
by Dialecticus
Ads