Message #1668

From: David Smith <>
Subject: Re: [MC4D] Goldilock’s function (Some math discussion! Enter at your own risk! :)
Date: Sat, 07 May 2011 14:08:42 -0700

Hi everyone,

I apologize; I had to rush the end of my post.  Something unexpected came up and
I had to quickly complete it.

Here are the counts again; there was a typo (7^3 cube):

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)
7^3 cube: 108 moves (WCA: 100 moves)
Megaminx: 73 moves (WCA: 70 moves)

The AveNumTwists part of the formula is pretty much set in stone, unless I
someday figure out how to implement puzzles like the starminx.  That’s not
high on my list of priorities, however, unless it is eventually needed.  As I
mentioned, guesswork comes into play when deciding the factor by which to
multiply AveNumTwists.  An intuitive argument suggests that one should add
one factor of AveNumTwists (remember, it estimates the average number of
moves it takes to move each piece once) each time the number of faces doubles
(as then each piece could theoretically travel to the newly created face it resides
next to).  When I simply plugged the 3-dimensional puzzles into my formula,
I obtained results that were all what Melinda anticipated: each puzzle, including
the megaminx, was greater than the WCA counts, by about a factor of 1.4.  The
megaminx had the greatest deviation from the rest, at 1.5.  However, I then realized
that for 3 dimensions, I should adjust the vaule of my formula very slightly: The
final factor should be equal to 2 when the order-3 cube is considered, rather
than 3 as in four dimensions, and the rest of the values should proceed from there.
I performed this calculation, and plugged in the puzzles again.  The results were
miraculous: All of the cubes were within a factor of 1.08 (my value divided by WCA’s)
of the values given by the WCA, and in an increasing progression!  But, the
megaminx was at a factor of 1.16! This all seemed too remarkable to be a coincidence.
I realized that with the previous base-2 logarithm, I was going on intuition - I had no
sound data of what the values should be, except for our rough approximations with
the 3^4 cube and the 120-cell.  What if this was not accurate enough?  Then, I
studied my evidence (the WCA values) and realized that if I added 0.5 moves each
time the number of faces doubled (exactly half!), then boom - the megaminx’s value
immediately corresponded with the cubes.  In fact, it corresponds as close as I
can possibly get:

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

7^3 cube: 108 moves (WCA: 100 moves)

Incredible!  Does anyone believe this is all a coincidence, or have I somehow
stumbled upon a very, very accurate formula?

My goal before was an approximation: I was attempting to find a formula that
gave good values, not worrying too much if I went over, for a reasonably scrambled
puzzle.  Now, with this slight modification, I believe I may have found a formula
that gets it almost exactly right, just as Melinda wanted: a value that is not too high,
and not too low.  I can’t prove that my new 120-cell count is not too low, but I believe
it is, based on all of the empirical data.  I have adjusted for each dimension, so the
math suggests that I may have found the "sweet spot".  On the other hand, this
modification was based mostly on the WCA’s counts.  They may not be as
accurate as I would like, especially since they are linear and powers of 10.  But
the fact that my formula gives values that are so close, even when we change the
shape of the puzzle, seems to be quite remarkable, and not automatically
coincidental.  What do any of you think?

To summarize, AveNumTwists is based on established mathematics (but is of course
an approximation).  The choice of the last factor is harder to establish with purely
mathematical methods, but appears to give remarkably accurate results in three
dimensions based on the data, and also good values in four dimensions.

And to clarify, I’m not surprised that my formula has worked, but am surprised
that when I simply doubled the logarithm, (not a logarithm with an irrational
base, but twice the value it was previously!) the megaminx fell into a virtually
exact pattern with the cubes.  The degree of accuracy seems almost too good
to be true. :)

I look forward to hearing from Melinda and anyone else who wants to comment!
If you’ve read this far, thanks for listening; I appreciate your time and hopefully
was not too chatty today. :)

All the best,

— On Sat, 5/7/11, David Smith <> wrote:

From: David Smith <>
Subject: Re: [MC4D] Goldilock’s function
Date: Saturday, May 7, 2011, 2:30 PM


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

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>

AveNumTwists = (Npieces*Nfaces/(Nstickers - N1Cpieces)) *

          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,

— On Sat, 5/7/11, Melinda Green
<> wrote:

From: Melinda Green <>
Subject: Re: [MC4D] Goldilock’s function
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;-)


On 5/6/2011 7&#58;45 PM, David Smith wrote&#58;<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



          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>


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


          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



          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>


          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,