Thread: "Goldilock's function"

--0-955182483-1304736321=:13140
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: quoted-printable

Hi Melinda (and everyone else),

I spent most of today working on the Goldilocks function problem, and belie=
ve I
have found a good function that will work!=A0 It's a bit detailed, so I hop=
e that's not a
problem.=A0 It's the simplest one I could come up with that is very well ma=
thematically
justified.

Here is the pseudocode:

Npieces =3D number of pieces in the puzzle (including 1-colored pieces)
Nfaces =3D number of faces in the puzzle
Nstickers =3D number of stickers in the puzzle
N1Cpieces =3D number of 1-colored pieces in the puzzle

ln(x) =3D natural logarithm of x
log2(x) =3D base 2 logarithm of x =3D ln(x)/ln(2) =3D ln(x)/0.693
__________________________________________________________________

AveNumTwists =3D (Npieces*Nfaces/(Nstickers - N1Cpieces)) * (0.577+ln(Npiec=
es))

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

AveNumTwists * log2(Nfaces)
__________________________________________________________________

Hopefully that's complex enough! ;)=A0 I observed that you have all of the =
functions
required (by attempting to create the ordinary Rubik's cube, which was appa=
rently
BRILLIANT!) except possibly log2 and N1Cpieces.=A0 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.=A0 It took some experimentation to arrive at=
this formula; I
tried many different approaches; this is the one that really worked.=A0 Ave=
NumTwists
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).=
=A0 It should
hopefully be clear that this average number of twists will provide a well-s=
crambled
puzzle when applied more than once.=A0 The second factor of AveNumTwists ut=
ilizes a
logarithm and the number 0.577, which some of you may recognize as the gamm=
a
constant.=A0 This factor is an approximation of the nth harmonic number (su=
m of the
first n terms in the harmonic series) for n =3D Npieces.

The last term of the final calculation uses the insight I had that as the n=
umber of
faces of the puzzle doubles, we need to move every piece an additional time=
, by
adding AveNumTwists one more time.=A0 Of course, attempting to move every p=
iece
across the entire puzzle, even via a direct path, would produce astronomica=
l results
for the 120-cell and other puzzles with a large number of faces.=A0 For the=
120-cell,=20
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 opposi=
te 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.)=A0 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 conside=
r the
size of the puzzle here; the number of faces is the important factor to con=
sider).

*** MATHEMATICS CONTENT HAS CEASED! ***

And as if by magic, when these calculations are performed we get the expect=
ed
values for the 3^4 cube and the 120-cell!=A0 Here are the values I have com=
puted 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:=A0 The number of twists for the hig=
her-order
cubes appears to be growing larger that your previous function was as the o=
rder
increases.=A0 Also, the number of twists for the order-3 simplex is just ov=
er half of the=20
previous number!=A0 I applied 16 twists to the puzzle (by doing a full scra=
mble and
solving 14 moves), and it did look just as scrambled as the original 30 twi=
sts.=A0 The
number for the 120-cell agrees with Andrey's analysis that 1000 twists is n=
ot enough
for a good scramble.

Well, what do you think Melinda?=A0 Do these numbers look too large?=A0 Hop=
efully the
calculation isn't too complex; I don't see any way to simplify it.=A0 I am =
very happy
with how my function turned out, and do believe it is matheamtically justif=
ied,
and so should work for every puzzle.=A0 Also, there is nothing special abou=
t 4
dimensions - this function should work for MagicCube5D and MagicCube7D as
well, if the programmers are interested.=A0 Just noting that!

Melinda, thanks for giving me this nice problem to work on, and I hope I wa=
s
helpful!=A0 It was a fun way to spend the day. :)=A0 I look froward to hear=
ing from
you.=A0 Until then, have a great weekend everybody!

All the best,
David

--0-955182483-1304736321=:13140
Content-Type: text/html; charset=iso-8859-1
Content-Transfer-Encoding: quoted-printable

top" style=3D"font: inherit;">Hi Melinda (and everyone else), I spen= t most of today working on the Goldilocks function problem, and believe Ir>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 pse= udocode: Npieces =3D number of pieces in the puzzle (including 1-col= ored pieces) Nfaces =3D number of faces in the puzzle Nstickers =3D n= umber of stickers in the puzzle N1Cpieces =3D number of 1-colored pieces= in the puzzle ln(x) =3D natural logarithm of x log2(x) =3D base = 2 logarithm of x =3D ln(x)/ln(2) =3D ln(x)/0.693 _______________________= ___________________________________________ AveNumTwists =3D (Npiece= s*Nfaces/(Nstickers - N1Cpieces)) * (0.577+ln(Npieces)) Number of Tw= ists to Scramble (round to nearest integer) =3D AveNumTwists * log2(Nfaces) _____= _____________________________________________________________ Hopefu= lly that's complex enough! ;)  I observed that you have all of the fun= ctions required (by attempting to create the ordinary Rubik's cube, whic= h 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. r>*** WARNING! MATHEMATICS CONTENT AHEAD! *** I'll give a brief expl= anation.  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 p= iece 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 utili= zes 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 ha= rmonic number (sum of the first n terms in the harmonic series) for n = =3D 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 mov= e every piece an additional time, by adding AveNumTwists one more time.&= nbsp; 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-cel= l, AveNumTwists is about 7, which sounds right, considering that even w= ith 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 asi= de: I proved that my original idea that the number of twists needed to r= andomize the 120-cell could be in the millions or higher was correct.)&n= bsp; So, I saw that AveNumTwists needs to be multiplied by the base 2 lo= garithm 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<= br> Here are some interesting observations:  The number of twists f= or 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 numbe= r!  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 tw= ists.  The number for the 120-cell agrees with Andrey's analysis th= at 1000 twists is not enough for a good scramble. Well, what do y= ou think Melinda?  Do these numbers look too large?  Hopefully th= e calculation isn't too complex; I don't see any way to simplify it.&nbs= p; I am very happy with how my function turned out, and do believe it is= matheamtically justified, and so should work for every puzzle.  Al= so, there is nothing special about 4 dimensions - this function should w= ork for MagicCube5D and MagicCube7D as well, if the programmers are inte= rested.  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.&n= bsp; Until then, have a great weekend everybody! All the best, Da= vid

--0-955182483-1304736321=:13140--

--------------080803000407080900010404
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

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
>
>
>
>

--------------080803000407080900010404
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit




http-equiv="Content-Type">


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:

type="cite">

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

Hi David, good to see you back.

It's an interesting formula you have there, and I would also like a bit of =
background on how you derived it. However, I may have spotted a little pro=
blem with it, and hopefully the feedback will help improve the formula, or =
prove to not be an issue. It was discussed that deeper cut puzzles would r=
equire less moves to scramble them, since twists affect more pieces, and wi=
ll thus move pieces around the puzzle faster. However, the formula doesn't=
quite bear this out for the various types of face-turning dodecahedra. I =
hope I haven't made a numerical error here, if I have I apologise.

Megaminx: 105 twists
Pyraminx crystal: 81 twists

So far so good.

Starminx: 381 twists

This is far deeper cut than a megaminx, but apparently takes over 3 times a=
s many moves to scramble? That result doesn't seem correct.

Pentultimate: 130 twists

I hope I haven't made a mistake, and made false accusations against your wo=
rk. Perhaps there is a way to introduce another parameter, either for the =
number of pieces moved during a twist, or perhaps the ratio of pieces which=
are moved, to those which aren't? Regardless, good work here :).

Matt

=C2=A0



=20=20


=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20

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

=20=20=20=20

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.

=20=20=20=20

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.=C2=A0
:-D=C2=A0 Luckily the timing is good as I've finished all the Android
projects that I set out to build and am not working yet.

=20=20=20=20

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.

=20=20=20=20

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!=C2=A0 :-)

=20=20=20=20

-Melinda

=20=20=20=20

On 5/6/2011 7:45 PM, David Smith wrote:
=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20=20=20
=20=20=20=20=20=20=20=20=20=20
Hi Melinda (and
everyone else),

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

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

have found a good function that will work!=C2=A0 It's a bit
detailed, so I hope that's not a

problem.=C2=A0 It's the simplest one I could come up with tha=
t
is very well mathematically

justified.

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

Here is the pseudocode:

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

Npieces =3D number of pieces in the puzzle (including
1-colored pieces)

Nfaces =3D number of faces in the puzzle

Nstickers =3D number of stickers in the puzzle

N1Cpieces =3D number of 1-colored pieces in the puzzle

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

ln(x) =3D natural logarithm of x

log2(x) =3D base 2 logarithm of x =3D ln(x)/ln(2) =3D
ln(x)/0.693

__________________________________________________________________

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

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

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

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

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

AveNumTwists * log2(Nfaces)

__________________________________________________________________

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

Hopefully that's complex enough! ;)=C2=A0 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.=C2=A0 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.

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

*** WARNING! MATHEMATICS CONTENT AHEAD! ***

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

I'll give a brief explanation.=C2=A0 It took some
experimentation to arrive at this formula; I

tried many different approaches; this is the one that
really worked.=C2=A0 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).=C2=A0 It should

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

puzzle when applied more than once.=C2=A0 The second factor o=
f
AveNumTwists utilizes a

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

constant.=C2=A0 This factor is an approximation of the nth
harmonic number (sum of the

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

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

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.=C2=A0 Of course, attemptin=
g
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.=C2=A0 For the 120-cell,=20

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.)=C2=A0 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).

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

*** MATHEMATICS CONTENT HAS CEASED! ***

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

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

values for the 3^4 cube and the 120-cell!=C2=A0 Here are the
values I have computed so

far:

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

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

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

Here are some interesting observations:=C2=A0 The number of
twists for the higher-order

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

increases.=C2=A0 Also, the number of twists for the order-3
simplex is just over half of the=20

previous number!=C2=A0 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.=C2=A0 The

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

for a good scramble.

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

Well, what do you think Melinda?=C2=A0 Do these numbers look
too large?=C2=A0 Hopefully the

calculation isn't too complex; I don't see any way to
simplify it.=C2=A0 I am very happy

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

and so should work for every puzzle.=C2=A0 Also, there is
nothing special about 4

dimensions - this function should work for MagicCube5D and
MagicCube7D as

well, if the programmers are interested.=C2=A0 Just noting
that!

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

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

helpful!=C2=A0 It was a fun way to spend the day. :)=C2=A0 I =
look
froward to hearing from

you.=C2=A0 Until then, have a great weekend everybody!

=20=20=20=20=20=20=20=20=20=20=20=20=20=20

All the best,

David

=20=20=20=20=20=20=20=20=20=20=20=20
=20=20=20=20=20=20=20=20=20=20
=20=20=20=20=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20
=20=20



=20=20=20=20
=20=20=20=20=20

=20=20=20=20
=20=20=20=20


=20



=20=20




--0-451473990-1304793028=:27399
Content-Type: text/html; charset=utf-8
Content-Transfer-Encoding: quoted-printable

top" style=3D"font: inherit;">Hi Melinda and Matt, Melinda, thanks s= o much for your positive words and encouragement that I am an asset to t= his wonderful community of good people!  It sounds like the Android>work is very interesting and fun; good luck with that.  It's certainl= y very impressive! Matt, thanks for the welcome!  I can explain= why the formula did not work for the starminx.  I hadn't even thou= ght to mention this, which is my fault (and I apologize), but the formul= a will only work for puzzles that are sliced 'normally'.  That is to s= ay, 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.&nb= sp; The reason why the starminx is so much larger is that it is built in= to 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 puzzl= es of any dimension.  I have improved the formula to account for th= is, and it turns out to be remarkably accurate.  I also modified th= e last term, turning a base-2 logarithm into a base-4 logarithm. (I woul= d consider this an improvement rather than a correction, but anyone can fee= l free to disagree! ;) )  I have to admit; which base to choose ori= ginally was a bit of guesswork.  It turns out that the base-2 loga= rithm formula, even when taking into account the lower number of dimensi= ons, 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, ther>megaminx almost automatically 'snapped' into place, again as if by magic.=   Here is the revised formula: _________________________________= _________________________________ Npieces =3D number of pieces in the puzzle (including 1-colored pieces) Nfaces =3D number of faces in the puzzle Nstickers =3D number of stickers in the puzzle N1Cpieces =3D number of 1-colored pieces in the puzzle d = =3D dimension of the puzzle ln(x) =3D natural logarithm of x log4(x) =3D base 4 logarithm of x =3D ln(x)/ln(4) =3D ln(x)/1.386 AveNumTwists =3D (Npieces*Nfaces/(Nstickers - N1Cpieces)) * (0.577+ln(Npieces)) Number of Twists to Scramble (round to nearest integer) =3Dr> AveNumTwists * (d-1+log4(Nfaces/(2*d))) __________________________________________________________________ T= he great thing about this new formula is that all of the 4-dimensional cube= s keep the same value.  The simplex becomes 14 moves, and the 120-c= ell 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 cu= be: 43 moves (WCA: 40 moves) 5^3 cube: 63 moves (WCA: 60 moves) 6^3 c= ube: 85 moves (WCA: 80 moves) 4^3 cube: 108 moves (WCA: 100 moves) Me= gaminx: 73 moves (WCA: 70 moves) These counts are remarkably close t= o 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 b= est, David --- On Sat, 5/7/11, Melinda Green <melinda@superliminal.com> wrote: "border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5= px;"> From: Melinda Green <melinda@superliminal.com> Subject: R= e: [MC4D] Goldilock's function To: 4D_Cubing@yahoogroups.com Date: Sa= turday, May 7, 2011, 1:40 AM   =20=20=20=20=20=20 =20=20=20=20=20=20 =20=20 =20=20 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: =20=20=20=20=20=20 =20=20=20=20=20=20 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 tha= t is very well mathematically justified. Here is the pseudocode: Npieces =3D number of pieces in the puzzle (including 1-colored pieces) Nfaces =3D number of faces in the puzzle Nstickers =3D number of stickers in the puzzle N1Cpieces =3D number of 1-colored pieces in the puzzle ln(x) =3D natural logarithm of x log2(x) =3D base 2 logarithm of x =3D ln(x)/ln(2) =3D ln(x)/0.693 __________________________________________________________________ AveNumTwists =3D (Npieces*Nfaces/(Nstickers - N1Cpieces)) * (0.577+ln(Npieces)) Number of Twists to Scramble (round to nearest integer) =3Dr> 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 o= f 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 =3D 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, attemptin= g 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 =20=20=20=20=20=20 =20=20 =20=20=20=20=20 =20

