Skip to content

Instantly share code, notes, and snippets.

@aemkei

aemkei/LICENSE.txt

Forked from 140bytes/LICENSE.txt
Created November 13, 2011 21:06
Show Gist options
  • Save aemkei/1362710 to your computer and use it in GitHub Desktop.
Save aemkei/1362710 to your computer and use it in GitHub Desktop.
Download ZIP
Rubik's Pocket Cube Solver - 140byt.es
Raw
README.md

Rubik's Pocket Cube Solver - 140byt.es

Solves Rubik's Pocket Cube (2x2x2) by using a simple brute force algorithm in only 100 bytes.

Demos:

You have to pass two movement instructions:

        TURN FRONT FACE CW:           ROTATE AROUND Y-AXIS:
          
          
              00 01                           01 03
              07 05                           00 02
                                              
      04 16   10 08   02 13           23 22   04 05   08 09
      06 17   11 09   03 15           21 20   06 07   10 11
                                      
              14 12                           18 16
              18 19                           19 17
                                              
              20 21                           15 14
              22 23                           13 12

This will solve the cube in less than a minute (~10.000.000 moves).

The same algorithm may be used to solve the original 3x3x3 cube, but it would take ages to find a solution.

For more information

See the 140byt.es site for a showcase of entries (built itself using 140-byte entries!), and follow @140bytes on Twitter.

To learn about byte-saving hacks for your own code, or to contribute what you've learned, head to the wiki.

140byt.es is brought to you by Jed Schmidt, with help from Alex Kloss. It was inspired by work from Thomas Fuchs and Dustin Diaz.

Raw
annotated.js
function(
a, // input layout
b, // 1st movement
c, // 2nd movement
d, // placeholder
e // placeholder
){
for ( // cycle though all stickers
b = Math.random( // get random instruction
e = [ // create output layout
d = 24 // 6 faces * 4 stickers to check
]
) < .5 ? c : b; // reassign movement for later usage
d--;
e[d] = a[b[d]] // move sticker based on instruction
)
c |= a[d] ^ a[d&28]; // set "solved" flag
// if sticker's color on face do not match
return [ // return state
c, // ... "false" if solved
e // modified layout
]
}
Raw
index.js
function(a,b,c,d,e){for(b=Math.random(e=[d=24])<.5?c:b;d--;e[d]=a[b[d]])c|=a[d]^a[d&28];return[c,e]}
Raw
LICENSE.txt
DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
Version 2, December 2004
Copyright (C) 2011 YOUR_NAME_HERE <YOUR_URL_HERE>
Everyone is permitted to copy and distribute verbatim or modified
copies of this license document, and changing it is allowed as long
as the name is changed.
DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
0. You just DO WHAT THE FUCK YOU WANT TO.
Raw
package.json
{
"name": "rubik",
"description": "Solves a Rubik's Pocket Cube.",
"keywords": [
"rubik",
"pocket",
"cube",
"solve",
"algorithm"
]
}
Raw
test.html
<!DOCTYPE html>
<title>Rubik's Pocket Cube Solver - 140byt.es</title>
<style type="text/css" media="screen">
body {
font-family: Arial;
font-size: 12px;
padding: 10px;
}
span {
display: inline-block;
width: 20px;
height: 20px;
margin: -1px;
border: 1px solid black;
text-align: center;
line-height: 20px;
overflow: hidden;
vertical-align: top;
}
#output {
position: relative;
height: 260px;
}
#output div {
position: absolute;
}
#side_0 { top: 0; left: 44px; }
#side_1 { top: 44px; left: 0; }
#side_2 { top: 44px; left: 44px; }
#side_3 { top: 44px; left: 88px; }
#side_4 { top: 88px; left: 44px; }
#side_5 { top: 132px; left: 44px; }
#output div {
width: 44px; height: 44px;
}
</style>
<div id="output"></div>
<div id="counter"></div>
<a href="https://gist.github.com/1362710">Source Code</a>
<script>
var rubik = function(a,b,c,d,e){for(b=Math.random(e=[d=24])<.5?c:b;d--;e[d]=a[b[d]])c|=a[d]^a[d&28];return[c,e]},
turn = [01,03,00,02, 23,22,21,20, 04,05,06,07, 08,09,10,11, 18,16,19,17, 15,14,13,12],
spin = [00,01,07,05, 04,16,06,17, 10,08,11,09, 02,13,03,15, 14,12,18,19, 20,21,22,23],
scrambled = [0,1,5,4, 3,3,0,5, 4,3,0,1, 2,2,2,5, 1,4,5,4, 3,1,2,0],
output = document.getElementById("output"),
counter = document.getElementById("counter"),
start = new Date(),
count = 0,
solved = false,
input = scrambled,
loopStart,
interval;
function draw(data){
var div, span, value, color,
colors = ["red", "blue", "white", "green", "orange", "yellow"]
output.innerHTML = "";
for (var i=0;i<24;i++){
side = Math.floor(i/4);
color = data[i];
if (i%4 == 0){
div = document.createElement("div");
div.id = "side_" + side;
output.appendChild(div);
}
span = document.createElement("span");
span.innerHTML = color;
div.appendChild(span);
span.style.backgroundColor = colors[color];
}
counter.innerHTML = counter.innerHTML = count + " moves " +
"(" + ~~((loopStart - start)/1000) + " sec)";
}
function next(){
var state;
loopStart = new Date();
while (!solved && (new Date() - loopStart) < 1000){
state = rubik(input, turn, spin);
solved = !state[0];
if(!solved) {
count++;
input = state[1]
} else {
draw(input);
alert("solved");
}
}
if (!solved) {
draw(input);
interval = setTimeout(next, 1);
}
};
next();
</script>
@tkissing
Copy link

