#global definitions

F := (1,7,9,3)(2,4,8,6)(12,37,34,27)(15,38,31,26)(18,39,28,25);
L := (1,19,46,37)(4,22,49,40)(7,25,52,43)(10,16,18,12)(11,13,17,15);
T := (1,28,54,10)(2,29,53,11)(3,30,52,12)(19,25,27,21)(20,22,26,24);
R := (3,39,48,21)(6,42,51,24)(9,45,54,27)(28,34,36,30)(29,31,35,33);
U := (7,16,48,34)(8,17,47,35)(9,18,46,36)(37,43,45,39)(38,40,44,42);
B := (10,21,36,43)(13,20,33,44)(16,19,30,45)(46,52,54,48)(47,49,53,51);

cube := Group( F, L, T, R, U, B );
f := FreeGroup( "F", "L", "T", "R", "U", "B" );
hom := GroupHomomorphismByImages( f, cube, GeneratorsOfGroup( f ), GeneratorsOfGroup( cube ) );

b := "blue";
g := "green";
o := "orange";
r := "red";
w := "white";
y := "yellow";

######################################

IsInputCorrect := function( c )
	#######
	#Input:		c, a cube represented by a list of colours.
	#Precondition:	IsList( c )
	#Output:	true if there are no obvious typos in c, otherwise false.
	#Postcondition:	c does not have obvious typos.
	#######

	local flag, col, i;

	flag := true;
	if not( Size( c ) = 54 ) then
		Print( "Typo. Cube must have 54 colours instead of ", Size( c ), ".\n");
		flag := false;
	fi;
	if not( IsDenseList( c ) ) then
		Print( "Typo. List of colours is not dense.\n");
		flag := false;
	fi;
	if not( IsDuplicateFree( [c[5],c[14],c[23],c[32],c[41],c[50]] ) ) then 
		Print( "Typo. Middlepieces are not duplicate free.\n" );
		flag := false;
	fi;
	col := Collected( c );
	if not( Size( col ) = 6 ) then
		Print( "Typo. Cube must have 6 different colours instead of ", Size( col ), ".\n");
		flag := false;
	fi;
	i := 1;
	while i <= Size( col ) do
		if col[i][1] in [b,g,o,r,w,y] then
			if not( col[i][2] = 9 ) then
				Print( "Typo. ", col[i][2], " pieces coloured in ", col[i][1], " instead of 9.\n");
				flag := false;
			fi;
		else
			Print( "Typo. Colour ", col[i][1], " does not exist.\n");
			flag := false;
		fi;
		i := i + 1;
	od;
	return flag;
end;

######################################

SolvedCube := function( u )
	#######
	#Input:		u, an unsolved cube represented by a list of 54 colours
	#Precondition:	IsInputCorrect( u )
	#Output:	solved cube, represented by a list of 54 colours
	#Postcondition:	middlepiecesC( u ) = middlepiecesC( solved ) and
	#		solved represents a solved cube
	#######

	local middlePiecesC, solved, i, j;

	middlePiecesC := [u[5],u[14],u[23],u[32],u[41],u[50]];
	solved := [];
	i := 1;
	while i <= Size( middlePiecesC ) do
		j := 1;
		while j <= 9 do
			Add( solved, middlePiecesC[i] );
			j := j + 1;
		od;
		i := i + 1;
	od;
	return solved;
end;

######################################

DisplayCube := function( cube )
	#######
	#Input:		cube, represented by a list of 54 colours.
	#Precondition:	IsInputCorrect( cube )
	#Output:	none, function prints the unfolded cube.
	#Postcondition:	none
	#######

	local c, i;

	#only display first character of strings
	c := ShallowCopy( cube );
	i := 1;
	while i <= 54 do
		c[i] := c[i]{[1]};
		i := i + 1;
	od;

	Print( "      ", c[19], " ", c[20], " ", c[21], "\n" );
	Print( "      ", c[22], " ", c[23], " ", c[24], "\n" );
	Print( "      ", c[25], " ", c[26], " ", c[27], "\n" );
	Print( c[10], " ", c[11], " ", c[12], " ", c[1], " ", c[2], " ", c[3], " ", c[28], " ", c[29], " ", c[30], "\n" );
	Print( c[13], " ", c[14], " ", c[15], " ", c[4], " ", c[5], " ", c[6], " ", c[31], " ", c[32], " ", c[33], "\n" );
	Print( c[16], " ", c[17], " ", c[18], " ", c[7], " ", c[8], " ", c[9], " ", c[34], " ", c[35], " ", c[36], "\n" );
	Print( "      ", c[37], " ", c[38], " ", c[39], "\n" );
	Print( "      ", c[40], " ", c[41], " ", c[42], "\n" );
	Print( "      ", c[43], " ", c[44], " ", c[45], "\n" );
	Print( "      ", c[46], " ", c[47], " ", c[48], "\n" );
	Print( "      ", c[49], " ", c[50], " ", c[51], "\n" );
	Print( "      ", c[52], " ", c[53], " ", c[54] );
