import java.util.*;
import java.text.*;

/**
Looks for semigroups of a given order.  Uses brute force,
so for order bigger than about 4, you need something else.
**/
public class SemiGroupList{
	
	/**
	* Turns an array of length n*n into an n-by-n array
	**/
	protected static int[][] makeSquare(int[] longTab)
	//	throws IllegalArgumentException
	{
	/*	if (longTab == null)
			throw new IllegalArgumentException("argument longTab is null");

		if (longTab.length == 0)
			throw new IllegalArgumentException(
			"argument longTab is of length zero");
	*/
	
		//Figure the floor of the squareroot of the length.  Do to
		//numerical error, we may get something one less than expected.
		int width = (int) Math.floor(Math.sqrt(longTab.length));
		
		//so we compenstate.
		if ((width+1)*(width+1) <= longTab.length)
			width++;
		
		if (width*width != longTab.length)
			throw new IllegalArgumentException(
				"argument longTab has length not a perfect square");
		
		int[][] squareTab = new int[width][width];
		
		int longIndex = 0;
		for (int x = 0; x < width; x++){
			for (int y=0; y < width; y++){
				squareTab[x][y] = longTab[longIndex];
				longIndex++;
			}
		}
		
		return squareTab;
		
	}
	
	/**
	* This is silly.  Jave should have a way to print an integer where
	* leading zeros become blanks.
	**/
	protected static String toStringFixedWidth(int input, int width)
	//	throws IllegalArgumentException
	{
	/*	if (width < 0)
			throw new IllegalArgumentException("width is negative.");
	*/
		
		String formatSymbol = "";
		String blankString = "";
		for (int n = 0; n < width; n++){
			formatSymbol += "#";
			blankString += " ";
		}
		DecimalFormat UpToThisWide = new DecimalFormat("###");
		
		String long_out = blankString + UpToThisWide.format(input);
		String short_out = long_out.substring(long_out.length()-width);
		
		return short_out;
		
	}
	
	/**
	* Prints out the table as an operation table.
	**/
	public static void printOp(int[][] table)
	//	throws IllegalArgumentException
	{
	/*	if (table == null)
			throw new IllegalArgumentException("null table as argument");
	*/
	
		int order = table.length;
	
		/*	boolean isSquare = true;
		for (int k = 0; k < order; k++)
			isSquare = isSquare && (table[k] != null) && (table[k].length == order);
		if (!isSquare)
			throw new IllegalArgumentException("table is not square");
	*/
		
		System.out.print("     ");
		for (int y = 0; y < order; y++)
			System.out.print(" " + toStringFixedWidth(y,3));
		System.out.println();

		System.out.print("------");
		for (int y = 0; y < order; y++)
			System.out.print("----");		
		System.out.println();
		
		for (int x = 0; x < order; x++){
			System.out.print(" " + toStringFixedWidth(x,3) + "|");
			for (int y = 0; y < order; y++)
				System.out.print(" " + toStringFixedWidth(table[x][y],3));
			System.out.println();
		}
		
		
	}
		
		
	/**
	* F	inds the "next" array with entrees between 0 and max.
	* Returns null if the input is all length-1 (the "last array");
	**/
	public static int[]  nextList(int[] inList, int max)
	//	throws IllegalArgumentException
	{
		
	/*	if (inList == null)
			throw new IllegalArgumentException("null array as argument");
	*/
	
		int len = inList.length;
		
	/*	boolean numbersOk = true;
		for (int k = 0; k < len; k++)
			numbersOk = numbersOk && (0 <= inList[k] ) && (inList[k] <= max);
		if (!numbersOk)
			throw new IllegalArgumentException("array has elements not in range 0 to " + max);
	*/
		
		int[] outList = (int[]) inList.clone();
		
		//First try to increment the right-most non-zero postion.
		//If so, put non-zero positions to the right down to 1.
		boolean haveIncremented = false;
		int j = len - 1;
		while (j >= 0 && !haveIncremented){
			if ( (0 < outList[j]) && (outList[j] < max) ){
				outList[j]++;
				haveIncremented = true;
				for (int k = j+1; k < len; k++)
					if (outList[k] > 0)
						outList[k] = 1;
			}
			j--;
		}
		if (haveIncremented)
			return outList;
		
		//Special case:  input is [max].
		if (len == 1)
			return null;		
		
		//Now try to move one of the nonzero spots to the left.  If so,
		//set the nonzero spots to 1, and move those to the left of the
		//shift to be adjacent to the shift.
		boolean haveShifted = false;
		j = 1;
		while (j < len && !haveShifted){
			if ( outList[j-1] == 0   &&   outList[j] > 0){
				outList[j-1] = 1;
				outList[j] = 0;
				haveShifted = true;
				for (int k = j+1; k < len; k++)
					if (outList[k] > 0)
						outList[k] = 1;
				int numSpotsToLeft = 0;
				for (int k=0; k < j - 1; k++)
					if (outList[k] > 0)
						numSpotsToLeft++;
				for (int k = 0; k < (j - 1 - numSpotsToLeft); k++)
					outList[k] =0;
				for (int k = (j - 1 - numSpotsToLeft); k < j-1; k++)
					outList[k] =1;
			}
			j++;
		}
		if (haveShifted)
			return outList;
		
		//Now try to increase the number of nonzero spots
		int numPos = 0;
		for (int k = 0; k < len; k++)
			if (outList[k] > 0)
				numPos++;
		if (numPos < len){
			for (int k = 0; k < (len - numPos - 1); k++)
				outList[k]=0;
			for (int k = (len - numPos - 1); k < len; k++)
				outList[k]=1;
			return outList;
		}
		
		return null;
		
	}	
	
	
	
