# # of 4x4x4 centers correctly placed in a scramble



## Lucas Garron (Sep 24, 2007)

I suppose this isn't specifically BLD, but is most practical here.

Does anyone know/can anyone calculate the average number of center pieces on their correct faces on a 4x4x4, and the distribution of probabilities from 1-24,...

a) ...when the cube orientation is preset?

b) ...when one is allowed to rotate the cube to maximize the number?

Johannes? (Got some theory?)
Stefan? (Got a simulation?)
Daniel? Chris? Mátyás?

Empirically, I tend to end up with 6-8 for b) when I do BLD, though I tend to over-value white pieces on D (so this could maybe be higher).
I've had 10, though I accidentally began memo with an x2 from that, giving me only 6...

I just scrambled my 4x4x4 and found 7. This seems to be a "magic number" for me when I do 4x4x4 BLD (i.e. I get it a lot, and 6-8 almost all the time)...
Lemme do an "average":
7 9 (6) 7 8 7 7 (10) 7 6 8 7 > 7.30

 < His glasses are opaque. He's doing 4x4x4 BLD.


----------



## Johannes91 (Sep 24, 2007)

Lucas Garron said:


> Johannes? (Got some theory?)


Theory? Me? What a joke! My math skills are inferior.
Just common sense and Perl one-liners.

```
$ perl -le 'sub _ { my $out; for $n (0..5) { $out += grep {$ _ == $n} @{$_[$n]} } $out } for (1..1e6) { @centers = map {($_)x4} 0..5; my @cube; while (@centers) { push @{$cube[@centers % 6]}, splice @centers, (rand @centers), 1 } $c += _ @cube } print "$c / 1e6 = ", $c / 1e6'
3999087 / 1e6 = 3.999087
```
That's an approximation for a), I'll try to do b) now. For the record, this took 10 minutes.

```
$ perl -mList::Util=max -le 'sub _ { my $out; for $n (0..5) { $out += grep {$ _ == $n} @{$_[$n]} } $out } for (1..1e5) { my @t; for (1..24) { @centers = map {($_)x4} 0..5; my @cube; while (@centers) { push @{$cube[@centers % 6]}, splice @centers, (rand @centers), 1 } push @t,  _ @cube } $c += max @t } print "$c / 1e5 = ", $c / 1e5'
792854 / 1e5 = 7.92854
```
My intuition says that this is correct for b). Not quite a "pure" way of doing it, but simple and logically should give the correct average. (This took 7 minutes)

Edit: Oops, didn't see the "_and the distribution of probabilities_" part. Wait a second.

```
$ perl -mList::Util=max,sum -le 'sub _ { my $out; for $n (0..5) { $out += grep {$ _ == $n} @{$_[$n]} } $out } for (1..1e7) { my @t; for (1..24) { @centers = map {($_)x4} 0..5; my @cube; while (@centers) { push @{$cube[@centers % 6]}, splice @centers, (rand @centers), 1 } push @t,  _ @cube; $ca[$t[-1]]++ } $cb[max @t]++ } ($a,$b) = ((sum @ca),sum @cb); print "\ncorrect centers | times | distribution\n\na)\ntotal: $a\nmean: ",  (sum map $_*$ca[$_], grep $ca[$_], 0..24) / $a, "\n"; $ca[$_] and printf "%2d: %8d  %.3f\n", $_, $ca[$_], $ca[$_]/$a for 0..24; print "\nb)\ntotal: $b\nmean: ", (sum map $_*$cb[$_], grep $cb[$_], 0..24) / $b, "\n"; $cb[$_] and printf "%2d: %8d  %.3f\n", $_, $cb[$_], $cb[$_]/$b for 0..24'

correct centers | times | distribution

a)
total: 240000000
mean: 4.00009665416667

 0:  3338073  0.014
 1: 15230287  0.063
 2: 33765699  0.141
 3: 48334329  0.201
 4: 50206280  0.209
 5: 40249724  0.168
 6: 25874279  0.108
 7: 13676951  0.057
 8:  6054183  0.025
 9:  2274718  0.009
10:   731267  0.003
11:   203462  0.001
12:    48524  0.000
13:    10035  0.000
14:     1850  0.000
15:      295  0.000
16:       40  0.000
17:        4  0.000

b)
total: 10000000
mean: 7.9294182

 4:      161  0.000
 5:    42235  0.004
 6:   848691  0.085
 7:  2971835  0.297
 8:  3331731  0.333
 9:  1856234  0.186
10:   688208  0.069
11:   200317  0.020
12:    48369  0.005
13:    10030  0.001
14:     1850  0.000
15:      295  0.000
16:       40  0.000
17:        4  0.000
```

