search

thewca / tnoodle-lib

scrambling code portion of TNoodle
GNU General Public License v3.0
39 stars 15 forks source link

Optimize 444 for javascript #14

Open jfly opened 11 years ago

jfly commented 11 years ago

Right now, 4x4 is the only scrambler that behaves differently in tnoodlejs than tnoodle.

jfly commented 11 years ago

Dude, threephase actually does work! Generating the pruning tables just takes forever, but after that, scramble generation is fairly quick.

>>> puzzles['444'].generateScramble()
...
10 89763295 18559908 tnoodlejs.nocache.js:11228
Mon Jun 10 01:56:02 GMT-700 2013 
INFO: FINISHED Generating threephase tables (took 650.00 seconds) tnoodlejs.nocache.js:2435
Mon Jun 10 01:56:03 GMT-700 2013 
FINER: STARTED Searching for solution in 1 moves. tnoodlejs.nocache.js:2435
Mon Jun 10 01:56:03 GMT-700 2013 
FINER: FINISHED Searching for solution in 1 moves. (took 0.00 seconds, expanded 56 nodes) tnoodlejs.nocache.js:2435
"B2 U R2 D2 B2 D R2 D2 B2 U' L' D' F' U R D R' B2 U' L2 Rw2 U2 Fw2 L2 F2 U' R' B2 Uw2 U' F' L' Fw F Uw2 Fw Uw' Fw D' R2 Fw L' F2"
>>> puzzles['444'].generateScramble()
Mon Jun 10 01:56:21 GMT-700 2013 
FINER: STARTED Searching for solution in 1 moves. tnoodlejs.nocache.js:2435
Mon Jun 10 01:56:21 GMT-700 2013 
FINER: FINISHED Searching for solution in 1 moves. (took 0.00 seconds, expanded 56 nodes) tnoodlejs.nocache.js:2435
"B2 D R2 U' B2 D2 B2 D2 R D2 R2 F R2 F' L U F' L' U' Fw2 R D Rw2 D' U' L2 Uw2 B2 R Uw2 D' U Fw R D2 Fw U2 Uw D' Rw' U' R2 Fw' B2"
>>> puzzles['444'].generateScramble()
Mon Jun 10 01:56:33 GMT-700 2013 
FINER: STARTED Searching for solution in 1 moves. tnoodlejs.nocache.js:2435
Mon Jun 10 01:56:33 GMT-700 2013 
FINER: FINISHED Searching for solution in 1 moves. (took 0.00 seconds, expanded 56 nodes) tnoodlejs.nocache.js:2435
"U2 L' D2 F2 U2 R B2 L D2 B' D' F2 U F R D R F2 D' B Uw2 Fw2 D2 R' F' L' B2 Uw2 F' U2 L' Uw' R F R2 D' L2 Fw' U' Rw F' D2 Rw' B2"
var start = Date.now(); for(var i = 0; i < 10; i++) { console.log(i + " " + puzzles['444'].generateScramble()); }; console.log((Date.now()-start)/1000);
Mon Jun 10 02:01:57 GMT-700 2013 
FINER: STARTED Searching for solution in 1 moves. tnoodlejs.nocache.js:2435
Mon Jun 10 02:01:58 GMT-700 2013 
FINER: FINISHED Searching for solution in 1 moves. (took 0.00 seconds, expanded 56 nodes) tnoodlejs.nocache.js:2435
0 F L2 D2 L2 F2 D2 F D2 F2 L2 D B R' F U D L2 F2 R U' Rw2 Uw2 F' Rw2 D' Rw2 F' B' U' R2 F B D' Rw' F2 Rw' L' Uw Fw F Uw' R2 Fw B2
Mon Jun 10 02:01:59 GMT-700 2013 
FINER: STARTED Searching for solution in 1 moves. tnoodlejs.nocache.js:2435
Mon Jun 10 02:01:59 GMT-700 2013 
FINER: FINISHED Searching for solution in 1 moves. (took 0.00 seconds, expanded 56 nodes) tnoodlejs.nocache.js:2435
1 F L2 F2 B R2 F2 B' L D R2 D' B2 D2 F2 U' B2 R' Rw2 U2 B' Uw2 Fw2 D B U2 F D' L2 D2 Rw R' U2 Rw' F Uw' Rw Fw' L' D2 U' F
Mon Jun 10 02:02:05 GMT-700 2013 
FINER: STARTED Searching for solution in 1 moves. tnoodlejs.nocache.js:2435
Mon Jun 10 02:02:05 GMT-700 2013 
FINER: FINISHED Searching for solution in 1 moves. (took 0.00 seconds, expanded 56 nodes) tnoodlejs.nocache.js:2435
2 L2 R2 U L2 B2 U2 L2 U B2 U D R U' F2 L D2 B2 R' U F' Fw2 Uw2 Rw2 D2 Rw2 B D' R2 Uw2 U' Rw2 U2 Rw R' D Rw2 R2 D2 Uw' L F' Uw' Fw2 F'
Mon Jun 10 02:02:08 GMT-700 2013 
FINER: STARTED Searching for solution in 1 moves. tnoodlejs.nocache.js:2435
Mon Jun 10 02:02:08 GMT-700 2013 
FINER: FINISHED Searching for solution in 1 moves. (took 0.00 seconds, expanded 56 nodes) tnoodlejs.nocache.js:2435
3 F2 R' L2 F R' U' D L2 D R' L2 D2 R2 D2 F2 D' R2 B2 U' Fw2 D' R Fw2 D L2 D L2 R2 Fw2 U D2 Fw Uw2 U L2 Fw2 Rw' F B Rw' Uw' L2 U R2
Mon Jun 10 02:02:17 GMT-700 2013 
FINER: STARTED Searching for solution in 1 moves. tnoodlejs.nocache.js:2435
Mon Jun 10 02:02:17 GMT-700 2013 
FINER: FINISHED Searching for solution in 1 moves. (took 0.00 seconds, expanded 56 nodes) tnoodlejs.nocache.js:2435
4 D' F2 U' R B2 D' F2 R L D' U2 B U2 B2 L2 F2 L2 F L2 F Rw2 F2 D F2 B' Rw2 F' U' Rw2 B2 R2 Fw2 L B' Rw D Rw B' Rw Fw Uw' F' R' Fw2 Uw
Mon Jun 10 02:02:19 GMT-700 2013 
FINER: STARTED Searching for solution in 1 moves. tnoodlejs.nocache.js:2435
Mon Jun 10 02:02:19 GMT-700 2013 
FINER: FINISHED Searching for solution in 1 moves. (took 0.00 seconds, expanded 56 nodes) tnoodlejs.nocache.js:2435
5 B2 U2 B D2 F2 R2 F D2 B D' F2 D' R D' F' D2 B2 F2 Rw2 F' Uw2 D' B' D2 Fw2 Uw2 Rw2 R2 U F2 D2 Rw' Uw2 R' F2 D F2 Fw' U Rw L2 Uw' R2 Fw
Mon Jun 10 02:02:24 GMT-700 2013 
FINER: STARTED Searching for solution in 1 moves. tnoodlejs.nocache.js:2435
Mon Jun 10 02:02:24 GMT-700 2013 
FINER: FINISHED Searching for solution in 1 moves. (took 0.00 seconds, expanded 56 nodes) tnoodlejs.nocache.js:2435
6 R U2 R2 D2 U2 L' U2 R' U2 R2 D2 B' D' B' F2 R F' D2 U2 Uw2 B Rw2 Uw2 U' R2 D' Rw2 R2 F' D2 Fw2 Rw R B L R' Fw2 Uw' Rw' Fw2 U2 B' Rw' B
Mon Jun 10 02:02:28 GMT-700 2013 
FINER: STARTED Searching for solution in 1 moves. tnoodlejs.nocache.js:2435
Mon Jun 10 02:02:28 GMT-700 2013 
FINER: FINISHED Searching for solution in 1 moves. (took 0.00 seconds, expanded 56 nodes) tnoodlejs.nocache.js:2435
7 L2 D B' D' F2 U' B' D R' U D2 B2 R2 D2 R2 B' U2 F' L2 Uw2 Fw2 F' D Rw2 L2 U Rw2 D' Fw2 D2 B' Rw U Rw' L U' Rw Uw' B' Rw2 F' Rw U2
Mon Jun 10 02:02:44 GMT-700 2013 
FINER: STARTED Searching for solution in 1 moves. tnoodlejs.nocache.js:2435
Mon Jun 10 02:02:44 GMT-700 2013 
FINER: FINISHED Searching for solution in 1 moves. (took 0.00 seconds, expanded 56 nodes) tnoodlejs.nocache.js:2435
8 F2 B2 R2 U' D' L2 R2 B2 U L' B' U' F R D' B2 R' U L2 D' Uw2 Fw2 F' Rw2 D2 B R2 B' Uw2 D2 R2 B2 Uw B2 L Uw R' Uw' Fw2 F' D Fw Rw R' B'
Mon Jun 10 02:02:47 GMT-700 2013 
FINER: STARTED Searching for solution in 1 moves. tnoodlejs.nocache.js:2435
Mon Jun 10 02:02:47 GMT-700 2013 
FINER: FINISHED Searching for solution in 1 moves. (took 0.00 seconds, expanded 56 nodes) tnoodlejs.nocache.js:2435
9 D U2 B2 L' R2 F' D' R' F R2 U' F2 D U' L2 F2 D2 F2 B2 Fw2 U' B2 U' Rw2 U Fw2 L' U' Fw2 U' Rw2 Fw U B' D' L2 U' Uw F2 Rw' L Fw L2 Uw
50.553

That's 10 scrambles in 50.553 seconds, so ~5 seconds on average per scramble.

jfly commented 10 years ago

As of https://github.com/cubing/tnoodle/pull/173, 444 actually works pretty darn well in the browser! Chen Shuang has been able to speed things up even more by manually massaging the javascript that GWT produces. It would be really nice to change things so that GWT produces the best javascript by default, or failing that, we could write down the rules for massaging the javascript by hand, and maybe codify them.