Nonoblock: Difference between revisions

Content added Content deleted

Inline

@@ Line 59: / Line 59: @@
 ;Reference:
 * The blog post [http://paddy3118.blogspot.co.uk/2014/03/nonogram-puzzle-solver-part-1.html Nonogram puzzle solver (part 1)] Inspired this task and donated its [[Nonoblock#Python]] solution.
+=={{header|C++}}==
+<lang cpp>
+#include <iomanip>
+#include <iostream>
+#include <algorithm>
+#include <numeric>
+#include <string>
+#include <vector>
+typedef std::pair<int, std::vector<int> > puzzle;
+class nonoblock {
+public:
+    void solve( std::vector<puzzle>& p ) {
+        for( std::vector<puzzle>::iterator i = p.begin(); i != p.end(); i++ ) {
+            counter = 0;
+            std::cout << " Puzzle: " << ( *i ).first << " cells and blocks [ ";
+            for( std::vector<int>::iterator it = ( *i ).second.begin(); it != ( *i ).second.end(); it++ )
+                std::cout << *it << " ";
+            std::cout << "] ";
+            int s = std::accumulate( ( *i ).second.begin(), ( *i ).second.end(), 0 ) + ( ( *i ).second.size() > 0 ? ( *i ).second.size() - 1 : 0 );
+            if( ( *i ).first - s < 0 ) {
+                std::cout << "has no solution!\n\n\n";
+                continue;
+            }
+            std::cout << "\n Possible configurations:\n\n";
+            std::string b( ( *i ).first, '-' );
+            solve( *i, b, 0 );
+            std::cout << "\n\n";
+        }
+    }
+private:
+    void solve( puzzle p, std::string n, int start ) {
+        if( p.second.size() < 1 ) {
+            output( n );
+            return;
+        }
+        std::string temp_string;
+        int offset,
+            this_block_size = p.second[0];
+        int space_need_for_others = std::accumulate( p.second.begin() + 1, p.second.end(), 0 );
+        space_need_for_others += p.second.size() - 1;
+        int space_for_curr_block = p.first - space_need_for_others - std::accumulate( p.second.begin(), p.second.begin(), 0 );
+        std::vector<int> v1( p.second.size() - 1 );
+        std::copy( p.second.begin() + 1, p.second.end(), v1.begin() );
+        puzzle p1 = std::make_pair( space_need_for_others, v1 );
+        for( int a = 0; a < space_for_curr_block; a++ ) {
+            temp_string = n;
+            if( start + this_block_size > n.length() ) return;
+            for( offset = start; offset < start + this_block_size; offset++ )
+                temp_string.at( offset ) = 'o';
+            if( p1.first ) solve( p1, temp_string, offset + 1 );
+            else output( temp_string );
+            start++;
+        }
+    }
+    void output( std::string s ) {
+        char b = 65 - ( s.at( 0 ) == '-' ? 1 : 0 );
+        bool f = false;
+        std::cout << std::setw( 3 ) << ++counter << "\t|";
+        for( std::string::iterator i = s.begin(); i != s.end(); i++ ) {
+            b += ( *i ) == 'o' && f ? 1 : 0;
+            std::cout << ( ( *i ) == 'o' ? b : '_' ) << "|";
+            f = ( *i ) == '-' ? true : false;
+        }
+        std::cout << "\n";
+    }
+    unsigned counter;
+};
+int main( int argc, char* argv[] )
+{
+    std::vector<puzzle> problems;
+    std::vector<int> blocks;
+    blocks.push_back( 2 ); blocks.push_back( 1 );
+    problems.push_back( std::make_pair( 5, blocks ) );
+    blocks.clear();
+    problems.push_back( std::make_pair( 5, blocks ) );
+    blocks.push_back( 8 );
+    problems.push_back( std::make_pair( 10, blocks ) );
+    blocks.clear();
+    blocks.push_back( 2 ); blocks.push_back( 3 );
+    problems.push_back( std::make_pair( 5, blocks ) );
+    blocks.push_back( 2 ); blocks.push_back( 3 );
+    problems.push_back( std::make_pair( 15, blocks ) );
+    nonoblock nn;
+    nn.solve( problems );
+    return 0;
+}
+</lang>
+{{out}}
+<pre>
+ Puzzle: 5 cells and blocks [ 2 1 ]
+ Possible configurations:
+|A|A|_|B|_|
+|A|A|_|_|B|
+|_|A|A|_|B|
+ Puzzle: 5 cells and blocks [ ]
+ Possible configurations:
+|_|_|_|_|_|
+ Puzzle: 10 cells and blocks [ 8 ]
+ Possible configurations:
+|A|A|A|A|A|A|A|A|_|_|
+|_|A|A|A|A|A|A|A|A|_|
+|_|_|A|A|A|A|A|A|A|A|
+ Puzzle: 5 cells and blocks [ 2 3 ] has no solution!
+ Puzzle: 15 cells and blocks [ 2 3 2 3 ]
+ Possible configurations:
+|A|A|_|B|B|B|_|C|C|_|D|D|D|_|_|
+|A|A|_|B|B|B|_|C|C|_|_|D|D|D|_|
+|A|A|_|B|B|B|_|C|C|_|_|_|D|D|D|
+|A|A|_|B|B|B|_|_|C|C|_|D|D|D|_|
+|A|A|_|B|B|B|_|_|C|C|_|_|D|D|D|
+|A|A|_|B|B|B|_|_|_|C|C|_|D|D|D|
+|A|A|_|_|B|B|B|_|C|C|_|D|D|D|_|
+|A|A|_|_|B|B|B|_|C|C|_|_|D|D|D|
+|A|A|_|_|B|B|B|_|_|C|C|_|D|D|D|
+|A|A|_|_|_|B|B|B|_|C|C|_|D|D|D|
+|_|A|A|_|B|B|B|_|C|C|_|D|D|D|_|
+|_|A|A|_|B|B|B|_|C|C|_|_|D|D|D|
+|_|A|A|_|B|B|B|_|_|C|C|_|D|D|D|
+|_|A|A|_|_|B|B|B|_|C|C|_|D|D|D|
+|_|_|A|A|_|B|B|B|_|C|C|_|D|D|D|
+</pre>
 =={{header|D}}==