Message #1663

From: David Smith <djs314djs314@yahoo.com>
Subject: Goldilock’s function
Date: Fri, 06 May 2011 19:45:21 -0700

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