end;

######################################

FindPosCornerCInCornersC := function( cC, csC )
	#######
	#Input:		cC, a list of 3 colours and
	#		csC, a list of lists of 3 colors
	#Precondition:	IsList( cC ) and
	#		IsList( csC )
	#Output:	i, an index which marks the position of cC in csC and
	#		the permutation p s.t. cC*p in csC
	#Postcondition:	cC = csC[i] and
	#		IsPerm( p ) and
	#		cC*p in csC
	#######

	local s3, i;

	s3 := [(),(1,2),(1,3),(2,3),(1,2,3),(1,3,2)];
	i := 1;
	while i <= Size( s3 ) do
		if Permuted( cC, s3[i] ) in csC then
			return [Position( csC, Permuted( cC, s3[i] ) ),s3[i]];
		fi;
		i := i + 1;
	od;
	ErrorNoReturn( "Corner [", cC[1], ",", cC[2], ",", cC[3], "] not found on the cube." );
end;

######################################

FindPosEdgeCInEdgesC := function( eC, esC )
	#######
	#Input:		eC, a list of 2 colours and
	#		esC, a list of lists of 2 colors
	#Precondition:	IsList( eC ) and
	#		IsList( esC )
	#Output:	i, an index which marks the position of eC in esC and
	#		the permutation p s.t. eC*p in esC
	#Postcondition:	eC = esC[i] and
	#		IsPerm( p ) and
	#		eC*p in esC
	#######

	local s2, i;

	s2 := [(),(1,2)];
	i := 1;
	while i <= Size( s2 ) do
		if Permuted( eC, s2[i] ) in esC then
			return [Position( esC, Permuted( eC, s2[i] ) ),s2[i]];
		fi;
		i := i + 1;
	od;
	ErrorNoReturn( "Edge [", eC[1], ",", eC[2], "] not found on the cube." );
end;

######################################

ColoursToNumbers := function( unsolved, solved )
	#######
	#Input:		unsolved, a cube represented by a list of 54 colours and
	#		solved, a cube represented by a list of 54 colours
	#Precondition:	IsList( unsolved ) and
	#		IsList( solved ) and
	#		IsInputCorrect( unsolved ) and
	#		solved = SolvedCube( unsolved )
	#Output:	l, a list containing the numbers 1..54
	#Postcondition:	IsList( l ) and
	#		Permuted( l, MappingPermListList( solvedNr, unsolvedNr ) ) = [1..54]
	#######

	local l, cornersC, cornersNr, edgesC, edgesNr, i, j, cornerC, edgeC, posPerm, n, c, e;

	l := [,,,,5,,,,,,,,,14,,,,,,,,,23,,,,,,,,,32,,,,,,,,,41,,,,,,,,,50,,,,];

	#Calculate corners of solved cube as colour triples
	cornersNr := [[1,12,25],[3,27,28],[7,18,37],[9,34,39],[10,19,52],[16,43,46],[21,30,54],[36,45,48]];
	cornersC := [];
	i := 1;
	while i <= Size( cornersNr ) do
		j := 1;
		c := [];
		while j <= Size( cornersNr[1] ) do
			Add( c, solved[cornersNr[i][j]] );
			j := j + 1;
		od;
		Add( cornersC, c );
		i := i + 1;
	od;

	#Calculate edges of solved cube as colour doubles
	edgesNr := [[2,26],[4,15],[6,31],[8,38],[11,22],[13,49],[17,40],[20,53],[24,29],[33,51],[35,42],[44,47]];
	edgesC := [];
	i := 1;
	while i <= Size( edgesNr ) do
		j := 1;
		e := [];
		while j <= Size( edgesNr[1] ) do
			Add( e, solved[edgesNr[i][j]] );
			j := j + 1;
		od;
		Add( edgesC, e );
		i := i + 1;
	od;

	#Locate corners of unsolved cube in solved cube
	i := 1;
	while i <= Size( cornersNr ) do
		cornerC := [unsolved[cornersNr[i][1]],unsolved[cornersNr[i][2]],unsolved[cornersNr[i][3]]];
		posPerm := FindPosCornerCInCornersC( cornerC, cornersC );
		n := Permuted( cornersNr[posPerm[1]], posPerm[2]^-1 );
		j := 1;
		while j <= 3 do
			l[cornersNr[i][j]] := n[j];
			j := j + 1;
		od;
		i := i + 1;
	od;

	#Locate edges of unsolved cube in solved cube
	i := 1;
	while i <= Size( edgesNr ) do
		edgeC := [unsolved[edgesNr[i][1]],unsolved[edgesNr[i][2]]];
		posPerm := FindPosEdgeCInEdgesC( edgeC, edgesC );
		n := Permuted( edgesNr[posPerm[1]], posPerm[2] );
		j := 1;
		while j <= 2 do
			l[edgesNr[i][j]] := n[j];
			j := j + 1;
		od;
		i := i + 1;
	od;
	return l;
