Commits

Anonymous committed dfe12fc

moving stuff into subdirectories

  • Participants
  • Parent commits 2d8368c

Comments (0)

Files changed (10)

File cube.html

-<html><head><title>QBX - JavaScript two phase solver</title>
-<style>
-a { text-decoration: none; }
-table.cube { border-collapse: collapse ; }
-td { width: 40px ; height: 40px ; border: solid 2px #000000;
-     text-align: center; font-weight: bold; }
-td.U { background-color: white; }
-td.L { background-color: blue; }
-td.F { background-color: orange; }
-td.R { background-color: green; }
-td.B { background-color: red; }
-td.D { background-color: yellow; }
-td.space { width: 5px; height: 10px; border: none; }
-td.wide { height: 5px; border: none; }
-td.void { border: none ; }
-td.big_r { border: none ; text-align: left; font-weight: normal; 
-   width: 250px ; }
-td.big_l { border: none ; text-align: center; font-weight: normal; 
-   width: 120px ; }
-td.button { border: none; height: 0px; width: 0px; }
-</style>
-<script src="solve.js"></script>
-<script src="mersennetwister.js"></script>
-<script>
-// globals
-id = "UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR" ;
-pos = id ;
-start_pos = pos;
-sol = "";
-st = 0;
-brush = "U";
-mt = new MersenneTwisterObject(new Date() + Math.random());
-// global funcs
-function validatepos() {
-   var f = document.forms[0] ;
-   var msg = "" ;
-   var syntaxerr = 0 ;
-   var i, j, cc ;
-   if (pos.length != id.length) {
-      msg = "Position is the wrong length" ;
-      syntaxerr = 1 ;
-   }
-   if (msg == "") {
-      for (i=0; i<id.length; i++) {
-         var c1 = id.charAt(i) ;
-         var c2 = pos.charAt(i) ;
-         if ((c1 == ' ') != (c2 == ' ')) {
-            msg = "Bad syntax" ;
-            syntaxerr = 1 ;
-         }
-      }
-   }
-   if (msg == "") {
-      var idchars = id.split('').sort().join('') ;
-      var poschars = pos.split('').sort().join('') ;
-      if (idchars != poschars)
-         msg = "Color count not right" ;
-   }
-   if (msg == "") {
-      var cid = id.split(" ") ;
-      var cpos = pos.split(" ") ;
-      var doublecid = new Array() ;
-      for (i=0; i<20; i++)
-         doublecid[i] = cid[i] + cid[i] ;
-      var searchable = doublecid.join(" ") ;
-      var mask = 0 ;
-      var corder = new Array() ;
-      var cosum = 0 ;
-      var eosum = 0 ;
-      for (i=0; i<20; i++) {
-         j = searchable.indexOf(cpos[i]) ;
-         if (j < 0) {
-            msg = "Bad cubie" ;
-         }
-         if (i < 12) {
-            cc = j / 5 ;
-            eosum += j % 5 ;
-            mask |= (1 << cc) ;
-         } else {
-            cc = (j - 60) / 7 ;
-            cosum += (j - 60) % 7 ;
-            mask |= (1 << (cc + 12)) ;
-         }
-         corder[i] = cc ;
-      }
-      if (msg == "") {
-         if (mask != 0xfffff)
-            msg = "Missing cubie" ;
-         else if (eosum % 2 != 0)
-            msg = "Edge orientation mismatch" ;
-         else if (cosum % 3 != 0)
-            msg = "Corner orientation mismatch" ;
-      }
-      if (msg == "") {
-         // check parity; quadratic
-         var p = 0 ;
-         for (i=0; i<12; i++)
-            for (j=0; j<i; j++)
-               if (corder[j] > corder[i])
-                  p++ ;
-         for (i=12; i<20; i++)
-            for (j=12; j<i; j++)
-               if (corder[j] > corder[i])
-                  p++ ;
-         if (p % 2 != 0)
-            msg = "Parity error" ;
-      }
-   }
-   if (msg == "") {
-      f.elements["generatebutton"].disabled = false ;
-      f.elements["solvebutton"].disabled = false ;
-   } else {
-      f.elements["generatebutton"].disabled = true ;
-      f.elements["solvebutton"].disabled = true ;
-   }
-   validation.innerHTML = msg ;
-}
-function showpos() {
-   validatepos() ;
-   CU.className = "U" ;
-   CF.className = "F" ;
-   CR.className = "R" ;
-   CD.className = "D" ;
-   CB.className = "B" ;
-   CL.className = "L" ;
-   var i ;
-   for (i=0; i<pos.length; i++) {
-      var c = pos.charAt(i) ;
-      if (c != ' ') {
-         document.getElementById("C"+i).className = c ;
-      }
-   }
-   document.forms["cube form"].elements["pos_entry"].value = pos ;
-}
-function paint(cell) {
-    var i, p, newpos = "" ;
-    cell.className = brush ;
-    p = parseInt(cell.id.substr(1)) ;
-    for (i=0; i<pos.length; i++) {
-	if (i == p)
-	    newpos += brush ;
-	else
-	    newpos += pos.charAt(i) ;
-    }
-    pos = newpos ;
-    document.forms["cube form"].elements["pos_entry"].value = pos ;
-    showpos() ;
-}
-function get_color(cell) {
-    brush = cell.className ;
-    document.getElementById("brush").className = brush ;
-}
-function mov(face) {
-   var out = pos ;
-   var i, j, ii, jj ;
-   for (i=36; i<68; i+=4) {
-      for (j=0; j<3; j++) {
-         if (id.charAt(i+j) == face) {
-            var from = id.charAt(i+(j+2)%3) ;
-            var to = id.charAt(i+(j+1)%3) ; 
-            var posd, srcjj ;
-            for (ii=0; ii<36; ii += 3) {
-               for (jj=0; jj<2; jj++) {
-                  if (id.charAt(ii+jj) == face &&
-                      id.charAt(ii+(jj+1)%2) == from) {
-                     srcjj = jj ;
-                     posd = pos.substr(ii, 2) ;
-                  }
-               }
-            }
-            for (ii=0; ii<36; ii += 3) {
-               for (jj=0; jj<2; jj++) {
-                  if (id.charAt(ii+jj) == face &&
-                      id.charAt(ii+(jj+1)%2) == to) {
-                      if (jj != srcjj)
-                         posd = posd.charAt(1) + posd.charAt(0) ;
-                      out = out.substring(0, ii) +  posd + out.substring(ii+2) ;
-                  }
-               }
-            }
-            var posc = pos.substr(i, 3); 
-            for (ii=36; ii<68; ii += 4) {
-               for (jj=0; jj<3; jj++) {
-                  if (id.charAt(ii+jj) == face &&
-                      id.charAt(ii+(jj+2)%3) == to) {
-                     srcjj = j ;
-                     while (jj != srcjj) {
-                        posc = posc.substring(1) + posc.charAt(0) ;
-                        srcjj = (srcjj + 2) % 3 ;
-                     }
-                     out = out.substring(0, ii) + posc + out.substring(ii+3) ;
-                  }
-               }
-            }
-         }
-      }
-   }
-   pos = out ;
-   showpos() ;
-   return false ;
-}
-function randomize() {
-   pos = id;
-   sol = "";
-   st = 0;
-
-   var a = pos.split(" ") ;
-   var i, j, s=0, p=0, t ;
-   for (i=0; i<11; i++) {
-      j = i + Math.floor((12-i)*mt.random()) ;
-      if (i != j) {
-         t = a[i] ; a[i] = a[j] ; a[j] = t ; // swap
-         p++ ;
-      }
-      if (mt.random() < 0.5) {
-         a[i] = a[i].charAt(1) + a[i].charAt(0) ;
-         s++ ;
-      }
-   }
-   if (s & 1) {
-      a[11] = a[11].charAt(1) + a[11].charAt(0) ;
-   }
-   s = 0 ;
-   for (i=0; i<7; i++) {
-      j = i + Math.floor((8-i)*mt.random()) ;
-      if (i != j) {
-         t = a[i+12]; a[i+12] = a[j+12] ; a[j+12] = t ;
-         p++ ;
-      }
-      var o = Math.floor(3*mt.random()) ;
-      while (o-- > 0) {
-         a[i+12] = a[i+12].substring(1) + a[i+12].charAt(0) ;
-         s++ ;
-      }
-   }
-   while (s % 3 > 0) {
-      a[19] = a[19].substring(1) + a[19].charAt(0) ;
-      s++ ;
-   }
-   if (p & 1) {
-      t = a[0] ; a[0] = a[1] ; a[1] = t ;
-   }
-   pos = a.join(" ") ;
-   document.forms[0].elements["solution"].value = "" ;
-   showpos() ;
-   return false ;
-}
-function solve() {
-   document.forms[0].elements["solution"].value = "Working..." ;
-   setTimeout(function(){document.forms[0].elements["solution"].value=sol=solvecube(pos, 0);st=0;},0) ;
-}
-function endstep() {
-	while (st < sol.length)
-		nextstep();
-	nextstep();
-}
-function nextstep() {
-	var i, j, c, num, inc, str = "";
-
-	if (st < 0) st = 0;
-	if (st >= sol.length) {
-		document.forms[0].elements["solution"].value = sol;
-		return;
-	}
-	for (i = 0; i < sol.length; i++) {
-		if (i == st) {
-			sol.charAt(i);
-			num = 1;
-			if (i + 1 < sol.length) {
-				switch (sol.charAt(i + 1)) {
-					case '-':
-					case '\'':
-					case '3': num = 3; break;
-					case '2': num = 2; break;
-					default:  num = 1; break;
-				}
-			}
-
-			if (i + 1 < sol.length) {
-				for (inc = 1; inc + i < sol.length; inc++) {
-					c = sol.charAt(i + inc);
-					if (c == "U" || c == "D" || c == "F" ||
-					c == "B" || c == "R" || c == "L")
-					break;
-				}
-			}
-
-			for (j = 0; j < num; j++)
-				mov(sol.charAt(i));
-
-			for (j = 0; j < inc; j++)
-				str += sol.charAt(i + j);
-
-			str += "  |  ";
-			i += inc - 1;
-			} else {
-			str += sol.charAt(i);
-		}
-	}
-	st += inc;
-
-	document.forms[0].elements["solution"].value = str;
-}
-function firststep() {
-    while (st > 0)
-		priorstep();
-    priorstep();
-}
-function priorstep() {
-	var i, j, c, num, inc, str = "";
-
-	if (st > sol.length) st = sol.length;
-	if (st < 0) {
-		document.forms[0].elements["solution"].value = sol;
-		return;
-	}
-	for (st--; st >= 0; st--) {
-		c = sol.charAt(st);
-		if (c == "U" || c == "D" || c == "F" ||
-		c == "B" || c == "R" || c == "L")
-		break;
-	}
-
-	for (i = 0; i < sol.length; i++) {
-		if (i == st) {
-			sol.charAt(i);
-			num = 1;
-			if (i + 1 < sol.length) {
-				switch (sol.charAt(i + 1)) {
-					case '-':
-					case '\'':
-					case '3': num = 1; break;
-					case '2': num = 2; break;
-					default:  num = 3; break;
-				}
-			}
-
-			if (i + 1 < sol.length) {
-				for (inc = 1; inc + i < sol.length; inc++) {
-					c = sol.charAt(i + inc);
-					if (c == "U" || c == "D" || c == "F" ||
-					c == "B" || c == "R" || c == "L")
-					break;
-				}
-			}
-
-			for (j = 0; j < num; j++)
-				mov(sol.charAt(i));
-
-			str += "  |  ";
-			for (j = 0; j < inc; j++)
-				str += sol.charAt(i + j);
-
-			i += inc - 1;
-			} else {
-			str += sol.charAt(i);
-		}
-	}
-
-	document.forms[0].elements["solution"].value = str;
-}
-function generate() {
-   document.forms[0].elements["solution"].value = "Working...";
-   setTimeout(function(){document.forms[0].elements["solution"].value=sol=solvecube(pos, 1);st=sol.length;},0) ;
-}
-function dobenchmark() {
-   document.forms[0].elements["solution"].value = "Working...";
-   setTimeout(function(){document.forms[0].elements["solution"].value="";validation.innerHTML=benchmark();},0) ;
-}
-function cubeclear() {
-   st = 0;
-   document.forms[0].elements["solution"].value = sol = "";
-   pos = id ;
-   showpos() ;
-   return false ;
-}
-function setpos() {
-    pos = document.forms[0].elements["pos_entry"].value ;
-    document.forms[0].elements["pos_entry"].value = "" ;
-    showpos() ;
-}
-function setsol() {
-	var i, j, k, str = document.forms[0].elements["solution"].value ;
-
-	k = 1;
-	for (i = 0; i < str.length; i++) {
-		switch (str.charAt(i)) {
-			case 'U':
-			case 'D':
-			case 'F':
-			case 'B':
-			case 'R':
-			case 'L': j = 0; break;
-			case '1':
-			case '+':
-			case '2':
-			case '3':
-			case '\'':
-			case '-': j = 1; break;
-			case ' ': j = 2; break;
-			default : j = 3; break;
-		}
-		if (j == 3 || (j == 1 && k == 1)) {
-			validation.innerHTML = "Bad character in sequence at pos " + i + " : " + str.charAt(i);
-			return;
-		}
-		k = j;
-	}
-	str += " ";
-	sol = str;
-	st = 0;
-	validation.innerHTML = "Sequence set";
-}
-
-function changecss(cls, atr, val) {
-	// thanks to Shawn Olson & http://www.shawnolson.net for the general mechanics behind this
-	var rules, tmp;
-	var r1, r2, s;
-
-	cls = cls.toLowerCase();
-	val = val.toLowerCase();
-
-	for (s = 0; s < document.styleSheets.length; s++) {
-		if (document.styleSheets[s]['rules']) {
-				rules = 'rules';
-			} else if (document.styleSheets[s]['cssRules']) {
-				rules = 'cssRules';
-			} else {
-			// no rules found... browser unknown
-		}
-
-		for (r1 = 0; r1 < document.styleSheets[s][rules].length; r1++) {
-			if (document.styleSheets[s][rules][r1].selectorText.toLowerCase() == val &&
-				document.styleSheets[s][rules][r1].style[atr]) {
-				break;
-			}
-		}
-
-
-		for (r2 = 0; r2 < document.styleSheets[s][rules].length; r2++) {
-			if (document.styleSheets[s][rules][r2].selectorText.toLowerCase() == cls &&
-				document.styleSheets[s][rules][r2].style[atr]) {
-				break;
-			}
-		}
-		tmp = document.styleSheets[s][rules][r1].style[atr];
-		document.styleSheets[s][rules][r1].style[atr] = document.styleSheets[s][rules][r2].style[atr];
-		document.styleSheets[s][rules][r2].style[atr] = tmp;
-		brush = val.substr(3);
-		document.getElementById("brush").className = brush ;
-	}
-
-}
-
-
-// hook in
-window.onload = function() { init_cube() ; showpos() ;}
-</script>
-</head>
-<body>
-<form name="cube form" action="" onsubmit="return false;">
-<table class="cube">
-<tr>
-	<td class="big_l" colspan="3" rowspan="3" valign="center">
-		<font size="7"><b>
-				<font color="blue">Q</font><font color="red">B</font><font color="green">X</font>
-		</b></font><br>
-		Evan Gates<br>
-		Tomas Rokicki
-	</td>
-	<td class="space"></td>
-	<td id="C44" onclick="paint(this);"></td><td id="C6" onclick="paint(this);"></td><td id="C40" onclick="paint(this);"></td><td class="space"></td>
-	<td class="big_r" colspan="7" rowspan="3">
-		Too slow? Try <a href="http://www.google.com/chrome">Chrome</a>. Up to 30x faster than Firefox. Do the benchmark.
-	</td>
-</tr>
-<tr>
-<td class="space"></td>
-<td id="C9" onclick="paint(this);"></td><td id="CU" onclick="changecss('td.' + this.className,'background-color','td.' + brush);">U</td><td id="C3" onclick="paint(this);"></td><td class="space"></td>
-</tr>
-<tr>
-<td class="space"></td>
-<td id="C48" onclick="paint(this);"></td><td id="C0" onclick="paint(this);"></td><td id="C36" onclick="paint(this);"></td><td class="space"></td>
-</tr>
-<tr>
-<td class="wide"></td><td class="wide"></td><td class="wide"></td><td class="space"></td>
-<td class="wide"></td><td class="wide"></td><td class="wide"></td><td class="space"></td>
-<td class="wide"></td><td class="wide"></td><td class="wide"></td><td class="space"></td>
-<td class="wide"></td><td class="wide"></td><td class="wide"></td>
-</tr>
-<tr>
-<td id="C46" onclick="paint(this);"></td><td id="C10" onclick="paint(this);"></td><td id="C49" onclick="paint(this);"></td> <td class="space"></td>
-<td id="C50" onclick="paint(this);"></td><td id="C1" onclick="paint(this);"></td><td id="C37" onclick="paint(this);"></td> <td class="space"></td>
-<td id="C38" onclick="paint(this);"></td><td id="C4" onclick="paint(this);"></td><td id="C41" onclick="paint(this);"></td> <td class="space"></td>
-<td id="C42" onclick="paint(this);"></td><td id="C7" onclick="paint(this);"></td><td id="C45" onclick="paint(this);"></td>
-</tr>
-<tr>
-<td id="C34" onclick="paint(this);"></td><td id="CL" onclick="changecss('td.' + this.className,'background-color','td.' + brush);">L</td><td id="C28" onclick="paint(this);"></td> <td class="space"></td>
-<td id="C27" onclick="paint(this);"></td><td id="CF" onclick="changecss('td.' + this.className,'background-color','td.' + brush);">F</td><td id="C24" onclick="paint(this);"></td> <td class="space"></td>
-<td id="C25" onclick="paint(this);"></td><td id="CR" onclick="changecss('td.' + this.className,'background-color','td.' + brush);">R</td><td id="C31" onclick="paint(this);"></td> <td class="space"></td>
-<td id="C30" onclick="paint(this);"></td><td id="CB" onclick="changecss('td.' + this.className,'background-color','td.' + brush);">B</td><td id="C33" onclick="paint(this);"></td>
-</tr>
-<tr>
-<td id="C61" onclick="paint(this);"></td><td id="C22" onclick="paint(this);"></td><td id="C58" onclick="paint(this);"></td> <td class="space"></td>
-<td id="C57" onclick="paint(this);"></td><td id="C13" onclick="paint(this);"></td><td id="C54" onclick="paint(this);"></td> <td class="space"></td>
-<td id="C53" onclick="paint(this);"></td><td id="C16" onclick="paint(this);"></td><td id="C66" onclick="paint(this);"></td> <td class="space"></td>
-<td id="C65" onclick="paint(this);"></td><td id="C19" onclick="paint(this);"></td><td id="C62" onclick="paint(this);"></td>
-</tr>
-<tr>
-<td class="wide"></td><td class="wide"></td><td class="wide"></td><td class="space"></td>
-<td class="wide"></td><td class="wide"></td><td class="wide"></td><td class="space"></td>
-<td class="wide"></td><td class="wide"></td><td class="wide"></td><td class="space"></td>
-<td class="wide"></td><td class="wide"></td><td class="wide"></td>
-</tr>
-<tr>
-<td class="big_l" colspan="4" rowspan="3">
-    <table align="center">
-	<tr>
-	    <td class="button"><input type="button" value="U" onclick="mov('U');"></td>
-	    <td class="button"><input type="button" value="F" onclick="mov('F');"></td>
-	    <td class="button"><input type="button" value="R" onclick="mov('R');"></td>
-	</tr>
-	<tr>
-	    <td class="button"><input type="button" value="D" onclick="mov('D');"></td>
-	    <td class="button"><input type="button" value="B" onclick="mov('B');"></td>
-	    <td class="button"><input type="button" value="L" onclick="mov('L');"></td>
-	</tr>
-	<tr>
-	    <td class="button" colspan="3">
-		<input type="button" value="clear" onclick="cubeclear();">
-		<input type="button" value="random" onclick="randomize();">
-	    </td>
-	</tr>
-    </table>
-</td>
-<td id="C56" onclick="paint(this);"></td><td id="C12" onclick="paint(this);"></td><td id="C52" onclick="paint(this);"></td><td class="space"></td>
-<td class="big_r" colspan="7" rowspan="7" valign="top">
-	Click on a color in the palette then click on squares in the cube to paint them.
-	Paint center squares first. You can manually edit or enter a cube or move sequence
-	in the text box and click set when done. Click the |&lt &lt &gt &gt| buttons to step
-	through a move sequence. Benchmark reports initialization and solving times to compare
-	browsers.
-</td>
-</tr>
-<tr>
-<td id="C21" onclick="paint(this);"></td><td id="CD" onclick="changecss('td.' + this.className,'background-color','td.' + brush);">D</td><td id="C15" onclick="paint(this);"></td><td class="space"></td>
-<td class="void"></td><td class="void"></td><td class="void"></td><td class="space"></td>
-<td class="void"></td><td class="void"></td><td class="void"></td>
-</tr>
-<tr>
-<td id="C60" onclick="paint(this);"></td><td id="C18" onclick="paint(this);"></td><td id="C64" onclick="paint(this);"></td><td class="space"></td>
-<td class="void"></td><td class="void"></td><td class="void"></td><td class="space"></td>
-<td class="void"></td><td class="void"></td><td class="void"></td>
-</tr>
-<tr>
-<td class="wide"></td><td class="wide"></td><td class="wide"></td><td class="space"></td>
-<td class="wide"></td><td class="wide"></td><td class="wide"></td><td class="space"></td>
-</tr>
-<tr>
-	<td class="U" onclick="get_color(this);"></td>
-	<td class="F" onclick="get_color(this);"></td>
-	<td class="R" onclick="get_color(this);"></td>
-	<td class="space"></td>
-	<td class="wide"></td>
-	<td class="wide"></td>
-	<td class="wide"></td>
-	<td class="space"></td>
-</tr>
-<tr>
-	<td class="D" onclick="get_color(this);"></td>
-	<td class="B" onclick="get_color(this);"></td>
-	<td class="L" onclick="get_color(this);"></td>
-	<td class="space"></td>
-	<td id="brush"></td>
-</tr>
-<tr>
-	<td class="wide"></td>
-	<td class="wide"></td>
-	<td class="wide"></td>
-	<td class="space"></td>
-	<td class="wide"></td>
-</tr>
-<tr><td class="wide"></td></tr>
-</table>
-<br>
-<input type="button" name="solvebutton" value="solve" onclick="solve();">
-<input type="button" name="generatebutton" value="generate" onclick="generate();">
-<input type="button" value="benchmark" onclick="dobenchmark();">
-<input type="button" value="|<" onclick="firststep();">
-<input type="button" value="<" onclick="priorstep();">
-<input type="button" value=">" onclick="nextstep();">
-<input type="button" value=">|" onclick="endstep();">
-<br>
-<input type="text" name="pos_entry" size="90">
-<input type="button" value="set" onclick="setpos();">
-<br>
-<input type="text" name="solution" size="90">
-<input type="button" value="set" onclick="setsol();">
-<div id="validation"></div>
-<br><br>
-&copy; 2010 Evan Gates and Tomas Rokicki<br>
-QBX is released under the <a href="http://www.gnu.org/licenses/gpl-2.0.html">GPLv2</a>
-</form>
-</body></html>
-

