- schiebe4 hinzugefügt

[schiebespiel.git] / MinSchritte.java

import java.util.*;
import java.lang.*;
import java.math.BigInteger;


class MinSchritte {
        class SteinCoords {
                int x,y;
                SteinCoords(int x, int y) {
                        this.x = x;
                        this.y = y;
                }
                public int distanz(SteinCoords sc) {
                        return Math.abs(x - sc.x) + Math.abs(y - sc.y);
                }
        }

        /* Index 0    -> Leere
       Index 1    -> Einer
           Index 2    -> Zweier horizontal
           Index 3    -> Zweier vertikal
       Index 4    -> Vierer */
    ArrayList< ArrayList<SteinCoords> > zielCoords = new ArrayList< ArrayList<SteinCoords> >();

        ArrayList< ArrayList<SteinCoords> > findCoords(Knoten k) {

                ArrayList<SteinCoords> einer                    = new ArrayList<SteinCoords>();
                ArrayList<SteinCoords> zweier_horiz     = new ArrayList<SteinCoords>();
                ArrayList<SteinCoords> zweier_vertik    = new ArrayList<SteinCoords>();
                ArrayList<SteinCoords> vierer                   = new ArrayList<SteinCoords>();
                SteinCoords sc;

                int[][] feld = k.get_spielfeld();
                for(int x = 0; x < feld.length; ++x) {
                        for(int y = 0; y < feld[0].length; ++y) {
                                switch(feld[x][y]) {
                                case Knoten.einer:
                                        sc = new SteinCoords(x,y);
                                        einer.add(sc);
                                        break;
                                case Knoten.zweier_links:
                                        sc = new SteinCoords(x,y);
                                        zweier_horiz.add(sc);
                                        break;
                                case Knoten.zweier_oben:
                                        sc = new SteinCoords(x,y);
                                        zweier_vertik.add(sc);
                                        break;
                                case Knoten.vierer_ro:
                                        sc = new SteinCoords(x,y);
                                        vierer.add(sc);
                                        break;
                                default:
                                        break;
                                }
                        }
                }
                ArrayList<ArrayList<SteinCoords>> coords = new ArrayList<ArrayList<SteinCoords>>();
                coords.add(einer);
                coords.add(zweier_horiz);
                coords.add(zweier_vertik);
                coords.add(vierer);

                return coords;
        }

        MinSchritte(Knoten ziel) {
                setZielCoords(ziel);
}

        void setZielCoords(Knoten ziel) {
                zielCoords = findCoords(ziel);
        }

        int computeLuftlinie(Knoten k) {

                PermutationGenerator x;
                int[] indices;
                int luftlinie = 0;
                ArrayList<ArrayList<SteinCoords>> kCoords = findCoords(k);
                ArrayList<SteinCoords> scList, zscList;

                for (int i=0; i<4; ++i) {
                        int minSum = 0;
                        scList     = kCoords.get(i);
                        zscList    = zielCoords.get(i);
                        x          = new PermutationGenerator(scList.size());
                        for (int j=0; j<scList.size(); ++j) {
                                minSum += scList.get(j).distanz(zscList.get(j));
                        }
                        while(x.hasMore()) {
                                int tmpSum  = 0;
                                indices = x.getNext();
                                for (int j=0; j<scList.size(); ++j) {
                                        tmpSum += scList.get(j).distanz(zscList.get(indices[j]));
                                }
                        //      System.out.println(i + " " + tmpSum);
                                if (minSum > tmpSum) {
                                        minSum = tmpSum;
                                }
                        }
                        luftlinie += minSum;
                }

                return luftlinie;
        }
}


//--------------------------------------
// Systematically generate permutations. 
//--------------------------------------

class PermutationGenerator {

  private int[] a;
  private BigInteger numLeft;
  private BigInteger total;

  //-----------------------------------------------------------
  // Constructor. WARNING: Don't make n too large.
  // Recall that the number of permutations is n!
  // which can be very large, even when n is as small as 20 --
  // 20! = 2,432,902,008,176,640,000 and
  // 21! is too big to fit into a Java long, which is
  // why we use BigInteger instead.
  //----------------------------------------------------------

  public PermutationGenerator (int n) {
    if (n < 1) {
      throw new IllegalArgumentException ("Min 1");
    }
    a = new int[n];
    total = getFactorial (n);
    reset ();
  }

  //------
  // Reset
  //------

  public void reset () {
    for (int i = 0; i < a.length; i++) {
      a[i] = i;
    }
    numLeft = new BigInteger (total.toString ());
  }

  //------------------------------------------------
  // Return number of permutations not yet generated
  //------------------------------------------------

  public BigInteger getNumLeft () {
    return numLeft;
  }

  //------------------------------------
  // Return total number of permutations
  //------------------------------------

  public BigInteger getTotal () {
    return total;
  }

  //-----------------------------
  // Are there more permutations?
  //-----------------------------

  public boolean hasMore() {
    return numLeft.compareTo (BigInteger.ZERO) == 1;
  }

  //------------------
  // Compute factorial
  //------------------

  private static BigInteger getFactorial (int n) {
    BigInteger fact = BigInteger.ONE;
    for (int i = n; i > 1; i--) {
      fact = fact.multiply (new BigInteger (Integer.toString (i)));
    }
    return fact;
  }

  //--------------------------------------------------------
  // Generate next permutation (algorithm from Rosen p. 284)
  //--------------------------------------------------------

  public int[] getNext () {

    if (numLeft.equals (total)) {
      numLeft = numLeft.subtract (BigInteger.ONE);
      return a;
    }

    int temp;

    // Find largest index j with a[j] < a[j+1]

    int j = a.length - 2;
    while (a[j] > a[j+1]) {
      j--;
    }

    // Find index k such that a[k] is smallest integer
    // greater than a[j] to the right of a[j]

    int k = a.length - 1;
    while (a[j] > a[k]) {
      k--;
    }

    // Interchange a[j] and a[k]

    temp = a[k];
    a[k] = a[j];
    a[j] = temp;

    // Put tail end of permutation after jth position in increasing order

    int r = a.length - 1;
    int s = j + 1;

    while (r > s) {
      temp = a[s];
      a[s] = a[r];
      a[r] = temp;
      r--;
      s++;
    }

    numLeft = numLeft.subtract (BigInteger.ONE);
    return a;

  }

}