	/**
	* Finds where the associative law "first' fails.  Returns null if this
	* is actually a semigroup.
	**/
	public static int[]  associativeFailure(int[][] table)
	//	throws IllegalArgumentException
	{
	/*	if (table == null)
			throw new IllegalArgumentException("null table as argument");
	*/	
		int order = table.length;

	/*	//Check for a square table, all entrees in the range 0 to the width-1.
		boolean isSquare = true;		
		for (int k = 0; k < order; k++)
			isSquare = isSquare && (table[k] != null) && (table[k].length == order);
		if (!isSquare)
			throw new IllegalArgumentException("table is not square");
		boolean numbersOk = true;
		for (int x = 0; x < order; x++)
			for (int y = 0; y < order; y++)
				numbersOk
					= numbersOk && (0 <= table[x][y] ) && (table[x][y] < order);
		if (!numbersOk)
			throw new IllegalArgumentException("array has elements not in range 0 to " + (order - 1));
	*/
	
		int x,y,z;
		boolean foundTrouble = false;
		x = -1;
		do{
			x++;
			y = -1;
			do{
				y++;
				z = -1;
				do{
					z++;
					foundTrouble = table[table[x][y]][z] != table[x][table[y][z]];
				}while(z < order - 1 && !foundTrouble);
			}while(y < order - 1 && !foundTrouble);
		}while(x < order - 1 && !foundTrouble);
		
		if (foundTrouble)
			return new int[]{x,y,z};
		
		return null;
		
	}




	
	public static void main(String[] args){
		
		if (args.length < 1){
			System.out.println(
				"One argument required; a natural number for the order."
				+"semigroup to seek"
			);
			System.exit(0);
		}
		
		
		int order = -1;
		try{
			order = Integer.parseInt(args[0]);
		}catch(NumberFormatException e){
			System.out.println("Argument is not an integer.");
			System.exit(0);
		}
		if (order <= 0){
			System.out.println("Argument is not postive.");
			System.exit(0);			
		}
		
		boolean listSemigroupsOnly = (args.length >= 2) && args[1].equals("only");
		
		// Here we will store the n*n elements that make up
		// the table for an operation.
		int[] longTable;
		
		longTable = new int[order*order];
		Arrays.fill(longTable, 0);
		
		
		do{
			int[][] operation = makeSquare(longTable);
			int[] bad = associativeFailure(operation);
			
			
			if (bad == null){
				printOp(operation);
				System.out.println("Semigroup");
				System.out.println("\n~~~~~~~~~~~~~~~~~~~~\n");			
			}else if (!listSemigroupsOnly){
				printOp(operation);
				System.out.print("(" + bad[0] + "*" + bad[1] + ")*" + bad[2] + " = " );
				System.out.print(operation[operation[bad[0]][bad[1]]][bad[2]]);
				System.out.print("  but   ");
				System.out.print(bad[0] + "*(" + bad[1] + "*" + bad[2] + ") = " );
				System.out.print(operation[bad[0]][operation[bad[1]][bad[2]]]);
				System.out.println();
				System.out.println("\n~~~~~~~~~~~~~~~~~~~~\n");			
			}
			longTable = nextList(longTable, order-1);
		}while(longTable != null);
		
		
		
		
		
		
	}

}