File mersennetwister.js

-//
-//	Version		File name			Description
-//	-------		---------			-----------
-//	2004-12-03	hr$mersennetwister.js		original version will stay available,
-//							but is no longer maintained by Henk Reints
-//
-//	2005-11-02	hr$mersennetwister2.js		o  renamed constructor from "MersenneTwister"
-//							   to "MersenneTwisterObject"
-//							o  exposure of methods now in separate section near the end
-//							o  removed "this." from internal references
-//
-// ====================================================================================================================
-// Mersenne Twister mt19937ar, a pseudorandom generator by Takuji Nishimura and Makoto Matsumoto.
-// Object Oriented JavaScript version by Henk Reints (http://henk-reints.nl)
-// ====================================================================================================================
-// Original header text from the authors (reformatted a little bit by HR):
-// -----------------------------------------------------------------------
-//
-//	A C-program for MT19937, with initialization improved 2002/1/26.
-//	Coded by Takuji Nishimura and Makoto Matsumoto.
-//
-//	Before using, initialize the state by using init_genrand(seed) or init_by_array(init_key, key_length).
-//
-//	Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura, All rights reserved.
-//
-//	Redistribution and use in source and binary forms, with or without modification,
-//	are permitted provided that the following conditions are met:
-//
-//	1. Redistributions of source code must retain the above copyright notice,
-//	   this list of conditions and the following disclaimer.
-//
-//	2. Redistributions in binary form must reproduce the above copyright notice,
-//	   this list of conditions and the following disclaimer in the documentation and/or
-//	   other materials provided with the distribution.
-//
-//	3. The names of its contributors may not be used to endorse or promote products derived from this software
-//	   without specific prior written permission.
-//
-//	THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED
-//	WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
-//	PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
-//	ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
-//	TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
-//	HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
-//	NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
-//	POSSIBILITY OF SUCH DAMAGE.
-//
-//	Any feedback is very welcome.
-//	http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
-//	email: m-mat @ math.sci.hiroshima-u.ac.jp (remove space)
-//
-// ====================================================================================================================
-// Remarks by Henk Reints about this JS version:
-//
-// Legal stuff:
-//	THE ABOVE LEGAL NOTICES AND DISCLAIMER BY THE ORIGINAL AUTHORS
-//	ALSO APPLY TO THIS JAVASCRIPT TRANSLATION BY HENK REINTS.
-//
-// Contact:
-//	For feedback or questions you can find me on the internet: http://henk-reints.nl
-//
-// Description:
-//	This is an Object Oriented JavaScript version of the Mersenne Twister.
-//
-// Constructor:
-//	MersenneTwisterObject([seed[,seedArray]])
-//		if called with 0 args then a default seed   is used for initialisation by the 'init' method;
-//		if called with 1 arg  then 'seed'           is used for initialisation by the 'init' method;
-//		if called with 2 args then 'seedArray,seed' is used for initialisation by the 'initByArray' method;
-//		if a supplied seed is NaN or not given then a default is used.
-//
-// Properties:
-//	none exposed
-//
-// Methods:
-//	init0(seed)		initialises the state array using the original algorithm
-//				  if seed is NaN or not given then a default is used
-//	init(seed)		initialises the state array using the improved algorithm
-//				  if seed is NaN or not given then a default is used
-//	initByArray(seedArray[,seed])
-//				initialises the state array based on an array of seeds,
-//				  the 2nd argument is optional, if given and not NaN then it overrides
-//				  the default seed which is used for the very first initialisation
-//	skip(n)			lets the random number generator skip a given count of randoms
-//				  if n <= 0 then it advances to the next scrambling round
-//				  in order to produce an unpredictable well-distributed sequence, you could let n be
-//				  generated by some other random generator which preferrably uses external events to
-//				  create an entropy pool from which to take the numbers.
-//				  this method has been added by Henk Reints, 2004-11-16.
-//	randomInt32()		returns a random 32-bit integer
-//	randomInt53()		returns a random 53-bit integer
-//				  this is done in the same way as was introduced 2002/01/09 by Isaku Wada
-//				  in his genrand_res53() function
-//	randomReal32()		returns a random floating point number in [0,1) with 32-bit precision
-//				  please note that - at least on Microsoft Platforms - JavaScript ALWAYS stores
-//				  Numbers with a 53 bit mantissa, so randomReal32() is not the best choice in JS.
-//				  it is provided to be able to produce output that can be compared to the demo
-//				  output given by the original authors. For JavaScript implementations I suggest
-//				  you always use the randomReal53 method.
-//	randomReal53()		returns a random floating point number in [0,1) with 53-bit precision
-//				  this is done in the same way as was introduced 2002/01/09 by Isaku Wada
-//				  in the genrand_res53() function
-//	randomString(len)	returns a random string of given length, existing of chars from the charset:
-//				  "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/", which is identical
-//				  to the character set used for base64 encoding, so effectively it generates a random
-//				  base64-encoded number of arbitrary precision.
-//				  If you intend to use a random string in a URL string, then the "+" and "/" should
-//				  be converted to URL syntax using the JavaScript built-in 'escape' method.
-//				  this method has been added by Henk Reints, 2004-11-16.
-//	random()		a synonym for randomReal53	[HR/2004-12-03]
-//	randomInt()		a synonym for randomInt32	[HR/2004-12-03]
-//				  these two synonyms are intended to be generic names for normal use.
-//
-// Examples of object creation:
-//	mt = new MersenneTwisterObject()			// create object with default initialisation
-//	mt = new MersenneTwisterObject(19571118)		// create object using a specific seed
-//	mt = new MersenneTwisterObject(Nan,[1957,11,18,03,06])	// create object using a seed array only
-//	mt = new MersenneTwisterObject(1957,[11,18,03,06])	// create object using a seed array AND a specific seed
-//
-// Examples of (re)initialisation (to be done after the object has been created):
-//	mt.init0()				// re-init using the old-style algorithm with its default seed
-//	mt.init0(181157)			// re-init using the old-style algorithm with a given seed
-//	mt.init()				// re-init using the new-style algorithm with its default seed
-//	mt.init(181157)				// re-init using the new-style algorithm with a given seed
-//	mt.initByArray([18,11,57])		// re-init using a seed array
-//	mt.initByArray([18,11,57],0306)		// re-init using a seed array AND a specific seed
-//
-// Example of generating random numbers (after creation of the object and optional re-initialisation of its state):
-//	while (condition)
-//	{	i = mt.randomInt32()			// get a random 32 bit integer
-//		a = mt.randomReal53()			// and a random floating point number of maximum precision
-//		x = myVerySophisticatedAlgorithm(i,a)	// do something with it
-//	}
-//
-// Functions for internal use only:
-//	dmul0(m,n)	performs double precision multiplication of two 32-bit integers and returns only the low order
-//			32 bits of the product; this function is necessary because JS always stores Numbers with a
-//			53-bit mantissa, leading to loss of 11 lowest order bits. In fact it is the pencil & paper
-//			method for multiplying 2 numbers of 2 digits each, but it uses digits of 16-bits each. Since
-//			only the low order result is needed, the steps that only affect the high order part of the
-//			result are left out.
-//
-// Renamed original functions:			to:
-//	init_genrand(s)				init(seed)
-//	init_by_array(init_key,key_length)	initByArray(seedArray[,seed])
-//	genrand_int32()				randomInt32()
-//	genrand_real2()				randomReal32()
-//	genrand_res53()				randomReal53()
-//
-// Other modifications w.r.t. the original:
-//	- did not include the other variants returning real values - I think [0,1) is the only appropriate interval;
-//	- included randomInt53() using the same method as was introduced 2002/01/09 by Isaku Wada in his genrand_res53;
-//	- included randomString(len);
-//	- included skip(n);
-//	- in the randomInt32 method I have changed the check "if (mti >= N)" to a 'while' loop decrementing mti by N
-//	  in each iteration, which allows skipping a range of randoms by simply adding a value to the mti property.
-//	  By setting mti to a negative value you can force an advance to the next scrambling round.
-//	  Since in this library the uninitialised state is not marked by mti==N+1 that's is a safe algorithm.
-//	  When using the constructor, a default initialisation is always performed.
-//
-// Notes:
-//	- Whenever I say 'random' in this file, I mean of course 'pseudorandom';
-//	- I have tested this only with Windows Script Host V5.6 on 32-bit Microsoft Windows platforms.
-//	  If it does not produce correct results on other platforms, then please don't blame me!
-//	- As mentioned by the authors and on many other internet sites,
-//	  the Mersenne Twister does _NOT_ produce secure sequences for cryptographic purposes!
-//	  It was primarily designed for producing good pseudorandom numbers to perform statistics.
-// ====================================================================================================================
-
-function MersenneTwisterObject(seed,seedArray)
-{	var N = 624, mask = 0xffffffff, mt = [], mti = NaN, m01 = [0,0x9908b0df]
-	var M = 397, N1 = N-1, NM = N-M, MN = M-N, U = 0x80000000, L = 0x7fffffff, R = 0x100000000
-	function dmul0(m,n)
-	{	var H=0xffff0000,L=0x0000ffff,R=0x100000000,m0=m&L,m1=(m&H)>>>16,n0=n&L,n1=(n&H)>>>16,p0,p1,x
-		p0=m0*n0,p1=p0>>>16,p0&=L,p1+=m0*n1,p1&=L,p1+=m1*n0,p1&=L,x=(p1<<16)|p0
-		return(x<0?x+R:x)
-	}
-	function init0(seed)
-	{	var x = (arguments.length > 0 && isFinite(seed) ? seed&mask : 4357), i
-		for (mt=[x], mti=N, i=1; i<N; mt[i++] = x = (69069 * x) & mask);
-	}
-	function init(seed)
-	{	var x = (arguments.length > 0 && isFinite(seed) ? seed&mask : 5489), i
-		for (mt=[x], mti=N, i=1; i<N; mt[i] = x = dmul0(x^(x>>>30),1812433253) + i++);
-	}
-	function initByArray(seedArray,seed)
-	{	var N1=N-1, L=seedArray.length, x,i,j,k
-		init (arguments.length > 1 && isFinite(seed) ? seed : 19650218)
-		x=mt[0], i=1, j=0, k=Math.max(N,L)
-		for (; k; j %= L, k--)
-		{	mt[i] = x = ( (mt[i++]^dmul0(x^(x>>>30),1664525)) + seedArray[j] + j++) & mask
-			if (i > N1) {mt[0] = x = mt[N1]; i = 1}
-		}
-		for (k=N-1; k; k--)
-		{	mt[i] = x = ( (mt[i]^dmul0(x^(x>>>30),1566083941)) - i++) & mask
-			if (i > N1) {mt[0] = x = mt[N1]; i = 1}
-		}
-		mt[0] = 0x80000000
-	}
-	function skip(n)
-	{	mti = (n<=0 ? -1 : mti+n)
-	}
-	function randomInt32()
-	{	var y,k
-		while (mti >= N || mti < 0)
-		{	mti = Math.max (0, mti-N)
-			for(k=0;k<NM;	y=(mt[k ]&U)|(mt[k+1]&L),mt[k ]=mt[k+M ]^(y>>>1)^m01[y&1],k++);
-			for(   ;k<N1;	y=(mt[k ]&U)|(mt[k+1]&L),mt[k ]=mt[k+MN]^(y>>>1)^m01[y&1],k++);
-					y=(mt[N1]&U)|(mt[0  ]&L),mt[N1]=mt[M-1 ]^(y>>>1)^m01[y&1]
-		}
-		y=mt[mti++], y^=(y>>>11), y^=(y<<7)&0x9d2c5680, y^=(y<<15)&0xefc60000, y^=(y>>>18)
-		return (y<0?y+R:y)
-	}
-	function randomInt53()
-	{	var two26=0x4000000
-		return (randomInt32()>>>5) * two26 + (randomInt32()>>>6)
-	}
-	function randomReal32()
-	{	var two32=0x100000000
-		return randomInt32()/two32
-	}
-	function randomReal53()
-	{	var two53=0x20000000000000
-		return randomInt53()/two53
-	}
-	function randomString(len)
-	{	var i,r,x="",C="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
-		for(i=0;i<len;x+=C.charAt((((i++)%5)>0?r:r=randomInt32())&63),r>>>=6);
-		return x
-	}
-
-        this.init0		= init0
-        this.init		= init
-        this.initByArray	= initByArray
-        this.skip		= skip
-
-        this.randomInt32	= randomInt32
-        this.randomInt53	= randomInt53
-        this.randomReal32	= randomReal32
-        this.randomReal53	= randomReal53
-        this.randomString	= randomString
-
-        this.random		= randomReal53
-        this.randomInt		= randomInt32
-
-	if	(arguments.length > 1)	initByArray(seedArray,seed)
-	else if	(arguments.length > 0)	init(seed)
-	else				init()
-}
-
-// ====================================================================================================================
-// now define a function with the obsoleted name which simply tells the user about how to update the code.
-function MersenneTwister(seed,seedArray)
-{	for (var a = [], i = 0; i < arguments.length; a[i] = arguments[i++] );
-	var msg="Your code correctly uses the hr$mersennetwister2.js file,"
-	+"\n"+	"but it does not yet use the new MersenneTwister constructor."
-	+"\n"+	'Please update your code and replace: "MersenneTwister('+a+')"'
-	+"\n"+	'with: "MersenneTwisterObject('+a+')"'
-	+"\n\n"+"http://Henk-Reints.nl"
-	var done
-	done=true;try{WScript.Echo(msg)}			catch(e){done=false};if(done)return;
-	done=true;try{alert       (msg)}			catch(e){done=false};if(done)return;
-	done=true;try{document.writeln('<pre>'+msg+'</pre>')}	catch(e){done=false};if(done)return;
-	throw msg
-}
-// ====================================================================================================================
-// End of file hr$mersennetwister2.js - Copyright (c) 2004,2005 Henk Reints, http://henk-reints.nl

