fork(1) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. template <typename T>
  6. class matrix {
  7. public:
  8.  
  9. 	size_t cols;
  10. 	size_t rows;
  11.  
  12. private:
  13.  
  14. 	std::vector<T> data;
  15.  
  16. public:
  17.  
  18. 	matrix() : cols(0), rows(0) {
  19.  
  20. 	}
  21. 	matrix(const size_t cols, const size_t rows) : cols(cols), rows(rows) {
  22. 		data = std::vector<T>(cols * rows);
  23. 	}
  24. 	matrix(const size_t cols, const size_t rows, const T val) : cols(cols), rows(rows) {
  25. 		data = std::vector<T>(cols * rows, val);
  26. 	}
  27.  
  28. 	T& operator()(const size_t col, const size_t row) {
  29. 		return data[col * rows + row];
  30. 	}
  31.  
  32. 	const T& operator()(const size_t col, const size_t row) const {
  33. 		return data[col * rows + row];
  34. 	}
  35.  
  36. 	matrix<T> rotate() const {
  37. 		matrix<T> new_mat;
  38.  
  39. 		new_mat = matrix(rows, cols);
  40. 		for (size_t col = 0; col < new_mat.cols; col++) {
  41. 			for (size_t row = 0; row < new_mat.rows; row++) {
  42. 				new_mat(col, row) = operator()(row, (rows - 1) - col);
  43. 			}
  44. 		}
  45.  
  46. 		return new_mat;
  47. 	}
  48.  
  49. 	matrix<T> copy(const size_t c_col, const size_t c_row, size_t c_cols, size_t c_rows) const {
  50.  
  51. 		if (c_col + c_cols > cols - 1) {
  52. 			c_cols = cols - c_col;
  53. 		}
  54. 		if (c_row + c_rows > rows - 1) {
  55. 			c_rows = rows - c_row;
  56. 		}
  57.  
  58. 		matrix<T> new_mat = matrix(c_cols, c_rows);
  59.  
  60. 		for (size_t col = 0; col < c_cols; col++) {
  61. 			for (size_t row = 0; row < c_rows; row++) {
  62. 				//std::cout << "(" << c_col + col << ", " << c_row + row << ") --> (" << col << ", " << row << ")" << std::endl;
  63. 				new_mat(col, row) = operator()(c_col + col, c_row + row);
  64. 				//std::cout << "(" << col << ", " << row << ") = " << i << std::endl;
  65.  
  66. 			}
  67. 		}
  68.  
  69. 		return new_mat;
  70. 	}
  71.  
  72. 	// You should change this to use a predicate to decide whether or not a value should be cropped.
  73. 	matrix<T> crop(const T empty_val) const {
  74.  
  75. 		matrix<T> new_mat = *this;
  76. 		// Use rotation to help crop!
  77.  
  78. 		int i = 4;
  79. 		while (i --> 0) {
  80. 			bool do_break = false;
  81. 			for (size_t col = 0; col < new_mat.cols; col++) {
  82. 				if (do_break) {
  83. 					break;
  84. 				}
  85.  
  86. 				for (size_t row = 0; row < new_mat.rows; row++) {
  87. 					if (new_mat(col, row) != empty_val) {
  88. 						new_mat = new_mat.copy(col, 0, new_mat.cols - col, new_mat.rows).rotate();
  89. 						do_break = true;
  90. 						break;
  91. 					}
  92. 				}
  93. 			}
  94. 		}
  95. 		return new_mat;
  96. 	}
  97.  
  98. 	// You have to go first by rows and then by columns since printing is sort of "row major".
  99. 	void print() const {
  100. 		for (size_t row = 0; row < rows; row++) {
  101. 			for (size_t col = 0; col < cols; col++) {
  102. 				std::cout << this->operator()(col, row) << ' ';
  103. 			}
  104. 			std::cout << std::endl;
  105. 		}
  106.  
  107. 		std::cout << std::endl;
  108. 	}
  109. };
  110.  
  111. int main() {
  112.  
  113. 	std::vector<std::string> words = { "colorful", "dividend", "fourteen", "alsatian" };
  114.  
  115. 	size_t side_size = 28;
  116.  
  117. 	matrix<char> empty_mat(side_size, side_size, ' ');
  118. 	matrix<char> best_mat(side_size, side_size, ' ');
  119.  
  120. 	// Try each possible sequence of words. For each word that you try, try every possible place that word can fit.
  121. 	std::sort(words.begin(), words.end());
  122. 	do {
  123. 		matrix<char> mat(empty_mat);
  124. 		for (std::string s : words) {
  125. 			size_t this_col = 0;
  126. 			size_t this_row = 0;
  127.  
  128. 			bool good = true;
  129. 			bool do_break = false;
  130.  
  131. 			int r = 4;
  132. 			while (r--> 0) {
  133. 				if (do_break == true) break;
  134.  
  135. 				// Rotate the matrix ninety degrees each time and only deal with the forward horizontal case.
  136. 				mat = mat.rotate();
  137.  
  138. 				// Find a place to try the word.
  139. 				for (size_t i = 0; i < s.size(); i++) {
  140. 					char& c = s[i];
  141. 					if (do_break == true) break;
  142. 					for (size_t col = 0; col < mat.cols; col++) {
  143. 						if (do_break == true) break;
  144. 						for (size_t row = 0; row < mat.rows; row++) {
  145. 							good = false;
  146. 							if (mat(col, row) == c) {
  147. 								good = true;
  148. 								// Make sure that the word isn't colliding with anything already there.
  149. 								for (size_t k = col - i; k < col - i + s.size(); k++) {
  150. 									for (size_t q = row - 1; q <= row + 1; q++) {
  151. 										if (q == 0) {
  152. 											if ((mat(k, row) != ' ') && (mat(k, row) != s[(k) - (col - i)])) {
  153. 												good = false;
  154. 												break;
  155. 											}
  156. 										}
  157. 										else if (k != col) {
  158. 											if (mat(k, q) != ' ') {
  159. 												good = false;
  160. 												break;
  161. 											}
  162. 										}
  163. 									}
  164. 								}
  165. 							}
  166. 							if (good) {
  167. 								this_col = col - i;
  168. 								this_row = row;
  169.  
  170. 								do_break = true;
  171. 								break;
  172. 							}
  173. 						}
  174. 					}
  175. 				}
  176. 			}
  177.  
  178. 			if (this_col == 0 && this_row == 0) {
  179. 				this_col = side_size / 2;
  180. 				this_row = side_size / 2;
  181. 			}
  182.  
  183. 			for (char c : s) {
  184. 				mat(this_col++, this_row) = c;
  185. 			}
  186. 		}
  187.  
  188. //		for (std::string s : words) {
  189. //			std::cout << s << ' ';
  190. //		}
  191. 		std::cout << std::endl;
  192.  
  193. 		mat.crop(' ').print();
  194.  
  195. 	} while (std::next_permutation(words.begin(), words.end()));
  196.  
  197. 	return 0;
  198. }
  199.  