--0-451473990-1304793028=:27399--

Thanks for the clarification David. I thought there would be something lik=
e that to explain the discrepancy. I would have been incredibly impressed =
it it applied to every single known puzzle, although at the rate you seem t=
o be churning out formulas I guess that one is only a matter of time ;). I=
t's impressive that the new numbers are so close to what the WCA uses alrea=
dy, that's definitely a sign of the formula being very well designed. And =
to think you keep worrying about not being able to contribute much here, th=
ere's clearly no risk of that happening any time soon.

Matt

--- In 4D_Cubing@yahoogroups.com, David Smith wrote:
>
> Hi Melinda and Matt,
>=20
> Melinda, thanks so much for your positive words and encouragement that I =
am
> an asset to this wonderful community of good people!=C2=A0 It sounds like=
the Android
> work is very interesting and fun; good luck with that.=C2=A0 It's certain=
ly very impressive!
>=20
> Matt, thanks for the welcome!=C2=A0 I can explain why the formula did not=
work for the
> starminx.=C2=A0 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'.=C2=
=A0 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.=C2=A0 The reason wh=
y the starminx
> is so much larger is that it is built into the formula that order-3 puzzl=
es will have
> one 1-colored piece per face.=C2=A0 The fact that there are six per face =
greatly increases
> the first factor of AveNumTwists, which makes the entire count much large=
r than
> it ought to be.=C2=A0 My formula does work for all MagicCube4D, 5D and 7D=
puzzles
> however.
>=20
> Having said this, I did realize this morning that I had jumped to conclus=
ions
> when I said the formula works for puzzles of any dimension.=C2=A0 I have =
improved the
> formula to account for this, and it turns out to be remarkably accurate.=
=C2=A0 I also
> modified the last term, turning a base-2 logarithm into a base-4 logarith=
m. (I
> would consider this an improvement rather than a correction, but anyone c=
an feel
> free to disagree! ;) )=C2=A0 I have to admit; which base to choose origin=
ally was a bit of=20
> guesswork.=C2=A0 It turns out that the base-2 logarithm formula, even whe=
n taking into
> account the lower number of dimensions, did not work as well for the mega=
minx
> as it did for the cubes.=C2=A0 I realized that if I doubled the base of t=
he logarithm, the
> megaminx almost automatically 'snapped' into place, again as if by magic.=
=C2=A0 Here
> is the revised formula:
> __________________________________________________________________
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
> Npieces =3D number of pieces in the puzzle (including
> 1-colored pieces)
>=20
> Nfaces =3D number of faces in the puzzle
>=20
> Nstickers =3D number of stickers in the puzzle
>=20
> N1Cpieces =3D number of 1-colored pieces in the puzzle
> d =3D dimension of the puzzle
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>=20
> ln(x) =3D natural logarithm of x
>=20
> log4(x) =3D base 4 logarithm of x =3D ln(x)/ln(4) =3D
> ln(x)/1.386
>=20
>=20
> AveNumTwists =3D (Npieces*Nfaces/(Nstickers - N1Cpieces)) *
> (0.577+ln(Npieces))
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>=20
> Number of Twists to Scramble (round to nearest integer) =3D
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>=20
> AveNumTwists * (d-1+log4(Nfaces/(2*d)))
>=20
> __________________________________________________________________
>=20
> The great thing about this new formula is that all of the 4-dimensional c=
ubes
> keep the same value.=C2=A0 The simplex becomes 14 moves, and the 120-cell=
becomes
> 1783.=C2=A0 I believe that both of these counts are accurate.=C2=A0 My ba=
sis for the base-4
> logarithm was from the 3D counts Melinda pointed out to me (thanks Melind=
a!)
> Just see how accurate my formula is in 3 dimensions:
>=20
> 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)
>=20
> These counts are remarkably close to the WCA counts, as you can see!=C2=
=A0 I was
> very surprised to see that.
>=20
> I have to go now, but I'll talk to you all later!
>=20
> All the best,
> David
>=20
> --- On Sat, 5/7/11, Melinda Green wrote:
>=20
> From: Melinda Green
> Subject: Re: [MC4D] Goldilock's function
> To: 4D_Cubing@yahoogroups.com
> Date: Saturday, May 7, 2011, 1:40 AM
>=20
>=20
>=20
>=20
>=20
>=20
>=20
> =C2=A0
>=20
>=20
>=20
>=20=20=20
>=20
>=20
>=20=20=20=20=20
>=20=20=20=20=20=20=20
>=20=20=20=20=20=20=20
>=20=20=20=20=20=20=20
>=20
>=20=20=20
>=20=20=20
> Wow, what a great email, David!! I especially liked your signposts
> showing where the scary math begins and ends.
>=20
>=20=20=20=20=20
>=20
> 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.
>=20
>=20=20=20=20=20
>=20
> 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.=C2=
=A0
> :-D=C2=A0 Luckily the timing is good as I've finished all the Android
> projects that I set out to build and am not working yet.
>=20
>=20=20=20=20=20
>=20
> 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.
>=20
>=20=20=20=20=20
>=20
> 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!=C2=A0 :-)
>=20
>=20=20=20=20=20
>=20
> -Melinda
>=20
>=20=20=20=20=20
>=20
> On 5/6/2011 7:45 PM, David Smith wrote:
>=20=20=20=20=20
>=20=20=20=20=20=20=20
>=20=20=20=20=20=20=20
>=20=20=20=20=20=20=20
>=20=20=20=20=20=20=20=20=20
>=20=20=20=20=20=20=20=20=20=20=20
> Hi Melinda (and
> everyone else),
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>=20
> I spent most of today working on the Goldilocks function
> problem, and believe I
>=20
> have found a good function that will work!=C2=A0 It's a bit
> detailed, so I hope that's not a
>=20
> problem.=C2=A0 It's the simplest one I could come up with t=
hat
> is very well mathematically
>=20
> justified.
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>=20
> Here is the pseudocode:
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>=20
> Npieces =3D number of pieces in the puzzle (including
> 1-colored pieces)
>=20
> Nfaces =3D number of faces in the puzzle
>=20
> Nstickers =3D number of stickers in the puzzle
>=20
> N1Cpieces =3D number of 1-colored pieces in the puzzle
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>=20
> ln(x) =3D natural logarithm of x
>=20
> log2(x) =3D base 2 logarithm of x =3D ln(x)/ln(2) =3D
> ln(x)/0.693
>=20
> __________________________________________________________________
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>=20
> AveNumTwists =3D (Npieces*Nfaces/(Nstickers - N1Cpieces)) *
> (0.577+ln(Npieces))
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>=20
> Number of Twists to Scramble (round to nearest integer) =3D
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>=20
> AveNumTwists * log2(Nfaces)
>=20
> __________________________________________________________________
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>=20
> Hopefully that's complex enough! ;)=C2=A0 I observed that y=
ou
> have all of the functions
>=20
> required (by attempting to create the ordinary Rubik's
> cube, which was apparently
>=20
> BRILLIANT!) except possibly log2 and N1Cpieces.=C2=A0 I gav=
e
> you a conversion formula
>=20
> for the former, and I'm betting you have the latter, but
> if not it shouldn't be too difficult
>=20
> to implement.
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>=20
> *** WARNING! MATHEMATICS CONTENT AHEAD! ***
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>=20
> I'll give a brief explanation.=C2=A0 It took some
> experimentation to arrive at this formula; I
>=20
> tried many different approaches; this is the one that
> really worked.=C2=A0 AveNumTwists
>=20
> counts the average number of twists needed to move every
> piece of a puzzle at least
>=20
> once. (Of course this number will in fact move many pieces
> more than once).=C2=A0 It should
>=20
> hopefully be clear that this average number of twists will
> provide a well-scrambled
>=20
> puzzle when applied more than once.=C2=A0 The second factor=
of
> AveNumTwists utilizes a
>=20
> logarithm and the number 0.577, which some of you may
> recognize as the gamma
>=20
> constant.=C2=A0 This factor is an approximation of the nth
> harmonic number (sum of the
>=20
> first n terms in the harmonic series) for n =3D Npieces.
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>=20
> The last term of the final calculation uses the insight I
> had that as the number of
>=20
> faces of the puzzle doubles, we need to move every piece
> an additional time, by
>=20
> adding AveNumTwists one more time.=C2=A0 Of course, attempt=
ing
> to move every piece
>=20
> across the entire puzzle, even via a direct path, would
> produce astronomical results
>=20
> for the 120-cell and other puzzles with a large number of
> faces.=C2=A0 For the 120-cell,=20
>=20
> AveNumTwists is about 7, which sounds right, considering
> that even with 10,000
>=20
> twists you will for all practical purposes never find a
> piece on the opposite side of
>=20
> the puzzle from where it started. (An aside: I proved that
> my original idea that the
>=20
> number of twists needed to randomize the 120-cell could be
> in the millions or higher
>=20
> was correct.)=C2=A0 So, I saw that AveNumTwists needs to be
> multiplied by the base 2
>=20
> logarithm of the number of faces of the puzzle (there is
> no need to consider the
>=20
> size of the puzzle here; the number of faces is the
> important factor to consider).
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>=20
> *** MATHEMATICS CONTENT HAS CEASED! ***
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>=20
> And as if by magic, when these calculations are performed
> we get the expected
>=20
> values for the 3^4 cube and the 120-cell!=C2=A0 Here are th=
e
> values I have computed so
>=20
> far:
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>=20
> 3^4 cube: 46 twists
>=20
> 4^4 cube: 78 twists
>=20
> 5^4 cube: 115 twists
>=20
> order-3 simplex: 16 twists
>=20
> order-3 120-cell: 2487
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>=20
> Here are some interesting observations:=C2=A0 The number of
> twists for the higher-order
>=20
> cubes appears to be growing larger that your previous
> function was as the order
>=20
> increases.=C2=A0 Also, the number of twists for the order-3
> simplex is just over half of the=20
>=20
> previous number!=C2=A0 I applied 16 twists to the puzzle (b=
y
> doing a full scramble and
>=20
> solving 14 moves), and it did look just as scrambled as
> the original 30 twists.=C2=A0 The
>=20
> number for the 120-cell agrees with Andrey's analysis that
> 1000 twists is not enough
>=20
> for a good scramble.
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>=20
> Well, what do you think Melinda?=C2=A0 Do these numbers loo=
k
> too large?=C2=A0 Hopefully the
>=20
> calculation isn't too complex; I don't see any way to
> simplify it.=C2=A0 I am very happy
>=20
> with how my function turned out, and do believe it is
> matheamtically justified,
>=20
> and so should work for every puzzle.=C2=A0 Also, there is
> nothing special about 4
>=20
> dimensions - this function should work for MagicCube5D and
> MagicCube7D as
>=20
> well, if the programmers are interested.=C2=A0 Just noting
> that!
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>=20
> Melinda, thanks for giving me this nice problem to work
> on, and I hope I was
>=20
> helpful!=C2=A0 It was a fun way to spend the day. :)=C2=A0 =
I look
> froward to hearing from
>=20
> you.=C2=A0 Until then, have a great weekend everybody!
>=20
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>=20
> All the best,
>=20
> David
>

