# 
# Solving the M12 puzzle for a specific using the group theory system GAP.
# (http://www.gap-system.org/)
#
# The M12 puzzle is presented in the Scientific American article
# Rubik's Cube Inspired Puzzles Demonstrate Math's "Simple Groups"
# http://www.sciam.com/article.cfm?id=simple-groups-at-play
# 
# For more info about this GAP program:
# See 
#   http://www.hakank.org/webblogg/archives/001226.html 
#   http://www.hakank.org/webblogg/archives/001227.html 
# for more info about this program.
# 
# Cf http://www.hakank.org/minizinc/M12.mzn for a solution in the
# constraint programming system MiniZinc.
#


#
# Define the operators
#

# Reverse (Inverse)
reverse := PermList([12,11,10,9,8,7,6,5,4,3,2,1]);

# Merge
merge:=PermList([1,3,5,7,9,11,12,10,8,6,4,2]);

# Create the group
g:=Group([reverse, merge]);


# Which group is it?
StructureDescription(g);
# "M12"

Size(g);
# 95040


#
# Create the puzzle to solve
#
puzzle:=[4, 5, 11, 1, 9, 6, 3, 10, 2, 7, 12, 8];;


#
# Solve the puzzle
#
Factorization(g, PermList(puzzle));

#
# This is the recommended function for factorizations, but it gives longer 
# solutions (strings) than Factorization.
#

#
# Create names to identify the operations
#
R:=g.1;
M:=g.2;  
hom:=EpimorphismFromFreeGroup(g:names:=["R","M"]);

#
# Now, solve the puzzle
#
PreImagesRepresentative(hom,PermList(puzzle));


#
# And as a function
#
# Example:
#
# gap> puzzle := [4,5,11,1,9,6,3,10,2,7,12,8];
# gap> M12(puzzle);
# x2^-5*x1*x2^-3*x1*x2^-2*x1*x
#
M12 := function(puzzle) 
  local g, reverse, merge, res;
  reverse := PermList([12,11,10,9,8,7,6,5,4,3,2,1]);
  merge := PermList([1,3,5,7,9,11,12,10,8,6,4,2]);
  g:=Group([reverse, merge]);
  res := Factorization(g, PermList(puzzle));
  return res;
end;