Message #1673
From: David Smith <djs314djs314@yahoo.com>
Subject: Re: [MC4D] Goldilock’s function
Date: Mon, 09 May 2011 02:19:59 -0700
HI Matt,
Thanks a lot for your positive 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
here 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:
From: Matthew <damienturtle@hotmail.co.uk>
Subject: Re: [MC4D] Goldilock’s function
To: 4D_Cubing@yahoogroups.com
Date: Saturday, May 7, 2011, 4:47 PM
Thanks for the clarification David. I thought there would be something like 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 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 here, there’s clearly no risk of that happening any time soon.
Matt
— In 4D_Cubing@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! It sounds like the Android
> work is very interesting and fun; good luck with that. It’s certainly very impressive!
>
> Matt, thanks for the welcome! I can explain why the formula did not work for the
> starminx. I hadn’t even thought to mention this, which is my fault (and I apologize),
> but the formula will only work for puzzles that are sliced ‘normally’. That is to say,
> faces are cut evenly, all 1-colored pieces are on the inside of the face and spaced
> evenly and according to the shape of the puzzle, etc. The reason why the starminx
> is so much larger is that it is built into the formula that order-3 puzzles will have
> one 1-colored piece per face. The fact that there are six per face greatly increases
> the first factor of AveNumTwists, which makes the entire count much larger than
> it ought to be. My formula does work for all MagicCube4D, 5D and 7D puzzles
> however.
>
> Having said this, I did realize this morning that I had jumped to conclusions
> when I said the formula works for puzzles of any dimension. I have improved the
> formula to account for this, and it turns out to be remarkably accurate. I also
> modified the last term, turning a base-2 logarithm into a base-4 logarithm. (I
> would consider this an improvement rather than a correction, but anyone can feel
> free to disagree! ;) )Â I have to admit; which base to choose originally was a bit of
> guesswork. It turns out that the base-2 logarithm formula, even when taking into
> account the lower number of dimensions, did not work as well for the megaminx
> as it did for the cubes. I realized that if I doubled the base of the logarithm, the
> megaminx almost automatically ‘snapped’ into place, again as if by magic. Here
> is the revised formula:
> __________________________________________________________
>
>
> 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
> d = dimension of the puzzle
>
>
>
> ln(x) = natural logarithm of x
>
> log4(x) = base 4 logarithm of x = ln(x)/ln(4) =
> ln(x)/1.386
>
>
> AveNumTwists = (Npieces*Nfaces/(Nstickers - N1Cpieces)) *
> (0.577+ln(Npieces))
>
>
>
> Number of Twists to Scramble (round to nearest integer) =
>
>
>
> AveNumTwists * (d-1+log4(Nfaces/(2*d)))
>
> __________________________________________________________
>
> The great thing about this new formula is that all of the 4-dimensional cubes
> keep the same value. The simplex becomes 14 moves, and the 120-cell becomes
> 1783. I believe that both of these counts are accurate. My basis for the base-4
> logarithm was from the 3D counts Melinda pointed out to me (thanks Melinda!)
> Just see how accurate my formula is in 3 dimensions:
>
> 2^3 cube: 11 moves
> 3^3 cube: 25 moves
> 4^3 cube: 43 moves (WCA: 40 moves)
> 5^3 cube: 63 moves (WCA: 60 moves)
> 6^3 cube: 85 moves (WCA: 80 moves)
> 4^3 cube: 108 moves (WCA: 100 moves)
> Megaminx: 73 moves (WCA: 70 moves)
>
> These counts are remarkably close to the WCA counts, as you can see! I was
> very surprised to see that.
>
> I have to go now, but I’ll talk to you all later!
>
> All the best,
> David
>
> — On Sat, 5/7/11, Melinda Green <melinda@…> wrote:
>
> From: Melinda Green <melinda@…>
> Subject: Re: [MC4D] Goldilock’s function
> To: 4D_Cubing@yahoogroups.com
> Date: Saturday, May 7, 2011, 1:40 AM
>
>
>
>
>
>
>
> Â
>
>
>
>
>
>
>
>
>
>
>
>
>
> Wow, what a great email, David!! I especially liked your signposts
> showing where the scary math begins and ends.
>
>
>
> I must say this looks *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
>