LS0tLS1CRUdJTiBQR1AgU0lHTkVEIE1FU1NBR0UtLS0tLQ0KSGFzaDogU0hBMQ0KDQpPbiBT
YXQsIDA3IE1heSAyMDExIDEzOjQyOjAwIC0wMDAwIG9yIHRoZXJlYWJvdXRzICJNYXR0aGV3
Ig0KPGRhbWllbnR1cnRsZUBob3RtYWlsLmNvLnVrPiB3cm90ZToNCg0KPiBIaSBEYXZpZCwg
Z29vZCB0byBzZWUgeW91IGJhY2suDQo+IA0KPiBJdCdzIGFuIGludGVyZXN0aW5nIGZvcm11
bGEgeW91IGhhdmUgdGhlcmUsIGFuZCBJIHdvdWxkIGFsc28gbGlrZSBhDQo+IGJpdCBvZiBi
YWNrZ3JvdW5kIG9uIGhvdyB5b3UgZGVyaXZlZCBpdC4gIEhvd2V2ZXIsIEkgbWF5IGhhdmUg
c3BvdHRlZA0KPiBhIGxpdHRsZSBwcm9ibGVtIHdpdGggaXQsIGFuZCBob3BlZnVsbHkgdGhl
IGZlZWRiYWNrIHdpbGwgaGVscA0KPiBpbXByb3ZlIHRoZSBmb3JtdWxhLCBvciBwcm92ZSB0
byBub3QgYmUgYW4gaXNzdWUuICBJdCB3YXMgZGlzY3Vzc2VkDQo+IHRoYXQgZGVlcGVyIGN1
dCBwdXp6bGVzIHdvdWxkIHJlcXVpcmUgbGVzcyBtb3ZlcyB0byBzY3JhbWJsZSB0aGVtLA0K
PiBzaW5jZSB0d2lzdHMgYWZmZWN0IG1vcmUgcGllY2VzLCBhbmQgd2lsbCB0aHVzIG1vdmUg
cGllY2VzIGFyb3VuZCB0aGUNCj4gcHV6emxlIGZhc3Rlci4gIEhvd2V2ZXIsIHRoZSBmb3Jt
dWxhIGRvZXNuJ3QgcXVpdGUgYmVhciB0aGlzIG91dCBmb3INCj4gdGhlIHZhcmlvdXMgdHlw
ZXMgb2YgZmFjZS10dXJuaW5nIGRvZGVjYWhlZHJhLiAgSSBob3BlIEkgaGF2ZW4ndCBtYWRl
DQo+IGEgbnVtZXJpY2FsIGVycm9yIGhlcmUsIGlmIEkgaGF2ZSBJIGFwb2xvZ2lzZS4NCj4g
DQo+IE1lZ2FtaW54OiAgICAgICAgIDEwNSB0d2lzdHMNCj4gUHlyYW1pbnggY3J5c3RhbDog
ODEgIHR3aXN0cw0KPiANCj4gU28gZmFyIHNvIGdvb2QuDQo+IA0KPiBTdGFybWlueDogICAg
ICAgICAzODEgdHdpc3RzDQo+IA0KPiBUaGlzIGlzIGZhciBkZWVwZXIgY3V0IHRoYW4gYSBt
ZWdhbWlueCwgYnV0IGFwcGFyZW50bHkgdGFrZXMgb3ZlciAzDQo+IHRpbWVzIGFzIG1hbnkg
bW92ZXMgdG8gc2NyYW1ibGU/ICBUaGF0IHJlc3VsdCBkb2Vzbid0IHNlZW0gY29ycmVjdC4N
Cj4gDQo+IFBlbnR1bHRpbWF0ZTogICAgIDEzMCB0d2lzdHMNCj4gDQo+IEkgaG9wZSBJIGhh
dmVuJ3QgbWFkZSBhIG1pc3Rha2UsIGFuZCBtYWRlIGZhbHNlIGFjY3VzYXRpb25zIGFnYWlu
c3QNCj4geW91ciB3b3JrLiAgUGVyaGFwcyB0aGVyZSBpcyBhIHdheSB0byBpbnRyb2R1Y2Ug
YW5vdGhlciBwYXJhbWV0ZXIsDQo+IGVpdGhlciBmb3IgdGhlIG51bWJlciBvZiBwaWVjZXMg
bW92ZWQgZHVyaW5nIGEgdHdpc3QsIG9yIHBlcmhhcHMgdGhlDQo+IHJhdGlvIG9mIHBpZWNl
cyB3aGljaCBhcmUgbW92ZWQsIHRvIHRob3NlIHdoaWNoIGFyZW4ndD8gIFJlZ2FyZGxlc3Ms
DQo+IGdvb2Qgd29yayBoZXJlIDopLg0KPiANCj4gTWF0dA0KDQoNCkhpIERhdmlkLA0KDQpJ
IGhhdmUgYmVlbiB2ZXJ5IGlsbCBzbyBJIGhhdmVuJ3QgaGFkIHRoZSBlbmVyZ3kgdG8gdGhp
bmsgYWJvdXQgdGhpcyBhDQpsb3Qgb3IgY29tcG9zZSBhIHZlcnkgdGhvdWdodGZ1bCBtZXNz
YWdlLg0KDQpJIHRoaW5rIG9uZSB0aGluZyB5b3UgYW5hbHlzaXMgZG9lc24ndCBjYXB0dXJl
IGlzIHRoZSAlIG9mIHBpZWNlcyBhcmUNCm1vdmVkIGluIGEgc2luZ2xlIHR3aXN0LiAgRm9y
IGEgcHV6emxlIGxpa2UgdGhlIFBlbnR1bHRpbWF0ZSB3aGVyZSA1MCUNCm9mIHRoZSBwaWVj
ZXMgbW92ZSBpbiBhIHR3aXN0IGl0IGRvZXNuJ3QgdGFrZSBtYW55IG1vdmVzIHRvIHNjcmFt
YmxlDQp0aGUgcHV6emxlIGJleW9uZCByZWNvZ25pdGlvbi4NCg0KSSd2ZSBzZWVuIHRoaXMg
cmVmZXJyZWQgdG8gYXMgdGhlICJicmFuY2hpbmctZmFjdG9yIiBiZWNhdXNlIGlmIHlvdQ0K
aW1hZ2luZSBhIHRyZWUgd2hlcmUgdGhlIHNvbHZlZCBzdGF0ZSBpcyB0aGUgcm9vdCBub2Rl
IGFuZCB0aGUNCm5leHQtbW9zdCBzb2x2ZWQgc3RhdGVzIGFyZSBpdHMgY2hpbGRyZW4gdGhl
biB0aGUgbW9yZSBwaWVjZXMgeW91IGFyZQ0KZm9yY2VkIHRvIG1vdmUgaW4gYSBzaW5nbGUg
dHdpc3QgdGhlIGZhcnRoZXIgYXdheSBmcm9tIHRoZSByb290IHlvdQ0Kd2lsbCBicmFuY2gu
ICBJIGRvbid0IGhhdmUgdGhlIHRpbWUgdG8gbWFrZSB0aGlzIGFyZ3VtZW50IG1vcmUgcmln
ZXJvdXMNCmJ1dCBvYnZpb3VzbHkgaW4gdGVybXMgb2YgYnJhbmNoaW5nIGZhY3RvcnMgdGhl
IG9yZGVyIHdvdWxkIGJlDQpNZWdhbWlueCA8IFB5cmFtaW54IENyeXN0YWwgPCBTdGFybWlu
eCA8IFBlbnR1bHRpbWF0ZQ0KYXMgdGhpcyBqdXN0IGZvbGxvd3MgdGhlIGN1dC1kZXB0aC4N
Cg0KRXNwZWNpYWxseSB0cm91YmxpbmcgaXMgdGhhdCB5b3UgcmVxdWlyZSBtb3JlIG1vdmVz
IHRvIHNjcmFtYmxlIGENClN0YXJtaW54IGFuZCBhIFBlbnR1bHRpbWF0ZSB0aGFuIGh1bWFu
cyBjYW4gc29sdmUgdGhlbS4gIEh1bWFuDQpzb2x2aW5nIHN0cmF0ZWdpZXMgYXJlIHZlcnkg
aW5lZmZpY2llbnQgY29tcGFyZWQgdG8gImdvZCdzIG51bWJlciIgZm9yDQp0aGVzZSBwdXp6
bGVzLiAgQmFzZWQgb24gaW50dWl0aW9uIGFuZCBhIGxvdCBvZiBjb21wdXRlciBzZWFyY2hp
bmcNCmVzdGltYXRlIGdvZCdzIG51bWJlciBmb3IgdGhlIFBlbnR1bHRpbWF0ZSBpcyBwcm9i
YWJseSBiZXR3ZWVuIDQwIGFuZA0KNzAgbW92ZXMuDQoNClRoZSBkZWVwZXItY3V0IHRoZSBw
dXp6bGUgaXMgdGhlIGJpZ2dlciB0aGUgYm9vc3QgeW91IGdldCBmcm9tIGVhY2gNCnJhbmRv
bSB0d2lzdCB0aGF0IHlvdSBkby4NCg0KUGVyaGFwcyB5b3UgY2FuIGluY29ycG9yYXRlIHNv
bWUgZmFjdG9yIGxpa2U6DQoNCi0gLTEgKihsbiAoQkYlIC8gMikpIC8gMw0KDQpXaGVyZSBC
RiUgaXMgdGhlIG51bWJlciBvZiBwaWVjZXMgaW4gdGhlIHB1enpsZSB0aGF0IG1vdmUgaW4g
YSBzaW5nbGUNCnR3aXN0LiAgVGhlIFBlbnR1dGltYXRlIHdvdWxkIGhhdmUgYSB2YWx1ZSBv
ZiAuNSB0aGVyZS4gIFlvdSdsbCB3YW50IHRvDQpwbGF5IHdpdGggdGhpcyBhbmQgdGhlIGNv
bnN0YW50cyB0byBzZWUgaWYgaXQgcHJvZHVjZXMgcmVzdWx0cyB0aGF0DQp5b3UgbGlrZS4N
Cg0KSSB0aGluayB5b3Ugc2hvdWxkIHNob290IGZvciBhIFN0YXJtaW54IHNjcmFtYmxlIGF0
IDIwMC0yNTAgbW92ZXMgYW5kIGENClBlbnR1bHRpbWF0ZSBzY3JhbWJsZSBhdCA4MC0xMDAg
bW92ZXMuICBZb3VyIE1lZ2FtaW54IGFuZCBQeXJhbWlueA0KQ3J5c3RhbCBudW1iZXJzIGxv
b2sgZ29vZCB0byBtZS4NCg0KQnJhbmRvbg0KDQoNCg0KLS0tLS1CRUdJTiBQR1AgU0lHTkFU
VVJFLS0tLS0NClZlcnNpb246IEdudVBHIHYyLjAuMTcgKEdOVS9MaW51eCkNCg0KaUVZRUFS
RUNBQVlGQWszSGZhZ0FDZ2tRcWFHUHpBc2w5NEp3R3dDZ3hpVlpYSzIyVzMyOHJLRStjQTBt
d2RHcw0Kend3QW4wck9paklwcERzV1llSGdpOWdwZkplWXBjZmsNCj1IdjlxDQotLS0tLUVO
RCBQR1AgU0lHTkFUVVJFLS0tLS0NCg==

Hello David,

I'm getting close here. Please do me a favor and add all of the test
values and their outputs in your favorite language something like this:
System.out.println("Goldilocks Function for");
System.out.println("2^3 cube = " + goldilocks(2*2*2, 6,
2*2*6, 0, 3) + " expected = 11");
System.out.println("3^3 cube = " + goldilocks(3*3*3-1, 6,
3*3*6, 6, 3) + " expected = 25");
System.out.println("4^3 cube = " + goldilocks(4*4*4-2*2*2, 6,
4*4*6, 4*6, 3) + " expected = 43");
System.out.println("3^4 cube = " + goldilocks(3*3*3*3, 8, 216,
8*1, 4) ....

I want to know when I've gotten the correct formula and that it's
expected output is it exactly right for all the puzzles that you expect.

Thanks,
-Melinda

=C2=A0



=20=20


=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20
Thanks for the clarification David. I thought there would be somethi=
ng like that to explain the discrepancy. I would have been incredibly impr=
essed it it applied to every single known puzzle, although at the rate you =
seem to be churning out formulas I guess that one is only a matter of time =
;). It's impressive that the new numbers are so close to what the WCA uses=
already, that's definitely a sign of the formula being very well designed.=
And to think you keep worrying about not being able to contribute much he=
re, there's clearly no risk of that happening any time soon.



Matt



--- In 4D_Cubing@yahoogroups.com, David Smith wrote:

>

> Hi Melinda and Matt,

>=20

> Melinda, thanks so much for your positive words and encouragement that I =
am

> an asset to this wonderful community of good people!=C3=82=C2=A0 It sound=
s like the Android

> work is very interesting and fun; good luck with that.=C3=82=C2=A0 It's c=
ertainly very impressive!

>=20

> Matt, thanks for the welcome!=C3=82=C2=A0 I can explain why the formula d=
id not work for the

> starminx.=C3=82=C2=A0 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'.=C3=
=82=C2=A0 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.=C3=82=C2=A0 The rea=
son why the starminx

> is so much larger is that it is built into the formula that order-3 puzzl=
es will have

> one 1-colored piece per face.=C3=82=C2=A0 The fact that there are six per=
face greatly increases

> the first factor of AveNumTwists, which makes the entire count much large=
r than

> it ought to be.=C3=82=C2=A0 My formula does work for all MagicCube4D, 5D =
and 7D puzzles

> however.

>=20

> Having said this, I did realize this morning that I had jumped to conclus=
ions

> when I said the formula works for puzzles of any dimension.=C3=82=C2=A0 I=
have improved the

> formula to account for this, and it turns out to be remarkably accurate.=
=C3=82=C2=A0 I also

> modified the last term, turning a base-2 logarithm into a base-4 logarith=
m. (I

> would consider this an improvement rather than a correction, but anyone c=
an feel

> free to disagree! ;) )=C3=82=C2=A0 I have to admit; which base to choose =
originally was a bit of=20

> guesswork.=C3=82=C2=A0 It turns out that the base-2 logarithm formula, ev=
en when taking into

> account the lower number of dimensions, did not work as well for the mega=
minx

> as it did for the cubes.=C3=82=C2=A0 I realized that if I doubled the bas=
e of the logarithm, the

> megaminx almost automatically 'snapped' into place, again as if by magic.=
=C3=82=C2=A0 Here

> is the revised formula:

> __________________________________________________________

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

> Npieces =3D number of pieces in the puzzle (including

> 1-colored pieces)

>=20

> Nfaces =3D number of faces in the puzzle

>=20

> Nstickers =3D number of stickers in the puzzle

>=20

> N1Cpieces =3D number of 1-colored pieces in the puzzle

> d =3D dimension of the puzzle

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

>=20

> ln(x) =3D natural logarithm of x

>=20

> log4(x) =3D base 4 logarithm of x =3D ln(x)/ln(4) =3D

> ln(x)/1.386

>=20

>=20

> AveNumTwists =3D (Npieces*Nfaces/(Nstickers - N1Cpieces)) *

> (0.577+ln(Npieces))

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

>=20

> Number of Twists to Scramble (round to nearest integer) =3D

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

>=20

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

>=20

> __________________________________________________________

>=20

> The great thing about this new formula is that all of the 4-dimensional c=
ubes

> keep the same value.=C3=82=C2=A0 The simplex becomes 14 moves, and the 12=
0-cell becomes

> 1783.=C3=82=C2=A0 I believe that both of these counts are accurate.=C3=82=
=C2=A0 My basis for the base-4

> logarithm was from the 3D counts Melinda pointed out to me (thanks Melind=
a!)

> Just see how accurate my formula is in 3 dimensions:

>=20

> 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)

>=20

> These counts are remarkably close to the WCA counts, as you can see!=C3=
=82=C2=A0 I was

> very surprised to see that.

>=20

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

>=20

> All the best,

> David

>=20

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

>=20

> From: Melinda Green

> Subject: Re: [MC4D] Goldilock's function

> To: 4D_Cubing@yahoogroups.com

> Date: Saturday, May 7, 2011, 1:40 AM

>=20

>=20

>=20

>=20

>=20

>=20

>=20

> =C3=82=C2=A0

>=20

>=20

>=20

>=20=20=20

>=20

>=20

>=20=20=20=20=20

>=20=20=20=20=20=20=20

>=20=20=20=20=20=20=20

>=20=20=20=20=20=20=20

>=20

>=20=20=20

>=20=20=20

> Wow, what a great email, David!! I especially liked your signposts

> showing where the scary math begins and ends.

>=20

>=20=20=20=20=20

>=20

> 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.

>=20

>=20=20=20=20=20

>=20

> 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.=C3=
=82=C2=A0

> :-D=C3=82=C2=A0 Luckily the timing is good as I've finished all the A=
ndroid

> projects that I set out to build and am not working yet.

>=20

>=20=20=20=20=20

>=20

> 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.

>=20

>=20=20=20=20=20

>=20

> 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!=C3=82=C2=A0 :-)

>=20

>=20=20=20=20=20

>=20

> -Melinda

>=20

>=20=20=20=20=20

>=20

> On 5/6/2011 7:45 PM, David Smith wrote:

>=20=20=20=20=20

>=20=20=20=20=20=20=20

>=20=20=20=20=20=20=20

>=20=20=20=20=20=20=20

>=20=20=20=20=20=20=20=20=20

>=20=20=20=20=20=20=20=20=20=20=20

> Hi Melinda (and

> everyone else),

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

>=20

> I spent most of today working on the Goldilocks function

> problem, and believe I

>=20

> have found a good function that will work!=C3=82=C2=A0 It's=
a bit

> detailed, so I hope that's not a

>=20

> problem.=C3=82=C2=A0 It's the simplest one I could come up =
with that

> is very well mathematically

>=20

> justified.

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

>=20

> Here is the pseudocode:

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

>=20

> Npieces =3D number of pieces in the puzzle (including

> 1-colored pieces)

>=20

> Nfaces =3D number of faces in the puzzle

>=20

> Nstickers =3D number of stickers in the puzzle

>=20

> N1Cpieces =3D number of 1-colored pieces in the puzzle

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

>=20

> ln(x) =3D natural logarithm of x

>=20

> log2(x) =3D base 2 logarithm of x =3D ln(x)/ln(2) =3D

> ln(x)/0.693

>=20

> __________________________________________________________

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

>=20

> AveNumTwists =3D (Npieces*Nfaces/(Nstickers - N1Cpieces)) *

> (0.577+ln(Npieces))

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

>=20

> Number of Twists to Scramble (round to nearest integer) =3D

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

>=20

> AveNumTwists * log2(Nfaces)

>=20

> __________________________________________________________

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

>=20

> Hopefully that's complex enough! ;)=C3=82=C2=A0 I observed =
that you

> have all of the functions

>=20

> required (by attempting to create the ordinary Rubik's

> cube, which was apparently

>=20

> BRILLIANT!) except possibly log2 and N1Cpieces.=C3=82=C2=A0=
I gave

> you a conversion formula

>=20

> for the former, and I'm betting you have the latter, but

> if not it shouldn't be too difficult

>=20

> to implement.

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

>=20

> *** WARNING! MATHEMATICS CONTENT AHEAD! ***

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

>=20

> I'll give a brief explanation.=C3=82=C2=A0 It took some

> experimentation to arrive at this formula; I

>=20

> tried many different approaches; this is the one that

> really worked.=C3=82=C2=A0 AveNumTwists

>=20

> counts the average number of twists needed to move every

> piece of a puzzle at least

>=20

> once. (Of course this number will in fact move many pieces

> more than once).=C3=82=C2=A0 It should

>=20

> hopefully be clear that this average number of twists will

> provide a well-scrambled

>=20

> puzzle when applied more than once.=C3=82=C2=A0 The second =
factor of

> AveNumTwists utilizes a

>=20

> logarithm and the number 0.577, which some of you may

> recognize as the gamma

>=20

> constant.=C3=82=C2=A0 This factor is an approximation of th=
e nth

> harmonic number (sum of the

>=20

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

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

>=20

> The last term of the final calculation uses the insight I

> had that as the number of

>=20

> faces of the puzzle doubles, we need to move every piece

> an additional time, by

>=20

> adding AveNumTwists one more time.=C3=82=C2=A0 Of course, a=
ttempting

> to move every piece

>=20

> across the entire puzzle, even via a direct path, would

> produce astronomical results

>=20

> for the 120-cell and other puzzles with a large number of

> faces.=C3=82=C2=A0 For the 120-cell,=20

>=20

> AveNumTwists is about 7, which sounds right, considering

> that even with 10,000

>=20

> twists you will for all practical purposes never find a

> piece on the opposite side of

>=20

> the puzzle from where it started. (An aside: I proved that

> my original idea that the

>=20

> number of twists needed to randomize the 120-cell could be

> in the millions or higher

>=20

> was correct.)=C3=82=C2=A0 So, I saw that AveNumTwists needs=
to be

> multiplied by the base 2

>=20

> logarithm of the number of faces of the puzzle (there is

> no need to consider the

>=20

> size of the puzzle here; the number of faces is the

> important factor to consider).

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

>=20

> *** MATHEMATICS CONTENT HAS CEASED! ***

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

>=20

> And as if by magic, when these calculations are performed

> we get the expected

>=20

> values for the 3^4 cube and the 120-cell!=C3=82=C2=A0 Here =
are the

> values I have computed so

>=20

> far:

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

>=20

> 3^4 cube: 46 twists

>=20

> 4^4 cube: 78 twists

>=20

> 5^4 cube: 115 twists

>=20

> order-3 simplex: 16 twists

>=20

> order-3 120-cell: 2487

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

>=20

> Here are some interesting observations:=C3=82=C2=A0 The num=
ber of

> twists for the higher-order

>=20

> cubes appears to be growing larger that your previous

> function was as the order

>=20

> increases.=C3=82=C2=A0 Also, the number of twists for the o=
rder-3

> simplex is just over half of the=20

>=20

> previous number!=C3=82=C2=A0 I applied 16 twists to the puz=
zle (by

> doing a full scramble and

>=20

> solving 14 moves), and it did look just as scrambled as

> the original 30 twists.=C3=82=C2=A0 The

>=20

> number for the 120-cell agrees with Andrey's analysis that

> 1000 twists is not enough

>=20

> for a good scramble.

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

>=20

> Well, what do you think Melinda?=C3=82=C2=A0 Do these numbe=
rs look

> too large?=C3=82=C2=A0 Hopefully the

>=20

> calculation isn't too complex; I don't see any way to

> simplify it.=C3=82=C2=A0 I am very happy

>=20

> with how my function turned out, and do believe it is

> matheamtically justified,

>=20

> and so should work for every puzzle.=C3=82=C2=A0 Also, ther=
e is

> nothing special about 4

>=20

> dimensions - this function should work for MagicCube5D and

> MagicCube7D as

>=20

> well, if the programmers are interested.=C3=82=C2=A0 Just n=
oting

> that!

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

>=20

> Melinda, thanks for giving me this nice problem to work

> on, and I hope I was

>=20

> helpful!=C3=82=C2=A0 It was a fun way to spend the day. :)=
=C3=82=C2=A0 I look

> froward to hearing from

>=20

> you.=C3=82=C2=A0 Until then, have a great weekend everybody=
!

>=20

>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20

>=20

> All the best,

>=20

> David

>





=20=20=20=20
=20=20=20=20=20

=20=20=20=20
=20=20=20=20


=20



=20=20




--0-258743496-1304932799=:76129
Content-Type: text/html; charset=utf-8
Content-Transfer-Encoding: quoted-printable

top" style=3D"font: inherit;">HI Matt, Thanks a lot for your positiv= e assessment of my work!  I'm glad I was able to clarify my formula= for you.  I appreciate that you are helping me realize I belong he= re and have much to contribute!  I don't doubt that anymore. :) >Thanks again! All the best, David --- On Sat, 5/7/11, = Matthew <damienturtle@hotmail.co.uk> wrote: style=3D"border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; paddin= g-left: 5px;"> From: Matthew <damienturtle@hotmail.co.uk> Subje= ct: Re: [MC4D] Goldilock's function To: 4D_Cubing@yahoogroups.com Dat= e: Saturday, May 7, 2011, 4:47 PM   =20=20=20=20=20=20 =20=20=20=20=20=20 Thanks for the clarification David. I thought there would be some= thing like that to explain the discrepancy. I would have been incredibly i= mpressed it it applied to every single known puzzle, although at the rate y= ou seem to be churning out formulas I guess that one is only a matter of ti= me ;). It's impressive that the new numbers are so close to what the WCA u= ses already, that's definitely a sign of the formula being very well design= ed. And to think you keep worrying about not being able to contribute much= here, there's clearly no risk of that happening any time soon. Matt --- In arget=3D"_blank" href=3D"/mc/compose?to=3D4D_Cubing%40yahoogroups.com">4D_C= ubing@yahoogroups.com, David Smith <djs314djs314@...> wrote: > > 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!=C3=82  It so= unds like the Android > work is very interesting and fun; good luck with that.=C3=82  It'= s certainly very impressive! > > Matt, thanks for the welcome!=C3=82  I can explain why the formul= a did not work for the > starminx.=C3=82  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'.= =C3=82  That is to say, > faces are cut evenly, all 1-colored pieces are on the inside of the fa= ce and spaced > evenly and according to the shape of the puzzle, etc.=C3=82  The = reason why the starminx > is so much larger is that it is built into the formula that order-3 pu= zzles will have > one 1-colored piece per face.=C3=82  The fact that there are six = per face greatly increases > the first factor of AveNumTwists, which makes the entire count much la= rger than > it ought to be.=C3=82  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 conc= lusions > when I said the formula works for puzzles of any dimension.=C3=82 = ; I have improved the > formula to account for this, and it turns out to be remarkably accurat= e.=C3=82  I also > modified the last term, turning a base-2 logarithm into a base-4 logar= ithm. (I > would consider this an improvement rather than a correction, but anyon= e can feel > free to disagree! ;) )=C3=82  I have to admit; which base to choo= se originally was a bit of > guesswork.=C3=82  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 m= egaminx > as it did for the cubes.=C3=82  I realized that if I doubled the = base of the logarithm, the > megaminx almost automatically 'snapped' into place, again as if by mag= ic.=C3=82  Here > is the revised formula: > __________________________________________________________ > > > Npieces =3D number of pieces in the puzzle (including > 1-colored pieces) > > Nfaces =3D number of faces in the puzzle > > Nstickers =3D number of stickers in the puzzle > > N1Cpieces =3D number of 1-colored pieces in the puzzler> > d =3D dimension of the puzzle > > > > ln(x) =3D natural logarithm of x > > log4(x) =3D base 4 logarithm of x =3D ln(x)/ln(4) =3D> > ln(x)/1.386 > > > AveNumTwists =3D (Npieces*Nfaces/(Nstickers - N1Cpieces)= ) * > (0.577+ln(Npieces)) > > > > Number of Twists to Scramble (round to nearest integer) = =3D > > > > AveNumTwists * (d-1+log4(Nfaces/(2*d))) > > __________________________________________________________ > > The great thing about this new formula is that all of the 4-dimensiona= l cubes > keep the same value.=C3=82  The simplex becomes 14 moves, and the= 120-cell becomes > 1783.=C3=82  I believe that both of these counts are accurate.=C3= =82  My basis for the base-4 > logarithm was from the 3D counts Melinda pointed out to me (thanks Mel= inda!) > 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!= =C3=82  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@...> wrote: > > From: Melinda Green <melinda@...> > Subject: Re: [MC4D] Goldilock's function > To: target=3D"_blank" href=3D"/mc/compose?to=3D4D_Cubing%40yahoogroups.com">4D= _Cubing@yahoogroups.com > Date: Saturday, May 7, 2011, 1:40 AM > > > > > > > > =C3=82  > > > > > > > > > > > > > > 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 al= l > the puzzles you tested do indeed sound ideal. I'm not surprised th= at > the simplex needs fewer than my 1-minute formula gives, and that t= he > 120 Cell needs a lot more--as Andrey has recently shown us. It'sr> > also great that your inputs are values we should either have on ha= nd > or be able to produce without much trouble, and that your equation= s > are simple enough that I think I can handle it. This is all exactl= y > what I had hoped for, and if it is not, then I suspect you'll ber> > 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.<= br> > > > > Of course this all puts the ball in my court now. I did the Androi= d > port in order to learn Android graphics and to impress potentialr> > employers, but I have a new laptop and have not been looking forwa= rd > 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.= =C3=82  > :-D=C3=82  Luckily the timing is good as I've finished all th= e 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<= br> > 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 y= ou > back? Actually, your enthusiasm is even more valuable than your ma= th > skills, but I'll very happily take both!=C3=82  :-) > > > > -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!=C3=82  I= t's a bit > detailed, so I hope that's not a > > problem.=C3=82  It's the simplest one I could come = up with that > is very well mathematically > > justified. > > > > Here is the pseudocode: > > > > Npieces =3D number of pieces in the puzzle (including> > 1-colored pieces) > > Nfaces =3D number of faces in the puzzle > > Nstickers =3D number of stickers in the puzzle > > N1Cpieces =3D number of 1-colored pieces in the puzzler> > > > > ln(x) =3D natural logarithm of x > > log2(x) =3D base 2 logarithm of x =3D ln(x)/ln(2) =3D> > ln(x)/0.693 > > __________________________________________________________ > > > > AveNumTwists =3D (Npieces*Nfaces/(Nstickers - N1Cpieces)= ) * > (0.577+ln(Npieces)) > > > > Number of Twists to Scramble (round to nearest integer) = =3D > > > > AveNumTwists * log2(Nfaces) > > __________________________________________________________ > > > > Hopefully that's complex enough! ;)=C3=82  I observ= ed that you > have all of the functions > > required (by attempting to create the ordinary Rubik'sr> > cube, which was apparently > > BRILLIANT!) except possibly log2 and N1Cpieces.=C3=82&nb= sp; 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.=C3=82  It took some<= br> > experimentation to arrive at this formula; I > > tried many different approaches; this is the one that> > really worked.=C3=82  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 piec= es > more than once).=C3=82  It should > > hopefully be clear that this average number of twists wi= ll > provide a well-scrambled > > puzzle when applied more than once.=C3=82  The seco= nd factor of > AveNumTwists utilizes a > > logarithm and the number 0.577, which some of you may> > recognize as the gamma > > constant.=C3=82  This factor is an approximation of= the nth > harmonic number (sum of the > > first n terms in the harmonic series) for n =3D 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.=C3=82  Of course= , attempting > 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 o= f > faces.=C3=82  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<= br> > piece on the opposite side of > > the puzzle from where it started. (An aside: I proved th= at > my original idea that the > > number of twists needed to randomize the 120-cell could = be > in the millions or higher > > was correct.)=C3=82  So, I saw that AveNumTwists ne= eds 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 performe= d > we get the expected > > values for the 3^4 cube and the 120-cell!=C3=82  He= re 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:=C3=82  The = number of > twists for the higher-order > > cubes appears to be growing larger that your previous> > function was as the order > > increases.=C3=82  Also, the number of twists for th= e order-3 > simplex is just over half of the > > previous number!=C3=82  I applied 16 twists to the = puzzle (by > doing a full scramble and > > solving 14 moves), and it did look just as scrambled as<= br> > the original 30 twists.=C3=82  The > > number for the 120-cell agrees with Andrey's analysis th= at > 1000 twists is not enough > > for a good scramble. > > > > Well, what do you think Melinda?=C3=82  Do these nu= mbers look > too large?=C3=82  Hopefully the > > calculation isn't too complex; I don't see any way to> > simplify it.=C3=82  I am very happy > > with how my function turned out, and do believe it is> > matheamtically justified, > > and so should work for every puzzle.=C3=82  Also, t= here is > nothing special about 4 > > dimensions - this function should work for MagicCube5D a= nd > MagicCube7D as > > well, if the programmers are interested.=C3=82  Jus= t noting > that! > > > > Melinda, thanks for giving me this nice problem to work<= br> > on, and I hope I was > > helpful!=C3=82  It was a fun way to spend the day. = :)=C3=82  I look > froward to hearing from > > you.=C3=82  Until then, have a great weekend everyb= ody! > > > > All the best, > > David > =20=20=20=20=20 =20

--0-258743496-1304932799=:76129--

=C2=A0



=20=20


=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20
-----BEGIN PGP SIGNED MESSAGE-----

Hash: SHA1



On Sat, 07 May 2011 13:42:00 -0000 or thereabouts "Matthew"

wrote:



> Hi David, good to see you back.

>=20

> It's an interesting formula you have there, and I would also like a

> bit of background on how you derived it. However, I may have spotted

> a little problem with it, and hopefully the feedback will help

> improve the formula, or prove to not be an issue. It was discussed

> that deeper cut puzzles would require less moves to scramble them,

> since twists affect more pieces, and will thus move pieces around the

> puzzle faster. However, the formula doesn't quite bear this out for

> the various types of face-turning dodecahedra. I hope I haven't made

> a numerical error here, if I have I apologise.

>=20

> Megaminx: 105 twists

> Pyraminx crystal: 81 twists

>=20

> So far so good.

>=20

> Starminx: 381 twists

>=20

> This is far deeper cut than a megaminx, but apparently takes over 3

> times as many moves to scramble? That result doesn't seem correct.

>=20

> Pentultimate: 130 twists

>=20

> I hope I haven't made a mistake, and made false accusations against

> your work. Perhaps there is a way to introduce another parameter,

> either for the number of pieces moved during a twist, or perhaps the

> ratio of pieces which are moved, to those which aren't? Regardless,

> good work here :).

>=20

> Matt





Hi David,



I have been very ill so I haven't had the energy to think about this a

lot or compose a very thoughtful message.



I think one thing you analysis doesn't capture is the % of pieces are

moved in a single twist. For a puzzle like the Pentultimate where 50%

of the pieces move in a twist it doesn't take many moves to scramble

the puzzle beyond recognition.



I've seen this referred to as the "branching-factor" because if you

imagine a tree where the solved state is the root node and the

next-most solved states are its children then the more pieces you are

forced to move in a single twist the farther away from the root you

will branch. I don't have the time to make this argument more rigerous

but obviously in terms of branching factors the order would be

Megaminx < Pyraminx Crystal < Starminx < Pentultimate

as this just follows the cut-depth.



Especially troubling is that you require more moves to scramble a

Starminx and a Pentultimate than humans can solve them. Human

solving strategies are very inefficient compared to "god's number" for

these puzzles. Based on intuition and a lot of computer searching

estimate god's number for the Pentultimate is probably between 40 and

70 moves.



The deeper-cut the puzzle is the bigger the boost you get from each

random twist that you do.



Perhaps you can incorporate some factor like:



- -1 *(ln (BF% / 2)) / 3



Where BF% is the number of pieces in the puzzle that move in a single

twist. The Pentutimate would have a value of .5 there. You'll want to

play with this and the constants to see if it produces results that

you like.



I think you should shoot for a Starminx scramble at 200-250 moves and a

Pentultimate scramble at 80-100 moves. Your Megaminx and Pyraminx

Crystal numbers look good to me.



Brandon







-----BEGIN PGP SIGNATURE-----

Version: GnuPG v2.0.17 (GNU/Linux)



iEYEARECAAYFAk3HfagACgkQqaGPzAsl94JwGwCgxiVZXK22W328rKE+cA0mwdGs

zwwAn0rOijIppDsWYeHgi9gpfJeYpcfk

=3DHv9q

-----END PGP SIGNATURE-----



=20=20=20=20
=20=20=20=20=20

=20=20=20=20
=20=20=20=20


=20



=20=20




--0-639919155-1304937397=:19105
Content-Type: text/html; charset=utf-8
Content-Transfer-Encoding: quoted-printable

