import java.util.LinkedList;


/////////////////// FINAL VERSION ///////////////////////

public class A1
{

    private static AStar a = new AStar();

    public static void test(State s, boolean isTraceDesired)     {
      try                                                     {
        State result = a.search(s, isTraceDesired);       
        if (result!=null)
          System.out.println(result);
        else
          System.out.println("no solution found");            }  
      catch(OutOfMemoryError e)                               {    
        System.out.print("search halted before completion");
        System.out.println("  -- memory exhausted");          } 
      finally                                                 {
        System.out.println();                                 }  }
              

     public static void main(String[] args)                     {

       LinkedList<Integer> ls = new LinkedList<Integer>();
       ls.add(64);
       ls.add(32);
       ls.add(16);
       ls.add(8);
       ls.add(4);
       ls.add(2);
       PartitionState s = new PartitionState(ls);
       test(s, true);

       ls = new LinkedList<Integer>();
       ls.add(18);
       ls.add(16);
       ls.add(11);
       ls.add(9);
       ls.add(8);
       ls.add(6);
       s = new PartitionState(ls);
       test(s, true);

       ls = new LinkedList<Integer>();
       ls.add(11);
       ls.add(10);
       ls.add(9);
       ls.add(8);
       ls.add(7);
       ls.add(6);
       ls.add(5);
       s = new PartitionState(ls);
       test(s, true);

       ls = new LinkedList<Integer>();
       ls.add(21);
       ls.add(13);
       ls.add(8);
       ls.add(5);
       ls.add(3);
       ls.add(2);
       ls.add(1);
       s = new PartitionState(ls);
       test(s, true);

       LinkedList<String> stringList = new LinkedList<String>();
       stringList.add("a");
       stringList.add("b");
       State s2 = new ShortestSuperstringState(stringList);
       test(s2, true);

       stringList = new LinkedList<String>();
       stringList.add("abb");
       stringList.add("bab");
       stringList.add("abab");
       stringList.add("bba");
       s2 = new ShortestSuperstringState(stringList);
       test(s2, true);

       stringList = new LinkedList<String>();
       stringList.add("ab");
       stringList.add("bc");
       stringList.add("ac");
       stringList.add("ca");
       stringList.add("ba");
       stringList.add("cb");
       s2 = new ShortestSuperstringState(stringList);
       test(s2, false);
       
       stringList = new LinkedList<String>();
       stringList.add("0");
       stringList.add("01");
       stringList.add("001");
       stringList.add("0001");
       stringList.add("00001");
       s2 = new ShortestSuperstringState(stringList);
       test(s2, true);
       
       stringList = new LinkedList<String>();
       stringList.add("000");
       stringList.add("001");
       stringList.add("010");
       stringList.add("011");
       stringList.add("100");
       stringList.add("101");
       stringList.add("110");
       stringList.add("111");
       s2 = new ShortestSuperstringState(stringList);
       test(s2, false);

       stringList = new LinkedList<String>();
       stringList.add("aa");
       stringList.add("aba");
       stringList.add("abba");
       stringList.add("abbba");
       s2 = new ShortestSuperstringState(stringList);
       test(s2, false);
       
       LinkedList<IntegerPair> prereqs = 
    	 new LinkedList<IntegerPair>();
       prereqs.add(new IntegerPair(1,2));
       prereqs.add(new IntegerPair(2,3));
       prereqs.add(new IntegerPair(3,4));
       prereqs.add(new IntegerPair(4,5));
       State s4 = new TopSortState(prereqs);
       test(s4, true);
       
       prereqs = new LinkedList<IntegerPair>();
       prereqs.add(new IntegerPair(1,2));
       prereqs.add(new IntegerPair(2,3));
       prereqs.add(new IntegerPair(3,4));
       prereqs.add(new IntegerPair(4,5));
       prereqs.add(new IntegerPair(5,1));
       s4 = new TopSortState(prereqs);
       test(s4, true);
                             
       prereqs = new LinkedList<IntegerPair>();
       prereqs.add(new IntegerPair(0,1));
       prereqs.add(new IntegerPair(6,7));
       prereqs.add(new IntegerPair(1,2));
       prereqs.add(new IntegerPair(1,4));
       prereqs.add(new IntegerPair(1,6));
       prereqs.add(new IntegerPair(3,2));
       prereqs.add(new IntegerPair(3,4));
       prereqs.add(new IntegerPair(3,6));
       prereqs.add(new IntegerPair(5,2));
       prereqs.add(new IntegerPair(5,4));
       prereqs.add(new IntegerPair(5,6));
       s4 = new TopSortState(prereqs);
       test(s4, true);
                             
       prereqs = new LinkedList<IntegerPair>();
       prereqs.add(new IntegerPair(2,1));
       prereqs.add(new IntegerPair(2,3));
       prereqs.add(new IntegerPair(2,5));
       prereqs.add(new IntegerPair(3,5));
       prereqs.add(new IntegerPair(3,1));
       prereqs.add(new IntegerPair(4,1));
       prereqs.add(new IntegerPair(4,2));
       prereqs.add(new IntegerPair(4,3));
       prereqs.add(new IntegerPair(4,5));
       prereqs.add(new IntegerPair(5,1));
       s4 = new TopSortState(prereqs);
       test(s4, true);

       LinkedList<IntegerPair> edges = 
           new LinkedList<IntegerPair>();
       edges.add(new IntegerPair(1,2));
       edges.add(new IntegerPair(1,3));
       edges.add(new IntegerPair(1,4));
       edges.add(new IntegerPair(2,3));
       edges.add(new IntegerPair(2,4));
       edges.add(new IntegerPair(3,4));
       State s5 = new GraphColoringState(edges);
       test(s5, true);
      
       edges = new LinkedList<IntegerPair>();
       edges.add(new IntegerPair(1,2));
       edges.add(new IntegerPair(1,3));
       edges.add(new IntegerPair(1,4));
       edges.add(new IntegerPair(2,3));
       edges.add(new IntegerPair(2,4));
       edges.add(new IntegerPair(3,4));
       edges.add(new IntegerPair(5,2));
       edges.add(new IntegerPair(5,3));
       edges.add(new IntegerPair(5,4));
       s5 = new GraphColoringState(edges);
       test(s5, true);

       edges = new LinkedList<IntegerPair>();
       edges.add(new IntegerPair(11,12));
       edges.add(new IntegerPair(12,13));
       edges.add(new IntegerPair(13,14));
       edges.add(new IntegerPair(21,22));
       edges.add(new IntegerPair(22,23));
       edges.add(new IntegerPair(23,24));
       edges.add(new IntegerPair(31,32));
       edges.add(new IntegerPair(32,33));
       edges.add(new IntegerPair(33,34));
       edges.add(new IntegerPair(11,21));
       edges.add(new IntegerPair(12,22));
       edges.add(new IntegerPair(13,23));
       edges.add(new IntegerPair(14,24));
       edges.add(new IntegerPair(21,31));
       edges.add(new IntegerPair(22,32));
       edges.add(new IntegerPair(23,33));
       edges.add(new IntegerPair(24,34));
       s5 = new GraphColoringState(edges);
       test(s5, true);
       
       edges = new LinkedList<IntegerPair>();
       edges.add(new IntegerPair(1,2));
       edges.add(new IntegerPair(1,3));
       edges.add(new IntegerPair(1,4));
       edges.add(new IntegerPair(1,5));
       edges.add(new IntegerPair(1,6));
       edges.add(new IntegerPair(2,3));
       edges.add(new IntegerPair(3,4));
       edges.add(new IntegerPair(4,5));
       edges.add(new IntegerPair(5,6));
       edges.add(new IntegerPair(6,2));
       s5 = new GraphColoringState(edges);
       test(s5, true);
    
       edges = new LinkedList<IntegerPair>();
       edges.add(new IntegerPair(1,2));
       edges.add(new IntegerPair(1,3));
       edges.add(new IntegerPair(1,4));
       edges.add(new IntegerPair(1,5));
       edges.add(new IntegerPair(1,6));
       edges.add(new IntegerPair(1,7));
       edges.add(new IntegerPair(3,4));
       edges.add(new IntegerPair(4,5));
       edges.add(new IntegerPair(5,6));
       edges.add(new IntegerPair(6,7));
       edges.add(new IntegerPair(7,2));
       s5 = new GraphColoringState(edges);
       test(s5, true);

       int[] a1 = {20,30,40,50,60};
       State s6 = new BinPackingState(a1);
       test(s6, true);

       int[] a2 = {1, 20,30,40,50,60,2};
       s6 = new BinPackingState(a2);
       test(s6, true);

       int[] a3 = {40,40,40,40,40};
       s6 = new BinPackingState(a3);
       test(s6, true);

       int[] a4 = {14, 28,42,57,71,85};
       s6 = new BinPackingState(a4);
       test(s6, true);

       int[][] a11 = {{0,2,2,2,1}, {1,0,2,2,2},
                   {2,1,0,2,2}, {2,2,1,0,2},
                   {2,2,2,1,0}};
       State s7 = new HamiltonianPathState(a11);
       test(s7, true);

       int[][] a12 = {{0,11,31,41,51}, {42,0,12,22,52},
                   {33,43,0,13,53}, {14,24,44,0,54},
                   {110,120,130,140,0}};
       s7 = new HamiltonianPathState(a12);
       test(s7, true);
       
       int[][] a13 = {{0,1,1,44,44,44}, {1,0,1,44,44,44},
                      {1,1,0,44,44,44}, {44,33,44,0,1,1}, 
                      {44,44,44,1,0,1}, {44,44,44,1,1,0}};
       s7 = new HamiltonianPathState(a13);
       test(s7, true);
   
       int[][] a14 = {{0,1,1,1,1,1,1,1,1,1,1}, 
    		   {1,0,1,1,1,1,1,1,1,1,1}, 
    		   {1,1,0,1,1,1,1,1,1,1,1}, 
    		   {1,1,1,0,1,1,1,1,1,1,1}, 
    		   {1,1,1,1,0,1,1,1,1,1,1}, 
    		   {1,1,1,1,1,0,1,1,1,1,1}, 
    		   {1,1,1,1,1,1,0,1,1,1,1}, 
    		   {1,1,1,1,1,1,1,0,1,1,1}, 
    		   {1,1,1,1,1,1,1,1,0,1,1}, 
    		   {1,1,1,1,1,1,1,1,1,0,1}, 
    		   {1,1,1,1,1,1,1,1,1,1,0}};
       s7 = new HamiltonianPathState(a14);
       test(s7, false);

       String[] aStrings = {"1","10111","10"};
       String[] bStrings = {"111","10","0"};
       State s8 = new PCPState(aStrings,bStrings);
       test(s8, true);

       String[] aStrings2 = {"1","11101","01"};
       String[] bStrings2 = {"111","01","0"};
       s8 = new PCPState(aStrings2,bStrings2);
       test(s8, true);

       String[] aStrings3 = {"b","bb","bbbbbbbb"};
       String[] bStrings3 = {"bb","bbbb","b"};
       s8 = new PCPState(aStrings3,bStrings3);
       test(s8, false);

       String[] aStrings4 = {"b","bbbb","01","01"};
       String[] bStrings4 = {"bbb","bb","0","10"};
       s8 = new PCPState(aStrings4,bStrings4);
       test(s8, true);
    
    }
}