Message #1664

From: Melinda Green <melinda@superliminal.com>
Subject: Re: [MC4D] Goldilock’s function
Date: Fri, 06 May 2011 22:40:33 -0700

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

I must say this looks *very* promising. The outputs you got for all the
puzzles you tested do indeed sound ideal. I’m not surprised that the
simplex needs fewer than my 1-minute formula gives, and that the 120
Cell needs a lot more–as Andrey has recently shown us. It’s also great
that your inputs are values we should either have on hand or be able to
produce without much trouble, and that your equations are simple enough
that I think I can handle it. This is all exactly what I had hoped for,
and if it is not, then I suspect you’ll be able to modify it to be so.
Once we’ve decided this is just right, I 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 port
in order to learn Android graphics and to impress potential employers,
but I have a new laptop and have not been looking forward to setting up
source control to work on the desktop version, but I am now out of
excuses and will simply have to just have to do it. :-D Luckily the
timing is good as I’ve finished all the Android 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
puzzles that Nan referred us to? I imagine that they will err more on
the side of safety than we need, but if your formula reproduces those
numbers multiplied by some constant, that will be even more evidence
that you’ve gotten it right. In fact that would mean that you could
introduce yet another scalar parameter for that constant which
represents the desired safety margin.

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

-Melinda

On 5/6/2011 7:45 PM, David Smith wrote:
>
>
> Hi Melinda (and everyone else),
>
> I spent most of today working on the Goldilocks function problem, and
> believe I
> have found a good function that will work! It’s a bit detailed, so I
> hope that’s not a
> problem. It’s the simplest one I could come up with that is very well
> mathematically
> justified.
>
> Here is the pseudocode:
>
> Npieces = number of pieces in the puzzle (including 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) = ln(x)/0.693
> __________________________________________________________________
>
> AveNumTwists = (Npieces*Nfaces/(Nstickers - N1Cpieces)) *
> (0.577+ln(Npieces))
>
> Number of Twists to Scramble (round to nearest integer) =
>
> AveNumTwists * log2(Nfaces)
> __________________________________________________________________
>
> Hopefully that’s complex enough! ;) I observed that you have all of
> the functions
> required (by attempting to create the ordinary Rubik’s cube, which was
> apparently
> BRILLIANT!) except possibly log2 and N1Cpieces. I gave you a
> conversion formula
> for the former, and I’m betting you have the latter, but if not it
> shouldn’t be too difficult
> to implement.
>
> *** WARNING! MATHEMATICS CONTENT AHEAD! ***
>
> I’ll give a brief explanation. It took some experimentation to arrive
> at this formula; I
> tried many different approaches; this is the one that really worked.
> AveNumTwists
> counts the average number of twists needed to move every piece of a
> puzzle at least
> once. (Of course this number will in fact move many pieces more than
> once). It should
> hopefully be clear that this average number of twists will provide a
> well-scrambled
> puzzle when applied more than once. The second factor of AveNumTwists
> utilizes a
> logarithm and the number 0.577, which some of you may recognize as the
> gamma
> constant. This factor is an approximation of the nth 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 had that as
> the number of
> faces of the puzzle doubles, we need to move every piece an additional
> time, by
> adding AveNumTwists one more time. Of course, attempting to move
> every piece
> across the entire puzzle, even via a direct path, would produce
> astronomical results
> for the 120-cell and other puzzles with a large number of faces. For
> the 120-cell,
> AveNumTwists is about 7, which sounds right, considering that even
> with 10,000
> twists you will for all practical purposes never find a piece on the
> opposite side of
> the puzzle from where it started. (An aside: I proved that my original
> idea that the
> number of twists needed to randomize the 120-cell could be in the
> millions or higher
> was correct.) So, I saw that AveNumTwists needs to be multiplied by
> the base 2
> logarithm of the number of faces of the puzzle (there is no need to
> consider the
> size of the puzzle here; the number of faces is the important factor
> to consider).
>
> *** MATHEMATICS CONTENT HAS CEASED! ***
>
> And as if by magic, when these calculations are performed we get the
> expected
> values for the 3^4 cube and the 120-cell! Here are the values I have
> computed so
> far:
>
> 3^4 cube: 46 twists
> 4^4 cube: 78 twists
> 5^4 cube: 115 twists
> order-3 simplex: 16 twists
> order-3 120-cell: 2487
>
> Here are some interesting observations: The number of twists for the
> higher-order
> cubes appears to be growing larger that your previous function was as
> the order
> increases. Also, the number of twists for the order-3 simplex is just
> over half of the
> previous number! I applied 16 twists to the puzzle (by doing a full
> scramble and
> solving 14 moves), and it did look just as scrambled as the original
> 30 twists. The
> number for the 120-cell agrees with Andrey’s analysis that 1000 twists
> is not enough
> for a good scramble.
>
> Well, what do you think Melinda? Do these numbers look too large?
> Hopefully the
> calculation isn’t too complex; I don’t see any way to simplify it. I
> am very happy
> with how my function turned out, and do believe it is matheamtically
> justified,
> and so should work for every puzzle. Also, there is nothing special
> about 4
> dimensions - this function should work for MagicCube5D and MagicCube7D as
> well, if the programmers are interested. Just noting that!
>
> Melinda, thanks for giving me this nice problem to work on, and I hope
> I was
> helpful! It was a fun way to spend the day. :) I look froward to
> hearing from
> you. Until then, have a great weekend everybody!
>
> All the best,
> David
>
>
>
>