File rand.c

-#include <stdio.h>
-#include <stdlib.h>
-#include <sys/time.h>
-
-char *names[] = { "UFU", "URU", "UBU", "ULU", "DFD", "DRD", "DBD", "DLD", "FRF", "FLF", "BRB", "BLB",
-                  "UFRUF", "URBUR", "UBLUB", "ULFUL", "DRFDR", "DFLDF", "DLBDL", "DBRDB" };
-
-int main()
-{
-    char *tmp;
-    long int r;
-    int i, o;
-
-    struct timeval tv;
-    gettimeofday(&tv, NULL);
-    srandom(tv.tv_usec);
-
-    for (i = 0; i < 12; i++) {
-	r = random() % 12;
-	if (r == i) {
-	    i--;
-	    continue;
-	}
-	tmp = names[i];
-	names[i] = names[r];
-	names[r] = tmp;
-    }
-
-    for (i = 0; i < 8; i++) {
-	r = random() % 8;
-	if (r == i) {
-	    i--;
-	    continue;
-	}
-	tmp = names[i + 12];
-	names[i + 12] = names[r + 12];
-	names[r + 12] = tmp;
-    }
-
-    o = 0;
-    for (i = 0; i < 11; i++) {
-	r = random() % 2;
-	o = (o + r) % 2;
-	printf("%0.2s ", names[i] + r);
-    }
-    printf("%0.2s ", names[11] + o);
-
-    o = 0;
-    for (i = 0; i < 7; i++) {
-	r = random() % 3;
-	o = (o + 3 - r) % 3;
-	printf("%0.3s ", names[i + 12] + r);
-    }
-    printf("%0.3s\n", names[19] + o);
-
-    return 0;
-}