I'm speechless.

@jed
Copy link

jed commented Nov 16, 2011

@aemkei, how hard would it be to post a 3x3x3 solver example? even if it takes too long to solve, i still think it would be even more impressive just watching the tiles change...

@aemkei
Copy link
Author

aemkei commented Nov 16, 2011

@jed: I run this code in my office for more than day: http://jsfiddle.net/aemkei/n2AwP/show/ but stopped it after about 3.000.000.000 moves.

It's still <140 bytes but I'm not sure if it will ever solve the cube.

@pvdz
Copy link

pvdz commented Nov 16, 2011

Alright, a few things:

Refactored the setting of flag (c), 122 bytes:

function(a,b,c,d,e,f){b=Math.random()<.5?c:b
for(f=[e=24];e--;f[e]=a[b[e]])c|=(a[e]>>2!=a[(e>>2)*4]>>2)
c||d(a)
return f
}

You could also just return an array with the three elements rather than the whole callback thing...

return [c,a,f];

And do the flag checking and callback calling in the "controller" code. That by itself reduces the code to 119 bytes.

Also, props on the test page. I like it :)

@pvdz
Copy link

pvdz commented Nov 16, 2011

Oh PS it solves the cube, both the original and my version. I checked a few times. Takes between 1M and 4M on my machine, <10sec. Except for this one time :p Sometimes you just need to refresh it or wait it out.

@tsaniel
Copy link

tsaniel commented Nov 16, 2011

What about

function(a,b,c,d,e,f){for(b=Math.random(f=[e=24])<.5?c:b;e--;f[e]=a[b[e]])c|=a[e]>>2^a[e/4<<2]>>2;return!c&&d(a),f}

?
Not sure if it works correctly.

Updated.

@aemkei
Copy link
Author

aemkei commented Nov 16, 2011

Hey @tsaniel it works! I merged it with @qfox suggestion down to 109 bytes:

function(a,b,c,e,f){for(b=Math.random(f=[e=24])<.5?c:b;e--;f[e]=a[b[e]])c|=a[e]>>2^a[e/4<<2]>>2;return[!c,f]}

@p01
Copy link

p01 commented Nov 17, 2011

105 bytes ?

function(a,b,c,e,f){for(b=Math.random(f=[e=24])<.5?c:b;e--;f[e]=a[b[e]])c|=(a[e]^a[e&20])/4;return[!c,f]}

@pvdz
Copy link

pvdz commented Nov 17, 2011

Why would you waste a byte on inverting the flag (!c) when you could just assert the outcome inverted? I dont get it...

@pvdz
Copy link

pvdz commented Nov 17, 2011

@p01: actually why would you even /4 the result if all you care about is a zero or non-zero result? Seems like an idle operation and a waste of 4 bytes, no?

@p01
Copy link

p01 commented Nov 17, 2011

@qfox: Nope. You forgot the |= which does cast the result of (a[e]^a[e&20])/4 to an integer. We care if results are both the same multiple of 4 ;)

