StateSpace.java

//      Sokoban puzzles auto generator
//      https://dxdy.ru/post1541620.html#p1541620
//      2021 dec B@R5uk

import java.util.*;

public class StateSpace {

    public static final int NO_STATE = -1;
    public static final int CELLS_LIMIT = 57;
    public static final int STATES_LIMIT = 10_000_000;
    public static final short COUNT_INFINITY = Short .MAX_VALUE;

    private static long iterCount = -1L;

    private int cellsNumber, boxesNumber, freeNumber, statesNumber, stateIndex;
    private long [] stateIds;
    private int [] childStates, parentStates;
    private short [] moveCounts, pushCounts;
    private boolean spaceFilledFlag;
    private SortedSet <Integer> queue;

    public StateSpace (int argCellsNumber, int argBoxesNumber) {
        cellsNumber = argCellsNumber;
        boxesNumber = argBoxesNumber;
        freeNumber  = cellsNumber - boxesNumber;
        if (CELLS_LIMIT < cellsNumber) {
            throw new IllegalArgumentException ("\n\nNumber of cells out of range.\n");
        }
        if (0 > boxesNumber || cellsNumber <= boxesNumber) {
            throw new IllegalArgumentException ("\n\nNumber of boxes out of range.\n");
        }
        long tmpStatesNumber = getStatesNumber (cellsNumber, boxesNumber);
        if (-1L == tmpStatesNumber || STATES_LIMIT < tmpStatesNumber) {
            throw new IllegalArgumentException ("\n\nNumber of states out of range.\n");
        }
        statesNumber = (int) tmpStatesNumber;
        stateIds     = new long  [statesNumber];
        stateIndex = statesNumber;
        spaceFilledFlag = false;
        childStates  = new int   [statesNumber * 4];
        parentStates = new int   [statesNumber * 4];
        Arrays .fill (childStates,  NO_STATE);
        Arrays .fill (parentStates, NO_STATE);
        moveCounts   = new short [statesNumber];
        pushCounts   = new short [statesNumber];
        queue = new TreeSet <> (new MovePriorityComparator ());
    }

    //      ================================================

    public int getCellsNumber () {
        return cellsNumber;
    }

    public int getBoxesNumber () {
        return boxesNumber;
    }

    public int getStatesNumber () {
        return statesNumber;
    }

    public void displayStats () {
        System .out .println (String .format ("\nNumber of cells: %14d", cellsNumber));
        System .out .println (String .format ("Number of boxes: %14d", boxesNumber));
        System .out .println (String .format ("Number of states: %13s", Helper .spacedNumber (statesNumber)));
    }

    //      ================================================

    public int getMoveCount (int stateIndex) {
        return moveCounts [stateIndex];
    }

    public int getPushCount (int stateIndex) {
        return pushCounts [stateIndex];
    }

    //      ================================================

    public void addState (int [] boxCells, int cell) {
        if (spaceFilledFlag) {
            throw new RuntimeException ("\n\nState Space has already been filled.\n");
        }
        long id = packState (boxCells, cell);
        //System .out .println (Long .toHexString (id) + " " + Arrays .toString (boxCells));
        if (statesNumber != stateIndex && 0 >= Long .compare (stateIds [stateIndex], id)) {
            throw new IllegalArgumentException ("\n\nProper order of state IDs is broken.\n");
        }
        --stateIndex;
        stateIds [stateIndex] = id;
        if (0 == stateIndex) {
            spaceFilledFlag = true;
        }
    }

    //      ================================================

    public void linkStates (int parentState, int childState, int move) {
        if (0 > move || 4 <= move) {
            throw new IllegalArgumentException ("\n\nMove index out of range.\n");
        }
        if (0 > parentState || statesNumber <= parentState) {
            throw new IllegalArgumentException ("\n\nParent state index out of range.\n");
        }
        if (0 > childState || statesNumber <= childState) {
            throw new IllegalArgumentException ("\n\nChild state index out of range.\n");
        }
        childStates      [4 * parentState + move]  = childState;
        if (isSamePlacement (parentState, childState)) {
            parentStates [4 * childState  + move]  = parentState;
        } else {
            parentStates [4 * childState  +
                   CellVector .reverseMove (move)] = parentState;
        }
    }

