debugging - Counting Correct Configurations of a 5*n board (Dynamic Programming, C++) -

the problem follows: write program determines number (modulo m) of white/black patterns on 5*n square grid, not contain of p forbidden patterns.

the input data has following format: first row contains 3 comma separated integers: n - number of columns, p - number of forbidden patterns , m - modulus. following 3*p lines contain 3 character long strings consisting of either . or x, . representing white field , x representing black field. these forbidden patterns, example:

x.. ..x .xx 

this dynamic algorithm solving problem:

let 3 column "block" represented 15 bit long bitset, bits mapping columns follows (1 == black, 0 == white):

0 5 10 1 6 11 2 7 12 3 8 13 4 9 14 

read input data , construct bitsets representing forbidden patterns (unused fields set 0). create vector of bools , under each each index binary representation equal forbidden pattern set value true. same indices represent forbidden patterns bit-shifted left 1 , 2 (because forbidden pattern might start in first, second or third row of column).

now, create 2 vectors of integers, left , right, each size of 1024 (2^10). indices in these vectors represent configurations of 2 column "blocks". in i-th iteration, values in left vector represent how many different correct configurations of board end 2 column pattern represented index of vector in (i-1)-th column. iterate through 32 possibilities 3rd column , add column 2 column pattern, each time checking if such 3 column pattern doesn't contain forbidden pattern. if does, skip next possibility 3rd column, if doesn't take value left vector representing first 2 columns of 3 column pattern , add field of right vector representing 2 column pattern made of 2nd , 3rd columns. after possible 2 columns considered, swap vectors, initialise right vector 0s , repeat process until reach n-th column.

the answer sum of fields left vector (since last operation swaps vectors).

i hope clear, if needs clarification, please leave comment.

my implementation returns correct results when forbidden patterns have @ least 1 x in both top , bottom row, i.e:

x.. ... ..x 

i can't figure out problem is. if in code unclear, please let me know , edit post clarify that.

here implementation: http://pastebin.com/2zpjiyuj

#include <iostream> #include <vector> #include <bitset> #include <stdio.h>  using namespace std;  ostream& operator<< ( ostream& os, const vector<uint32_t>& v ) {   for( auto = v.begin(); != v.end(); it++ )   {     os << *it << "\n";   }   return os; }  inline bitset<15> make_pattern() {   char field;   bitset<15> pattern;    for( uint32_t offset = 0; offset < 3; offset++ )   {     cin >> field;     if( field == 'x' ) pattern.set(offset);      cin >> field;     if( field == 'x' ) pattern.set(offset + 5);      cin >> field;     if( field == 'x' ) pattern.set(offset + 10);   }   return pattern; }  int main() {   uint32_t n, m, p;   cin >> n;   cin >> p;   cin >> m;    vector<bool> forbidden_patterns( 33000 );    for( uint32_t = 0; < p; i++ )   {     auto pattern = make_pattern();     forbidden_patterns[pattern.to_ulong()] = true;  // true := forbidden; false := allowed.     forbidden_patterns[(pattern << 1).to_ulong()] = true;     forbidden_patterns[(pattern << 2).to_ulong()] = true;     //cout << forbidden_patterns[(pattern<<3).to_ulong()];     //cout << pattern.to_ulong();   }    for( uint32_t = 0; i< 33000; i++ ) //checking contents of forbidden_patterns vector   {     bitset<15> bs = i;     if(forbidden_patterns[i] == true)       cout << bs << "\n";   }   cout << "\n\n";    //bitmasks setting 2 rows of 3 column pattern 0;   bitset<15> bottom_rows_reset_mask;   bottom_rows_reset_mask.set(3); bottom_rows_reset_mask.set(8); bottom_rows_reset_mask.set(13);   bottom_rows_reset_mask.set(4); bottom_rows_reset_mask.set(9); bottom_rows_reset_mask.set(14);   bottom_rows_reset_mask = ~bottom_rows_reset_mask;    bitset<15> top_rows_reset_mask;   top_rows_reset_mask.set(0); top_rows_reset_mask.set(5); top_rows_reset_mask.set(10);   top_rows_reset_mask.set(1); top_rows_reset_mask.set(6); top_rows_reset_mask.set(11);   top_rows_reset_mask = ~top_rows_reset_mask;    bitset<15> top_and_bottom_reset_mask;   top_and_bottom_reset_mask.set(0); top_and_bottom_reset_mask.set(5); top_and_bottom_reset_mask.set(10);   top_and_bottom_reset_mask.set(4); top_and_bottom_reset_mask.set(9); top_and_bottom_reset_mask.set(14);   top_and_bottom_reset_mask = ~top_and_bottom_reset_mask;    vector<uint32_t> left( 1024, 1 );   vector<uint32_t> right( 1024, 0 );    for( uint32_t column = 3; column <= n; column++ )   {     for( uint32_t first_2_columns = 0; first_2_columns < 1024; first_2_columns++ )     {       if( left[first_2_columns] == 0 ) continue;       for( uint32_t third_column = 0; third_column < 32; third_column++ )       {         bitset<15> t_patt = (first_2_columns | third_column << 10) & top_and_bottom_reset_mask.to_ulong();         //cout << t_patt << "\n"; //getchar();         if( forbidden_patterns[t_patt.to_ulong()] == true )         {           //cout << t_patt << "\n"; getchar();           continue;         }          t_patt = (first_2_columns | third_column << 10) & bottom_rows_reset_mask.to_ulong();         //cout << t_patt << "\n"; //getchar();         if( forbidden_patterns[t_patt.to_ulong()] == true )         {           //cout << t_patt << "\n"; getchar();           continue;         }          t_patt = (first_2_columns | third_column << 10) & top_rows_reset_mask.to_ulong();         //cout << t_patt << "\n"; //getchar();         if( forbidden_patterns[t_patt.to_ulong()] == true )         {           //cout << t_patt << "\n"; getchar();           continue;         }          t_patt = first_2_columns | third_column << 10;         //cout << t_patt << "\n";         auto next_2_column_pattern = (t_patt >> 5).to_ulong();         //t_patt = next_2_column_pattern; cout << t_patt << "\n"; getchar();         right[next_2_column_pattern] = (right[next_2_column_pattern] + left[first_2_columns]) % m;       }     }     left.swap(right);     right.assign(1024, 0u);   }   uint32_t sum = 0;   for( int = 0; < 1024; i++ )     sum = (sum + left[i]) % m;    cout << sum; } 

