fork(2) download
copy 
  1. #include <iostream>
  2. #include <sstream>
  3. #define show(variable) std::cout << #variable << " = " << variable << std::endl; 
  4.  
  5. // 	The Knight, from its starting position onwards, can only move forward in the 4 ways, as defined by the Knight move in chess.
  6.  
  7. const int WIDTH = 8, LENGTH = 12, START_X = 4, START_Y = 0;
  8. const bool showDetails = false;
  9.  
  10. class ChessBoard {
  11. private:
  12. 	class Node {
  13. 		private:
  14. 			ChessBoard& chessBoard;  // reference data member because a ChessBoard::Node always belongs to a ChessBoard
  15. 			int value, x, y;
  16. 			Node *child1, *child2, *child3, *child4, *parent1, *parent2, *parent3, *parent4;
  17. 			friend class ChessBoard;
  18. 			Node (ChessBoard& cb, int X, int Y): chessBoard (cb), x (X), y (Y) {  // Many private functions, including the constructor.
  19. 				chessBoard.nodesFound[x][y] = this;  // Storing this new Node into nodesFound.
  20. 				child1 = child2 = child3 = child4 = NULL;  // Initializing temporarily for use in updateValue() for a new Node (else the program will crash).  The children will be established right after.
  21. 				establishParents();
  22. 				updateValue();
  23. 				if (showDetails) {std::cout << "chessBoard.nodesFound["<<x<<"]["<<y<<"] officially created." << std::endl;  std::cout << "chessBoard.nodesFound["<<x<<"]["<<y<<"]: " << chessBoard.nodesFound[x][y] << std::endl;}
  24. 				createChildren();  // Node constructor called recursively within.
  25. 			}
  26. 			~Node () {   // Running the destructor will cause a crash because inevitably a Node already deleted will attempt to be deleted again
  27. 				//std::cout << "[Node destructor called]" << std::endl;  delete leftChild; delete rightChild; delete leftParent;  delete rightParent; 
  28. 			}
  29. 			void establishParents () {
  30. 				parent1 = parent2 = parent3 = parent4 = NULL;  // Some of these NULL values will be overridden below.
  31. 				if ( (y >= 1 && x >= 2) && (chessBoard.nodesFound[x-2][y-1]) )
  32. 				{
  33. 					if (showDetails) std::cout << "chessBoard.nodesFound["<<x-2<<"]["<<y-1<<"]: " << chessBoard.nodesFound[x-2][y-1] << std::endl;
  34. 					parent1 = chessBoard.nodesFound[x-2][y-1];
  35. 					parent1->child4 = this;  
  36. 				}
  37. 				if ( (y >= 1 && x <= chessBoard.dimension_x - 3) && (chessBoard.nodesFound[x+2][y-1]) )
  38. 				{
  39. 					if (showDetails) std::cout << "chessBoard.nodesFound["<<x+2<<"]["<<y-1<<"]: " << chessBoard.nodesFound[x+2][y-1] << std::endl;
  40. 					parent4 = chessBoard.nodesFound[x+2][y-1];
  41. 					parent4->child1 = this;  
  42. 				}
  43. 				if ( (y >= 2 && x >= 1) && (chessBoard.nodesFound[x-1][y-2]) )
  44. 				{
  45. 					if (showDetails) std::cout << "chessBoard.nodesFound["<<x-1<<"]["<<y-2<<"]: " << chessBoard.nodesFound[x-1][y-2] << std::endl;
  46. 					parent2 = chessBoard.nodesFound[x-1][y-2];
  47. 					parent2->child3 = this;  
  48. 				}
  49. 				if ( (y >= 2 && x <= chessBoard.dimension_x - 2) && (chessBoard.nodesFound[x+1][y-2]) )
  50. 				{
  51. 					if (showDetails) std::cout << "chessBoard.nodesFound["<<x+1<<"]["<<y-2<<"]: " << chessBoard.nodesFound[x+1][y-2] << std::endl;
  52. 					parent3 = chessBoard.nodesFound[x+1][y-2];
  53. 					parent3->child2 = this;  
  54. 				}
  55. 			}
  56. 			void updateValue () {
  57. 				if (x == chessBoard.start_x && y == chessBoard.start_y)
  58. 				{
  59. 					value = 1;
  60. 					chessBoard.nodesFound[x][y] = this; 
  61. 				}
  62. 				else 
  63. 				{
  64. 					value = 0;
  65. 					if (parent1)
  66. 					{
  67. 				 		value += parent1->value;
  68. 				 		if (showDetails) {std::cout << x << y << " has parent1" <<  std::endl; show (parent1);  show (parent1->value);}
  69. 				 	}
  70. 				 	if (parent2)
  71. 					{
  72. 						value += parent2->value;
  73. 					 	if (showDetails) {std::cout << x << y  << " has parent2" <<  std::endl; show (parent2);  show (parent2->value);}
  74. 					}
  75. 					if (parent3)
  76. 					{
  77. 				 		value += parent3->value;
  78. 				 		if (showDetails) {std::cout << x << y << " has parent3" <<  std::endl; show (parent3);  show (parent3->value);}
  79. 				 	}
  80. 				 	if (parent4)
  81. 					{
  82. 						value += parent4->value;
  83. 					 	if (showDetails) {std::cout << x << y  << " has parent4" <<  std::endl; show (parent4);  show (parent4->value);}
  84. 					}
  85. 					if (showDetails) std::cout << x << y << " value = " << value << std::endl;
  86. 				}
  87. 				if (child1)  // Vital to update the values of all children, because changes this Node's value will affect their values too!
  88. 					child1->updateValue();
  89. 				if (child2)
  90. 					child2->updateValue();
  91. 				if (child3)
  92. 					child3->updateValue();
  93. 				if (child4)
  94. 					child4->updateValue();
  95. 			}
  96. 			void checkChild1 () {
  97. 				if (chessBoard.nodesFound[x-2][y+1])
  98. 				{
  99. 					if (showDetails) std::cout << x-2 << y+1 << " found.  Applying changes to it." << std::endl;
  100. 					chessBoard.nodesFound[x-2][y+1]->applyChanges();
  101. 				}
  102. 				else 
  103. 				{
  104. 					if (showDetails) std::cout << "Creating " << x-2 << y+1 << std::endl;
  105. 					child1 = new Node (chessBoard, x - 2, y + 1);
  106. 				}
  107. 			}
  108. 			void checkChild2 () {
  109. 				if (chessBoard.nodesFound[x-1][y+2])
  110. 				{
  111. 					if (showDetails) std::cout << x-1 << y+2 << " found.  Applying changes to it." << std::endl;
  112. 					chessBoard.nodesFound[x-1][y+2]->applyChanges();
  113. 				}
  114. 				else
  115. 				{
  116. 					if (showDetails) std::cout << "Creating " << x-1 << y+2 << std::endl;
  117. 					child2 = new Node (chessBoard, x - 1, y + 2);
  118. 				}
  119. 			}
  120. 			void checkChild3 () {
  121. 				if (chessBoard.nodesFound[x+1][y+2])
  122. 				{
  123. 					if (showDetails) std::cout << x+1 << y+2 << " found.  Applying changes to it." << std::endl;
  124. 					chessBoard.nodesFound[x+1][y+2]->applyChanges();
  125. 				}
  126. 				else
  127. 				{
  128. 					if (showDetails) std::cout << "Creating " << x+1 << y+2 << std::endl;
  129. 					child3 = new Node (chessBoard, x + 1, y + 2);
  130. 				}
  131. 			}
  132. 			void checkChild4 () {
  133. 				if (chessBoard.nodesFound[x+2][y+1])
  134. 				{
  135. 					if (showDetails) std::cout << x+2 << y+1 << " found.  Applying changes to it." << std::endl;
  136. 					chessBoard.nodesFound[x+2][y+1]->applyChanges();
  137. 				}
  138. 				else
  139. 				{
  140. 					if (showDetails) std::cout << "Creating " << x+2 << y+1 << std::endl;
  141. 					child4 = new Node (chessBoard, x + 2, y + 1);
  142. 				}
  143. 			}			
  144. 			void createChildren () {  
  145. 				if ( (x >= 2) && (y <= chessBoard.dimension_y - 2) )	
  146. 					checkChild1();
  147. 				if ( (x >= 1) && (y <= chessBoard.dimension_y - 3) )
  148. 					checkChild2();
  149. 				if ( (x <= chessBoard.dimension_x - 2) && (y <= chessBoard.dimension_y - 3) )
  150. 					checkChild3();
  151. 				if ( (x <= chessBoard.dimension_x - 3) && (y <= chessBoard.dimension_y - 2) )
  152. 					checkChild4();		
  153. 				if (showDetails) std::cout << "Value at " << x << y << " = " << value << std::endl;
  154. 			}
  155. 			void applyChanges () {
  156. 				establishParents();
  157. 				updateValue();
  158. 				createChildren();
  159. 			}
  160. 		public:
  161. 			int Value () const {return value;}
  162. 	};
  163. public:
  164. 	ChessBoard (int X, int Y, int startX, int startY): dimension_x (X), dimension_y (Y), start_x (startX), start_y (startY) {  // Private constructor of ChessBoard::Node callable because ChessBoard is declared friend of RectangularPrism::Node. 
  165. 		nodesFound = new Node**[dimension_x + 1];  // This is also how a multi-dimensional array is returned from a function in C++ (i.e. do all this, and then return nodesFound).
  166. 		for (int i = 0; i < dimension_x; i++)
  167. 		{
  168. 			nodesFound[i] = new Node*[dimension_y + 1];
  169. 			for (int j = 0; j < dimension_y; j++)
  170. 				nodesFound[i][j] = NULL;
  171. 		}
  172. 		startingPoint = new Node (*this, start_x, start_y);  // Placing this line before the nodesFound construction above will cause a crash because the Node constructor uses nodesFound.
  173. 	}
  174. //	~ChessBoard () { 
  175. //		std::cout << std::endl << "[ChessBoard destructor called]" << std::endl;
  176. //		delete startingPoint;
  177. //		for (int i = 0; i < dimension_x; i++)
  178. //		{
  179. //			for (int j = 0; j < dimension_y; j++)
  180. //				delete[] nodesFound[i][j];
  181. //			delete[] nodesFound[i];
  182. //		}
  183. //		delete[] nodesFound;
  184. //	}
  185. 	Node*** NodesFound () const {return nodesFound;}
  186. 	int Dimension_x() const {return dimension_x;}
  187. 	int Dimension_y() const {return dimension_y;}
  188. private:
  189. 	const int dimension_x, dimension_y, start_x, start_y;
  190. 	Node *startingPoint;
  191. 	Node ***nodesFound;  /* This 2-dimensional array of Node*'s is to search all Nodes found so that the latest constructed Node with the same coordinates as some Node already found 
  192. 	would be made equal to that Node.  An std::map<std::tuple<int, int, int>, void*> could instead be used where the key are the co-ordinates and the values the Nodes, so then map::find would 
  193. 	binary search for the coordinates in logarithmic time, but a simple multi-dimensional array (or vector) can use its random access iterator to find the Node in constant time, the drawback
  194. 	being a lot of unused allocated space when the dimensions are large, but since this program is a stand-alone that should be fine. */
  195. };
  196.  
  197. template <typename T> 
  198. const std::string toString (T t) {
  199.     std::ostringstream os;
  200.     os << t;
  201.     return os.str();
  202. }
  203.  
  204. std::string bigNumberWithCommas (const unsigned long long n) {  // Note:  No comma for a 4-digit number
  205. 	std::string numStr = toString (n);
  206. 	if (numStr.length () <= 4)
  207.         return numStr;
  208. 	size_t pos = numStr.length () % 3;  // position of the first comma to insert
  209.     if (pos == 0)  // e.g. the number 142789, having 6 digits, should have the comma in position 3
  210.         pos = 3;
  211. 	while (pos < numStr.length ())
  212.     {
  213.         numStr.insert (pos, 1, ',');  // Since ',' is a char, the 1 is needed (which is size_t number of characters to insert).  Note that numStr.insert (pos, ",") also works, since "," is a string.
  214.         pos += 4; // skip the comma plus 3 digits.
  215.     }
  216.     return numStr;
  217. }
  218.  
  219. const int spacing (int length) {
  220. 	if (length <= 4)
  221. 		return 3;
  222. 	else if (length <= 7)
  223. 		return 4;
  224. 	else if (length <= 10)
  225. 		return 5;
  226. 	else if (length <= 13)
  227. 		return 6;
  228. 	else if (length <= 16)
  229. 		return 7;
  230. 	else return 8;
  231. }
  232.  
  233. int main () {
  234. 	ChessBoard chessBoard (WIDTH, LENGTH, START_X, START_Y);
  235. 	const int space = spacing (chessBoard.Dimension_y());
  236. 	int sum = 0;
  237. 	for (int j = chessBoard.Dimension_y() - 1; j >= 0; j--)
  238. 	{
  239. 		for (int i = 0; i < chessBoard.Dimension_x(); i++)
  240. 		{
  241. 			std::cout.width (space);
  242. 			if (chessBoard.NodesFound()[i][j])
  243. 			{
  244. 				std::cout << std::left << chessBoard.NodesFound()[i][j]->Value();
  245. 				if (j == chessBoard.Dimension_y() - 1)
  246. 					sum += chessBoard.NodesFound()[i][j]->Value();
  247. 			}
  248. 			else
  249. 				std::cout << std::left << 0;
  250. 		}
  251. 		std::cout << std::endl << std::endl;
  252. 	}
  253. 	std::cout << std::endl << bigNumberWithCommas (sum) << " paths from the starting position to the top row." << std::endl;
  254. 	std::cin.get();
  255. 	return 0;
  256. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1013  1449  2092  2186  2030  1937  1512  1148  

483   597   757   897   971   869   559   425   

168   256   384   382   336   332   279   209   

91    99    124   154   185   154   93    69    

27    44    75    64    54    55    55    39    

17    16    18    27    37    28    14    11    

3     9     14    12    6     10    11    8     

3     3     1     6     7     6     1     2     

0     2     3     2     0     2     2     2     

1     0     0     1     2     1     0     0     

0     0     1     0     0     0     1     0     

0     0     0     0     1     0     0     0     


13,367 paths from the starting position to the top row.
https://ideone.com/Hu2eZF
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!