File solve.c

-#include <stdio.h>
-#include <string.h>
-
-char *names[] = { "UFU", "URU", "UBU", "ULU", "DFD", "DRD", "DBD", "DLD", "FRF", "FLF", "BRB", "BLB",
-                  "UFRUF", "URBUR", "UBLUB", "ULFUL", "DRFDR", "DFLDF", "DLBDL", "DBRDB" };
-/*
- * index  : 0   1   2   3   4   5   6   7   8   9   10  11
- * corners: UFR URB UBL ULF DRF DFL DLB DBR
- * edges  : UF  UR  UB  UL  DF  DR  DB  DL  FR  FL  BR  BL
- */
-char co[8],             eo[12],            cp[8],              ep[12];
-char co_prune[2187],    eo_prune[2048],    cp_prune[40320],    ep_prune[40320],    ud1_prune[495],    ud2_prune[24];
-int  co_trans[2187][6], eo_trans[2048][6], cp_trans[40320][6], ep_trans[40320][6], ud1_trans[495][6], ud2_trans[24][6];
-
-/*
- * moves are:
- * U U2 U' D D2 D' F F2 F' B B2 B' R  R2 R' L  L2 L'
- * 0 1  2  3 4  5  6 7  8  9 10 11 12 13 14 15 16 17
- */
-int sol[30];
-
-/*
- * groups are:
- * 0 = G0 = <U, D, F , B , R , L >
- * 1 = G1 = <U, D, F2, B2, R2, L2>
- */
-
-char c_cycles[6][4] = {
-	{ 0, 1, 2, 3 }, // U
-	{ 4, 5, 6, 7 }, // D
-	{ 0, 3, 5, 4 }, // F
-	{ 1, 7, 6, 2 }, // B
-	{ 0, 4, 7, 1 }, // R
-	{ 2, 6, 5, 3 }, // L
-};
-char e_cycles[6][4] = {
-	{ 0,  1, 2,  3 }, // U
-	{ 4,  7, 6,  5 }, // D
-	{ 0,  9, 4,  8 }, // F
-	{ 2, 10, 6, 11 }, // B
-	{ 1,  8, 5, 10 }, // R
-	{ 3, 11, 7,  9 }, // L
-};
-char c_twists[6][4] = {
-	{ 0, 0, 0, 0 }, // U
-	{ 0, 0, 0, 0 }, // D
-	{ 2, 1, 2, 1 }, // F
-	{ 1, 2, 1, 2 }, // B
-	{ 1, 2, 1, 2 }, // R
-	{ 1, 2, 1, 2 }, // L
-};
-char e_twists[6][4] = {
-	{ 0, 0, 0, 0 }, // U
-	{ 0, 0, 0, 0 }, // D
-	{ 1, 1, 1, 1 }, // F
-	{ 1, 1, 1, 1 }, // B
-	{ 0, 0, 0, 0 }, // R
-	{ 0, 0, 0, 0 }, // L
-};
-
-/*
- * perform the permutation cycle 1 - 3 times based on move
- * perform the orientation twists on the cubies that are being cycled
- */
-void move_pieces(char *perm, char *orie, char *cycle, char *twist, int mod)
-{
-	char otmp, ptmp, i;
-
-	ptmp = perm[cycle[0]];
-	otmp = orie[cycle[0]];
-	for (i = 0; i < 3; i++) {
-		orie[cycle[i]] = (orie[cycle[i + 1]] + twist[i + 1]) % mod;
-		perm[cycle[i]] =  perm[cycle[i + 1]];
-	}
-	orie[cycle[3]] = (otmp + twist[0]) % mod;
-	perm[cycle[3]] =  ptmp;
-}
-
-/*
- * perform the given move on the array cube
- */
-void do_move(int mv)
-{
-	int face = mv / 3;
-
-	for (mv = mv % 3 + 1; mv; mv--) {
-		move_pieces(cp, co, c_cycles[face], c_twists[face], 3);
-		move_pieces(ep, eo, e_cycles[face], e_twists[face], 2);
-	}
-}
-
-// math functions
-int fact [12] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800 };
-int choose(int n, int k) { return fact[n]/(fact[k] * fact[n - k]); }
-
-/*
- * coordinate functions
- *
- * the ud1 and ud2 coordinates are based on descriptions at http://kociemba.org/math/twophase.htm
- * the oriention and permuation functions are based on descirptions at http://www.jaapsch.net/puzzles/compindx.htm
- *
- * the get functions return the coordinate for the current state of the array cube
- * the set functions set the current state of the array cube to the given coordinate
- */
-
-/*
- * ud1 coordinate
- */
-void set_ud1_coord(int coord)
-{
-	int i, j;
-
-	memset(ep, 0, 12);
-	for (i = 11, j = 4; i >= 0 && j; i--) {
-		if (coord >= choose(i, j - 1)) {
-			coord -= choose(i, j - 1);
-		} else {
-			ep[i] = 8;
-			j--;
-		}
-	}
-}
-
-int get_ud1_coord(void)
-{
-	int i, j = 0, coord = 0;
-
-	for (i = 0; i < 12; i++) {
-		if (ep[i] > 7     ) j++;
-		if (ep[i] < 8 && j) coord += choose(i, j - 1);
-	}
-	return coord;
-}
-
-/*
- * generic orientation coordinate
- */
-void set_o_coord(char *orie, int len, int coord, int mod)
-{
-	int i, s = 0;
-
-	for (i = len - 2; i >= 0; i--) {
-		orie[i] = coord % mod;
-		s = (s - orie[i] + mod) % mod;
-		coord /= mod;
-	}
-	orie[len - 1] = s;
-}
-
-int get_o_coord(char *orie, int len, int mod)
-{
-	int i, coord = 0;
-
-	for (i = 0; i < len - 1; i++)
-		coord = coord * mod + orie[i];
-
-	return coord;
-}
-
-/*
- * specific orientation coordinates
- */
-void set_eo_coord(int coord) { set_o_coord(eo, 12, coord, 2); }
-void set_co_coord(int coord) { set_o_coord(co,  8, coord, 3); }
-
-int get_eo_coord(void) { return get_o_coord(eo, 12, 2); }
-int get_co_coord(void) { return get_o_coord(co,  8, 3); }
-
-/*
- * generic permutation coordinate
- */
-void set_p_coord(char *perm, int len, int coord)
-{
-	int i, j;
-
-	perm[len - 1] = 1;
-
-	for (i = len - 2; i >= 0; i--) {
-		perm[i] = (coord % (len - i)) + 1;
-		coord /= len - i;
-		for (j = i + 1; j < len; j++)
-			if (perm[j] >= perm[i])
-				perm[j]++;
-	}
-}
-
-int get_p_coord(char *perm, int len)
-{
-	int i, j, coord = 0;
-
-	for (i = 0; i < len - 1; i++) {
-		coord *= (len - i);
-		for (j = i + 1; j < len; j++)
-			if (perm[i] > perm[j])
-				coord++;
-	}
-	return coord;
-}
-
-/*
- * specific permutation coordinates
- */
-void set_cp_coord (int coord) { set_p_coord(cp,     8, coord); }
-void set_ep_coord (int coord) { set_p_coord(ep,     8, coord); }
-void set_ud2_coord(int coord) { set_p_coord(ep + 8, 4, coord); }
-
-int get_cp_coord (void) { return get_p_coord(cp,     8); }
-int get_ep_coord (void) { return get_p_coord(ep,     8); }
-int get_ud2_coord(void) { return get_p_coord(ep + 8, 4); }
-
-/*
- * generic pruning table initialization
- */
-void init_prune(int group, int coord, char prune_table[], int trans_table[][6], int mdepth, int depth, int last)
-{
-	int i, mv, old = coord;
-
-	if (depth == mdepth || prune_table[coord] <= depth)
-		return;
-
-	prune_table[coord] = depth;
-
-	for (mv = 0; mv < 18; mv += 3, coord = old) {
-		if (mv / 3 == last / 3)
-			continue;
-		for (i = 0; i < 3; i++) {
-			if (group && mv >= 6 && i) // only want double turns on F, B, R, L in G1
-				break;
-			coord = trans_table[coord][mv / 3];
-			init_prune(group, coord, prune_table, trans_table, mdepth, depth + 1, mv);
-		}
-	}
-}
-
-/*
- * specific pruning table initializations
- */
-void init_prune_tables(void)
-{
-	memset(eo_prune,  127, sizeof(eo_prune ));
-	memset(co_prune,  127, sizeof(co_prune ));
-	memset(ep_prune,  127, sizeof(ep_prune ));
-	memset(cp_prune,  127, sizeof(cp_prune ));
-	memset(ud1_prune, 127, sizeof(ud1_prune));
-	memset(ud2_prune, 127, sizeof(ud2_prune));
-
-	init_prune(0, 0, eo_prune,  eo_trans,  8, 0, -1);
-	init_prune(0, 0, co_prune,  co_trans,  7, 0, -1);
-	init_prune(0, 0, ud1_prune, ud1_trans, 6, 0, -1);
-
-	init_prune(1, 0, cp_prune,  cp_trans, 14, 0, -1);
-	init_prune(1, 0, ep_prune,  ep_trans,  9, 0, -1);
-	init_prune(1, 0, ud2_prune, ud2_trans, 5, 0, -1);
-}
-
-/*
- * generic transition table initialization
- */
-void init_trans(int group, int tran_table[][6], int len, void (*set_coord)(int), int (*get_coord)(void))
-{
-	int i, mv;
-
-	for (i = 0; i < len; i++) {
-		for (mv = 0; mv < 18; mv += 3) {
-			set_coord(i);
-			do_move(mv);
-			if (group && mv >= 6) // only want double turns on F, B, R, L in G1
-				do_move(mv);
-			tran_table[i][mv / 3] = get_coord();
-		}
-	}
-}
-
-/*
- * specific transition table initializations
- */
-void init_trans_tables(void)
-{
-	init_trans(0, eo_trans,  2048,  set_eo_coord,  get_eo_coord );
-	init_trans(0, co_trans,  2187,  set_co_coord,  get_co_coord );
-	init_trans(0, ud1_trans, 495,   set_ud1_coord, get_ud1_coord);
-
-	init_trans(1, cp_trans,  40320, set_cp_coord,  get_cp_coord );
-	init_trans(1, ep_trans,  40320, set_ep_coord,  get_ep_coord );
-	init_trans(1, ud2_trans, 24,    set_ud2_coord, get_ud2_coord);
-}
-
-/*
- * generic phase solver
- */
-int solve(int group, int e_coord, int c_coord, int ud_coord, int depth, int last)
-{
-	int mv, i, e_tmp, c_tmp, ud_tmp, face;
-
-	if (e_coord == 0 && c_coord == 0 && ud_coord == 0) return 1; // success!
-	if (!group && (depth == 0 || eo_prune[e_coord] > depth || co_prune[c_coord] > depth || ud1_prune[ud_coord] > depth)) return 0;
-	if ( group && (depth == 0 || ep_prune[e_coord] > depth || cp_prune[c_coord] > depth || ud2_prune[ud_coord] > depth)) return 0;
-
-	for (mv = face = 0; mv < 18; mv += 3, face = mv / 3) {
-		// no two moves in a row on same face, no move on same axis after U, F, R
-		if (face == last || ((last & 1) == 0 && face == last + 1))
-			continue;
-
-		e_tmp  = e_coord;
-		c_tmp  = c_coord;
-		ud_tmp = ud_coord;
-
-		for (i = 0; i < 3; i++) {
-			e_tmp  = group ? ep_trans [e_tmp ][face] : eo_trans [e_tmp ][face];
-			c_tmp  = group ? cp_trans [c_tmp ][face] : co_trans [c_tmp ][face];
-			ud_tmp = group ? ud2_trans[ud_tmp][face] : ud1_trans[ud_tmp][face];
-
-			if (solve(group, e_tmp, c_tmp, ud_tmp, depth - 1, face)) {
-				sol[(group ? 30 : 12) - depth] = mv + ((group && mv >= 6) ? 1 : i);
-				return 1;
-			}
-			if (group && mv >= 6)
-				break;
-		}
-	}
-	return 0;
-}
-
-void print_move(int mv)
-{
-	char *faces = "UDFBRL", *num = " 2'";
-
-	printf("%c%c ", faces[mv / 3], num[mv % 3]);
-}
-
-/*
- * set array cube from input
- */
-void set_cube(char *cube)
-{
-	char *p, *t, i, j;
-
-	for (i = 0, p = strtok(cube, " \n"); p && i < 12; i++, p = strtok(NULL, " \n")) {
-		for (j = 0; (t = strstr(names[j], p)) == NULL; j++)
-			;
-		ep[i] = j;
-		eo[i] = t - names[j];
-	}
-
-	for (i = 0; p && i < 8; i++, p = strtok(NULL, " \n")) {
-		for (j = 0; (t = strstr(names[j + 12], p)) == NULL; j++)
-			;
-		cp[i] = j;
-		co[i] = t - names[j + 12];
-	}
-}
-
-int main(int argc, char **argv)
-{
-	char buf[128], i;
-
-	init_trans_tables();
-	init_prune_tables();
-
-	while (fgets(buf, sizeof(buf), stdin)) {
-		memset(sol, -1, sizeof(sol));
-		set_cube(buf);
-
-		for (i = 0; solve(0, get_eo_coord(), get_co_coord(), get_ud1_coord(), i, -1) == 0; i++)
-			;
-
-		for (i = 12 - i; i < 12; i++)
-			do_move(sol[i]);
-
-		for (i = 0; solve(1, get_ep_coord(), get_cp_coord(), get_ud2_coord(), i, -1) == 0; i++)
-			;
-
-		// if the last move from phase 1 and first move from phase 2 are on the same face
-		// it will always be a quarter turn then half turn on FBLR
-		if (sol[30 - i] > -1 && sol[30 - i] / 6 == sol[11] / 6) {
-			sol[30 - i] = -1;
-			sol[11] += (sol[11] % 3) ? -2 : 2;
-		}
-
-		for (i = 0; i < 30; i++)
-			if (sol[i] > -1)
-				print_move(sol[i]);
-
-		printf("\n");
-	}
-	return 0;
-}
-
-/* vim: set ts=4 sw=4 noexpandtab : */

