Message #1666

From: David Smith <djs314djs314@yahoo.com>
Subject: Re: [MC4D] Goldilock’s function
Date: Sat, 07 May 2011 11:30:28 -0700

Hi Melinda and Matt,

Melinda, thanks so much for your positive words and encouragement that I am
an asset to this wonderful community of good people!  It sounds like the Android
work is very interesting and fun; good luck with that.  It’s certainly very impressive!

Matt, thanks for the welcome!  I can explain why the formula did not work for the
starminx.  I hadn’t even thought to mention this, which is my fault (and I apologize),
but the formula will only work for puzzles that are sliced ‘normally’.  That is to say,
faces are cut evenly, all 1-colored pieces are on the inside of the face and spaced
evenly and according to the shape of the puzzle, etc.  The reason why the starminx
is so much larger is that it is built into the formula that order-3 puzzles will have
one 1-colored piece per face.  The fact that there are six per face greatly increases
the first factor of AveNumTwists, which makes the entire count much larger than
it ought to be.  My formula does work for all MagicCube4D, 5D and 7D puzzles
however.

Having said this, I did realize this morning that I had jumped to conclusions
when I said the formula works for puzzles of any dimension.  I have improved the
formula to account for this, and it turns out to be remarkably accurate.  I also
modified the last term, turning a base-2 logarithm into a base-4 logarithm. (I
would consider this an improvement rather than a correction, but anyone can feel
free to disagree! ;) )  I have to admit; which base to choose originally was a bit of
guesswork.  It turns out that the base-2 logarithm formula, even when taking into
account the lower number of dimensions, did not work as well for the megaminx
as it did for the cubes.  I realized that if I doubled the base of the logarithm, the
megaminx almost automatically ‘snapped’ into place, again as if by magic.  Here
is the revised formula:
__________________________________________________________________

          <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


AveNumTwists = (Npieces*Nfaces/(Nstickers - N1Cpieces)) *
(0.577+ln(Npieces))

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

          

          AveNumTwists &#42; (d-1+log4(Nfaces/(2&#42;d)))

__________________________________________________________________

The great thing about this new formula is that all of the 4-dimensional cubes
keep the same value.  The simplex becomes 14 moves, and the 120-cell becomes
1783.  I believe that both of these counts are accurate.  My basis for the base-4
logarithm was from the 3D counts Melinda pointed out to me (thanks Melinda!)
Just see how accurate my formula is in 3 dimensions:

2^3 cube: 11 moves
3^3 cube: 25 moves
4^3 cube: 43 moves (WCA: 40 moves)
5^3 cube: 63 moves (WCA: 60 moves)
6^3 cube: 85 moves (WCA: 80 moves)
4^3 cube: 108 moves (WCA: 100 moves)
Megaminx: 73 moves (WCA: 70 moves)

These counts are remarkably close to the WCA counts, as you can see!  I was
very surprised to see that.

I have to go now, but I’ll talk to you all later!

All the best,
David

— On Sat, 5/7/11, Melinda Green <melinda@superliminal.com> wrote:

From: Melinda Green <melinda@superliminal.com>
Subject: Re: [MC4D] Goldilock’s function
To: 4D_Cubing@yahoogroups.com
Date: Saturday, May 7, 2011, 1:40 AM

 







Wow, what a great email, David!! I especially liked your signposts
showing where the scary math begins and ends.

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