Advertisement

# 36 cube iterative solution FULL

a guest
Jan 18th, 2011
459
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. <?php
2.
3. \$colors = array(
4.      1 => 'R',
5.      2 => 'O',
6.      4 => 'Y',
7.      8 => 'G',
8.     16 => 'B',
9.     32 => 'P',
10.     false => 'X',
11. );
12.
13. \$used_towers = array_fill(0, 6, 0);
14.
15. \$cube = array(
16.     array(1,3,4,5,2,0),
17.     array(2,5,1,4,1,3),
18.     array(0,1,3,2,5,4),
19.     array(5,4,0,3,0,2),
20.     array(4,2,5,0,3,1),
21.     array(3,0,2,1,4,5),
22. );
23.
24. \$solution = array_fill(0, 6, array_fill(0, 6, false));
25. \$solutions = array( );
26.
27. function test_color(\$pos, \$solution, \$used_towers, \$color, \$size) {
28.     if (36 <= \$pos) {
29.         return false;
30.     }
31.
32.     // check if piece exists in solution at this location
33.     if (false !== \$solution[floor(\$pos / 6)][\$pos % 6]) {
34.         return false;
35.     }
36.
37.     // check if tower of this size and color has already been used
38.     if (\$color & \$used_towers[\$size]) {
39.         return false;
40.     }
41.
42.     // check if tower has already been used in row or column:
43.     for (\$i = 0; \$i < 6; ++\$i) {
44.         if (\$color == \$solution[floor(\$pos / 6)][\$i]) {
45.             return false;
46.         }
47.
48.         if (\$color == \$solution[\$i][\$pos % 6]) {
49.             return false;
50.         }
51.     }
52.
53.     // special conditions for the two special towers
54.     if (array(1, 2) == (array(floor(\$pos / 6), \$pos % 6)) && (4 != \$color)) {
55.         return false;
56.     }
57.
58.     if (array(3, 2) == (array(floor(\$pos / 6), \$pos % 6)) && (2 != \$color)) {
59.         return false;
60.     }
61.
62.     return true;
63. }
64.
65.
66. function filter_color(\$used, \$color) {
67.     foreach (\$used as & \$row) {
68.         \$row = (bool) (\$color & \$row);
69.     }
70.     unset(\$row);
71.
72.     return array_filter(\$used);
73. }
74.
75.
76. function solve_color_by_pieces(\$color, \$solution, \$used_towers, \$continue_colors = false) {
77.     global \$colors, \$cube, \$MASTER;
78.
79.     \$orig = \$solution;
80.
81.     if (32 < \$color) {
82.         // convert all numbers to letters based on position and flatten
83.         list(\$converted, \$key) = convert_solution(\$solution);
84.         if ( ! in_array(\$converted, \$MASTER['solution'])) {
85.             \$MASTER['solution'][] = \$converted;
86.             \$MASTER['key'][] = \$key;
87.         }
88.
89.         return \$solution;
90.     }
91.
92.     if (6 <= count(filter_color(\$used_towers, \$color))) {
93.         return solve_color_by_pieces(\$color << 1, \$solution, \$used_towers, \$continue_colors);;
94.     }
95.
96.     \$sols = array( );
97.     \$size = 0;
98.
99.     while (5 >= \$size) {
100.         if (\$color & \$used_towers[\$size]) {
101.             \$size++;
102.             continue;
103.         }
104.
105.         // find ALL possible solutions for this size
106.         for (\$pos = 0; \$pos < 36; ++\$pos) {
107.             if (\$size != \$cube[floor(\$pos / 6)][\$pos % 6]) {
108.                 continue;
109.             }
110.
111.             if ( ! test_color(\$pos, \$solution, \$used_towers, \$color, \$size)) {
112.                 continue;
113.             }
114.
115.             // add to this solution path and continue...
116.             \$solution[floor(\$pos / 6)][\$pos % 6] = \$color;
117.             \$used_towers[\$size] |= \$color;
118.
119.             // if we're not done with this color
120.             if (6 > count(filter_color(\$used_towers, \$color))) {
121.                 \$return = solve_color_by_pieces(\$color, \$solution, \$used_towers, \$continue_colors);
122.             }
123.             elseif (\$continue_colors) {
124.                 \$return = solve_color_by_pieces(\$color << 1, \$solution, \$used_towers, \$continue_colors);
125.             }
126.             else {
127.                 \$return = \$solution;
128.             }
129.
130.             if (\$return) {
131.                 \$sols[] = \$return;
132.             }
133.
134.             // remove this solution and continue searching this level
135.             \$solution[floor(\$pos / 6)][\$pos % 6] = false;
136.             \$used_towers[\$size] ^= \$color;
137.         }
138.
139.         break;
140.     }
141.
142.     return \$sols;
143. }
144.
145.
146. function convert_solution(\$sol) {
147.     global \$colors;
148.
149.     \$letters = array('A','B','C','D','E','F');
150.
151.     \$output = '';
152.     foreach (\$sol as \$i => & \$row) {
153.         foreach (\$row as \$j => & \$piece) {
154.             if ( ! \$i) {
155.                 \$conv[\$piece] = \$letters[\$j];
156.             }
157.             \$output .= \$conv[\$piece];
158.         }
159.     }
160.
161.     \$key = array( );
162.     foreach (\$conv as \$color => \$letter) {
163.         \$key[\$letter] = \$colors[\$color];
164.     }
165.
166.     return array(\$output, \$key);
167. }
168.
169. // solve for red
170. \$solution[1][2] = 4; // yellow
171. \$size = \$cube[1][2];
172. \$used_towers[\$size] |= 4;
173.
174. \$solution[3][2] = 2; // orange
175. \$size = \$cube[3][2];
176. \$used_towers[\$size] |= 2;
177. \$color = 1;
178.
179. \$MASTER = array('solution' => array( ), 'key' => array( ));
180.
181. solve_color_by_pieces(\$color, \$solution, \$used_towers, true);
182. debug(\$MASTER);
183.
184.
185.
186. /** function call [dump] [debug]
187.  *      This function is for debugging only
188.  *      Outputs given var to screen
189.  *      or, if no var given, outputs stars to note position
190.  *
191.  * @param mixed optional var to output
192.  * @param bool optional bypass debug value and output anyway
193.  * @action outputs var to screen
194.  * @return void
195.  */
196. function call(\$var = 'Th&F=xUFucreSp2*ezAhe=ApuPR*\$axe', \$bypass = false, \$show_from = true, \$new_window = false, \$error = false)
197. {
198.     if ((( ! defined('DEBUG') || ! DEBUG) || ! empty(\$GLOBALS['NODEBUG'])) && ! (bool) \$bypass) {
199.         return false;
200.     }
201.
202.     if ('Th&F=xUFucreSp2*ezAhe=ApuPR*\$axe' === \$var) {
203.         \$contents = '<span style="font-size:larger;font-weight:bold;color:red;">--==((OO88OO))==--</span>';
204.     }
205.     else {
206.         // begin output buffering so we can escape any html
207.         // and print_r is better at catching recursion than var_export
208.         ob_start( );
209.
210.         if ((is_string(\$var) && ! preg_match('/^\\s*\$/', \$var))) { // non-whitespace strings
211.             print_r(\$var);
212.         }
213.         else {
214.             if ( ! function_exists('xdebug_disable')) {
215.                 if (is_array(\$var) || is_object(\$var)) {
216.                     print_r(\$var);
217.                 }
218.                 else {
219.                     var_dump(\$var);
220.                 }
221.             }
222.             else {
223.                 var_dump(\$var);
224.             }
225.         }
226.
227.         // end output buffering and output the result
228.         if ( ! function_exists('xdebug_disable')) {
229.             \$contents = htmlentities(ob_get_contents( ));
230.         }
231.         else {
232.             \$contents = ob_get_contents( );
233.         }
234.
235.         ob_end_clean( );
236.     }
237.
238.     \$j = 0;
239.     \$html = '';
240.     \$debug_funcs = array('dump', 'debug');
241.     if ((bool) \$show_from) {
242.         \$called_from = debug_backtrace( );
243.
244.         if (isset(\$called_from[\$j + 1]) && in_array(\$called_from[\$j + 1]['function'], \$debug_funcs)) {
245.             ++\$j;
246.         }
247.
248.         \$file0 = substr(\$called_from[\$j]['file'], strlen(\$_SERVER['DOCUMENT_ROOT']));
249.         \$line0 = \$called_from[\$j]['line'];
250.
251.         \$called = '';
252.         if (isset(\$called_from[\$j + 1]['file'])) {
253.             \$file1 = substr(\$called_from[\$j + 1]['file'], strlen(\$_SERVER['DOCUMENT_ROOT']));
254.             \$line1 = \$called_from[\$j + 1]['line'];
255.             \$called = "{\$file1} : {\$line1} called ";
256.         }
257.         elseif (isset(\$called_from[\$j + 1]['class'])) {
258.             \$called = \$called_from[\$j + 1]['class'].\$called_from[\$j + 1]['type'].\$called_from[\$j + 1]['function'].' called ';
259.         }
260.
261.         \$html = "<strong>{\$called}{\$file0} : {\$line0}</strong>\n";
262.     }
263.
264.     if ( ! \$new_window) {
265.         \$color = '#000';
266.         if (\$error) {
267.             \$color = '#F00';
268.         }
269.
270.         echo "\n\n<pre style=\"background:#FFF;color:{\$color};font-size:larger;\">{\$html}{\$contents}\n<hr /></pre>\n\n";
271.     }
272.     else { ?>
273.         <script language="javascript">
274.             myRef = window.open('','debugWindow');
275.             myRef.document.write('\n\n<pre style="background:#FFF;color:#000;font-size:larger;">');
276.             myRef.document.write('<?php echo str_replace("'", "\'", str_replace("\n", "<br />", "{\$html}{\$contents}")); ?>');
277.             myRef.document.write('\n<hr /></pre>\n\n');
278.         </script>
279.     <?php }
280. }
281. function dump(\$var = 'Th&F=xUFucreSp2*ezAhe=ApuPR*\$axe', \$bypass = false, \$show_from = true, \$new_window = false, \$error = false) { call(\$var, \$bypass, \$show_from, \$new_window, \$error); }
282. function debug(\$var = 'Th&F=xUFucreSp2*ezAhe=ApuPR*\$axe', \$bypass = true, \$show_from = true, \$new_window = false, \$error = false) { call(\$var, \$bypass, \$show_from, \$new_window, \$error); }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement