// Utility.java
import java.util.Vector;

public class Utility
{
   private static int findFirstAvailable(boolean[] A)
   {
      for(int i = 0; i < A.length; i++)
         if (A[i] == false)
            return i;
      return -1;
   }

   public static int[] makeGoalState(int puzzleSize)
   {
      int[] goal = new int[puzzleSize];
      for(int i = 0; i < puzzleSize - 1; i++)
        goal[i] = i + 1;
      goal[puzzleSize - 1] = 0;
      return goal;
   }

   public static boolean isSameState(int[] A, int[] B)
   {
      for(int i = 0; i < A.length; i++)
        if (A[i] != B[i])
          return false;
      return true;
   }

   public static void swap(int i, int j, int[] A)
   {
      int temp = A[i];
      A[i] = A[j];
      A[j] = temp;
   }

   public static int posOfElement(int element, int[] A, int puzzleSize)
   {
      for(int i = 0; i < puzzleSize; i++)
        if (A[i] == element)
          return i;
      return -1;
   }

   public static boolean isValidPermutation(int[] initState,
                                            int[] goalState)
   {
      int puzzleSize = initState.length,
          dim = (int)Math.sqrt(puzzleSize);

      // Create a copy of the array initState and an array of booleans.
      int[] A = new int[puzzleSize];
      boolean[] mark = new boolean[puzzleSize];
      for(int i = 0; i < puzzleSize; i++)
      {
         A[i] = initState[i];
         mark[i] = false;
      }

      // Move the space to the bottom right corner before counting the
      // number of swaps necessary to solve the puzzle.
      int pos = posOfElement(0, A, puzzleSize);
      while ((pos + 1) % dim != 0)
      {
         swap(pos, pos + 1, A);
         pos = posOfElement(0, A, puzzleSize);
      }
      while (pos != (puzzleSize - 1))
      {
         swap(pos, pos + dim, A);
         pos = posOfElement(0, A, puzzleSize);
      }

      int numOfSwaps = 0,
          start = findFirstAvailable(mark);
      while (start != -1)
      {
         boolean done = false;
         int i = start;
         mark[i] = true;
         while (!done)
         {
            if (A[i] != start)
            {
               numOfSwaps++;
               mark[A[i]] = true;
               i = A[i];
            }
            else
               done = true;
         }
         start = findFirstAvailable(mark);
      }
      return (numOfSwaps % 2 != dim % 2);
   }

   public static Vector makeTileVector(String pathStr, int[] initState,
                                       int puzzleSize)
   {
      Vector v = new Vector();
      int dim = (int)Math.sqrt(puzzleSize);
      int[] stateCopy = new int[puzzleSize];
      for(int i = 0; i < puzzleSize; i++)
         stateCopy[i] = initState[i];
      for(int i = 0; i < pathStr.length(); i++)
      {
         int p = posOfElement(0, stateCopy, puzzleSize);
         if (pathStr.charAt(i) == 'U')
         {
            v.addElement(new Integer(stateCopy[p - dim]));
            swap(p, p - dim, stateCopy);
         }
         else if (pathStr.charAt(i) == 'D')
         {
            v.addElement(new Integer(stateCopy[p + dim]));
            swap(p, p + dim, stateCopy);
         }
         else if (pathStr.charAt(i) == 'L')
         {
            v.addElement(new Integer(stateCopy[p - 1]));
            swap(p, p - 1, stateCopy);
         }
         else
         {
            v.addElement(new Integer(stateCopy[p + 1]));
            swap(p, p + 1, stateCopy);
         }
      }
      return v;
   }

}