fork download
copy 
  1. import std.algorithm;
  2. import std.array;
  3. import std.range;
  4. import std.stdio;
  5.  
  6. immutable int NA = -1;
  7.  
  8. auto mult (int [] p, int [] q)
  9. {
  10. 	auto n = p.length;
  11. 	auto res = new int [n];
  12. 	foreach (i; 0..n)
  13. 	{
  14. 		if (q[i] != NA)
  15. 		{
  16. 			res[i] = p[q[i]];
  17. 		}
  18. 	}
  19. 	return res;
  20. }
  21.  
  22. void main ()
  23. {
  24. 	immutable int scale = 2; // 1 for testing, 2 for the actual problem
  25. 	immutable int n = 14 * scale;
  26. 	immutable int parts = 2 * scale;
  27. 	immutable int num1Right = 2 * scale;
  28. 	immutable int num3Right = 4 * scale;
  29. 	auto b = n.iota.array;
  30. 	foreach (j; 0..parts)
  31. 	{
  32. 		bringToFront (b[j * 7 + 0..j * 7 + 1],
  33. 		    b[j * 7 + 1..j * 7 + 7]);
  34. 	}
  35. 	debug {writeln (b);}
  36. 	auto bi = new int [n];
  37. 	foreach (i; 0..n)
  38. 	{
  39. 		bi[b[i]] = i;
  40. 	}
  41. 	auto ab = new int [n];
  42. 	ab[] = NA;
  43. 	auto u = new bool [n];
  44.  
  45. 	bool check ()
  46. 	{
  47. 		foreach (i; 0..n)
  48. 		{
  49. 			if (ab[i] != NA)
  50. 			{
  51. 				if (ab[i] == i)
  52. 				{
  53. 					return false;
  54. 				}
  55. 				if (ab[ab[i]] != NA)
  56. 				{
  57. 					if (ab[ab[i]] != i)
  58. 					{
  59. 						return false;
  60. 					}
  61. 				}
  62. 			}
  63. 		}
  64.  
  65. 		auto a = mult (ab, bi);
  66. 		int num1 = 0;
  67. 		int num3 = 0;
  68. 		foreach (i; 0..n)
  69. 		{
  70. 			if (a[i] != NA)
  71. 			{
  72. 				if (a[i] == i)
  73. 				{
  74. 					num1 += 1;
  75. 					if (num1 > num1Right)
  76. 					{
  77. 						return false;
  78. 					}
  79. 				}
  80. 				else
  81. 				{
  82. 					if (a[a[i]] != NA)
  83. 					{
  84. 						if (a[a[i]] == i)
  85. 						{
  86. 							return false;
  87. 						}
  88. 						else if (a[a[a[i]]] != NA)
  89. 						{
  90. 							if (a[a[a[i]]] == i)
  91. 							{
  92. 								num3 += 1;
  93. 								if (num3 > num3Right)
  94. 								{
  95. 									return false;
  96. 								}
  97. 							}
  98. 							else
  99. 							{
  100. 								return false;
  101. 							}
  102. 						}
  103. 					}
  104. 				}
  105. 			}
  106. 		}
  107.  
  108. 		return true;
  109. 	}
  110.  
  111. 	void recur (int k)
  112. 	{
  113. 		if (k == n)
  114. 		{
  115. 			writeln (ab);
  116. 			return;
  117. 		}
  118. 		auto a = mult (ab, bi);
  119. //		debug {writeln (a);}
  120. 		foreach (i; 0..n)
  121. 		{
  122. 			if (a[i] != NA && a[i] != i &&
  123. 			    a[a[i]] != NA)
  124. 			{
  125. 				if (a[a[a[i]]] == NA)
  126. 				{
  127. //					a[a[a[i]]] = i;
  128. 					ab[bi[a[a[i]]]] = i;
  129. 					a = mult (ab, bi);
  130. 					assert (a[a[a[i]]] == i);
  131. 					recur (k);
  132. 					ab[bi[a[a[i]]]] = NA;
  133. 					return;
  134. 				}
  135. 			}
  136. 		}
  137. 		if (ab[k] != NA)
  138. 		{
  139. 			recur (k + 1);
  140. 			return;
  141. 		}
  142. 		debug {writeln (ab);}
  143. 		if (!check ())
  144. 		{
  145. 			return;
  146. 		}
  147. 		foreach (i; 0..n)
  148. 		{
  149. 			if (!u[i])
  150. 			{
  151. 				if (i == k || ab[i] != NA)
  152. 				{
  153. 					continue;
  154. 				}
  155. 				u[i] = true;
  156. 				ab[k] = i;
  157. 				ab[i] = k;
  158. 				recur (k + 1);
  159. 				ab[i] = NA;
  160. 				ab[k] = NA;
  161. 				u[i] = false;
  162. 			}
  163. 		}
  164. 	}
  165.  
  166. 	recur (0);
  167. }
  168.  
Success #stdin #stdout 0.19s 2704KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dvtS6F
language:
D (dmd 2.085.0)
created:
7 years ago
visibility:
secret

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!