StateProcessor.java

//  Sokoban state space explorer.
//  Discussion: https://dxdy.ru/topic144781.html

import java.util.*;

public class StateProcessor {

    private MapHandler mapHandler;
    private CellsAdjacency cellsAdjacency;

    private Queue     <State> stateQueue;
    private SortedSet <State> forwardStateSet, backwardStateSet;
    private ArrayList <State> uniqueForwardStates, uniqueBackwardStates;
    private ArrayList <State> matchedForwardStates, matchedBackwardStates;

    private static String formatString;

    public StateProcessor (MapHandler mapHandler) {
        this .mapHandler = mapHandler;
        stateQueue = new ArrayDeque <> ();
    }

    public void run (boolean flag) {
        if (flag) {
            cellsAdjacency = mapHandler .getCellsAdjacencySmart ();
        } else {
            cellsAdjacency = mapHandler .getCellsAdjacencySimple ();
        }
        State .init (cellsAdjacency);
        processForward ();
        processBackward ();
        matchStates ();
    }

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

        stateQueue .clear ();
        forwardStateSet = new TreeSet <> ();
        state = new State (mapHandler .getPorterCell (), mapHandler .getBoxCells ());
        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 void processBackward () {
        int k, l, length, limit;
        short cell;
        short [] netrepValues, stateCells;
        int   [] netrepIndices;
        State state;
        State [] states;

        netrepValues  = cellsAdjacency .getValues ();
        netrepIndices = cellsAdjacency .getIndices ();
        stateQueue .clear ();
        backwardStateSet = new TreeSet <> ();
        stateCells = mapHandler .getTargetCells ();
        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)) {
                    state = new State (cell, stateCells);
                    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 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:
                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);
            }
        }
    }

    public void displayMapStats () {
        int cellsCount, boxesCount, activeCellsCount;
        long placementsCount, statesCount;
        long placementsCount2, statesCount2;
        String placementsString, statesString;
        String placementsString2, statesString2;

        cellsCount = mapHandler .getCellsNumber ();
        boxesCount = mapHandler .getBoxesNumber ();
        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 ()));

        activeCellsCount = mapHandler .getActiveCellsNumber ();
        placementsCount2 = nchoosek (activeCellsCount, boxesCount);
        statesCount2 = placementsCount2 * (cellsCount - boxesCount);
        placementsString2 = formattedNumber (placementsCount2);
        statesString2     = formattedNumber (statesCount2);

        System .out .println (String .format ("Cells:  %5d", cellsCount));
        System .out .println (String .format ("Active: %5d", activeCellsCount));
        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));
        System .out .println (String .format (formatString, "Reduced:        ", placementsString2, statesString2));
    }

    public 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 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 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 ();
    }

    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;
    }
}