end;

######################################

Solve := function( unsolved )
	#######
	#Input:		unsolved, a cube represented by a list of 54 colours
	#Precondition:	IsList( unsolved )
	#Output:	solution, a word representing a composition of group generators
	#Postcondition:	IsWord( solution) and
	#		solution applied to unsolved results in SolvedCube( unsolved )
	#######

	local solved, solvedNr, unsolvedNr, p, solution;

	if not( IsInputCorrect( unsolved ) ) then
		return;
	fi;

	solved := SolvedCube( unsolved );
	solvedNr := [1..54];
	unsolvedNr := ColoursToNumbers( solved, unsolved );

	#Evaluate single permutation to solve cube
	p := MappingPermListList( unsolvedNr, solvedNr );

	#Handle non-existing cubes
	if not( p in cube ) then
		ErrorNoReturn( "Cube does not exist. Check input." );
	fi;

	#Decompose single permutation into group generators
	solution := PreImagesRepresentative( hom, p );

	return solution;
end;

######################################

SolveGuide := function( unsolved, n )
	#######
	#Input:		unsolved, a cube represented by a list of 54 colours and
	#		n, a non-negativ integer
	#Precondition:	IsList( unsolved ) and
	#		IsInt( n ) and
	#		n >= 0
	#Output:	nothing is returned, solution gets printed
	#Postcondition:	none
	#######

	local solved, solvedNr, unsolvedNr, p, solution, i, j, partlysolved, middlePiecesC, c, s;

	Print( "Your initial cube:\n" );
	DisplayCube( unsolved );
	Print( "\n\n" );
	if not( IsInputCorrect( unsolved ) ) then
		return;
	fi;

	solved := SolvedCube( unsolved );
	solvedNr := [1..54];
	unsolvedNr := ColoursToNumbers( unsolved, solved );

	#Evaluate single permutation to solve cube
	p := MappingPermListList( solvedNr, unsolvedNr );

	#Handle non-existing cubes
	if not( p in cube ) then
		ErrorNoReturn( "Cube does not exist. Check input." );
	fi;

	#Decompose single permutation into group generators
	solution := PreImagesRepresentative( hom, p );

	if n = 0 then
		Print( Length( solution ), " turns required:\n", solution, "\nYour cube is then solved.\n________________" );
		return;
	fi;
	partlysolved := unsolved;
	i := 1;
	j := 1;
	while i <= Length( solution ) - n do
		s := Subword( solution, i, i + n - 1 );
		Print( "Step ", j, ":\n" );
		Print( s, "\n" );
		partlysolved := Permuted( partlysolved, Image( hom, s ) );
		DisplayCube( partlysolved );
		Print( "\n\n" );
		i := i + n;
		j := j + 1;
	od;
	Print( "Step ", j, ": \n" );
	Print( Subword( solution, i, Length( solution ) ) );
	Print( "\nYour cube is now solved.\n________________" );
	return;
end;

######################################

DistrNumberOfMoves := function( n )
	#######
	#Input:		n, an integer
	#Precondition:	IsList( unsolved ) and
	#		IsInt( n )
	#Output:	a, a list
	#Postcondition:	IsList( a )
	#######

	local c, i, a;

	hom := GroupHomomorphismByImages( f, cube, GeneratorsOfGroup( f ), GeneratorsOfGroup( cube ) );
	a := [];
	i := 1;
	while i <= n do
		c := PreImagesRepresentative( hom, Random( cube ) );
		Add( a, Length( c ) );
		i := i + 1;
	od;
	a := Collected( a );
	return a;
end;