File solve.js

-var names = [ "UFU", "URU", "UBU", "ULU", "DFD", "DRD", "DBD", "DLD", "FRF", "FLF", "BRB", "BLB",
-              "UFRUF", "URBUR", "UBLUB", "ULFUL", "DRFDR", "DFLDF", "DLBDL", "DBRDB" ];
-
-var co_trans  = make_array( 2187 * 6);
-var eo_trans  = make_array( 2048 * 6);
-var ud1_trans = make_array(  495 * 6);
-var cp_trans  = make_array(40320 * 6);
-var ep_trans  = make_array(40320 * 6);
-var ud2_trans = make_array(   24 * 6);
-
-var co_prune  = make_array( 2187);
-var eo_prune  = make_array( 2048);
-var ud1_prune = make_array(  495);
-var cp_prune  = make_array(40320);
-var ep_prune  = make_array(40320);
-var ud2_prune = make_array(   24);
-
-var co = make_array( 8);
-var eo = make_array(12);
-var cp = make_array( 8);
-var ep = make_array(12);
-
-var co_coord, eo_coord, ud1_coord;
-var cp_coord, ep_coord, ud2_coord;
-
-var phase_1_moves = make_array(12);
-var phase_2_moves = make_array(18);
-
-var c_cycles = [
-	[ 0, 1, 2, 3 ], // U
-	[ 4, 5, 6, 7 ], // D
-	[ 0, 3, 5, 4 ], // F
-	[ 1, 7, 6, 2 ], // B
-	[ 0, 4, 7, 1 ], // R
-	[ 2, 6, 5, 3 ], // L
-];
-var e_cycles = [
-	[ 0,  1, 2,  3 ], // U
-	[ 4,  7, 6,  5 ], // D
-	[ 0,  9, 4,  8 ], // F
-	[ 2, 10, 6, 11 ], // B
-	[ 1,  8, 5, 10 ], // R
-	[ 3, 11, 7,  9 ], // L
-];
-var c_twists = [
-	[ 0, 0, 0, 0 ], // U
-	[ 0, 0, 0, 0 ], // D
-	[ 2, 1, 2, 1 ], // F
-	[ 1, 2, 1, 2 ], // B
-	[ 1, 2, 1, 2 ], // R
-	[ 1, 2, 1, 2 ], // L
-];
-var e_twists = [
-	[ 0, 0, 0, 0 ], // U
-	[ 0, 0, 0, 0 ], // D
-	[ 1, 1, 1, 1 ], // F
-	[ 1, 1, 1, 1 ], // B
-	[ 0, 0, 0, 0 ], // R
-	[ 0, 0, 0, 0 ], // L
-];
-
-function make_array(len)
-{
-	var array;
-
-	array = new Array();
-	array.length = len;
-	return array;
-}
-
-function move_pieces(perm, orie, cycle, twist, mod)
-{
-	var otmp, ptmp, i;
-
-	ptmp = perm[cycle[0]];
-	otmp = orie[cycle[0]];
-
-	for (i = 0; i < 3; i++) {
-		orie[cycle[i]] = (orie[cycle[i + 1]] + twist[i + 1]) % mod;
-		perm[cycle[i]] = perm[cycle[i + 1]];
-	}
-	orie[cycle[3]] = (otmp + twist[0]) % mod;
-	perm[cycle[3]] = ptmp;
-}
-
-function do_move(mv)
-{
-	var i, face;
-
-	face = Math.floor(mv / 3);
-
-	for (i = 0; i < (mv % 3) + 1; i++) {
-		move_pieces(cp, co, c_cycles[face], c_twists[face], 3);
-		move_pieces(ep, eo, e_cycles[face], e_twists[face], 2);
-	}
-}
-
-function fact(n)
-{
-	var i;
-
-	for (i = 1; n > 1; n--)
-		i *= n;
-
-	return i;
-}
-
-function choose(n, k)
-{
-	return fact(n) / (fact(k) * fact(n - k));
-}
-
-function set_eo_coord(coord)
-{
-	var i;
-
-	eo[11] = 0;
-	for (i = 10; i >= 0; i--, coord >>= 1) {
-		eo[i] = coord & 1;
-		eo[11] ^= eo[i];
-	}
-}
-
-function get_eo_coord()
-{
-	var i, coord;
-
-	for (i = coord = 0; i < 11; i++, coord <<= 1)
-		coord |= eo[i];
-
-	return coord >> 1;
-}
-
-function set_co_coord(coord)
-{
-	var i, p = 729;
-
-	co[7] = 0;
-	for (i = 6; i >= 0; i--, p = Math.floor(p / 3)) {
-		co[i] = Math.floor(coord / p);
-		coord -= co[i] * p;
-		co[7] = (co[7] + 3 - co[i]) % 3;
-	}
-}
-
-function get_co_coord()
-{
-	var i, p, coord;
-
-	for (i = coord = 0, p = 1; i < 7; i++, p *= 3)
-		coord += co[i] * p;
-
-	return coord;
-}
-
-function set_ud1_coord(coord)
-{
-	var i, j;
-
-	for (i = 0; i < 12; i++)
-		ep[i] = 0;
-	for (i = 11, j = 4; i >= 0 && j; i--) {
-		if (coord >= choose(i, j - 1)) {
-			coord -= choose(i, j - 1);
-		} else {
-			ep[i] = 8;
-			j--;
-		}
-	}
-}
-
-function get_ud1_coord()
-{
-	var i, j = 0, coord = 0;
-
-	for (i = 0; i < 12; i++) {
-		if (ep[i] > 7)
-			j++;
-		if (j && ep[i] < 8)
-			coord += choose(i, j - 1);
-	}
-	return coord;
-}
-
-// set a permutation coordinate: cp, ep, ud2
-function set_p_coord(perm, start, len, coord)
-{
-	var val = 076543210;
-	var p = fact(len);
-	var i;
-	for (i = 0; i < len; i++) {
-		p /= (len - i);
-		var v = 3 * Math.floor(coord / p);
-		coord %= p;
-		perm[start + ((val >> v) & 07)] = i ;
-		var m = (1 << v) - 1;
-		val = (val & m) + ((val >> 3) & ~m);
-	}
-}
-function get_p_coord(iperm, start, len)
-{
-        var perm = new Array(8) ;
-	var r = 0;
-	var val = 076543210;
-	var i;
-	var m = len - 1;
-        for (i=0; i<len; i++)
-           perm[iperm[start+i] & m] = i ;
-	for (i = 0; i + 1 < len; i++) {
-		var v = 3 * perm[i];
-		r = (len - i) * r + ((val >> v) & 07);
-		val -= 011111110 << v;
-	}
-	return r;
-}
-
-function set_cp_coord (coord) { set_p_coord(cp, 0, 8, coord); }
-function set_ep_coord (coord) { set_p_coord(ep, 0, 8, coord); }
-function set_ud2_coord(coord) { set_p_coord(ep, 8, 4, coord); }
-
-function get_cp_coord () { return get_p_coord(cp, 0, 8); }
-function get_ep_coord () { return get_p_coord(ep, 0, 8); }
-function get_ud2_coord() { return get_p_coord(ep, 8, 4); }
-
-function get_bits(perm) {
-   var r = 0 ;
-   var i ;
-   for (i=0; i<7; i++)
-      r |= (perm[i] & 4) << i ;
-   return r >> 2 ;
-}
-
-function init_trans2(group, tran_table, len, set_coord, get_coord, perm)
-{
-	var i, j, k, b, t, klim ;
-        var base = new Array(128) ;
-	for (i=0; i<len; i+=24) {
-		set_coord(i) ;
-		b = get_bits(perm) ;
-		if (base[b] == undefined) {
-			base[b] = i ;
-			klim = 24 ;
-		} else {
-			klim = 1 ;
-		}
-		b = base[b] * 6 ;
-		for (k=0; k<klim; k++) {
-			for (j=0; j<6; j++) {
-				set_coord(i + k) ;
-				if (group && j >= 2) {
-					do_move(j*3+1) ;
-				} else {
-					do_move(j*3) ;
-				}
-				tran_table[(i+k)*6+j] = get_coord() ;
-			}
-		}
-		for (j=0; j<6; j++) {
-			t = tran_table[i*6+j] - tran_table[b+j] ;
-			for (k=klim; k<24; k++)
-				tran_table[(i+k)*6+j] = t + tran_table[b+k*6+j] ;
-		}
-	}
-}
-
-function init_trans(group, tran_table, len, set_coord, get_coord)
-{
-	var i, j;
-	for (i = 0; i < len; i++) {
-		for (j = 0; j < 6; j++) {
-			if (tran_table[i * 6 + j] == undefined) {
-				var start = i;
-				var face = j;
-				set_coord(start);
-				while (tran_table[start * 6 + face] == undefined) {
-					if (group && face >= 2) // double turns on F, B, R, L, in G1
-						do_move(3 * face + 1);
-					else
-						do_move(3 * face);
-					var newpos = get_coord();
-					tran_table[start * 6 + face] = newpos;
-					if (len == 40320) {
-						tran_table[(len - 1 - start) * 6 + face] = len - 1 - newpos;
-					}
-					start = newpos;
-					face = 0;
-					while (face < 5 && tran_table[start * 6 + face] != undefined) {
-						face++;
-					}
-				}
-			}
-		}
-	}
-}
-
-function init_trans_tables()
-{
-	init_trans(0, eo_trans, 2048, set_eo_coord,  get_eo_coord );
-	init_trans(0, co_trans, 2187, set_co_coord,  get_co_coord );
-	init_trans(0, ud1_trans, 495, set_ud1_coord, get_ud1_coord);
-
-	init_trans2(1, ep_trans, 40320, set_ep_coord,  get_ep_coord, ep);
-	init_trans2(1, cp_trans, 40320, set_cp_coord,  get_cp_coord, cp);
-	init_trans(1, ud2_trans,   24, set_ud2_coord, get_ud2_coord);
-}
-
-function init_prune(group, coord, prune_table, tran_table, mdepth, depth, last)
-{
-	var i, mv;
-
-	if (depth == mdepth)
-		return;
-	prune_table[coord] = depth;
-
-	for (mv = 0; mv < 18; mv += 3) {
-		var thisface = mv / 3;
-		if (thisface == last || ((last & 1) == 0 && thisface == last + 1)) // don't do two moves in a row on the same face
-			continue;
-		var coord2 = coord;
-		for (i = 0; i < 3; i++) {
-			if (group && mv >= 6 && i) // double turns in G1
-				break;
-			coord2 = tran_table[coord2 * 6 + thisface];
-			if (!(prune_table[coord2] <= depth + 1))
-				init_prune(group, coord2, prune_table, tran_table, mdepth, depth + 1, thisface);
-		}
-	}
-}
-
-function init_prune2(group, prune_table, tran_table, mdepth)
-{
-	var i;
-	for (i = prune_table.length - 1; i >= 0; i--) {
-		prune_table[i] = mdepth;
-	}
-	init_prune(group, 0, prune_table, tran_table, mdepth - 1, 0, 18);
-}
-
-function init_prune_tables()
-{
-	init_prune2(0, eo_prune,  eo_trans,  8);
-	init_prune2(0, co_prune,  co_trans,  7);
-	init_prune2(0, ud1_prune, ud1_trans, 6);
-
-	init_prune2(1, ep_prune,  ep_trans,  9);
-	init_prune2(1, cp_prune,  cp_trans, 14);
-	init_prune2(1, ud2_prune, ud2_trans, 5);
-}
-
-function phase_1(eo_coord, co_coord, ud1_coord, depth, last)
-{
-	var face, i;
-
-	if (depth == 0)
-		return (eo_coord == 0 && co_coord == 0 && ud1_coord == 0) ;
-	depth-- ;
-	for (face=0; face<6; face++) {
-		// no two moves in a row on same face, no move on same axis after U, F, R
-		if (face == last || (face == last + 1 && (last & 1) == 0))
-			continue;
-		var eo_coord2  = eo_coord;
-		var co_coord2  = co_coord;
-		var ud1_coord2 = ud1_coord;
-		for (i = 0; i < 3; i++) {
-			eo_coord2  = eo_trans [eo_coord2  * 6 + face];
-			co_coord2  = co_trans [co_coord2  * 6 + face];
-			ud1_coord2 = ud1_trans[ud1_coord2 * 6 + face];
-			if (co_prune[co_coord2] <= depth &&
-                            eo_prune[eo_coord2] <= depth &&
-                            ud1_prune[ud1_coord2] <= depth &&
-	                    phase_1(eo_coord2, co_coord2, ud1_coord2, depth, face)) {
-				phase_1_moves[depth] = 3*face + i;
-				return 1;
-			}
-		}
-	}
-	return 0;
-}
-
-function phase_2(ep_coord, cp_coord, ud2_coord, depth, last)
-{
-	var mv, face, i;
-
-	if (depth == 0)
-		return (ep_coord == 0 && cp_coord == 0 && ud2_coord == 0) ;
-	depth-- ;
-	for (face=0; face<6; face++) {
-		// no two moves in a row on same face, no move on same axis after U, F, R
-		if (face == last || (face == last + 1 && (last & 1) == 0))
-			continue;
-		var ep_coord2  = ep_coord;
-		var cp_coord2  = cp_coord;
-		var ud2_coord2 = ud2_coord;
-		for (i=0; i<3; i++) {
-			ep_coord2  = ep_trans [ep_coord2  * 6 + face];
-			cp_coord2  = cp_trans [cp_coord2  * 6 + face];
-			ud2_coord2 = ud2_trans[ud2_coord2 * 6 + face];
-			if (ep_prune[ep_coord2] <= depth &&
-                            cp_prune[cp_coord2] <= depth &&
-                            ud2_prune[ud2_coord2] <= depth &&
-	                    phase_2(ep_coord2, cp_coord2, ud2_coord2, depth, face)) {
-				phase_2_moves[depth] = 3*face + (face >= 2 ? 1 : i) ;
-				return 1;
-			}
-			if (face >= 2)
-				break;
-		}
-	}
-	return 0;
-}
-
-function set_cube(cube)
-{
-	var i, j, p, t;
-
-	for (i = 0; i < 12; i++) {
-		p = cube.substring(i * 3, i * 3 + 2);
-		for (j = 0; j < 12; j++) {
-			if ((t = names[j].indexOf(p)) != -1) {
-				ep[i] = j;
-				eo[i] = t;
-			}
-		}
-	}
-
-	for (i = 0; i < 8; i++) {
-		p = cube.substring((12 * 3) + (i * 4), (12 * 3) + (i * 4) + 3);
-		for (j = 0; j < 8; j++) {
-			if ((t = names[j + 12].indexOf(p)) != -1) {
-				cp[i] = j;
-				co[i] = t;
-			}
-		}
-	}
-
-	co_coord  = get_co_coord();
-	eo_coord  = get_eo_coord();
-	ud1_coord = get_ud1_coord();
-}
-
-function print_move(mv)
-{
-	var faces = [ "U", "D", "F", "B", "R", "L" ];
-	var num   = [ "", "2", "'" ];
-	if (mv == undefined) return "";
-	return faces[Math.floor(mv / 3)] + num[mv % 3] + " ";
-}
-
-function init_cube()
-{
-	var i;
-
-	ep_coord = cp_coord = ud2_coord = 0;
-
-	init_trans_tables();
-
-	init_prune_tables();
-}
-
-function benchmark()
-{
-	var very_beg, very_end, beg, end, res = "";
-	var cubes = [
-		"BD FU FR DF LB LF RU LU BR DL RD BU RDB RFD BLU LFU LDF LBD BUR RUF",
-		"RB DL LF FR UL BL UB UF FD DR BD UR BRD FRU FLD RFD RBU ULF DLB BLU",
-		"DL BD LU DR UR FD BR FL RF LB UB FU LDF BRD DLB DRF LFU UBL RUF URB",
-		"FU LB LD FR DR LU RU UB FD FL RB BD LUB RUF RBU DRF DBR BDL ULF LDF",
-	];
-
-	co_trans  = make_array( 2187 * 6);
-	eo_trans  = make_array( 2048 * 6);
-	ud1_trans = make_array(  495 * 6);
-	cp_trans  = make_array(40320 * 6);
-	ep_trans  = make_array(40320 * 6);
-	ud2_trans = make_array(   24 * 6);
-	
-	co_prune  = make_array( 2187);
-	eo_prune  = make_array( 2048);
-	ud1_prune = make_array(  495);
-	cp_prune  = make_array(40320);
-	ep_prune  = make_array(40320);
-	ud2_prune = make_array(   24);
-
-	very_beg = beg = new Date();
-	init_trans_tables();
-	end = new Date();
-	res += "initializing transition tables took " + (end - beg) + " ms<br>";
-
-	beg = new Date();
-	init_prune_tables();
-	end = new Date();
-	res += "initializing pruning tables took " + (end - beg) + " ms<br>";
-	res += "<br>";
-
-	for (i = 0; i < cubes.length; i++) {
-		res += "solving cube " + i + " (" + cubes[i] + ")<br>";
-		res += solvecube_benchmark(cubes[i]);
-		res += "<br>";
-	}
-
-	very_end = new Date();
-
-	res += "Total time: " + (very_end - very_beg) + " ms";
-
-	return res;
-}
-
-function solvecube_benchmark(pos) {
-	phase_1_moves = make_array(12);
-	phase_2_moves = make_array(18);
-	set_cube(pos);
-	var i, beg, end;
-	var sol = "";
-
-	beg = new Date();
-	for (i = 0; phase_1(eo_coord, co_coord, ud1_coord, i, 6) == 0; i++) {}
-	end = new Date();
-	sol += "phase 1 searched to depth " + i + " and took " + (end - beg) + " ms<br>";
-	for (i = 11; i > -1; i--)
-		if (phase_1_moves[i] != undefined)
-			do_move(phase_1_moves[i]);
-
-	ep_coord  = get_ep_coord();
-	cp_coord  = get_cp_coord();
-	ud2_coord = get_ud2_coord();
-
-	beg = new Date();
-	for (i = 0; phase_2(ep_coord, cp_coord, ud2_coord, i, 18) == 0; i++) {}
-	end = new Date();
-	sol += "phase 2 searched to depth " + i + " and took " + (end - beg) + " ms<br>";
-	return sol;
-}
-
-function solvecube(pos, invert) {
-	phase_1_moves = make_array(12);
-	phase_2_moves = make_array(18);
-	set_cube(pos);
-	var i, sol = "";
-
-	for (i = 0; phase_1(eo_coord, co_coord, ud1_coord, i, 6) == 0; i++) {}
-	for (i = 11; i > -1; i--)
-		if (phase_1_moves[i] != undefined)
-			do_move(phase_1_moves[i]);
-
-	ep_coord  = get_ep_coord();
-	cp_coord  = get_cp_coord();
-	ud2_coord = get_ud2_coord();
-
-	for (i = 0; phase_2(ep_coord, cp_coord, ud2_coord, i, 18) == 0; i++) {}
-
-	i--;
-	if (Math.floor(phase_1_moves[0] / 6) == Math.floor(phase_2_moves[i] / 6)) {
-		phase_1_moves[0] = phase_1_moves[0] - (phase_1_moves[0] % 3) + ((phase_1_moves[0] % 3) ? 0 : 2);
-		phase_2_moves[i] = undefined;
-	}
-
-	if (invert) {
-		for (i = 0; i < 18; i++)
-			if (phase_2_moves[i] != undefined)
-				sol += print_move(phase_2_moves[i] + 2 - 2 * (phase_2_moves[i] % 3));
-		for (i = 0; i < 12; i++)
-			if (phase_1_moves[i] != undefined)
-				sol += print_move(phase_1_moves[i] + 2 - 2 * (phase_1_moves[i] % 3));
-	} else {
-		for (i = 11; i > -1; i--)
-			sol += print_move(phase_1_moves[i]);
-		for (i = 17; i > -1; i--)
-			sol += print_move(phase_2_moves[i]);
-	}
-	return sol;
-}
-
-/* vim: set ts=4 sw=4 noexpandtab : */

