Finding optimal solution

Question

We have 7 shirts in a random order, say 3 4 5 7 1 6 2. We can perform 4 operations on them. In each operation, the removed shirt is placed in the gap made.

1. Remove the middle shirt and move the adjacent 3 shirts to the right.
2. Remove the middle shirt and move the adjacent 3 shirts to the left.
3. Remove the leftmost shirt and move the adjacent 3 shirts to the the left.
4. Remove the rightmost shirt and move the adjacent 3 shirts to the right.

Given 7 shirts in random order, find the minimum number of operations required to put the shirts in serial order, i.e. , 1 2 3 4 5 6 7.

I tried a solution using permutations but that fails beyond 7 operations.

This is my solution:

import java.util.*;

class shirt2 {

public static void main(String[] ar)
{

    Scanner sc = new Scanner(System.in);
    String n = sc.next();
    if(n.equals("1234567"))
    {
        System.out.println("0");
        System.exit(0);
    }
    for(int i = 1; ; i++)
    {
        PermutationsWithRepetition gen = new PermutationsWithRepetition("1234",i);
        List<String> v = gen.getVariations();
        for(String j : v)
        {
            String t = n;
            for(int k = 0;k < j.length(); k++)
            {
                int l = j.charAt(k) - '0';
                t = operation(t,l);
            }
            if(t.equals("1234567"))
            {
                System.out.println(i + "\t" + j);
                System.exit(0);
            }
        }
     }
}

public static String operation(String t, int l)
{
    if(l == 1)
        return "" + t.charAt(3) + t.substring(0,3) + t.substring(4);
    else if(l == 2)
        return t.substring(0,3) + t.substring(4) + t.charAt(3);
    else if(l == 3)
        return t.substring(1,4) + t.charAt(0) + t.substring(4);
    else
    {
        return t.substring(0,3) + t.charAt(6) + t.substring(3,6);
    }
}

}

public class PermutationsWithRepetition {
private String a;
private int n;
public PermutationsWithRepetition(String a, int n) {
    this.a = a;
    this.n = n;
}
public List<String> getVariations() {
    int l = a.length();
    int permutations = (int) Math.pow(l, n);
    char[][] table = new char[permutations][n];

    for (int x = 0; x < n; x++) {
        int t2 = (int) Math.pow(l, x);
        for (int p1 = 0; p1 < permutations;) {
            for (int al = 0; al < l; al++) {
                for (int p2 = 0; p2 < t2; p2++) {
                    table[p1][x] = a.charAt(al);
                    p1++;
                }
            }
        }
    }


    List<String> result = new ArrayList<String>();
    for (char[] permutation : table) {
        result.add(new String(permutation));
    }
    return result;
}
public static void main(String[] args) {

    PermutationsWithRepetition gen = new PermutationsWithRepetition("abc", 3);
    List<String> v = gen.getVariations();
    for (String s : v) {
        System.out.println(s);
    }
}

Answer 1

If you intend to do it in brute force, just make a tree with four-way nodes where each way represents one of the methods. If you encounter the answer on one of the nodes, print it. If you keep track of the iteration you know how many steps it took, if you keep track of the path you know which operations it used.

public static void main(String[] args)
{
    int[] shirts = new int[] { 3, 4, 5, 7, 1, 6, 2 };

    Path shortestPath = shirtAlgorithm(shirts);
}


public static class Path
{
    private ArrayList<Integer> path;
    private int[] shirts;

    public Path(ArrayList<Integer> _path_, int[] _shirts_)
    {
        this.path = _path_;
        this.shirts = _shirts_;
    }

    public void setPath(ArrayList<Integer> _path_)
    { this.path = _path_; }

    public ArrayList<Integer> getPath()
    { return this.path; }

    public void setShirts(int[] _shirts_)
    { this.shirts = _shirts_; }

    public int[] getShirts()
    { return this.shirts; }
}




public static Path shirtAlgorithm(int[] shirts)
{
    ArrayList<Path> paths = new ArrayList<>();

    paths.add(new Path(new ArrayList<Integer>(), shirts));

    while (true)
    {
        ArrayList<Path> newpaths = new ArrayList<Path>();

        for (Path curpath : paths)
        {
            for (int operation = 1; operation <= 4; operation++)
            {
                ArrayList<Integer> curnewpath = new ArrayList<Integer>(curpath.getPath());
                curnewpath.add(operation);

                Path newestPath = new Path(
                        curnewpath, 
                        operation(curpath.shirts, operation));

                if (algorithmComplete(newestPath))
                    return newestPath;

                newpaths.add(newestPath);
            }
        }

        paths = newpaths;
    }
}

private static int[] operation(int[] shirts, int operationtype)
{
    int[] newshirts = new int[shirts.length];
    System.arraycopy(shirts, 0, newshirts, 0, shirts.length);
    // logic here
    return newshirts;
}

private static boolean algorithmComplete(Path path)
{
    // true if the shirts are in the right order
}

This is one of the most simple brute-force algorithms with your operations.

Answer 2

Try the A* path finding approach which is a BEST FIRST approach Here is the algorithm :

1. Start .
2. Find the approximate cost estimation to the goal state (which is total displacement of each shirt from its position in the goal state .. which means if shirt 1 is in position 3, its displacement is 2, if shirt 3 is in position 1 its displacement is 2 (only magnitudes ). Add them all up to get the cost estimation to reach the goal. For the start state you have given, the cost estimate is 18)
3. For this state, calculate the cost estimation for each of its neighboring states. (in this question, there are four possible equidistant neighboring states (move 1 results in a new state, move 2 in a different state and so on ) , so evaluate the cost estimation to reach the goal state for all these neighboring states.
4. Select the state that has the lowest estimate cost to reach the goal at each state. At each state, make sure that the neighboring state has a cost estimate less than the cost estimate of the current state.
5. You will eventually end up at the goal state ( which has a cost estimate of 0 to reach the goal)

Hope this helped. :)