top" style=3D"font: inherit;">Hi Brandon, Thanks for writing, and I = hope you are starting to feel better!  No worries for taking your t= ime, and I hope you are well soon. To clarify, my formula does accou= nt for the percentage of pieces moved in a twist. Otherwise it would not= work at all! :)  I approximate this number as best as I can, and f= or some puzzles it is more accurate than others.  Please remember that= making my formula work for all puzzles is not a priority right now; I a= m dedicated to making it as accurate as possible for all of our higher-d= imensional puzzles in the programs Melinda, Don, Roice, Andrey, and othe= rs have made for us (but only Melinda specifically requested this). <= br>The problem with making my formula work for all puzzles is that for many= puzzles there is no single value for the number of pieces in the puzzle that move in a single twist.  Many puzzles have differently shaped faces, for example the du= oprisms. But the real issue lies in slice moves.  Slice moves affec= t far fewer pieces on many large puzzles, such as the n-cube.  And = the n-cube is one of the most important puzzles to implement as accurate= ly as possible. This would be the ideal formula for AveNumTwists:> AveNumTwists =3D (nPieces/(number of pieces moved in an average twist)= )* (0.577 + ln(nPieces) But the number of pieces moved in an aver= age twist is very hard to calculate for all different puzzles via a sing= le formula.  Some puzzles will have many slice moves, such as the l= arger cubes, others will have none, such as the Pentultimate and the Sta= rminx, some will have few slice moves, such as the dodecahedral prism, some= will have many, etc. My current formula works by treating the pu= zzle as if it has slice moves and calculating the number of pieces moved in a such a move.  It does this via the number of 1-colored = pieces.   This approximation works very well, as for larger cubes= if we used a face move, the count would be far too low.  For MC4D = puzzles with no or few slice moves, such as the 120-cell, it is not too = far off because such puzzles usually have few 1-colored pieces per face,= and many other types of pieces, and are of small order.  The 120-c= ell has 2740 pieces, and only 120 of them are 1-colored, making the slic= e move count negligible.  And there are no 120-cells of order large= r than 3, and there really can't be, just as for all puzzles with no slice = moves, for if there were, slice moves would be required to move the inne= r 1-colored pieces. Note that both the Starminx and Pentultimate are= special cases - they each do not have any slice moves, while at the sam= e time having a large ratio of 1-colored pieces to total number of pieces, due to their small order and unique design. However, it is n= ow clear how we can fix the formula for those two puzzles!  Since t= here are no slice moves, we simply remove the 'minus n1CStickers' in the fo= rmula! We get a new formula for AveNumTwists: AveNumTwists =3D (n= Pieces*nFaces/nStickers)*(0.577+ln(nPieces)) Now, let us see how our= modified formula works for the Starminx and the Pentultimate: St= arminx: 131 moves Pentultimate: 54 moves These numbers should= be much more accurate.  I actually felt that your estimates for th= e Starminx and Pentultimate were too high prior to these calculations (e= specially considering that the Pentultimate only has 32 pieces; I think = 80-100 moves would be too many).  Normally that would just be my op= inion, but in this instance the mathematics seems to back it up.  Nor>offense intended!!  You were probably just making a rough estimate, and perhaps you will agree that my formula now gives very acc= urate results for these two puzzles. Thanks again for writing!&nb= sp; When Melinda deems it appropriate, I will be happy to provide furthe= r explanation of my formula. All the best, David --- On >Mon, 5/9/11, Brandon Enright <bmenrigh@ucsd.edu> wrote:r> : 5px; padding-left: 5px;"> From: Brandon Enright <bmenrigh@ucsd.edu&= gt; Subject: Re: [MC4D] Re: Goldilock's function To: 4D_Cubing@yahoog= roups.com Cc: damienturtle@hotmail.co.uk, bmenrigh@ucsd.edu Date: Mon= day, May 9, 2011, 1:37 AM   =20=20=20=20=20=20 =20=20=20=20=20=20 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Sat, 07 May 2011 13:42:00 -0000 or thereabouts "Matthew" <get=3D"_blank" href=3D"/mc/compose?to=3Ddamienturtle%40hotmail.co.uk">damie= nturtle@hotmail.co.uk> wrote: > Hi David, good to see you back. > > It's an interesting formula you have there, and I would also like a> > bit of background on how you derived it. However, I may have spotted<= br> > a little problem with it, and hopefully the feedback will help > improve the formula, or prove to not be an issue. It was discussed> > that deeper cut puzzles would require less moves to scramble them, > since twists affect more pieces, and will thus move pieces around the<= br> > puzzle faster. However, the formula doesn't quite bear this out forr> > the various types of face-turning dodecahedra. I hope I haven't made<= br> > a numerical error here, if I have I apologise. > > Megaminx: 105 twists > Pyraminx crystal: 81 twists > > So far so good. > > Starminx: 381 twists > > This is far deeper cut than a megaminx, but apparently takes over 3> > times as many moves to scramble? That result doesn't seem correct.> > > Pentultimate: 130 twists > > I hope I haven't made a mistake, and made false accusations against> > your work. Perhaps there is a way to introduce another parameter, > either for the number of pieces moved during a twist, or perhaps ther> > ratio of pieces which are moved, to those which aren't? Regardless,r> > good work here :). > > Matt Hi David, I have been very ill so I haven't had the energy to think about this a lot or compose a very thoughtful message. I think one thing you analysis doesn't capture is the % of pieces are moved in a single twist. For a puzzle like the Pentultimate where 50% of the pieces move in a twist it doesn't take many moves to scramble the puzzle beyond recognition. I've seen this referred to as the "branching-factor" because if you imagine a tree where the solved state is the root node and the next-most solved states are its children then the more pieces you are forced to move in a single twist the farther away from the root you will branch. I don't have the time to make this argument more rigerous but obviously in terms of branching factors the order would be Megaminx < Pyraminx Crystal < Starminx < Pentultimate as this just follows the cut-depth. Especially troubling is that you require more moves to scramble a Starminx and a Pentultimate than humans can solve them. Human solving strategies are very inefficient compared to "god's number" for these puzzles. Based on intuition and a lot of computer searching estimate god's number for the Pentultimate is probably between 40 and 70 moves. The deeper-cut the puzzle is the bigger the boost you get from each random twist that you do. Perhaps you can incorporate some factor like: - -1 *(ln (BF% / 2)) / 3 Where BF% is the number of pieces in the puzzle that move in a single twist. The Pentutimate would have a value of .5 there. You'll want to play with this and the constants to see if it produces results that you like. I think you should shoot for a Starminx scramble at 200-250 moves and a Pentultimate scramble at 80-100 moves. Your Megaminx and Pyraminx Crystal numbers look good to me. Brandon -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.17 (GNU/Linux) iEYEARECAAYFAk3HfagACgkQqaGPzAsl94JwGwCgxiVZXK22W328rKE+cA0mwdGs zwwAn0rOijIppDsWYeHgi9gpfJeYpcfk =3DHv9q -----END PGP SIGNATURE----- =20=20=20=20=20 =20

--0-639919155-1304937397=:19105--

=C2=A0



=20=20


=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20
Hi Brandon,

Thanks for writing, and I hope you are starting to feel better!=C2=A0 No wo=
rries for
taking your time, and I hope you are well soon.

To clarify, my formula does account for the percentage of pieces moved in a=
twist.
Otherwise it would not work at all! :)=C2=A0 I approximate this number as b=
est as I can,
and for some puzzles it is more accurate than others.=C2=A0 Please remember=
that making
my formula work for all puzzles is not a priority right now; I am dedicated=
to making
it as accurate as possible for all of our higher-dimensional puzzles in the=
programs
Melinda, Don, Roice, Andrey, and others have made for us (but only Melinda
specifically requested this).

The problem with making my formula work for all puzzles is that for many pu=
zzles
there is no single value for the number of pieces in the puzzle
that move in a single

twist.=C2=A0 Many puzzles have differently shaped faces, for example the du=
oprisms.
But the real issue lies in slice moves.=C2=A0 Slice moves affect far fewer =
pieces on many
large puzzles, such as the n-cube.=C2=A0 And the n-cube is one of the most =
important
puzzles to implement as accurately as possible.

This would be the ideal formula for AveNumTwists:

AveNumTwists =3D (nPieces/(number of pieces moved in an average twist))*
(0.577 + ln(nPieces)

But the number of pieces moved in an average twist is very hard to calculat=
e for
all different puzzles via a single formula.=C2=A0 Some puzzles will have ma=
ny slice moves,
such as the larger cubes, others will have none, such as the Pentultimate a=
nd the
Starminx, some will have few slice moves, such as the dodecahedral prism, s=
ome
will have many, etc.

My current formula works by treating the puzzle as if it has slice moves an=
d
calculating the number of pieces
moved in a such a move.=C2=A0 It does this via the number
of 1-colored pieces.=C2=A0=C2=A0 This approximation works very well, as for=
larger cubes if we
used a face move, the count would be far too low.=C2=A0 For MC4D puzzles wi=
th no or few
slice moves, such as the 120-cell, it is not too far off because such puzzl=
es usually
have few 1-colored pieces per face, and many other types of pieces, and are=
of
small order.=C2=A0 The 120-cell has 2740 pieces, and only 120 of them are 1=
-colored,
making the slice move count negligible.=C2=A0 And there are no 120-cells of=
order
larger than 3, and there really can't be, just as for all puzzles with no s=
lice moves,
for if there were, slice moves would be required to move the inner 1-colore=
d pieces.

Note that both the Starminx and Pentultimate are special cases - they each =
do
not have any slice moves, while at the same time having a large ratio of 1-=
colored
pieces to total number
of pieces, due to their small order and unique design.
However, it is now clear how we can fix the formula for those two puzzles!=
=C2=A0 Since
there are no slice moves, we simply remove the 'minus n1CStickers' in the f=
ormula!
We get a new formula for AveNumTwists:

AveNumTwists =3D (nPieces*nFaces/nStickers)*(0.577+ln(nPieces))

Now, let us see how our modified formula works for the Starminx and the
Pentultimate:

Starminx: 131 moves

Pentultimate: 54 moves

These numbers should be much more accurate.=C2=A0 I actually felt that your
estimates for the Starminx and Pentultimate were too high prior to these
calculations (especially considering that the Pentultimate only has 32 piec=
es;
I think 80-100 moves would be too many).=C2=A0 Normally that would just be =
my
opinion, but in this instance the mathematics seems to back it up.=C2=A0 No
offense intended!!=C2=A0 You were probably just making a rough
estimate, and
perhaps you will agree that my formula now gives very accurate results for
these two puzzles.

Thanks again for writing!=C2=A0 When Melinda deems it appropriate, I will b=
e happy
to provide further explanation of my formula.

All the best,
David

--- On Mon, 5/9/11, Brandon Enright wrote:

From: Brandon Enright
Subject: Re: [MC4D] Re: Goldilock's function
To: 4D_Cubing@yahoogroups.com
Cc: damienturtle@hotmail.co.uk, bmenrigh@ucsd.edu
Date: Monday, May 9, 2011, 1:37 AM







=C2=A0



=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20
-----BEGIN PGP SIGNED MESSAGE-----

Hash: SHA1



On Sat, 07 May 2011 13:42:00 -0000 or thereabouts "Matthew"

wrote:



> Hi David, good to see you back.

>=20

> It's an interesting formula you have there, and I would also like a

> bit of background on how you derived it. However, I may have spotted

> a little problem with it, and hopefully the feedback will help

> improve the formula, or prove to not be an issue. It was discussed

> that deeper cut puzzles would require less moves to scramble them,

> since twists affect more pieces, and will thus move pieces around the

> puzzle faster. However, the formula doesn't quite bear this out for

> the various types of face-turning dodecahedra. I hope I haven't made

> a numerical error here, if I have I apologise.

>=20

> Megaminx: 105 twists

> Pyraminx crystal: 81 twists

>=20

> So far so good.

>=20

> Starminx: 381 twists

>=20

> This is far deeper cut than a megaminx, but apparently takes over 3

> times as many moves to scramble? That result doesn't seem correct.

>=20

> Pentultimate: 130 twists

>=20

> I hope I haven't made a mistake, and made false accusations against

> your work. Perhaps there is a way to introduce another parameter,

> either for the number of pieces moved during a twist, or perhaps the

> ratio of pieces which are moved, to those which aren't? Regardless,

> good work here :).

>=20

> Matt





Hi David,



I have been very ill so I haven't had the energy to think about this a

lot or compose a very thoughtful message.



I think one thing you analysis doesn't capture is the % of pieces are

moved in a single twist. For a puzzle like the Pentultimate where 50%

of the pieces move in a twist it doesn't take many moves to scramble

the puzzle beyond recognition.



I've seen this referred to as the "branching-factor" because if you

imagine a tree where the solved state is the root node and the

next-most solved states are its children then the more pieces you are

forced to move in a single twist the farther away from the root you

will branch. I don't have the time to make this argument more rigerous

but obviously in terms of branching factors the order would be

Megaminx < Pyraminx Crystal < Starminx < Pentultimate

as this just follows the cut-depth.



Especially troubling is that you require more moves to scramble a

Starminx and a Pentultimate than humans can solve them. Human

solving strategies are very inefficient compared to "god's number" for

these puzzles. Based on intuition and a lot of computer searching

estimate god's number for the Pentultimate is probably between 40 and

70 moves.



The deeper-cut the puzzle is the bigger the boost you get from each

random twist that you do.



Perhaps you can incorporate some factor like:



- -1 *(ln (BF% / 2)) / 3



Where BF% is the number of pieces in the puzzle that move in a single

twist. The Pentutimate would have a value of .5 there. You'll want to

play with this and the constants to see if it produces results that

you like.



I think you should shoot for a Starminx scramble at 200-250 moves and a

Pentultimate scramble at 80-100 moves. Your Megaminx and Pyraminx

Crystal numbers look good to me.



Brandon







-----BEGIN PGP SIGNATURE-----

Version: GnuPG v2.0.17 (GNU/Linux)



iEYEARECAAYFAk3HfagACgkQqaGPzAsl94JwGwCgxiVZXK22W328rKE+cA0mwdGs

zwwAn0rOijIppDsWYeHgi9gpfJeYpcfk

=3DHv9q

-----END PGP SIGNATURE-----



=20=20=20=20
=20=20=20=20=20



=20




=20=20=20=20
=20=20=20=20=20

=20=20=20=20
=20=20=20=20


=20



=20=20




--0-1684802860-1304943896=:73936
Content-Type: text/html; charset=utf-8
Content-Transfer-Encoding: quoted-printable

