Message #1666

          <br> Npieces = number of pieces in the puzzle (including<br>
          1-colored pieces)

          Nfaces = number of faces in the puzzle

          Nstickers = number of stickers in the puzzle

          N1Cpieces = number of 1-colored pieces in the puzzle<br> d = dimension of the puzzle

          

          ln(x) = natural logarithm of x

          log4(x) = base 4 logarithm of x = ln(x)/ln(4) =<br>
          ln(x)/1.386

          Number of Twists to Scramble (round to nearest integer) =

          

          AveNumTwists * (d-1+log4(Nfaces/(2*d)))

I must say this looks &#42;very&#42; promising. The outputs you got for all<br>
the puzzles you tested do indeed sound ideal. I'm not surprised that<br>
the simplex needs fewer than my 1-minute formula gives, and that the<br>
120 Cell needs a lot more--as Andrey has recently shown us. It's<br>
also great that your inputs are values we should either have on hand<br>
or be able to produce without much trouble, and that your equations<br>
are simple enough that I think I can handle it. This is all exactly<br>
what I had hoped for, and if it is not, then I suspect you'll be<br>
able to modify it to be so. Once we've decided this is just right, I<br>
hope that you will describe how you generated your final formula.



Of course this all puts the ball in my court now. I did the Android<br>
port in order to learn Android graphics and to impress potential<br>
employers, but I have a new laptop and have not been looking forward<br>
to setting up source control to work on the desktop version, but I<br>
am now out of excuses and will simply have to just have to do it. <br>
&#58;-D  Luckily the timing is good as I've finished all the Android<br>
projects that I set out to build and am not working yet.



BTW, how does your formula do with the official numbers for the 3D<br>
puzzles that Nan referred us to? I imagine that they will err more<br>
on the side of safety than we need, but if your formula reproduces<br>
those numbers multiplied by some constant, that will be even more<br>
evidence that you've gotten it right. In fact that would mean that<br>
you could introduce yet another scalar parameter for that constant<br>
which represents the desired safety margin.



This is very cool, David. Thank you for putting substantial effort<br>
into this problem. Oh, and now do you see why we're glad to have you<br>
back? Actually, your enthusiasm is even more valuable than your math<br>
skills, but I'll very happily take both!  &#58;-)



-Melinda



On 5/6/2011 7&#58;45 PM, David Smith wrote&#58;<br>
<br>
  <br>
  <br>
  <br>
    <br>
      <br>
        Hi Melinda (and<br>
          everyone else),

          

          I spent most of today working on the Goldilocks function<br>
          problem, and believe I

          have found a good function that will work!  It's a bit<br>
          detailed, so I hope that's not a

          problem.  It's the simplest one I could come up with that<br>
          is very well mathematically

          justified.

          

          Here is the pseudocode&#58;

          

          Npieces = number of pieces in the puzzle (including<br>
          1-colored pieces)

          Nfaces = number of faces in the puzzle

          Nstickers = number of stickers in the puzzle

          N1Cpieces = number of 1-colored pieces in the puzzle

          

          ln(x) = natural logarithm of x

          log2(x) = base 2 logarithm of x = ln(x)/ln(2) =<br>
          ln(x)/0.693

          AveNumTwists = (Npieces&#42;Nfaces/(Nstickers - N1Cpieces)) &#42;<br>
          (0.577+ln(Npieces))

          

          Number of Twists to Scramble (round to nearest integer) =

          

          AveNumTwists &#42; log2(Nfaces)

          Hopefully that's complex enough! ;)  I observed that you<br>
          have all of the functions

          required (by attempting to create the ordinary Rubik's<br>
          cube, which was apparently

          BRILLIANT!) except possibly log2 and N1Cpieces.  I gave<br>
          you a conversion formula

          for the former, and I'm betting you have the latter, but<br>
          if not it shouldn't be too difficult

          to implement.

          

          &#42;&#42;&#42; WARNING! MATHEMATICS CONTENT AHEAD! &#42;&#42;&#42;

          

          I'll give a brief explanation.  It took some<br>
          experimentation to arrive at this formula; I

          tried many different approaches; this is the one that<br>
          really worked.  AveNumTwists

          counts the average number of twists needed to move every<br>
          piece of a puzzle at least

          once. (Of course this number will in fact move many pieces<br>
          more than once).  It should

          hopefully be clear that this average number of twists will<br>
          provide a well-scrambled

          puzzle when applied more than once.  The second factor of<br>
          AveNumTwists utilizes a

          logarithm and the number 0.577, which some of you may<br>
          recognize as the gamma

          constant.  This factor is an approximation of the nth<br>
          harmonic number (sum of the

          first n terms in the harmonic series) for n = Npieces.

          

          The last term of the final calculation uses the insight I<br>
          had that as the number of

          faces of the puzzle doubles, we need to move every piece<br>
          an additional time, by

          adding AveNumTwists one more time.  Of course, attempting<br>
          to move every piece

          across the entire puzzle, even via a direct path, would<br>
          produce astronomical results

          for the 120-cell and other puzzles with a large number of<br>
          faces.  For the 120-cell, 

          AveNumTwists is about 7, which sounds right, considering<br>
          that even with 10,000

          twists you will for all practical purposes never find a<br>
          piece on the opposite side of

          the puzzle from where it started. (An aside&#58; I proved that<br>
          my original idea that the

          number of twists needed to randomize the 120-cell could be<br>
          in the millions or higher

          was correct.)  So, I saw that AveNumTwists needs to be<br>
          multiplied by the base 2

          logarithm of the number of faces of the puzzle (there is<br>
          no need to consider the

          size of the puzzle here; the number of faces is the<br>
          important factor to consider).

          

          &#42;&#42;&#42; MATHEMATICS CONTENT HAS CEASED! &#42;&#42;&#42;

          

          And as if by magic, when these calculations are performed<br>
          we get the expected

          values for the 3&#94;4 cube and the 120-cell!  Here are the<br>
          values I have computed so

          far&#58;

          

          3&#94;4 cube&#58; 46 twists

          4&#94;4 cube&#58; 78 twists

          5&#94;4 cube&#58; 115 twists

          order-3 simplex&#58; 16 twists

          order-3 120-cell&#58; 2487

          

          Here are some interesting observations&#58;  The number of<br>
          twists for the higher-order

          cubes appears to be growing larger that your previous<br>
          function was as the order

          increases.  Also, the number of twists for the order-3<br>
          simplex is just over half of the 

          previous number!  I applied 16 twists to the puzzle (by<br>
          doing a full scramble and

          solving 14 moves), and it did look just as scrambled as<br>
          the original 30 twists.  The

          number for the 120-cell agrees with Andrey's analysis that<br>
          1000 twists is not enough

          for a good scramble.

          

          Well, what do you think Melinda?  Do these numbers look<br>
          too large?  Hopefully the

          calculation isn't too complex; I don't see any way to<br>
          simplify it.  I am very happy

          with how my function turned out, and do believe it is<br>
          matheamtically justified,

          and so should work for every puzzle.  Also, there is<br>
          nothing special about 4

          dimensions - this function should work for MagicCube5D and<br>
          MagicCube7D as

          well, if the programmers are interested.  Just noting<br>
          that!

          

          Melinda, thanks for giving me this nice problem to work<br>
          on, and I hope I was

          helpful!  It was a fun way to spend the day. &#58;)  I look<br>
          froward to hearing from

          you.  Until then, have a great weekend everybody!

          

          All the best,

          David