import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;

import javax.swing.JOptionPane;


public class StateMachineExplorer
{
	static String puzzleName;
	static ArrayList<byte[]> solved;
	static byte[][][] moves;
	static byte permutationElements;
	static String[][] moveNames;
	public static void main(String[] args) throws IOException
	{
		String fileName="Trillion";
		importData(fileName);
		System.out.println();
		exploreStateMachine(fileName);

	}
	public static void exploreStateMachine(String fileName) throws IOException
	{
		FileWriter writer=new FileWriter(new File(fileName+"Output.txt"));
		HashSet<ByteArrayWrapper> current=new HashSet<ByteArrayWrapper>();
		HashSet<ByteArrayWrapper> previous=new HashSet<ByteArrayWrapper>();
		HashSet<ByteArrayWrapper> previousPrevious=previous;
		for(byte[] i:solved)
			previous.add(new ByteArrayWrapper(i));
		if(previous.size()==1)
			writer.write("Using 1 solved state:\r\n");
		else
			writer.write("Using "+previous.size()+" solved states:\r\n");
		for(byte[] i:solved)
			writer.write(printPermutation(i)+"\r\n");
		writer.write("\r\n");
		int depth=1;
		long numberOfElements=previous.size();
		writer.write(" 0 - "+previous.size()+"\r\n");
		long time=System.currentTimeMillis();
		Iterator<ByteArrayWrapper> iterator;
		long count;
		int generatorsLength;
		while(previous.size()>0)
		{
			iterator=previous.iterator();
			count=0;
			while(iterator.hasNext())
			{
				count++;
				if(count%100000==0)
					System.out.print("\r  Depth "+depth+": "+(100.0*count/previous.size())+"% complete...");
				byte[] state=iterator.next().data;
				generatorsLength=moves[state[permutationElements]].length;
				for(int i=0;i<generatorsLength;i++)
				{
					ByteArrayWrapper next=new ByteArrayWrapper(compose(state,moves[state[permutationElements]][i]));
					if(!previous.contains(next)&&!previousPrevious.contains(next))
						current.add(next);
				}
			}
			if(current.size()>0)
			{
				numberOfElements+=current.size();
				writer.write((depth<10?" ":"")+depth+" - "+current.size()+"\r\n");
				System.out.print("\r                                                            ");
				System.out.println("\r "+depth+" - "+current.size());
			}
			previousPrevious=previous;
			previous=current;
			current=new HashSet<ByteArrayWrapper>();
			depth++;
		}
		time=System.currentTimeMillis()-time;
		writer.write("Total number of configurations: "+numberOfElements+"\r\n\r\n");
		iterator=previousPrevious.iterator();
		if(previousPrevious.size()==1)
			writer.write("The single antipode position:\r\n"+printPermutation(iterator.next().data)+"\r\n");
		else
		{
			writer.write("The "+previousPrevious.size()+" hardest positions:\r\n");
			while(iterator.hasNext())
				writer.write(printPermutation(iterator.next().data)+"\r\n");
		}
		writer.write("\r\n");
		writer.write("Time spent: "+time);
		writer.close();
	}
	public static byte[] compose(byte[] start, byte[] operation)
	{
		byte[] ans=new byte[start.length];
		for(int i=0;i<permutationElements;i++)
			ans[i]=start[operation[i]];
		ans[permutationElements]=operation[permutationElements];
		return ans;
	}
	public static void importData(String fileName) throws IOException
	{
		BufferedReader in = new BufferedReader(new FileReader(fileName+".txt"));
		System.out.println("Reading file "+fileName+".txt...");
		puzzleName=in.readLine();
		String line=in.readLine();
		while(line!=null&&line.compareTo("Moves:")!=0)
			line=in.readLine();
		line=in.readLine();
		int numberOfStates=0;
		ArrayList<Byte> numberOfMoves=new ArrayList<Byte>();
		byte maxPermutationElement=0;
		while(line!=null&&line.compareTo("")!=0)
		{
			numberOfStates++;
			line=in.readLine();
			byte numberOfMovesHere=0;
			while(line!=null&&line.compareTo("")!=0&&line.substring(0,5).compareTo("State")!=0)
			{
				numberOfMovesHere++;
				for(int i=line.indexOf(':')+1;i<line.indexOf(',');i++)
				if(line.charAt(i)!='('&&line.charAt(i)!=')'&&line.charAt(i)!='.'&&characterInterpretation(line.charAt(i))>maxPermutationElement)
					maxPermutationElement=characterInterpretation(line.charAt(i));
				line=in.readLine();
			}
			numberOfMoves.add(numberOfMovesHere);
		}
		permutationElements=++maxPermutationElement;
		System.out.println(numberOfStates+" states found.");
		System.out.print("States have {");
		for(int i=0;i<numberOfMoves.size();i++)
		{
			if(i!=0)
				System.out.print(",");
			System.out.print(numberOfMoves.get(i));
		}
		System.out.println("} moves available");
		System.out.println(permutationElements+" permutation elements used.");
		in.close();
		moves=new byte[numberOfStates][][];
		moveNames=new String[numberOfStates][];
		solved=new ArrayList<byte[]>();
		byte[] tempsolved=new byte[permutationElements+1];
		for(byte i=0;i<permutationElements;i++)
			tempsolved[i]=i;
		solved.add(tempsolved);
		in = new BufferedReader(new FileReader(fileName+".txt"));
		line=in.readLine();
		while(line!=null)
		{
			if(line.compareTo("Moves:")==0)
			{
				line=in.readLine();
				int state=0;
				while(line!=null&&line.compareTo("")!=0)
				{
					System.out.println("State "+state);
					moves[state]=new byte[numberOfMoves.get(state)][permutationElements+1];
					moveNames[state]=new String[numberOfMoves.get(state)];
					int move=0;
					line=in.readLine();
					while(line!=null&&line.compareTo("")!=0&&line.substring(0,5).compareTo("State")!=0)
					{
						moveNames[state][move]=line.substring(0,line.indexOf(':'));
						for(byte i=0;i<permutationElements;i++)
							moves[state][move][i]=i;
						byte temp=-1,last=-1;
						for(int i=line.indexOf(':')+1;i<line.indexOf(',');i++)
						{
							if(line.charAt(i)=='(')
							{
								i++;
								temp=last=characterInterpretation(line.charAt(i));
							}
							else if(line.charAt(i)==')')
								moves[state][move][last]=temp;
							else
							{
								moves[state][move][characterInterpretation(line.charAt(i))]=temp;
								temp=characterInterpretation(line.charAt(i));
							}
						}
						moves[state][move][permutationElements]=characterInterpretation(line.charAt(line.indexOf(',')+1));
						System.out.println(moveNames[state][move]+": "+printPermutation(moves[state][move]));
						line=in.readLine();
						move++;
					}
					state++;
				}
			}
			else if(line.compareTo("Indistinguishables:")==0)
			{
				line=in.readLine();
				while(line!=null&&line.compareTo("")!=0)
				{
					for(int i=1;i<line.length();i++)
						solved.get(0)[characterInterpretation(line.charAt(i))]=characterInterpretation(line.charAt(0));
					line=in.readLine();
				}
				System.out.println("Assumed solved state accounting for indistinguishable permutation elements:");
				System.out.println(printPermutation(solved.get(0)));
			}
			line=in.readLine();
		}
		in.close();
	}
	public static String printPermutation(byte[] array)
	{
		String ans="";
		for(int i=0;i<array.length;i++)
		{
			if(i==permutationElements)
				ans+=",";
			if(array[i]==-1)
				ans+="?";
			else if(array[i]<10)
				ans+=array[i];
			else if(array[i]<36)
				ans+=(char)(array[i]-10+'a');
			else
				ans+=(char)(array[i]-36+'A');
		}
		return ans;
	}
	public static byte characterInterpretation(char c)
	{
		if(c>='0'&&c<='9')
			return (byte)(c-'0');
		if(c>='a'&&c<='z')
			return (byte)(c-'a'+10);
		if(c>='A'&&c<='Z')
			return (byte)(c-'A'+36);
		return -1;
	}
}
class ByteArrayWrapper
{
    final byte[] data;
    public ByteArrayWrapper(byte[] data)
    {
        this.data = data;
    }

    @Override
    public boolean equals(Object other)
    {
        if(!(other instanceof ByteArrayWrapper))
            return false;
        return Arrays.equals(data,((ByteArrayWrapper)other).data);
    }

    @Override
    public int hashCode()
    {
        return Arrays.hashCode(data);
    }
}