Guest User

36 cube iterative solution FULL

a guest
Jan 18th, 2011
375
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); }
RAW Paste Data