Last (?) edit: updated the statistics with bigger numbers.


----------



## Lucas Garron (Sep 24, 2007)

Wow, you're fast 
Thanks...

a)
I got 4.0049 with 100,000 trials.
4.00028 for 1,000,000.

```
<< DiscreteMath`Combinatorica`
a = Table[Floor[0.75 + n/4], {n, 1, 24}];
b = Table[0, {25}];
Do[(++b[[#]]) & /@ Table[Total[If[# == 0, 1,0] & /@(RandomPermutation[a] - a)] + 1, {1000}], {1000}]
(MapIndexed[(#*(#2[[1]] - 1)) &, b] // Total)/1000000 // N
```

(MapIndexed[{(#2[[1]] - 1), #} &, b]) gave:
{{0, 13904}, {1, 63649}, {
2, 140850}, {3, 200659}, {4, 209652}, {5, 167744}, {6, 
107520}, {7, 56973}, {8, 25403}, {9, 9462}, {10, 3052}, {11, 863}, {12,
210}, {13, 49}, {14, 7}, {15, 1}, {16, 2}, {17, 0}, {18, 0}, {19, 0}, {20, 
0}, {21, 0}, {22, 0}, {23, 0}, {24, 0}}

Tried again: 3.99599

Who wants to bet that it's theoretically 4? Maybe because there are 4 centers...
Then again, it could be 1 gazillionth off from 4...

This applies to any type of center on any size of cube, right?
So on a 6x6x6 I'd expect 16 centers placed?

How fast is your code? Mine takes 140 seconds for 1000000 checks, consitently... Maybe I should try Perl...

Edit 1: Took out a +, speeds up the code.


----------



## Johannes91 (Sep 24, 2007)

Lucas Garron said:


> Wow, you're fast


Solved about 100 Project Euler problems from shell. Kinda got the hang of it... 



Lucas Garron said:


> Who wants to bet that it's theoretically 4? Maybe because there are 4 centers...
> Then again, it could be 1 gazillionth off from 4...
> 
> This applies to any type of center on any size of cube, right?
> So on a 6x6x6 I'd expect 16 centers placed?


I ran it a few times with 1e6 (1,000,000), and the results average to almost exactly 4 (one of the runs got 4.00005). I don't like proving things, I'll leave that to someone else.

I agree with that it applies to all sizes similarly.



Lucas Garron said:


> How fast is your code? Mine takes 140 seconds for 1000000 checks, consitently... Maybe I should try Perl...


About 53 seconds for that. Perl is really nice for simple things like this. And if you need it to run _really_ fast, use the awesome Inline::C-module. You just put C-function(s) into a string and then you can call those functions from Perl.


----------



## cmhardw (Sep 24, 2007)

Doing this type of problem with just probability and pure maths interests me very much, but I don't yet know how to calculate those types of probabilities. If anyone has any hints I would be appreciative.

Empirically I almost always can memorize the centers of a 4x4 in 3 locations, which would be 19 pieces in my cycle max and 15 minimum because of how I memorize. So that would be 5 pieces solved ranging up to 9 pieces solved.

I can sometimes memorize the centers in 2 locations, giving roughly 12-13 pieces in my cycle leaving 12 or 11 centers already solved. This doesn't happen too terribly often, but it's happened to me often enough that I don't think the probability is too too small for this case.

I wish I could give you a pure number, but again I am still learning how to calculate probabilities like this.

Chris


----------



## Lucas Garron (Sep 30, 2007)

```
a={139216, 635534, 1407486, 2013693, 2091757, 1674656, 1079544, 569305, 252506, 94666, 30534, 8533, 2076, 408, 66, 17, 2, 1, 0, 0, 0, 0, 0, 0, 0};
a=a/Total[a];
c=1;
x=(Table[d=c*((1-(Total[Drop[b, n]])/c)^24);c-=d;d,{n,Length[b]}]/.Indeterminate->0)// N;
(MapIndexed[(#*(#2[[1]]-1))&, x]//Total)/Total[x]//N
```
gives 7.86018 as an average highest value by basically iterating the distribution, assuming independence from each angle of the cube.
Running it on your data gives 7.8594.
So either one of us wrote wrong code, or you cannot assume that each postition reached by a distinct net cube rotation independently follows the single-orientation probability distribution (or perhaps some random number generator is curiously off).


----------

