How to make this algorithm of pattern finding?

Question

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:

We choose one number from every row.
The next choosen number from second row must be an opposite of the precedent.
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:

Choosed a number: 0(2) //what is in "()" represents the position of the value..position start from 1 to 10 on rows.
1(4)
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?

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
– High Performance Mark, Commented Apr 4, 2012 at 7:50

Mike T · Accepted Answer · 2012-04-04 08:30:23Z

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;

answered Apr 4, 2012 at 8:30

Mike T

4,7954 gold badges35 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Dialecticus · Accepted Answer · 2012-04-04 11:21:57Z

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.

answered Apr 4, 2012 at 11:21

Dialecticus

16.8k7 gold badges47 silver badges108 bronze badges

Collectives™ on Stack Overflow

How to make this algorithm of pattern finding?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related