File stand_alone/rand.c

+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/time.h>
+
+char *names[] = { "UFU", "URU", "UBU", "ULU", "DFD", "DRD", "DBD", "DLD", "FRF", "FLF", "BRB", "BLB",
+                  "UFRUF", "URBUR", "UBLUB", "ULFUL", "DRFDR", "DFLDF", "DLBDL", "DBRDB" };
+
+int main()
+{
+    char *tmp;
+    long int r;
+    int i, o;
+
+    struct timeval tv;
+    gettimeofday(&tv, NULL);
+    srandom(tv.tv_usec);
+
+    for (i = 0; i < 12; i++) {
+	r = random() % 12;
+	if (r == i) {
+	    i--;
+	    continue;
+	}
+	tmp = names[i];
+	names[i] = names[r];
+	names[r] = tmp;
+    }
+
+    for (i = 0; i < 8; i++) {
+	r = random() % 8;
+	if (r == i) {
+	    i--;
+	    continue;
+	}
+	tmp = names[i + 12];
+	names[i + 12] = names[r + 12];
+	names[r + 12] = tmp;
+    }
+
+    o = 0;
+    for (i = 0; i < 11; i++) {
+	r = random() % 2;
+	o = (o + r) % 2;
+	printf("%0.2s ", names[i] + r);
+    }
+    printf("%0.2s ", names[11] + o);
+
+    o = 0;
+    for (i = 0; i < 7; i++) {
+	r = random() % 3;
+	o = (o + 3 - r) % 3;
+	printf("%0.3s ", names[i + 12] + r);
+    }
+    printf("%0.3s\n", names[19] + o);
+
+    return 0;
+}

