Fingertrick Analyzer

[watermelon]

Thanks for the example Stefan, I'm starting to understand your logic more clearly now. Just to confirm, at each move, you'll try switching to any of the 24 cube orientations and you'll try both the move and its corresponding double layer turn? Then, for each of those possibilities, you'll have to determine which of the previous states requires the least number of time units to get to that position?

qqwref, the formatting shouldn't be too hard to add once the program is finished. I'll definitely be sure to add it in.

 

[Stefan]

Just to confirm, at each move, you'll try switching to any of the 24 cube orientations and you'll try both the move and its corresponding double layer turn?

Yes, although I'm not sure the double layer turn needs to be tried explicitly. It might suffice to try the single layer turn if it's tried combined with any cube orientation anyway. I'm really not certain about that myself.

Then, for each of those possibilities, you'll have to determine which of the previous states requires the least number of time units to get to that position?

Not quite, at least not the way I presented it so far. Here's some pseudo code:

#--- Initialize table as "Everything takes infinite time".
for all M,C,L,R
  minLength[noparse][M][C][L][R][/noparse] = infinity

#--- The exception is that the start state takes zero time.
minLength[noparse][0][0][0][0][/noparse] = 0

#--- Compute how long it takes to reach each state.
for M = 1 .. AlgLength
  for all C,L,R
    for all c,l,r
      T = actualTurn( algorithm, M, c )
      minimize minLength[noparse][M][C][L][R][/noparse] by
        minLength[noparse][M-1][c][l][r][/noparse] + cost( c, l, r, T, C, L, R )

That's bottom-up dynamic programming. Alternatively it might be nicer to think top-down, using memoization, this might be closer to what you thought of:

function minLength ( M, C, L, R ) {

  #--- Start of the alg, answer is zero or infinity.
  if M == 0
    return 0 if C=L=R=0, otherwise infinity
    
  #--- If we haven't stored the result for this M/C/L/R yet, then compute it.
  if not stored[noparse][M][C][L][R][/noparse] {
    stored[noparse][M][C][L][R][/noparse] = infinity
    for all c,l,r
      T = actualTurn( algorithm, M, c )
      minimize stored[noparse][M][C][L][R][/noparse] by
        minLength( M-1, c, l, r ) + cost( c, l, r, T, C, L, R )
  }
  
  #--- Return the stored value.
  return stored[noparse][M][C][L][R][/noparse]
}

In both versions, this computes how fast you can get to each state, and you can use that data to construct actual executions by going "backwards" from M=algorithmLength. In case dynamic programming and memoization are new for you, it might be better to solve a simpler problem with them first, for example the longest common subsequence problem.

 

[Stefan]

Btw, something else I realized today: When doing R2 U R U R' U' R' U' R' U R', I pull the bold R with my right ring finger so the orientation of the right hand pretty much stays the same and I can pull both U turns surrounding it with the right index finger and don't lose time for regripping.

 

[watermelon]

Btw, something else I realized today: When doing R2 U R U R' U' R' U' R' U R', I pull the bold R with my right ring finger

Don't you mean your left ring finger?

 

[Stefan]

No I don't. But it's an interesting idea.

 

[watermelon]

Ah, I see what you mean now.

Back to the program, I have one last question before I start to implement the latter of your solutions. Why would we initialize any initial position to infinity unless it's the starting cube orientation/hand position? Wouldn't we assume that you can start from any position without having to move there and use up valuable time?

 

[Stefan]

Wouldn't we assume that you can start from any position without having to move there and use up valuable time?

But it *does* take time, doesn't it?

 

[watermelon]

In that mindset, wouldn't you initialize the beginning cells to the time it takes to get to that orientation (most likely 1) rather than infinity? Again, this is probably a misunderstanding on my part.

Also, the reason for my previous response is when you're about to do an algorithm, you're not necessarily in the starting position.

 

[Stefan]

You could do that, but it's also covered by the cost function when making the first turn. Um, let me document that one:

cost( c, l, r, T, C, L, R ) = The amount of time it takes to start at state (c,l,r), make turn T, and end up at state state (C,L,R).

Btw, I might make it sound easy, but I think this is quite a lot of work...

 

[watermelon]

I see your reasoning now, though I might use my idea just because I'm not sure how to program in infinity.

Btw, I might make it sound easy, but I think this is quite a lot of work...

Implementing this search will only require me to add two additional functions to my classes at the moment, and since you've explained the logic, I hope it won't be too hard to get working properly.

 

[Stefan]

Try infinity = 999. Really just a large number that gets beaten by everything but not so large it overflows when something is added to it.

Or if you used float/double, you could actually use the value infinity (as those types usually have a representation for it and can calculate with it).

 

[xXdaveXsuperstarXx]

I would apply algorithms from an optimal cube solver to this.