OTOH, we could save one ton of bytes if we were looking for a specific orientation of the cube: The orientation where a[e]^e is always 0; It would most likely take longer to solve the cube but would lead us to this 95 bytes implementation.

function(a,b,c,e,f){for(b=Math.random(f=[e=24])<.5?c:b;e--;f[e]=a[b[e]])c|=a[e]^e;return[!c,f]}

@aemkei
Copy link
Author

aemkei commented Nov 17, 2011

We could also save ~8 bytes by using colors instead of index values in the scrambled and output array:

[03,05,21,17, 12,15,01,22, 19,14,00,07, 11,08,10,20, 04,16,23,18, 13,06,09,02] // old
[ 0, 1, 5, 4,  3, 3, 0, 5,  4, 3, 0, 1,  2, 2, 2, 5,  1, 4, 5, 4,  3, 1, 2, 0] // new

... and then use something like a[e]^a[e/4<<2] to compare the colors.

@aemkei
Copy link
Author

aemkei commented Nov 17, 2011

Maybe we get the code down to ~80 bytes to include an encoded (toString(25)) version of the moves:

[00,01,07,05, 04,16,06,17, 10,08,11,09, 02,13,03,15, 14,12,18,19, 20,21,22,23] // old
"01754g6ha8b92d3fecijklmn" // new

[01,03,00,02, 23,22,21,20, 04,05,06,07, 08,09,10,11, 18,16,19,17, 15,14,13,12] // old
"1302nmlk456789abigjhfedc" // new

@p01
Copy link

p01 commented Nov 17, 2011

Actually, using colors sounds more correct than using indexes everywhere.

a[e]^a[e&20] is 2 bytes shorter than a[e]^a[e/4<<2]

@aemkei
Copy link
Author

aemkei commented Nov 17, 2011

Okay, here is another suggestion that will slow things down but results into 89 bytes:

Replace: Math.random()<.5 with new Date%2

function(a,b,c,e,f){for(b=new Date%2?c:b,f=[e=24];e--;f[e]=a[b[e]])c|=a[e]^e;return[c,f]}

@p01
Copy link

p01 commented Nov 17, 2011

My desktop computer can run this function almost a thousand times per millisecond. The new Date%2 approach is gonna kill the overall performance.

@aemkei
Copy link
Author

aemkei commented Nov 18, 2011

Okay, I reverted my new Date% and a[e]^e to care about performance and work with all correct solutions.
@p01 Using e&20 instead of e/4<<2 works only if e<7.

Now back to 102bytes:

function(a,b,c,d,e){for(b=Math.random(e=[d=24])<.5?c:b;d--;e[d]=a[b[d]])c|=a[d]^a[d/4<<2];return[c,e]}

@p01
Copy link

p01 commented Nov 18, 2011

How did I manage to get that wrong ? o_O

d/4<<2 is not equivalent to d&20 but to d&28 for values of d in the range [ 0; 24 [
Sorry, so 100 bytes ?

function(a,b,c,d,e){for(b=Math.random(e=[d=24])<.5?c:b;d--;e[d]=a[b[d]])c|=a[d]^a[d&28];return[c,e]}

@aemkei
Copy link
Author

aemkei commented Nov 18, 2011

@p01: Nice move!

@p01
Copy link

p01 commented Nov 20, 2011

Using a color index instead of just an index, enforcing a target orientation of cube saves an extra 4 bytes, bringing us down to 96 bytes:

function(a,b,c,d,e){for(b=Math.random(e=[d=24])<.5?c:b;d--;e[d]=a[b[d]])c|=a[d]^d/4;return[c,e]}

Still far from being able to fit the movement instruction inside the function though :\

@aemkei
Copy link
Author

aemkei commented Nov 21, 2011

How about replacing the "brute force" attempt with trying all possible movements one by one? This might save 11 bytes in Math.random.

Something like counting from 0 to Infinity and run the method with a movement based on the reversed binary index.

1 => [1]          => spin  
2 => [1,0]        => turn, spin
3 => [1,1]        => spin, spin
4 => [1,0,0]      => turn, turn, spin
5 => [1,0,1]      => spin, turn, spin
6 => [1,1,1]      => spin, spin, spin
...
20 => [1,0,1,0,0] => turn, turn, spin, turn, spin 
21 => [1,0,1,0,1] => spin, turn, spin, turn, spin 
...

... and then stop at the first correct solution. This might also return the shortest path.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment