State_Space_Explorer_1.java

import java.util.*;

public class State_Space_Explorer_1 {

    //private static final String fileName = "test.txt";
    private static final String fileName = "sokwhole.txt";
    private static final int mapIndex = 23;

    private static MapHandler .NetworkRep netrep;
    private static Queue     <State> stateQueue = new ArrayDeque <> ();
    private static SortedSet <State> forwardStateSet, backwardStateSet;
    private static ArrayList <State> uniqueForwardStates, uniqueBackwardStates;
    private static ArrayList <State> matchedForwardStates, matchedBackwardStates;

    private static String formatString;

    public static void main (String [] args) {

        String [] mapLines = MapLoader .load (fileName, mapIndex);
        if (null == mapLines) {
            System .out .println ("File reading error");
            return;
        }
        if (!MapHandler .process (mapLines)) {
            System .out .println (MapHandler .errorMessage ());
            return;
        }
        MapHandler .setMarkersType (3);
        MapHandler .displayState (MapHandler .stateCells ());
        displayMapStats ();
        //MapHandler .displayMaze ();
        //MapHandler .displayMap ();

        netrep = MapHandler .networkRepresentation ();
        State .init (netrep);
        processForward ();
        processBackward ();
        matchStates ();

        displaySetStats ();
        //displayForwardSet ();
    }

    private static void processForward () {
        int k;
        State state;
        State [] states;

        stateQueue .clear ();
        forwardStateSet = new TreeSet <> ();
        state = new State (MapHandler .stateCells ());
        forwardStateSet .add (state);
        stateQueue      .add (state);

        while (!stateQueue .isEmpty ()) {
            states = stateQueue .poll () .expandForth ();
            for (k = 0; states .length > k; ++k) {
                state = states [k];
                if (forwardStateSet .add (state)) {
                    stateQueue      .add (state);
                    //MapHandler .displayState (state .stateCells ());
                }
            }
        }
    }

    private static void processBackward () {
        int k, l, length, limit;
        short cell;
        short [] netrepValues, stateCells, newStateCells;
        int   [] netrepIndices;
        State state;
        State [] states;

        netrepValues  = netrep .values ();
        netrepIndices = netrep .indices ();
        stateQueue .clear ();
        backwardStateSet = new TreeSet <> ();
        stateCells = MapHandler .targetCells ();
        Arrays .sort (stateCells);
        length = stateCells .length;

        for (k = 0; length > k; ++k) {
            cell = stateCells [k];
            limit = netrepIndices [cell + 1];
            for (l = netrepIndices [cell] + 1; limit > l; l += 4) {
                cell = netrepValues [l];
                if (0 > Arrays .binarySearch (stateCells, cell)) {
                    newStateCells = Arrays .copyOf (stateCells, length + 1);
                    newStateCells [length] = cell;
                    state = new State (newStateCells);
                    if (backwardStateSet .add (state)) {
                        stateQueue       .add (state);
                        //MapHandler .displayState (newStateCells);
                    }
                }
            }
        }

        while (!stateQueue .isEmpty ()) {
            states = stateQueue .poll () .expandBack ();
            for (k = 0; states .length > k; ++k) {
                state = states [k];
                if (backwardStateSet .add (state)) {
                    stateQueue       .add (state);
                    //MapHandler .displayState (state .stateCells ());
                }
            }
        }
    }

    private static void matchStates () {
        Iterator <State> forwardStatesIterator, backwardStatesIterator;
        State forwardState, backwardState;

        uniqueForwardStates    = new ArrayList <> ();
        uniqueBackwardStates   = new ArrayList <> ();
        matchedForwardStates   = new ArrayList <> ();
        matchedBackwardStates  = new ArrayList <> ();
        forwardStatesIterator  = forwardStateSet  .iterator ();
        backwardStatesIterator = backwardStateSet .iterator ();
        forwardState  = forwardStatesIterator  .next ();
        backwardState = backwardStatesIterator .next ();

        while (forwardStatesIterator .hasNext () && backwardStatesIterator .hasNext ()) {
            switch (forwardState .compareTo (backwardState)) {
            case 0:
                matchedForwardStates  .add (forwardState);
                matchedBackwardStates .add (backwardState);
                forwardState  = forwardStatesIterator  .next ();
                backwardState = backwardStatesIterator .next ();
                break;
            case -1:
                uniqueForwardStates   .add (forwardState);
                forwardState  = forwardStatesIterator  .next ();
                break;
            case 1:
                //MapHandler .displayState (backwardState .stateCells ());
                uniqueBackwardStates  .add (backwardState);
                backwardState = backwardStatesIterator .next ();
                break;
            }
        }

        if (forwardStatesIterator .hasNext ()) {
            while (forwardStatesIterator  .hasNext () && 0 != forwardState .compareTo (backwardState)) {
                uniqueForwardStates   .add (forwardState);
                forwardState  = forwardStatesIterator .next ();
            }
            if (forwardStatesIterator .hasNext ()) {
                matchedForwardStates  .add (forwardState);
                matchedBackwardStates .add (backwardState);
                while (forwardStatesIterator .hasNext ()) {
                    uniqueForwardStates .add (forwardStatesIterator .next ());
                }
            } else {
                uniqueForwardStates   .add (forwardState);
                uniqueBackwardStates  .add (backwardState);
            }
        } else {
            while (backwardStatesIterator .hasNext () && 0 != forwardState .compareTo (backwardState)) {
                uniqueBackwardStates  .add (backwardState);
                backwardState = backwardStatesIterator .next ();
            }
            if (backwardStatesIterator .hasNext ()) {
                matchedForwardStates  .add (forwardState);
                matchedBackwardStates .add (backwardState);
                while (backwardStatesIterator .hasNext ()) {
                    uniqueBackwardStates .add (backwardStatesIterator .next ());
                }
            } else {
                uniqueForwardStates   .add (forwardState);
                uniqueBackwardStates  .add (backwardState);
            }
        }
    }

    private static int countPlacements (Collection <State> statesCollection) {
        int result;
        Iterator <State> statesIterator;
        State state, oldState;

        if (statesCollection .isEmpty ()) {
            return 0;
        }

        statesIterator = statesCollection .iterator ();
        oldState = statesIterator .next ();
        result = 1;

        while (statesIterator .hasNext ()) {
            state = statesIterator .next ();
            if (oldState .isSamePlacementAs (state)) {
                continue;
            }
            oldState = state;
            ++result;
        }

        return result;
    }

    @SuppressWarnings ("unused")
    private static void displayStates (Collection <State> statesCollection) {
        Iterator <State> statesIterator;
        State state;

        statesIterator = statesCollection .iterator ();

        while (statesIterator .hasNext ()) {
            state = statesIterator .next ();
            System .out .println (String .format ("Moves: %d, pushes: %d", state .moveCount (), state .pushCount ()));
            MapHandler .displayState (state .stateCells ());
        }
    }

    private static long nchoosek (int n, int k) {
        long result = 1;
        for (int l = 1; 0 < k; ++l, --k, --n) {
            result *= n;
            result /= l;
        }
        return result;
    }

    private static void displayMapStats () {
        int cellsCount, boxesCount;
        long placementsCount, statesCount;
        String placementsString, statesString;

        cellsCount = MapHandler .cellsCount ();
        boxesCount = MapHandler .boxesCount ();
        placementsCount = nchoosek (cellsCount, boxesCount);
        statesCount = placementsCount * (cellsCount - boxesCount);

        placementsString = formattedNumber (placementsCount);
        statesString     = formattedNumber (statesCount);
        formatString = String .format (
                "%%s   %%%ds   %%%ds",
                Integer .max (10, placementsString .length ()),
                Integer .max (6,  statesString     .length ()));

        System .out .println (String .format ("Cells: %5d", cellsCount));
        System .out .println (String .format ("Boxes: %5d", boxesCount));
        System .out .println (String .format (formatString, "                ", "Placements", "States"));
        System .out .println (String .format (formatString, "Theoretical:    ", placementsString, statesString));
    }

    private static void displaySetStats () {
        String placementsString, statesString;

        placementsString = formattedNumber (countPlacements (forwardStateSet));
        statesString     = formattedNumber (forwardStateSet      .size ());
        System .out .println (String .format (formatString, "Forward total:  ", placementsString, statesString));
        placementsString = formattedNumber (countPlacements (uniqueForwardStates));
        statesString     = formattedNumber (uniqueForwardStates  .size ());
        System .out .println (String .format (formatString, "Forward dead:   ", placementsString, statesString));
        placementsString = formattedNumber (countPlacements (matchedForwardStates));
        statesString     = formattedNumber (matchedForwardStates .size ());
        System .out .println (String .format (formatString, "Matched:        ", placementsString, statesString));
        placementsString = formattedNumber (countPlacements (uniqueBackwardStates));
        statesString     = formattedNumber (uniqueBackwardStates .size ());
        System .out .println (String .format (formatString, "Backward dead:  ", placementsString, statesString));
        placementsString = formattedNumber (countPlacements (backwardStateSet));
        statesString     = formattedNumber (backwardStateSet     .size ());
        System .out .println (String .format (formatString, "Backward total: ", placementsString, statesString));
        System .out .println ();
    }

    private static String formattedNumber (long number) {
        int k, l, length;
        String numberString;
        StringBuilder result;

        numberString = Long .toString (number);
        length = numberString .length ();
        k = 0;
        l = length % 3;
        if (0 == l) {
            l = 3;
        }
        result = new StringBuilder ();

        while (true) {
            result .append (numberString .substring (k, l));
            k = l;
            l += 3;
            if (length == k) {
                break;
            }
            result .append (' ');
        }

        return result .toString ();
    }
}