#-----------------------------------------------------------------------------
# This program analyses the WCA megaminx scrambler. See also:
# http://www.stefan-pochmann.info/spocc/other_stuff/tools/scramble_megaminx/
#
# So far it only computes the probability of where each center ends up. The
# results are shown on the above-mentioned page.
#
# Implementation:
#   1) Configure the scramble length and specify the puzzle (pieces+moves).
#   2) Compute the probability of center C ending up at position P after
#      M moves as $probability{C}{P}{M}. This is done using dynamic programming.
#   3) Evaluate the results.
#
# Note that this is *not* an analysis of a limited number of scrambles, for
# example a million scrambles. This is an analysis of *all* 2^70 possible
# scrambles.
#-----------------------------------------------------------------------------

use strict;

#--- Configure the scramble length
my $scrambleLength = 70;

#--- Specify where the centers start
my %origin = (
  white     => 'U',
  green     => 'F',
  turquoise => 'ULF',
  brown     => 'ULB',
  blue      => 'URB',
  purple    => 'URF',
  yellow    => 'D',
  green2    => 'B',
  pink      => 'DLB',
  blue2     => 'DLF',
  red       => 'DRF',
  orange    => 'DRB'
);

#--- Specify the effects of the moves on the centers (list the cycles)
my %effects = (
  'D++' => 'F ULB URF ULF URB + B DLF DRB DLB DRF',
  'R++' => 'U DLB F ULB DLF + URF B DRF URB D'
);
@effects{'R--','D--'} = map { join ' ', reverse split } @effects{'R++','D++'};

#--- Initialize the center-position probabilities before scrambling
my %probability;
for my $center ( keys %origin ) {
  $probability{$center}{$origin{$center}}{0} = 1;
}

#--- Spread the love (the probabilities through moves)
for my $numberOfMoves ( 1..$scrambleLength ) {
  for my $center ( keys %origin ) {
    for my $positionBeforeMove ( values %origin ) {
      for my $move ( $numberOfMoves%2 ? ( 'R++', 'R--' ) : ( 'D++', 'D--' ) ) {
        my $positionAfterMove = applyMove( $move, $positionBeforeMove );
        $probability{$center}{$positionAfterMove}{$numberOfMoves} +=
          0.5 * $probability{$center}{$positionBeforeMove}{$numberOfMoves-1};
      }
    }
  }
}

#--- Evaluate the center-position probabilities after scrambling
print "          ";
printf "%-6s", $_ foreach values %origin;
print "  min   max      sum\n";
for my $center ( keys %origin ) {
  printf "%9s ", $center;
  my ( $min, $max, $sum ) = ( 100, 0, 0 );
  for my $position ( values %origin ) {
    my $p = 100 * $probability{$center}{$position}{$scrambleLength};
    printf "%.3f ", $p;
    $min = $p if $p < $min;
    $max = $p if $p > $max;
    $sum += $p;
  }
  printf "  %.3f-%.3f => %.3f\n", $min, $max, $sum;
}



#--- Helper for applying a move
sub applyMove {
  my ( $move, $position ) = @_;
  my $effects = join ' + ', map { "$_ $_" } split / \+ /, $effects{$move};
  return $effects =~ /\b$position\b (\w+)/  ?  $1 : $position;
};

#--- Helper for debugging
sub show {
  use Data::Dumper;
  print Dumper( @_ );
};