top" style=3D"font: inherit;">Whoops!  I made an obvious error when I = said, "And there are no 120-cells of order larger than 3, and there real= ly can't be, just as for all puzzles with no slice moves, for if there w= ere, slice moves would be required to move the inner 1-colored pieces." = I don't know exactly why I said that.  I just now realized that if we = do *not* count fixed centers in our counts of nStickers, nPieces, and n1= CStickers, then the formula will be more accurate.  Melinda, I apol= ogize for this oversight.  But, if it is easier to keep the formula= the way it is, I'm fine with that, as the difference between the curren= t formula and this new improved one would be negligible, and besides by = keeping it the way it is, we are slightly overcounting, which is safe.&n= bsp; Also, your program no doubt has functions for the three functions involved already, and they would have to be modified, making the formul= a more complex. I'm fine with overcounting if you are, and it only affec= ts pieces with fixed centers. All the best, David --- = On Mon, 5/9/11, David Smith <djs314djs314@yahoo.com> wr= ote: n-left: 5px; padding-left: 5px;"> From: David Smith <djs314djs314@yah= oo.com> Subject: Re: [MC4D] Re: Goldilock's function To: 4D_Cubing= @yahoogroups.com Date: Monday, May 9, 2011, 6:36 AM v357923685">   =20=20=20=20=20=20 =20=20=20=20=20=20 > Hi Brandon, Thanks for = writing, and I hope you are starting to feel better!  No worries forr>taking your time, and I hope you are well soon. To clarify, my for= mula does account for the percentage of pieces moved in a twist. Otherwi= se it would not work at all! :)  I approximate this number as best as = I can, and for some puzzles it is more accurate than others.  Pleas= e remember that making my formula work for all puzzles is not a priority= right now; I am dedicated to making it as accurate as possible for all = of our higher-dimensional puzzles in the programs Melinda, Don, Roice, A= ndrey, and others have made for us (but only Melinda specifically reques= ted this). The problem with making my formula work for all puzzles i= s that for many puzzles there is no single value for the number of piece= s in the puzzle that move in a single twist.  Many puzzles have differently shaped faces, for example the du= oprisms. But the real issue lies in slice moves.  Slice moves affec= t far fewer pieces on many large puzzles, such as the n-cube.  And = the n-cube is one of the most important puzzles to implement as accurate= ly as possible. This would be the ideal formula for AveNumTwists:> AveNumTwists =3D (nPieces/(number of pieces moved in an average twist)= )* (0.577 + ln(nPieces) But the number of pieces moved in an aver= age twist is very hard to calculate for all different puzzles via a sing= le formula.  Some puzzles will have many slice moves, such as the l= arger cubes, others will have none, such as the Pentultimate and the Sta= rminx, some will have few slice moves, such as the dodecahedral prism, some= will have many, etc. My current formula works by treating the pu= zzle as if it has slice moves and calculating the number of pieces moved in a such a move.  It does this via the number of 1-colored = pieces.   This approximation works very well, as for larger cubes= if we used a face move, the count would be far too low.  For MC4D = puzzles with no or few slice moves, such as the 120-cell, it is not too = far off because such puzzles usually have few 1-colored pieces per face,= and many other types of pieces, and are of small order.  The 120-c= ell has 2740 pieces, and only 120 of them are 1-colored, making the slic= e move count negligible.  And there are no 120-cells of order large= r than 3, and there really can't be, just as for all puzzles with no slice = moves, for if there were, slice moves would be required to move the inne= r 1-colored pieces. Note that both the Starminx and Pentultimate are= special cases - they each do not have any slice moves, while at the sam= e time having a large ratio of 1-colored pieces to total number of pieces, due to their small order and unique design. However, it is n= ow clear how we can fix the formula for those two puzzles!  Since t= here are no slice moves, we simply remove the 'minus n1CStickers' in the fo= rmula! We get a new formula for AveNumTwists: AveNumTwists =3D (n= Pieces*nFaces/nStickers)*(0.577+ln(nPieces)) Now, let us see how our= modified formula works for the Starminx and the Pentultimate: St= arminx: 131 moves Pentultimate: 54 moves These numbers should= be much more accurate.  I actually felt that your estimates for th= e Starminx and Pentultimate were too high prior to these calculations (e= specially considering that the Pentultimate only has 32 pieces; I think = 80-100 moves would be too many).  Normally that would just be my op= inion, but in this instance the mathematics seems to back it up.  Nor>offense intended!!  You were probably just making a rough estimate, and perhaps you will agree that my formula now gives very acc= urate results for these two puzzles. Thanks again for writing!&nb= sp; When Melinda deems it appropriate, I will be happy to provide furthe= r explanation of my formula. All the best, David --- On >Mon, 5/9/11, Brandon Enright <bmenrigh@ucsd.edu> wrote:r> From: = Brandon Enright <bmenrigh@ucsd.edu> Subject: Re: [MC4D] Re: Goldil= ock's function To: 4D_Cubing@yahoogroups.com Cc: damienturtle@hotmail= .co.uk, bmenrigh@ucsd.edu Date: Monday, May 9, 2011, 1:37 AM id=3D"yiv357923685">   =20=20=20=20=20=20 =20=20=20=20=20=20 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Sat, 07 May 2011 13:42:00 -0000 or thereabouts "Matthew" <damienturtle@hotmail.co.uk> wrote: > Hi David, good to see you back. > > It's an interesting formula you have there, and I would also like a> > bit of background on how you derived it. However, I may have spotted<= br> > a little problem with it, and hopefully the feedback will help > improve the formula, or prove to not be an issue. It was discussed> > that deeper cut puzzles would require less moves to scramble them, > since twists affect more pieces, and will thus move pieces around the<= br> > puzzle faster. However, the formula doesn't quite bear this out forr> > the various types of face-turning dodecahedra. I hope I haven't made<= br> > a numerical error here, if I have I apologise. > > Megaminx: 105 twists > Pyraminx crystal: 81 twists > > So far so good. > > Starminx: 381 twists > > This is far deeper cut than a megaminx, but apparently takes over 3> > times as many moves to scramble? That result doesn't seem correct.> > > Pentultimate: 130 twists > > I hope I haven't made a mistake, and made false accusations against> > your work. Perhaps there is a way to introduce another parameter, > either for the number of pieces moved during a twist, or perhaps ther> > ratio of pieces which are moved, to those which aren't? Regardless,r> > good work here :). > > Matt Hi David, I have been very ill so I haven't had the energy to think about this a lot or compose a very thoughtful message. I think one thing you analysis doesn't capture is the % of pieces are moved in a single twist. For a puzzle like the Pentultimate where 50% of the pieces move in a twist it doesn't take many moves to scramble the puzzle beyond recognition. I've seen this referred to as the "branching-factor" because if you imagine a tree where the solved state is the root node and the next-most solved states are its children then the more pieces you are forced to move in a single twist the farther away from the root you will branch. I don't have the time to make this argument more rigerous but obviously in terms of branching factors the order would be Megaminx < Pyraminx Crystal < Starminx < Pentultimate as this just follows the cut-depth. Especially troubling is that you require more moves to scramble a Starminx and a Pentultimate than humans can solve them. Human solving strategies are very inefficient compared to "god's number" for these puzzles. Based on intuition and a lot of computer searching estimate god's number for the Pentultimate is probably between 40 and 70 moves. The deeper-cut the puzzle is the bigger the boost you get from each random twist that you do. Perhaps you can incorporate some factor like: - -1 *(ln (BF% / 2)) / 3 Where BF% is the number of pieces in the puzzle that move in a single twist. The Pentutimate would have a value of .5 there. You'll want to play with this and the constants to see if it produces results that you like. I think you should shoot for a Starminx scramble at 200-250 moves and a Pentultimate scramble at 80-100 moves. Your Megaminx and Pyraminx Crystal numbers look good to me. Brandon -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.17 (GNU/Linux) iEYEARECAAYFAk3HfagACgkQqaGPzAsl94JwGwCgxiVZXK22W328rKE+cA0mwdGs zwwAn0rOijIppDsWYeHgi9gpfJeYpcfk =3DHv9q -----END PGP SIGNATURE----- =20=20=20=20=20 =20 =20=20=20=20=20 =20

--0-1684802860-1304943896=:73936--

=C2=A0



=20=20


=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20
Whoops!=C2=A0 I made an obvious error when I said, "And there are no =
120-cells of order
larger than 3, and there really can't be, just as for all puzzles with no s=
lice moves,
for if there were, slice moves would be required to move the inner 1-colore=
d pieces."
I don't know exactly why I said that.=C2=A0 I just now realized that if we =
do *not* count
fixed centers in our counts of nStickers, nPieces, and n1CStickers, then th=
e
formula will be more accurate.=C2=A0 Melinda, I apologize for this oversigh=
t.=C2=A0 But, if it
is easier to keep the formula the way it is, I'm fine with that, as the dif=
ference
between the current formula and this new improved one would be negligible,
and besides by keeping it the way it is, we are slightly overcounting, whic=
h is
safe.=C2=A0 Also, your program no doubt has functions for the three functio=
ns
involved
already, and they would have to be modified, making the formula more comple=
x.
I'm fine with overcounting if you are, and it only affects pieces with fixe=
d centers.

All the best,
David


--- On Mon, 5/9/11, David Smith wrote:

From: David Smith
Subject: Re: [MC4D] Re: Goldilock's function
To: 4D_Cubing@yahoogroups.com
Date: Monday, May 9, 2011, 6:36 AM







=C2=A0



=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20
Hi Brandon,

Thanks for writing, and I hope you are starting to feel better!=C2=A0 No wo=
rries for
taking your time, and I hope you are well soon.

To clarify, my formula does account for the percentage of pieces moved in a=
twist.
Otherwise it would not work at all! :)=C2=A0 I approximate this number as b=
est as I can,
and for some puzzles it is more accurate than others.=C2=A0 Please remember=
that making
my formula work for all puzzles is not a priority right now; I am dedicated=
to making
it as accurate as possible for all of our higher-dimensional puzzles in the=
programs
Melinda, Don, Roice, Andrey, and others have made for us (but only Melinda
specifically requested this).

The problem with making my formula work for all puzzles is that for many pu=
zzles
there is no single value for the number of pieces
in the puzzle
that move in a single

twist.=C2=A0 Many puzzles have differently shaped faces, for example the du=
oprisms.
But the real issue lies in slice moves.=C2=A0 Slice moves affect far fewer =
pieces on many
large puzzles, such as the n-cube.=C2=A0 And the n-cube is one of the most =
important
puzzles to implement as accurately as possible.

This would be the ideal formula for AveNumTwists:

AveNumTwists =3D (nPieces/(number of pieces moved in an average twist))*
(0.577 + ln(nPieces)

But the number of pieces moved in an average twist is very hard to calculat=
e for
all different puzzles via a single formula.=C2=A0 Some puzzles will have ma=
ny slice moves,
such as the larger cubes, others will have none, such as the Pentultimate a=
nd the
Starminx, some will have few slice moves, such as the dodecahedral prism, s=
ome
will have many, etc.

My current formula works by treating the puzzle as if it has slice moves an=
d
calculating the number of pieces
moved in a such a move.=C2=A0 It does this via the number
of 1-colored pieces.=C2=A0=C2=A0 This approximation works very well, as for=
larger cubes if we
used a face move, the count would be far too low.=C2=A0 For MC4D puzzles wi=
th no or few
slice moves, such as the 120-cell, it is not too far off because such puzzl=
es usually
have few 1-colored pieces per face, and many other types of pieces, and are=
of
small order.=C2=A0 The 120-cell has 2740 pieces, and only 120 of them are 1=
-colored,
making the slice move count negligible.=C2=A0 And there are no 120-cells of=
order
larger than 3, and there really can't be, just as for all puzzles with no s=
lice moves,
for if there were, slice moves would be required to move the inner 1-colore=
d pieces.

Note that both the Starminx and Pentultimate are special cases - they each =
do
not have any slice moves, while at the same time having a large ratio of 1-=
colored
pieces to total number
of pieces, due to their small order and unique design.
However, it is now clear how we can fix the formula for those two puzzles!=
=C2=A0 Since
there are no slice moves, we simply remove the 'minus n1CStickers' in the f=
ormula!
We get a new formula for AveNumTwists:

AveNumTwists =3D (nPieces*nFaces/nStickers)*(0.577+ln(nPieces))

Now, let us see how our modified formula works for the Starminx and the
Pentultimate:

Starminx: 131 moves

Pentultimate: 54 moves

These numbers should be much more accurate.=C2=A0 I actually felt that your
estimates for the Starminx and Pentultimate were too high prior to these
calculations (especially considering that the Pentultimate only has 32 piec=
es;
I think 80-100 moves would be too many).=C2=A0 Normally that would just be =
my
opinion, but in this instance the mathematics seems to back it up.=C2=A0 No
offense intended!!=C2=A0 You were probably just making a rough
estimate, and
perhaps you will agree that my formula now gives very accurate results for
these two puzzles.

Thanks again for writing!=C2=A0 When Melinda deems it appropriate, I will b=
e happy
to provide further explanation of my formula.

All the best,
David

--- On Mon, 5/9/11, Brandon Enright wrote:

From: Brandon Enright
Subject: Re: [MC4D] Re: Goldilock's function
To: 4D_Cubing@yahoogroups.com
Cc: damienturtle@hotmail.co.uk, bmenrigh@ucsd.edu
Date: Monday, May 9, 2011, 1:37 AM







=C2=A0



=20=20=20=20
=20=20=20=20=20=20
=20=20=20=20=20=20
-----BEGIN PGP SIGNED MESSAGE-----

Hash: SHA1



On Sat, 07 May 2011 13:42:00 -0000 or thereabouts "Matthew"

wrote:



> Hi David, good to see you back.

>=20

> It's an interesting formula you have there, and I would also like a

> bit of background on how you derived it. However, I may have spotted

> a little problem with it, and hopefully the feedback will help

> improve the formula, or prove to not be an issue. It was discussed

> that deeper cut puzzles would require less moves to scramble them,

> since twists affect more pieces, and will thus move pieces around the

> puzzle faster. However, the formula doesn't quite bear this out for

> the various types of face-turning dodecahedra. I hope I haven't made

> a numerical error here, if I have I apologise.

>=20

> Megaminx: 105 twists

> Pyraminx crystal: 81 twists

>=20

> So far so good.

>=20

> Starminx: 381 twists

>=20

> This is far deeper cut than a megaminx, but apparently takes over 3

> times as many moves to scramble? That result doesn't seem correct.

>=20

> Pentultimate: 130 twists

>=20

> I hope I haven't made a mistake, and made false accusations against

> your work. Perhaps there is a way to introduce another parameter,

> either for the number of pieces moved during a twist, or perhaps the

> ratio of pieces which are moved, to those which aren't? Regardless,

> good work here :).