File stand_alone/solve.c

+#include <stdio.h>
+#include <string.h>
+
+char *names[] = { "UFU", "URU", "UBU", "ULU", "DFD", "DRD", "DBD", "DLD", "FRF", "FLF", "BRB", "BLB",
+                  "UFRUF", "URBUR", "UBLUB", "ULFUL", "DRFDR", "DFLDF", "DLBDL", "DBRDB" };
+/*
+ * index  : 0   1   2   3   4   5   6   7   8   9   10  11
+ * corners: UFR URB UBL ULF DRF DFL DLB DBR
+ * edges  : UF  UR  UB  UL  DF  DR  DB  DL  FR  FL  BR  BL
+ */
+char co[8],             eo[12],            cp[8],              ep[12];
+char co_prune[2187],    eo_prune[2048],    cp_prune[40320],    ep_prune[40320],    ud1_prune[495],    ud2_prune[24];
+int  co_trans[2187][6], eo_trans[2048][6], cp_trans[40320][6], ep_trans[40320][6], ud1_trans[495][6], ud2_trans[24][6];
+
+/*
+ * moves are:
+ * U U2 U' D D2 D' F F2 F' B B2 B' R  R2 R' L  L2 L'
+ * 0 1  2  3 4  5  6 7  8  9 10 11 12 13 14 15 16 17
+ */
+int sol[30];
+
+/*
+ * groups are:
+ * 0 = G0 = <U, D, F , B , R , L >
+ * 1 = G1 = <U, D, F2, B2, R2, L2>
+ */
+
+char c_cycles[6][4] = {
+	{ 0, 1, 2, 3 }, // U
+	{ 4, 5, 6, 7 }, // D
+	{ 0, 3, 5, 4 }, // F
+	{ 1, 7, 6, 2 }, // B
+	{ 0, 4, 7, 1 }, // R
+	{ 2, 6, 5, 3 }, // L
+};
+char e_cycles[6][4] = {
+	{ 0,  1, 2,  3 }, // U
+	{ 4,  7, 6,  5 }, // D
+	{ 0,  9, 4,  8 }, // F
+	{ 2, 10, 6, 11 }, // B
+	{ 1,  8, 5, 10 }, // R
+	{ 3, 11, 7,  9 }, // L
+};
+char c_twists[6][4] = {
+	{ 0, 0, 0, 0 }, // U
+	{ 0, 0, 0, 0 }, // D
+	{ 2, 1, 2, 1 }, // F
+	{ 1, 2, 1, 2 }, // B
+	{ 1, 2, 1, 2 }, // R
+	{ 1, 2, 1, 2 }, // L
+};
+char e_twists[6][4] = {
+	{ 0, 0, 0, 0 }, // U
+	{ 0, 0, 0, 0 }, // D
+	{ 1, 1, 1, 1 }, // F
+	{ 1, 1, 1, 1 }, // B
+	{ 0, 0, 0, 0 }, // R
+	{ 0, 0, 0, 0 }, // L
+};
+
+/*
+ * perform the permutation cycle 1 - 3 times based on move
+ * perform the orientation twists on the cubies that are being cycled
+ */
+void move_pieces(char *perm, char *orie, char *cycle, char *twist, int mod)
+{
+	char otmp, ptmp, i;
+
+	ptmp = perm[cycle[0]];
+	otmp = orie[cycle[0]];
+	for (i = 0; i < 3; i++) {
+		orie[cycle[i]] = (orie[cycle[i + 1]] + twist[i + 1]) % mod;
+		perm[cycle[i]] =  perm[cycle[i + 1]];
+	}
+	orie[cycle[3]] = (otmp + twist[0]) % mod;
+	perm[cycle[3]] =  ptmp;
+}
+
+/*
+ * perform the given move on the array cube
+ */
+void do_move(int mv)
+{
+	int face = mv / 3;
+
+	for (mv = mv % 3 + 1; mv; mv--) {
+		move_pieces(cp, co, c_cycles[face], c_twists[face], 3);
+		move_pieces(ep, eo, e_cycles[face], e_twists[face], 2);
+	}
+}
+
+// math functions
+int fact [12] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800 };
+int choose(int n, int k) { return fact[n]/(fact[k] * fact[n - k]); }
+
+/*
+ * coordinate functions
+ *
+ * the ud1 and ud2 coordinates are based on descriptions at http://kociemba.org/math/twophase.htm
+ * the oriention and permuation functions are based on descirptions at http://www.jaapsch.net/puzzles/compindx.htm
+ *
+ * the get functions return the coordinate for the current state of the array cube
+ * the set functions set the current state of the array cube to the given coordinate
+ */
+
+/*
+ * ud1 coordinate
+ */
+void set_ud1_coord(int coord)
+{
+	int i, j;
+
+	memset(ep, 0, 12);
+	for (i = 11, j = 4; i >= 0 && j; i--) {
+		if (coord >= choose(i, j - 1)) {
+			coord -= choose(i, j - 1);
+		} else {
+			ep[i] = 8;
+			j--;
+		}
+	}
+}
+
+int get_ud1_coord(void)
+{
+	int i, j = 0, coord = 0;
+
+	for (i = 0; i < 12; i++) {
+		if (ep[i] > 7     ) j++;
+		if (ep[i] < 8 && j) coord += choose(i, j - 1);
+	}
+	return coord;
+}
+
+/*
+ * generic orientation coordinate
+ */
+void set_o_coord(char *orie, int len, int coord, int mod)
+{
+	int i, s = 0;
+
+	for (i = len - 2; i >= 0; i--) {
+		orie[i] = coord % mod;
+		s = (s - orie[i] + mod) % mod;
+		coord /= mod;
+	}
+	orie[len - 1] = s;
+}
+
+int get_o_coord(char *orie, int len, int mod)
+{
+	int i, coord = 0;
+
+	for (i = 0; i < len - 1; i++)
+		coord = coord * mod + orie[i];
+
+	return coord;
+}
+
+/*
+ * specific orientation coordinates
+ */
+void set_eo_coord(int coord) { set_o_coord(eo, 12, coord, 2); }
+void set_co_coord(int coord) { set_o_coord(co,  8, coord, 3); }
+
+int get_eo_coord(void) { return get_o_coord(eo, 12, 2); }
+int get_co_coord(void) { return get_o_coord(co,  8, 3); }
+
+/*
+ * generic permutation coordinate
+ */
+void set_p_coord(char *perm, int len, int coord)
+{
+	int i, j;
+
+	perm[len - 1] = 1;
+
+	for (i = len - 2; i >= 0; i--) {
+		perm[i] = (coord % (len - i)) + 1;
+		coord /= len - i;
+		for (j = i + 1; j < len; j++)
+			if (perm[j] >= perm[i])
+				perm[j]++;
+	}
+}
+
+int get_p_coord(char *perm, int len)
+{
+	int i, j, coord = 0;
+
+	for (i = 0; i < len - 1; i++) {
+		coord *= (len - i);
+		for (j = i + 1; j < len; j++)
+			if (perm[i] > perm[j])
+				coord++;
+	}
+	return coord;
+}
+
+/*
+ * specific permutation coordinates
+ */
+void set_cp_coord (int coord) { set_p_coord(cp,     8, coord); }
+void set_ep_coord (int coord) { set_p_coord(ep,     8, coord); }
+void set_ud2_coord(int coord) { set_p_coord(ep + 8, 4, coord); }
+
+int get_cp_coord (void) { return get_p_coord(cp,     8); }
+int get_ep_coord (void) { return get_p_coord(ep,     8); }
+int get_ud2_coord(void) { return get_p_coord(ep + 8, 4); }
+
+/*
+ * generic pruning table initialization
+ */
+void init_prune(int group, int coord, char prune_table[], int trans_table[][6], int mdepth, int depth, int last)
+{
+	int i, mv, old = coord;
+
+	if (depth == mdepth || prune_table[coord] <= depth)
+		return;
+
+	prune_table[coord] = depth;
+
+	for (mv = 0; mv < 18; mv += 3, coord = old) {
+		if (mv / 3 == last / 3)
+			continue;
+		for (i = 0; i < 3; i++) {
+			if (group && mv >= 6 && i) // only want double turns on F, B, R, L in G1
+				break;
+			coord = trans_table[coord][mv / 3];
+			init_prune(group, coord, prune_table, trans_table, mdepth, depth + 1, mv);
+		}
+	}
+}
+
+/*
+ * specific pruning table initializations
+ */
+void init_prune_tables(void)
+{
+	memset(eo_prune,  127, sizeof(eo_prune ));
+	memset(co_prune,  127, sizeof(co_prune ));
+	memset(ep_prune,  127, sizeof(ep_prune ));
+	memset(cp_prune,  127, sizeof(cp_prune ));
+	memset(ud1_prune, 127, sizeof(ud1_prune));
+	memset(ud2_prune, 127, sizeof(ud2_prune));
+
+	init_prune(0, 0, eo_prune,  eo_trans,  8, 0, -1);
+	init_prune(0, 0, co_prune,  co_trans,  7, 0, -1);
+	init_prune(0, 0, ud1_prune, ud1_trans, 6, 0, -1);
+
+	init_prune(1, 0, cp_prune,  cp_trans, 14, 0, -1);
+	init_prune(1, 0, ep_prune,  ep_trans,  9, 0, -1);
+	init_prune(1, 0, ud2_prune, ud2_trans, 5, 0, -1);
+}
+
+/*
+ * generic transition table initialization
+ */
+void init_trans(int group, int tran_table[][6], int len, void (*set_coord)(int), int (*get_coord)(void))
+{
+	int i, mv;
+
+	for (i = 0; i < len; i++) {
+		for (mv = 0; mv < 18; mv += 3) {
+			set_coord(i);
+			do_move(mv);
+			if (group && mv >= 6) // only want double turns on F, B, R, L in G1
+				do_move(mv);
+			tran_table[i][mv / 3] = get_coord();
+		}
+	}
+}
+
+/*
+ * specific transition table initializations
+ */
+void init_trans_tables(void)
+{
+	init_trans(0, eo_trans,  2048,  set_eo_coord,  get_eo_coord );
+	init_trans(0, co_trans,  2187,  set_co_coord,  get_co_coord );
+	init_trans(0, ud1_trans, 495,   set_ud1_coord, get_ud1_coord);
+
+	init_trans(1, cp_trans,  40320, set_cp_coord,  get_cp_coord );
+	init_trans(1, ep_trans,  40320, set_ep_coord,  get_ep_coord );
+	init_trans(1, ud2_trans, 24,    set_ud2_coord, get_ud2_coord);
+}
+