# Algorithm analyzer / simulator



## Cynthia Moore (Jul 23, 2014)

Has anyone written a program that will analyze an algorithm to determine which pieces were moved and to where?

I think it would be very instructive in learning how the puzzle works and what the various methods actually do.

For example, how are the pieces positioned after executing algorithms like these?


```
F' U L' U'
U R U' R' U' F' U F
R L F2 B2 L' R' U R L B2 F2 L' R'
```

Alternatively, is there a list somewhere that provides this information for some set of algorithms?

And, reaching for the moon, has anyone written a program that will generate an algorithm to move a piece from one location (including the orientation) to another location with another orientation? Optionally, I could indicate which pieces must be preserved.

For example, I would specify that I need to move the piece in the upper right hand corner to the upper left hand corner such that its Right face becomes its Up face and that I need to preserve the other top layer pieces.

Thanks


----------



## Jakube (Jul 23, 2014)

1) Why don't you just take a cube and apply the algorithms?
Alternative you can use any sim (like alg.cubing.net).

2) Cube Explorer has such an option. You can specify the fixed pieces, and just leave the other pieces grey. (http://kociemba.org/cube.htm)


----------



## Cynthia Moore (Jul 23, 2014)

Jakube said:


> 1) Why don't you just take a cube and apply the algorithms?



Well, uh, yes, of course, I do do that. But there are at least two problems:



I make mistakes. A simulator would be handy to ensure that an algorithm is doing what I think it is.
It is very difficult, for me at least, to keep track of where all 20 pieces were before the algorithm was run. In order to properly evaluate an algorithm, I need to know both where the target piece (or pieces) go as well as whether any other pieces were disturbed.
 


Jakube said:


> Alternative you can use any sim (like alg.cubing.net).
> 
> 2) Cube Explorer has such an option. You can specify the fixed pieces, and just leave the other pieces grey. (http://kociemba.org/cube.htm)



I'll look into these. Thanks


----------



## Lucas Garron (Jul 24, 2014)

http://alg.cubing.net/?alg=R_L_F2_B2_L-_R-_U_R_L_B2_F2_L-_R-

Try changing "3x3x3 Full Moves" to "3x3x3 Full Algorithm" or press the "Invert" button.
Let me know if you have requests/ideas for alg.cubing.net features.

Cube Explorer is great for solving 3x3x3 states, though.


----------



## Cynthia Moore (Jul 24, 2014)

Lucas Garron said:


> http://alg.cubing.net/?alg=R_L_F2_B2_L-_R-_U_R_L_B2_F2_L-_R-
> 
> Try changing "3x3x3 Full Moves" to "3x3x3 Full Algorithm" or press the "Invert" button.



It doesn't seem to be working correctly for me. It often stops before the last move (or the first when reversing).



Lucas Garron said:


> Let me know if you have requests/ideas for alg.cubing.net features.



I would love to be able to enter an algorithm, such as [R' D R] and have the program tell me which pieces moved, to where, and with what orientation after each move.

We'd need some notation that would uniquely identify every piece on the cube both before and after the moves. We'd also need a way to specify the orientation. Edge pieces have two possible orientations and corner pieces have three.

Thanks


----------



## Lucas Garron (Jul 24, 2014)

Cynthia Moore said:


> It doesn't seem to be working correctly for me. It often stops before the last move (or the first when reversing).



The algorithm doesn't end with the solved state. Does that mean the last R' move doesn't animate for you?
If so, I've never seenthat error; could you let me know your OS/browser? (Screenshot/cap would also be convincing, as well as console output if you know how to get it.)




Cynthia Moore said:


> I would love to be able to enter an algorithm, such as [R' D R] and have the program tell me which pieces moved, to where, and with what orientation after each move.
> 
> We'd need some notation that would uniquely identify every piece on the cube both before and after the moves. We'd also need a way to specify the orientation. Edge pieces have two possible orientations and corner pieces have three.
> 
> Thanks



We do have cycle notation, and it's easy to annotate with orientation. Randelshofer's applets do that. I want to support it some time, but it's not a priority. I'll think about supporting it when I rewrite the permutation system, though.


----------



## Lucas Garron (Jul 24, 2014)

Cynthia Moore said:


> It doesn't seem to be working correctly for me. It often stops before the last move (or the first when reversing).



The algorithm doesn't end with the solved state. Does that mean the last R' move doesn't animate for you?
If so, I've never seenthat error; could you let me know your OS/browser? (Screenshot/cap would also be convincing, as well as console output if you know how to get it.)




Cynthia Moore said:


> I would love to be able to enter an algorithm, such as [R' D R] and have the program tell me which pieces moved, to where, and with what orientation after each move.
> 
> We'd need some notation that would uniquely identify every piece on the cube both before and after the moves. We'd also need a way to specify the orientation. Edge pieces have two possible orientations and corner pieces have three.
> 
> Thanks



We do have cycle notation, and it's easy to annotate with orientation. Randelshofer's applets do that. I want to support it some time, but it's not a priority. I'll think about supporting it when I rewrite the permutation system, though.


----------



## Cynthia Moore (Jul 24, 2014)

Lucas Garron said:


> The algorithm doesn't end with the solved state. Does that mean the last R' move doesn't animate for you?
> If so, I've never seen that error; could you let me know your OS/browser? (Screenshot/cap would also be convincing, as well as console output if you know how to get it.)



I'm using Firefox 30.0 on a Win XP system.

I've attached 2 screen shots. The first shows the screen just after startup. The second shows the results of the Play button after pasting the algorithm. It did not do the last R'. I get the same if I jump to the end (>>|) or step through it one move at a time.

I don't know how to capture the console output, but if you can tell me how, I'll try to get it.


----------



## Lucas Garron (Jul 24, 2014)

Cynthia Moore said:


> I've attached 2 screen shots. The first shows the screen just after startup. The second shows the results of the Play button after pasting the algorithm. It did not do the last R'. I get the same if I jump to the end (>>|) or step through it one move at a time..



The output looks correct to me.

Are you aware that the algorithm intentionally doesn't restore the cube to solved / did you try it on a cube?


----------



## Cynthia Moore (Jul 24, 2014)

Lucas Garron said:


> The output looks correct to me.



My mistake. I thought that algorithm was a NOP, leaving the cube unaltered. I see that I was missing a final D'. Here's the correct algorithm (I think).

R L F2 B2 L' R' U R L B2 F2 L' R' D’

I could have sworn that it failed to undo the first move when reversing, but I can't make it do that now.


----------



## Cynthia Moore (Jul 24, 2014)

Lucas Garron said:


> We do have cycle notation, and it's easy to annotate with orientation. Randelshofer's applets do that. I want to support it some time, but it's not a priority. I'll think about supporting it when I rewrite the permutation system, though.



I think it would be enormously helpful to be able to see the total effect of an algorithm. I've attached an image showing a way to display it in 2D.


----------



## Stefan (Jul 24, 2014)

Cynthia Moore said:


> I would love to be able to enter an algorithm, such as [R' D R] and have the program tell me which pieces moved, to where, and with what orientation after each move.
> 
> We'd need some notation that would uniquely identify every piece on the cube both before and after the moves. We'd also need a way to specify the orientation. Edge pieces have two possible orientations and corner pieces have three.



Not sure this is helpful, but it does pretty much everything you said:
http://ideone.com/Ux1eWN
(look at the output on the bottom)

Edit: Oops, I didn't see your "after each move". I could change it, but I guess this way of displaying things is too inconvenient anyway...


----------



## Cynthia Moore (Jul 25, 2014)

Stefan said:


> Not sure this is helpful, but it does pretty much everything you said:
> http://ideone.com/Ux1eWN
> (look at the output on the bottom)



This looks very promising, but I can't figure out the notation. Can you explain it? The 12 2-character codes (UF UR UB UL DF DR DB DL FR FL BR BL) must be the 12 edge pieces and the 8 3-character codes (UFR URB UBL ULF DRF DFL DLB DBR) must be the 8 corner pieces, but I guess I'm too dense to work it out. 

Is that all of the code needed to process any algorithm?



Stefan said:


> Edit: Oops, I didn't see your "after each move". I could change it, but I guess this way of displaying things is too inconvenient anyway...



The "after each move" is not critical, because I can always use a shorter algorithm.


----------



## 10461394944000 (Jul 25, 2014)

Cynthia Moore said:


> The 12 2-character codes (UF UR UB UL DF DR DB DL FR FL BR BL) must be the 12 edge pieces and the 8 3-character codes (UFR URB UBL ULF DRF DFL DLB DBR) must be the 8 corner pieces, but I guess I'm too dense to work it out.



didnt you just work it out in the previous sentence


----------



## Stefan (Jul 25, 2014)

Cynthia Moore said:


> This looks very promising, but I can't figure out the notation.



"UFR moved to RFD" means the corner that was at up-front-right moved to right-front-down. Note that this also tells you the orientation.



Cynthia Moore said:


> Is that all of the code needed to process any algorithm?



For basic notation with just UDLRFB moves, yes. Not for other stuff, though.


----------



## Cynthia Moore (Jul 25, 2014)

Stefan said:


> "UFR moved to RFD" means the corner that was at up-front-right moved to right-front-down.



I finally worked it out. The UFR notation seems to me to be with respect to the Up face. I have been working with algorithms that are relative to the Front face, so it threw me for awhile.

How about a Cartesian coordinate notation. UFR => 331, RFD => 311, etc.? This is from the perspective of the Front face. This seems much more intuitive to me. 




Stefan said:


> Note that this also tells you the orientation.



How so? Can't a corner piece be twisted into three different orientations?



Stefan said:


> For basic notation with just UDLRFB moves, yes. Not for other stuff, though.



If I download a Python interpreter, will I be able to generate that move list with just the code you show? If so, Python has to be the most compact language since APL.

PS: Is there any way to generate these multiple quotes other than cutting and pasting the markup?


----------



## 10461394944000 (Jul 25, 2014)

Cynthia Moore said:


> How about a Cartesian coordinate notation. UFR => 331, RFD => 311, etc.? This is from the perspective of the Front face. This seems much more intuitive to me.



needlessly overcomplicating things



Cynthia Moore said:


> How so? Can't a corner piece be twisted into three different orientations?



URF and RFU and FUR are 3 orientations

if URF moves to DFR that tells you that the U sticker moved to the D face so you know the orientation


----------



## Cynthia Moore (Jul 25, 2014)

Stefan said:


> Not sure this is helpful, but it does pretty much everything you said:
> http://ideone.com/Ux1eWN
> (look at the output on the bottom)



Stefan,

Can I edit the string on line 3 [alg = "R' D R"] to enter a different algorithm and rerun the program?

I tried editing it and clicking the Run button, but it took me to a different page.

Thanks



10461394944000 said:


> URF and RFU and FUR are 3 orientations
> 
> if URF moves to DFR that tells you that the U sticker moved to the D face so you know the orientation



Are these three "results" equivalent?



URF moves to DRF
RFU moves to RFD
FUR moves to FDR


----------



## 10461394944000 (Jul 25, 2014)

Cynthia Moore said:


> Are these three "results" equivalent?
> 
> 
> 
> ...



no if URF moves to DFR (i think reading the faces of a corner clockwise is standard) then the U sticker moves to the D face, but if RFU moves to RDF then the U sticker moves to the F face and if FUR moves to FRD then the U sticker moves to the R face


----------



## Cynthia Moore (Jul 25, 2014)

10461394944000 said:


> no if URF moves to DFR (i think reading the faces of a corner clockwise is standard) then the U sticker moves to the D face,



...and the R sticker moves to the F face and the F sticker moves to the R face, right?



10461394944000 said:


> but if RFU moves to RDF then the U sticker moves to the F face and if FUR moves to FRD then the U sticker moves to the R face



But that's not what I said. I said:



URF moves to DRF
RFU moves to RFD (not RDF)
FUR moves to FDR (not FRD)

Unless I am completely daft, all of these designations are clockwise and all have the U sticker in the same relative position as the D sticker. It's the first letter in the first example, the third in the second, and the second in the third.

No?

Or am I missing something?


----------



## 10461394944000 (Jul 25, 2014)

Cynthia Moore said:


> ...and the R sticker moves to the F face and the F sticker moves to the R face, right?



yes



Cynthia Moore said:


> But that's not what I said. I said:
> 
> 
> 
> ...



no you are wrong

DRF, RFD and FDR are not clockwise


----------



## Cynthia Moore (Jul 25, 2014)

10461394944000 said:


> no you are wrong
> 
> DRF, RFD and FDR are not clockwise



Quite right. My dylsexia must be acting up again. At least that's what my friends say when I tell them that life has been handing me melons.

So then these three "results" are equivalent, no?



URF moves to DFR
RFU moves to FRD
FUR moves to RDF

And they all convey exactly the same information. Right?


----------



## IQubic (Jul 25, 2014)

Cynthia Moore said:


> Quite right. My dylsexia must be acting up again. At least that's what my friends say when I tell them that life has been handing me melons.
> 
> So then these three "results" are equivalent, no?
> 
> ...



Yes they do. One is not better than another, they are all different.


----------



## qqwref (Jul 25, 2014)

Cynthia: Only the FIRST letter in a corner matters - the other two can be in either order. You can write either URF or UFR. And yes, if you just modify the alg in line 3 of Stefan's code and rerun the program, it should output what the pieces do.


Stefan: That's a cool little program, but how does it actually do the moves? I assume the magic is in lines 9 and 10 but I don't really get what you're doing there. More specifically, what's the function of the maketrans and translate functions? I assume those are Python specific?


----------



## Cynthia Moore (Jul 25, 2014)

qqwref said:


> Cynthia: Only the FIRST letter in a corner matters - the other two can be in either order. You can write either URF or UFR.



Since the WGO (white-green-orange) piece will always have those three colors in that (clockwise) order, identifying the new position of any one color uniquely determines the other two. Nevertheless, I think it makes sense to have a consistent order, so I'm good with always specifying the corner colors in clockwise order. It also has the advantage of making it easy to read where all three colors went directly from the code.



qqwref said:


> And yes, if you just modify the alg in line 3 of Stefan's code and rerun the program, it should output what the pieces do.



I tried that and couldn't get it to work. Were you able to do that? Can you tell me what you did, step by step?



qqwref said:


> Stefan: That's a cool little program, but how does it actually do the moves? I assume the magic is in lines 9 and 10 but I don't really get what you're doing there. More specifically, what's the function of the maketrans and translate functions? I assume those are Python specific?



I assumed at least one of those were subroutines that aren't shown.



Cynthia Moore said:


> Stefan,
> 
> Can I edit the string on line 3 [alg = "R' D R"] to enter a different algorithm and rerun the program?
> 
> ...



Stefan,

I signed up for an Ideone account hoping to run your cool little program. I got the following error message:


```
Compilation error
             
stdin
Standard input is empty
             
compilation info
Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/usr/lib/python2.7/py_compile.py", line 117, in compile
    raise py_exc
py_compile.PyCompileError: Sorry: IndentationError: ('unexpected indent', ('prog.py', 1, 4, '    import string\n'))

stdout
Standard output is empty
```

Can you help?


----------



## Stefan (Jul 26, 2014)

Cynthia Moore said:


> If I download a Python interpreter, will I be able to generate that move list with just the code you show?



For Python 2 it should work, for Python 3 use this instead:
http://ideone.com/haMUAm
(I should have done Python 3 right away, slightly shorter)



Cynthia Moore said:


> If so, Python has to be the most compact language since APL.



Python helps, but it really is the approach that makes it short. qq could probably rewrite it to J or K and make it a third of the size. And I'd love to see that, even though it would look just like gibberish to me 



Cynthia Moore said:


> PS: Is there any way to generate these multiple quotes other than cutting and pasting the markup?



I don't think so.



qqwref said:


> Cynthia: Only the FIRST letter in a corner matters - the other two can be in either order. You can write either URF or UFR.



That's a possible convention, but I prefer to use all-same-direction because then readers don't need to know about that convention.



qqwref said:


> Stefan: That's a cool little program, but how does it actually do the moves? I assume the magic is in lines 9 and 10 but I don't really get what you're doing there. More specifically, what's the function of the maketrans and translate functions? I assume those are Python specific?



They're like Perl's tr/.../.../, maybe you know that? Translates for example "ABC" to "xyz", meaning it replaces every "A" in the target string by "x", every "B" by "y", etc. Very similar to saying "UFR moved to RFD" actually, where the U moved to R, the F to F, and the R to D.

In variable "state", I store the current positions of cubies "UF UR ... DBR". So if at some point the first letter pair in state is "LB", that means that the "UF" cubie is at position "LB". Now let's say I want to simulate a U turn. That affects all cubies currently in the U layer, i.e., those cubies with a "U" in their current position string. And for all of these, every "F" becomes "L", every "L" becomes "B", etc. So lines 7 to 9 prepare the translation "FLBR"-to-"LBRF", and in line 10 it gets applied to all cubie positions containing "U". For example, position "FUR" becomes "LUF" while "DLF" isn't changed. I really love this way to represent and simulate the cube. Easily generalizes to for example Megaminx as well.



Cynthia Moore said:


> Can you help?



Looks like you added spaces where you shouldn't have. If this doesn't help, please post the URL.

*Edit:* Geez, I'm a noob. Improved the last part of the program and changed variable names while I was at it (only the Python 3 version).


----------