>=20

> Matt





Hi David,



I have been very ill so I haven't had the energy to think about this a

lot or compose a very thoughtful message.



I think one thing you analysis doesn't capture is the % of pieces are

moved in a single twist. For a puzzle like the Pentultimate where 50%

of the pieces move in a twist it doesn't take many moves to scramble

the puzzle beyond recognition.



I've seen this referred to as the "branching-factor" because if you

imagine a tree where the solved state is the root node and the

next-most solved states are its children then the more pieces you are

forced to move in a single twist the farther away from the root you

will branch. I don't have the time to make this argument more rigerous

but obviously in terms of branching factors the order would be

Megaminx < Pyraminx Crystal < Starminx < Pentultimate

as this just follows the cut-depth.



Especially troubling is that you require more moves to scramble a

Starminx and a Pentultimate than humans can solve them. Human

solving strategies are very inefficient compared to "god's number" for

these puzzles. Based on intuition and a lot of computer searching

estimate god's number for the Pentultimate is probably between 40 and

70 moves.



The deeper-cut the puzzle is the bigger the boost you get from each

random twist that you do.



Perhaps you can incorporate some factor like:



- -1 *(ln (BF% / 2)) / 3



Where BF% is the number of pieces in the puzzle that move in a single

twist. The Pentutimate would have a value of .5 there. You'll want to

play with this and the constants to see if it produces results that

you like.



I think you should shoot for a Starminx scramble at 200-250 moves and a

Pentultimate scramble at 80-100 moves. Your Megaminx and Pyraminx

Crystal numbers look good to me.



Brandon







-----BEGIN PGP SIGNATURE-----

Version: GnuPG v2.0.17 (GNU/Linux)



iEYEARECAAYFAk3HfagACgkQqaGPzAsl94JwGwCgxiVZXK22W328rKE+cA0mwdGs

zwwAn0rOijIppDsWYeHgi9gpfJeYpcfk

=3DHv9q

-----END PGP SIGNATURE-----



=20=20=20=20
=20=20=20=20=20



=20




=20=20=20=20
=20=20=20=20=20



=20




=20=20=20=20
=20=20=20=20=20

=20=20=20=20
=20=20=20=20


=20



=20=20




--0-1701750626-1304944971=:59909
Content-Type: text/html; charset=utf-8
Content-Transfer-Encoding: quoted-printable

top" style=3D"font: inherit;">Whoops!  I yet again have a correction t= o announce - a correction to a correction! My apologies! The form= ula is correct as it stands; no modification needs to be made regarding = fixed centers!  Also, this statement: "The 120-cell has 2740 pi= eces, and only 120 of them are 1-colored, making the slice move count ne= gligible." was in error as well: The slice move count works correctl= y for the 120-cell, as the centers are fixed. My apologies again!=   I'm a bit rushed this morning.  If I'm not right this time, = I'll eat my hat! All the best, David --- On Mon, 5/9/11= , David Smith <djs314djs314@yahoo.com> wrote: te style=3D"border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padd= ing-left: 5px;"> From: David Smith <djs314djs314@yahoo.com> Sub= ject: Re: [MC4D] Re: Goldilock's function To: 4D_Cubing@yahoogroups.com Da= te: Monday, May 9, 2011, 8:24 AM   =20=20=20=20=20=20 =20=20=20=20=20=20 > Whoops!  I made an obviou= s error when I said, "And there are no 120-cells of order larger than 3,= and there really can't be, just as for all puzzles with no slice moves,>for if there were, slice moves would be required to move the inner 1-color= ed pieces." I don't know exactly why I said that.  I just now reali= zed that if we do *not* count fixed centers in our counts of nStickers, = nPieces, and n1CStickers, then the formula will be more accurate.  = Melinda, I apologize for this oversight.  But, if it is easier to k= eep the formula the way it is, I'm fine with that, as the difference bet= ween the current formula and this new improved one would be negligible, = and besides by keeping it the way it is, we are slightly overcounting, whic= h is safe.  Also, your program no doubt has functions for the three functions involved already, and they would have to be modified, making the formul= a more complex. I'm fine with overcounting if you are, and it only affec= ts pieces with fixed centers. All the best, David --- = On Mon, 5/9/11, David Smith <djs314djs314@yahoo.com> wr= ote: = From: David Smith <djs314djs314@yahoo.com> Subject: Re: [MC4D] Re:= Goldilock's function To: 4D_Cubing@yahoogroups.com Date: Monday, May= 9, 2011, 6:36 AM   =20=20=20=20=20=20 =20=20=20=20=20=20 > Hi Brandon, Thanks for = writing, and I hope you are starting to feel better!  No worries forr>taking your time, and I hope you are well soon. To clarify, my for= mula does account for the percentage of pieces moved in a twist. Otherwi= se it would not work at all! :)  I approximate this number as best as = I can, and for some puzzles it is more accurate than others.  Pleas= e remember that making my formula work for all puzzles is not a priority= right now; I am dedicated to making it as accurate as possible for all = of our higher-dimensional puzzles in the programs Melinda, Don, Roice, A= ndrey, and others have made for us (but only Melinda specifically reques= ted this). The problem with making my formula work for all puzzles i= s that for many puzzles there is no single value for the number of piece= s in the puzzle that move in a single twist.  Many puzzles have differently shaped faces, for example the du= oprisms. But the real issue lies in slice moves.  Slice moves affec= t far fewer pieces on many large puzzles, such as the n-cube.  And = the n-cube is one of the most important puzzles to implement as accurate= ly as possible. This would be the ideal formula for AveNumTwists:> AveNumTwists =3D (nPieces/(number of pieces moved in an average twist)= )* (0.577 + ln(nPieces) But the number of pieces moved in an aver= age twist is very hard to calculate for all different puzzles via a sing= le formula.  Some puzzles will have many slice moves, such as the l= arger cubes, others will have none, such as the Pentultimate and the Sta= rminx, some will have few slice moves, such as the dodecahedral prism, some= will have many, etc. My current formula works by treating the pu= zzle as if it has slice moves and calculating the number of pieces moved in a such a move.  It does this via the number of 1-colored = pieces.   This approximation works very well, as for larger cubes= if we used a face move, the count would be far too low.  For MC4D = puzzles with no or few slice moves, such as the 120-cell, it is not too = far off because such puzzles usually have few 1-colored pieces per face,= and many other types of pieces, and are of small order.  The 120-c= ell has 2740 pieces, and only 120 of them are 1-colored, making the slic= e move count negligible.  And there are no 120-cells of order large= r than 3, and there really can't be, just as for all puzzles with no slice = moves, for if there were, slice moves would be required to move the inne= r 1-colored pieces. Note that both the Starminx and Pentultimate are= special cases - they each do not have any slice moves, while at the sam= e time having a large ratio of 1-colored pieces to total number of pieces, due to their small order and unique design. However, it is n= ow clear how we can fix the formula for those two puzzles!  Since t= here are no slice moves, we simply remove the 'minus n1CStickers' in the fo= rmula! We get a new formula for AveNumTwists: AveNumTwists =3D (n= Pieces*nFaces/nStickers)*(0.577+ln(nPieces)) Now, let us see how our= modified formula works for the Starminx and the Pentultimate: St= arminx: 131 moves Pentultimate: 54 moves These numbers should= be much more accurate.  I actually felt that your estimates for th= e Starminx and Pentultimate were too high prior to these calculations (e= specially considering that the Pentultimate only has 32 pieces; I think = 80-100 moves would be too many).  Normally that would just be my op= inion, but in this instance the mathematics seems to back it up.  Nor>offense intended!!  You were probably just making a rough estimate, and perhaps you will agree that my formula now gives very acc= urate results for these two puzzles. Thanks again for writing!&nb= sp; When Melinda deems it appropriate, I will be happy to provide furthe= r explanation of my formula. All the best, David --- On >Mon, 5/9/11, Brandon Enright <bmenrigh@ucsd.edu> wrote:r> From: = Brandon Enright <bmenrigh@ucsd.edu> Subject: Re: [MC4D] Re: Goldil= ock's function To: 4D_Cubing@yahoogroups.com Cc: damienturtle@hotmail= .co.uk, bmenrigh@ucsd.edu Date: Monday, May 9, 2011, 1:37 AM id=3D"yiv41671531">   =20=20=20=20=20=20 =20=20=20=20=20=20 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Sat, 07 May 2011 13:42:00 -0000 or thereabouts "Matthew" <damienturtle@hotmail.co.uk> wrote: > Hi David, good to see you back. > > It's an interesting formula you have there, and I would also like a> > bit of background on how you derived it. However, I may have spotted<= br> > a little problem with it, and hopefully the feedback will help > improve the formula, or prove to not be an issue. It was discussed> > that deeper cut puzzles would require less moves to scramble them, > since twists affect more pieces, and will thus move pieces around the<= br> > puzzle faster. However, the formula doesn't quite bear this out forr> > the various types of face-turning dodecahedra. I hope I haven't made<= br> > a numerical error here, if I have I apologise. > > Megaminx: 105 twists > Pyraminx crystal: 81 twists > > So far so good. > > Starminx: 381 twists > > This is far deeper cut than a megaminx, but apparently takes over 3> > times as many moves to scramble? That result doesn't seem correct.> > > Pentultimate: 130 twists > > I hope I haven't made a mistake, and made false accusations against> > your work. Perhaps there is a way to introduce another parameter, > either for the number of pieces moved during a twist, or perhaps ther> > ratio of pieces which are moved, to those which aren't? Regardless,r> > good work here :). > > Matt Hi David, I have been very ill so I haven't had the energy to think about this a lot or compose a very thoughtful message. I think one thing you analysis doesn't capture is the % of pieces are moved in a single twist. For a puzzle like the Pentultimate where 50% of the pieces move in a twist it doesn't take many moves to scramble the puzzle beyond recognition. I've seen this referred to as the "branching-factor" because if you imagine a tree where the solved state is the root node and the next-most solved states are its children then the more pieces you are forced to move in a single twist the farther away from the root you will branch. I don't have the time to make this argument more rigerous but obviously in terms of branching factors the order would be Megaminx < Pyraminx Crystal < Starminx < Pentultimate as this just follows the cut-depth. Especially troubling is that you require more moves to scramble a Starminx and a Pentultimate than humans can solve them. Human solving strategies are very inefficient compared to "god's number" for these puzzles. Based on intuition and a lot of computer searching estimate god's number for the Pentultimate is probably between 40 and 70 moves. The deeper-cut the puzzle is the bigger the boost you get from each random twist that you do. Perhaps you can incorporate some factor like: - -1 *(ln (BF% / 2)) / 3 Where BF% is the number of pieces in the puzzle that move in a single twist. The Pentutimate would have a value of .5 there. You'll want to play with this and the constants to see if it produces results that you like. I think you should shoot for a Starminx scramble at 200-250 moves and a Pentultimate scramble at 80-100 moves. Your Megaminx and Pyraminx Crystal numbers look good to me. Brandon -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.17 (GNU/Linux) iEYEARECAAYFAk3HfagACgkQqaGPzAsl94JwGwCgxiVZXK22W328rKE+cA0mwdGs zwwAn0rOijIppDsWYeHgi9gpfJeYpcfk =3DHv9q -----END PGP SIGNATURE----- =20=20=20=20=20 =20 =20=20=20=20=20 =20 =20=20=20=20=20 =20

--0-1701750626-1304944971=:59909--