Success #stdin #stdout 0s 3420KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
  l               
  u               
  f o u r t e e n 
  r               
  o       d       
a l s a t i a n   
  o       v       
  c       i       
          d       
          e       
          n       
          d       


          n             
          a             
        d i v i d e n d 
          t             
          a             
          s             
l u f r o l o c         
    o     a             
    u                   
    r                   
    t                   
    e                   
    e                   
    n                   


          d       
          n       
          e       
          d       
  c       i       
  o       v       
a l s a t i a n   
  o       d       
  r               
  f o u r t e e n 
  u               
  l               


    f             
  c o l o r f u l 
    u             
    r       n     
    t       a     
d n e d i v i d   
    e       t     
    n       a     
            s     
            l     
            a     


d i v i d e n d       
            a         
            i     c   
      n e e t r u o f 
            a     l   
            s     o   
            l     r   
            a     f   
                  u   
                  l   


        n             
    d n e d i v i d   
        e             
a l s a t i a n       
        r             
        u             
      c o l o r f u l 
        f             


            l               
            u               
            f o u r t e e n 
            r               
    d       o               
n a i t a s l a             
    v       o               
    i       c               
    d                       
    e                       
    n                       
    d                       


                l   
          f     u   
          o     f   
          u     r   
          r     o   
    n a i t a s l a 
          e     o   
d i v i d e n d c   
          n         


              a   
              l   
              s   
              a   
              t   
  d n e d i v i d 
              a   
f o u r t e e n   


              f           
              o           
              u           
              r           
              t           
          d n e d i v i d 
              e           
a l s a t i a n           


            a         
            l         
            s       l 
            a       u 
      n e e t r u o f 
            i       r 
            a       o 
d i v i d e n d     l 
                    o 
                    c 


    d                       
    i                       
    v                       
    i       a l s a t i a n 
    d         u             
n e e t r u o f             
    n         r             
    d         o             
              l             
              o             
              c             


    d                       
    n                       
    e                       
    d                       
    i       c               
    v       o               
n a i t a s l a             
    d       o               
            r               
            f o u r t e e n 
            u               
            l               


            f               
            o   d           
c o l o r f u l n           
            r   e           
            t   d           
            e   i           
            e   v           
            n a i t a s l a 
                d           


          a       
l u f r o l o c   
          s       
          a       
  f o u r t e e n 
          i       
          a       
          n       


    l u f r o l o c 
        o           
        u           
        r           
a l s a t i a n     
        e           
        e           
        n           


    a               
c o l o r f u l     
    s               
    a               
    t               
    i   d           
    a   n           
    n e e t r u o f 
        d           
        i           
        v           
        i           
        d           


    d                     
    n       c             
n e e t r u o f           
    d       l             
    i       o             
    v       r             
    i       f             
    d       u             
          a l s a t i a n 


          n         
d i v i d e n d c   
          e     o   
    n a i t a s l a 
          r     o   
          u     r   
          o     f   
          f     u   
                l   


d                   
i                   
v                   
i     n             
d     e             
e     e             
n a i t a s l a     
d     r             
      u             
    c o l o r f u l 
      f             


              n   
              e   
              e   
              t   
              r   
  a           u   
  l u f r o l o c 
  s           f   
  a               
  t               
d i v i d e n d   
  a               
  n               


        f             
      c o l o r f u l 
        u             
        r             
a l s a t i a n       
        e             
    d n e d i v i d   
        n             


            a     
            l     
            s     
    n       a     
    e       t     
d n e d i v i d   
    t       a     
    r       n     
    u             
  c o l o r f u l 
    f             


              f     
  l u f r o l o c   
              u     
              r     
              t     
    d i v i d e n d 
              e     
a l s a t i a n
https://ideone.com/SRmrEW
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!