    //      ================================================

    public int getStateIndexById (long stateId) {
        if (!spaceFilledFlag) {
            throw new RuntimeException ("\n\nState Space has not yet been filled.\n");
        }
        int stateIndex = Arrays .binarySearch (stateIds, stateId);
        if (0 > stateIndex) {
            throw new IllegalArgumentException ("\n\nIllegal state ID.\n");
        }
        return stateIndex;
    }

    //      ================================================

    public int getStateIndex (int [] boxCells, int cell) {
        if (!spaceFilledFlag) {
            throw new RuntimeException ("\n\nState Space has not yet been filled.\n");
        }
        return Arrays .binarySearch (stateIds, packState (boxCells, cell));
    }

    //      ================================================

    public long getStateIdByIndex (int stateIndex) {
        if (!spaceFilledFlag) {
            throw new RuntimeException ("\n\nState Space has not yet been filled.\n");
        }
        return stateIds [stateIndex];
    }

    //      ================================================

    public int unpackStateByIndex (int stateIndex, int [] boxCells, boolean [] occupiedCells) {
        if (!spaceFilledFlag) {
            throw new RuntimeException ("\n\nState Space has not yet been filled.\n");
        }
        return unpackStateFromId (stateIds [stateIndex], boxCells, occupiedCells);
    }

    //      ================================================

    public int unpackStateByIndex (int stateIndex, int [] boxCells) {
        if (!spaceFilledFlag) {
            throw new RuntimeException ("\n\nState Space has not yet been filled.\n");
        }
        return unpackStateFromId (stateIds [stateIndex], boxCells);
    }

    //      ================================================

    public long packState (int [] boxCells, int agentCell) {
        int cell;
        long stateId;
        if (boxesNumber != boxCells .length) {
            throw new IllegalArgumentException ("\n\nIncorrect number of boxes.\n");
        }
        if (0 > agentCell || cellsNumber <= agentCell) {
            throw new IllegalArgumentException ("\n\nCell index out of range.\n");
        }
        stateId = agentCell;
        for (int k = 0; boxesNumber > k; ++k) {
            cell = boxCells [k];
            if (cellsNumber <= cell) {
                throw new IllegalArgumentException ("\n\nCell index out of range.\n");
            }
            long value = 0x4000000000000000L >>> cell;
            if (0L != (stateId & value)) {
                throw new IllegalArgumentException ("\n\nDuplicate cell index.\n");
            }
            stateId |= value;
        }
        return stateId;
    }

    //      ================================================

    public int unpackStateFromId (long stateId, int [] boxCells, boolean [] occupiedCells) {
        int k = 0, index = 0;
        long mask = 0x4000000000000000L;
        Arrays .fill (occupiedCells, false);
        for (; cellsNumber > k; ++k, mask >>>= 1) {
            if (0L == (stateId & mask)) {
                continue;
            }
            boxCells [index] = k;
            occupiedCells [k] = true;
            ++index;
        }
        if (boxesNumber != index) {
            throw new RuntimeException ("\n\nNumber of boxes does not concur.\n");
        }
        return (int) (stateId & 0x3F);
    }

    //      ================================================

    public int unpackStateFromId (long stateId, int [] boxCells) {
        int k = 0, index = 0;
        long mask = 0x4000000000000000L;
        for (; cellsNumber > k; ++k, mask >>>= 1) {
            if (0L == (stateId & mask)) {
                continue;
            }
            boxCells [index] = k;
            ++index;
        }
        if (boxesNumber != index) {
            throw new RuntimeException ("\n\nNumber of boxes does not concur.\n");
        }
        return (int) (stateId & 0x3F);
    }

    //      ================================================

    public long replaceAgentCell (long stateId, int agentCell) {
        if (0 > agentCell || cellsNumber <= agentCell) {
            throw new IllegalArgumentException ("\n\nCell index out of range.\n");
        }
        return stateId & 0xFFFFFFFFFFFFFFC0L | agentCell;
    }

    //      ================================================

    public boolean isSamePlacement (int stateIndex1, int stateIndex2) {
        if (!spaceFilledFlag) {
            throw new RuntimeException ("\n\nState Space has not yet been filled.\n");
        }
        return 0 == ((stateIds [stateIndex1] ^ stateIds [stateIndex2]) & 0xFFFFFFFFFFFFFFC0L);
    }

    //      ================================================

    public int findMostDistantState () {
        int k, bestIndex = NO_STATE;
        short moveCount, pushCount, bestMoveCount = -1, bestPushCount = -1;
        for (k = 0; statesNumber > k; ++k) {
            moveCount = moveCounts [k];
            if (COUNT_INFINITY == moveCount) {
                continue;
            }
            pushCount = pushCounts [k];
            if (DoubleComp .isGreater (moveCount, bestMoveCount, pushCount, bestPushCount)) {
                bestMoveCount = moveCount;
                bestPushCount = pushCount;
                bestIndex = k;
            }
        }
        return bestIndex;
    }

    //      ================================================

    public void performForwardDijkstraSearch (int startState) {
        int state, newState, childIndex, childIndexLimit;
        short moveCount, pushCount, pushCountM1;

        if (!spaceFilledFlag) {
            throw new RuntimeException ("\n\nState Space has not yet been filled.\n");
        }
        Arrays .fill (moveCounts, COUNT_INFINITY);
        Arrays .fill (pushCounts, COUNT_INFINITY);
        queue .clear ();
        queue .add (startState);
        moveCounts [startState] = 0;
        pushCounts [startState] = 0;

        while (!queue .isEmpty ()) {
            state = queue .first ();
            queue .remove (state);
            moveCount   = (short) (moveCounts [state] + 1);
            pushCount   = (short) (pushCounts [state] + 1);
            pushCountM1 = pushCounts [state];
            childIndex      = 4 * state;
            childIndexLimit = 4 * state + 4;
            for (; childIndexLimit > childIndex; ++childIndex) {
                newState = childStates [childIndex];
                if (NO_STATE == newState) {
                    continue;
                }
                if (isSamePlacement (state, newState)) {
                    if (DoubleComp .isGreater (
                            moveCounts [newState], moveCount,
                            pushCounts [newState], pushCountM1)) {
                        queue .remove (newState);
                        moveCounts [newState] = moveCount;
                        pushCounts [newState] = pushCountM1;
                        queue .add (newState);
                    }
                } else {
                    if (DoubleComp .isGreater (
                            moveCounts [newState], moveCount,
                            pushCounts [newState], pushCount)) {
                        queue .remove (newState);
                        moveCounts [newState] = moveCount;
                        pushCounts [newState] = pushCount;
                        queue .add (newState);
                    }
                }
            }
        }
    }

    //      ================================================

    public void performBackwardDijkstraSearch (int startState) {
        int state, newState, parentIndex, parentIndexLimit;
        short moveCount, pushCount, pushCountM1;

        if (!spaceFilledFlag) {
            throw new RuntimeException ("\n\nState Space has not yet been filled.\n");
        }
        Arrays .fill (moveCounts, COUNT_INFINITY);
        Arrays .fill (pushCounts, COUNT_INFINITY);
        queue .clear ();
        queue .add (startState);
        moveCounts [startState] = 0;
        pushCounts [startState] = 0;

        while (!queue .isEmpty ()) {
            state = queue .first ();
            queue .remove (state);
            moveCount   = (short) (moveCounts [state] + 1);
            pushCount   = (short) (pushCounts [state] + 1);
            pushCountM1 = pushCounts [state];
            parentIndex      = 8 * state;
            parentIndexLimit = 8 * state + 8;
            for (; parentIndexLimit > parentIndex; ++parentIndex) {
                newState = parentStates [parentIndex];
                if (NO_STATE == newState) {
                    continue;
                }
                if (isSamePlacement (state, newState)) {
                    if (DoubleComp .isGreater (
                            moveCounts [newState], moveCount,
                            pushCounts [newState], pushCountM1)) {
                        queue .remove (newState);
                        moveCounts [newState] = moveCount;
                        pushCounts [newState] = pushCountM1;
                        queue .add (newState);
                    }
                } else {
                    if (DoubleComp .isGreater (
                            moveCounts [newState], moveCount,
                            pushCounts [newState], pushCount)) {
                        queue .remove (newState);
                        moveCounts [newState] = moveCount;
                        pushCounts [newState] = pushCount;
                        queue .add (newState);
                    }
                }
            }
        }
    }

    //      ================================================

    public void performMultistartDijkstraSearch (int startState) {
        int state, newState, parentIndex, parentIndexLimit;
        short moveCount, pushCount, pushCountM1;

        if (!spaceFilledFlag) {
            throw new RuntimeException ("\n\nState Space has not yet been filled.\n");
        }
        Arrays .fill (moveCounts, COUNT_INFINITY);
        Arrays .fill (pushCounts, COUNT_INFINITY);
        queue .clear ();
        startState = startState - startState % freeNumber;
        for (newState = startState; startState + freeNumber > newState; ++newState) {
            queue .add (newState);
            moveCounts [newState] = 0;
            pushCounts [newState] = 0;
        }

        while (!queue .isEmpty ()) {
            state = queue .first ();
            queue .remove (state);
            moveCount   = (short) (moveCounts [state] + 1);
            pushCount   = (short) (pushCounts [state] + 1);
            pushCountM1 = pushCounts [state];
            parentIndex      = 4 * state;
            parentIndexLimit = 4 * state + 4;
            for (; parentIndexLimit > parentIndex; ++parentIndex) {
                newState = parentStates [parentIndex];
                if (NO_STATE == newState) {
                    continue;
                }
                if (isSamePlacement (state, newState)) {
                    if (DoubleComp .isGreater (
                            moveCounts [newState], moveCount,
                            pushCounts [newState], pushCountM1)) {
                        queue .remove (newState);
                        moveCounts [newState] = moveCount;
                        pushCounts [newState] = pushCountM1;
                        queue .add (newState);
                    }
                } else {
                    if (DoubleComp .isGreater (
                            moveCounts [newState], moveCount,
                            pushCounts [newState], pushCount)) {
                        queue .remove (newState);
                        moveCounts [newState] = moveCount;
                        pushCounts [newState] = pushCount;
                        queue .add (newState);
                    }
                }
            }
        }
    }

    //      ================================================

    public AnalysisResult performDistanceAnalysis () {
        int startState, limitState, newState, state, parentIndex, parentIndexLimit;
        short moveCount, pushCount, pushCountM1;
        AnalysisResult result = new AnalysisResult ();
        Arrays .fill (result .bestMoveCounts, (short) -1);
        Arrays .fill (result .bestPushCounts, (short) -1);
        Arrays .fill (result .bestPlacements, -1);
        limitState = 0;
        iterCount  = 0;
        while (statesNumber > limitState) {
            startState = limitState;
            limitState += freeNumber;
            Arrays .fill (moveCounts, COUNT_INFINITY);
            Arrays .fill (pushCounts, COUNT_INFINITY);
            queue .clear ();
            for (newState = startState; limitState > newState; ++newState) {
                queue .add (newState);
                moveCounts [newState] = 0;
                pushCounts [newState] = 0;
            }
            while (!queue .isEmpty ()) {
                state = queue .first ();
                queue .remove (state);
                moveCount   = moveCounts [state];
                pushCount   = pushCounts [state];
                pushCountM1 = pushCount;
                if (DoubleComp .isGreater (
                        moveCount, result .bestMoveCounts [state],
                        pushCount, result .bestPushCounts [state])) {
                    result .bestMoveCounts [state] = moveCount;
                    result .bestPushCounts [state] = pushCount;
                    result .bestPlacements [state] = startState;
                }
                ++iterCount;
                ++moveCount;
                ++pushCount;
                parentIndex      = 4 * state;
                parentIndexLimit = 4 * state + 4;
                for (; parentIndexLimit > parentIndex; ++parentIndex) {
                    newState = parentStates [parentIndex];
                    if (NO_STATE == newState) {
                        continue;
                    }
                    if (isSamePlacement (state, newState)) {
                        if (DoubleComp .isGreater (
                                moveCounts [newState], moveCount,
                                pushCounts [newState], pushCountM1)) {
                            queue .remove (newState);
                            moveCounts [newState] = moveCount;
                            pushCounts [newState] = pushCountM1;
                            queue .add (newState);
                        }
                    } else {
                        if (DoubleComp .isGreater (
                                moveCounts [newState], moveCount,
                                pushCounts [newState], pushCount)) {
                            queue .remove (newState);
                            moveCounts [newState] = moveCount;
                            pushCounts [newState] = pushCount;
                            queue .add (newState);
                        }
                    }
                }
            }
        }
        return result;
    }

    public static long getIterCount () {
        return iterCount;
    }

    //      ================================================

    public class AnalysisResult {

        private short [] bestMoveCounts, bestPushCounts;
        private int [] bestPlacements;

        private AnalysisResult () {
            bestMoveCounts = new short [statesNumber];
            bestPushCounts = new short [statesNumber];
            bestPlacements = new int   [statesNumber];
        }

        public int [] getBest () {
            int state, bestState = -1, bestPlacement = -1, bestMoveCount = -1, bestPushCount = -1;
            int [] result = new int [4];
            for (state = 0; statesNumber > state; ++state) {
                if (DoubleComp .isGreater (
                        bestMoveCounts [state], bestMoveCount,
                        bestPushCounts [state], bestPushCount)) {
                    bestState = state;
                    bestPlacement = bestPlacements [state];
                    bestMoveCount = bestMoveCounts [state];
                    bestPushCount = bestPushCounts [state];
                }
            }
            result [0] = bestState;
            result [1] = bestPlacement;
            result [2] = bestMoveCount;
            result [3] = bestPushCount;
            return result;
        }
    }

    //      ================================================

    private class MovePriorityComparator implements Comparator <Integer> {
        @Override
        public int compare (Integer arg1, Integer arg2) {
            int result;
            if (0 != (result = moveCounts [arg1] - moveCounts [arg2])) {
                return result;
            }
            if (0 != (result = pushCounts [arg1] - pushCounts [arg2])) {
                return result;
            }
            return arg1 - arg2;
        }
    }

    //      ================================================

    public static String stateIdToHex (long stateId) {
        return String .format ("%16H", stateId);
    }

    //      ================================================

    public static long getStatesNumber (int cellsNumber, int boxesNumber) {
        long result, value;
        if (cellsNumber < boxesNumber) {
            return -1L;
        }
        result = nchoosek (cellsNumber, boxesNumber);
        if (-1L == result) {
            return -1L;
        }
        value = cellsNumber - boxesNumber;
        if (result > Long .MAX_VALUE / value) {
            return -1L;
        }
        return result * value;
    }

    //      ================================================

    public static long nchoosek (int n, int k) {
        long result = 1, value;
        if (0 > k || n < k) {
            return 0;
        }
        k = Integer .min (k, n - k);
        for (int l = 1; 0 < k; ++l, --k, --n) {
            value = result / l;
            //      a <= |_ b / c _|  ==>  a c <= b
            //      a >  |_ b / c _|  ==>  a c >  b
            if (value > Long .MAX_VALUE / n) {
                return -1;
            }
            result = value * n + result % l * n / l;
            if (0 > result) {
                return -1;
            }
        }
        return result;
    }
}