i've managed fix problem myself (though paulmckenzie deserves big thank sending me in right direction).

the problem algorithm did not distinguish between forbidden patterns shifted 0, 1 or 2 bits left. when input data had patterns containing @ least 1 x in bottom , top rows fine, once pattern .'s in top or bottom row given, program began misbehave.

consider forbidden pattern without x's in top row - after shifting 1 bit left, top 2 rows of pattern become zeroed. 1 of innermost loop's ifs in program sets top 2 rows of pattern being tested zeroes , compares what's left against forbidden_patterns vector, can possibly matched 1 of patterns without x's in top row shifted 1 bit left! logically faulty because forbidden pattern has been shifted 1 bit left starts in 2nd row, whereas pattern top 2 rows zeroed can contain forbidden pattern starting in 3rd row. caused program enter innermost loop's ifs more should, "under-counting" correct configurations.

the solution simple - split forbidden_patterns vector 3 vectors - 1 containing patterns without shift, 1 containing patterns shifted 1 left , 3rd containing patterns shifted 2 left. appropriate vector used in innermost loop's ifs.

fixed code: http://pastebin.com/wcb8eb9f

#include <iostream> #include <vector> #include <bitset> #include <stdio.h>  using namespace std;  inline bitset<15> make_pattern() {   char field;   bitset<15> pattern;    for( uint32_t offset = 0; offset < 3; offset++ )   {     cin >> field;     if( field == 'x' ) pattern.set(offset);      cin >> field;     if( field == 'x' ) pattern.set(offset + 5);      cin >> field;     if( field == 'x' ) pattern.set(offset + 10);   }   return pattern; }  int main() {   uint32_t n, m, p;   cin >> n;   cin >> p;   cin >> m;    vector<bool> top_forbidden_patterns( 32768 ); // top_forbidden patterns can compared 3 column patterns have top 2 rows zeroed.   vector<bool> mid_forbidden_patterns( 32768 ); // mid_forbidden patterns can compared 3 column patterns have top , bottom row zeroed.   vector<bool> bottom_forbidden_patterns( 32768 ); // bottom_forbidden patterns can compared 3 column patterns have bottom 2 rows zeroed.    for( uint32_t = 0; < p; i++ )   {     auto pattern = make_pattern();     bottom_forbidden_patterns[pattern.to_ulong()] = true;  // true := forbidden; false := allowed.     mid_forbidden_patterns[(pattern << 1).to_ulong()] = true;     top_forbidden_patterns[(pattern << 2).to_ulong()] = true;   }    //bitmasks setting 2 rows of 3 column pattern 0;   bitset<15> bottom_rows_reset_mask;   bottom_rows_reset_mask.set(3); bottom_rows_reset_mask.set(8); bottom_rows_reset_mask.set(13);   bottom_rows_reset_mask.set(4); bottom_rows_reset_mask.set(9); bottom_rows_reset_mask.set(14);   bottom_rows_reset_mask = ~bottom_rows_reset_mask;    bitset<15> top_rows_reset_mask;   top_rows_reset_mask.set(0); top_rows_reset_mask.set(5); top_rows_reset_mask.set(10);   top_rows_reset_mask.set(1); top_rows_reset_mask.set(6); top_rows_reset_mask.set(11);   top_rows_reset_mask = ~top_rows_reset_mask;    bitset<15> top_and_bottom_reset_mask;   top_and_bottom_reset_mask.set(0); top_and_bottom_reset_mask.set(5); top_and_bottom_reset_mask.set(10);   top_and_bottom_reset_mask.set(4); top_and_bottom_reset_mask.set(9); top_and_bottom_reset_mask.set(14);   top_and_bottom_reset_mask = ~top_and_bottom_reset_mask;    vector<uint32_t> left( 1024, 1 );   vector<uint32_t> right( 1024, 0 );    for( uint32_t column = 3; column <= n; column++ )   {     for( uint32_t first_2_columns = 0; first_2_columns < 1024; first_2_columns++ )     {       if( left[first_2_columns] == 0 ) continue;       for( uint32_t third_column = 0; third_column < 32; third_column++ )       {         bitset<15> t_patt = (first_2_columns | third_column << 10) & top_and_bottom_reset_mask.to_ulong();         if( mid_forbidden_patterns[t_patt.to_ulong()] == true )           continue;          t_patt = (first_2_columns | third_column << 10) & bottom_rows_reset_mask.to_ulong();         if( bottom_forbidden_patterns[t_patt.to_ulong()] == true )           continue;          t_patt = (first_2_columns | third_column << 10) & top_rows_reset_mask.to_ulong();         if( top_forbidden_patterns[t_patt.to_ulong()] == true )           continue;          t_patt = first_2_columns | third_column << 10;         auto next_2_column_pattern = (t_patt >> 5).to_ulong();         right[next_2_column_pattern] = (right[next_2_column_pattern] + left[first_2_columns]) % m;       }     }     left.swap(right);     right.assign(1024, 0u);   }   uint32_t sum = 0;   for( auto el : left )     sum = (sum + el) % m;    cout << sum;   return 0; }