StateProcessor.java

//  Sokoban brute solver.
//  2021, May, B@R5uk
//  Discussion: https://dxdy.ru/topic144781.html

import java.util.*;

public class StateProcessor {

    private static final int MEMORY_RESERVE_PERCENT = 20;
    private static final Runtime rt = Runtime .getRuntime ();

    private SortedMap <State, State> statesCollection;
    private Queue     <State>        statesQueue;
    State solutionRoot;

    public StateProcessor () {
        statesCollection = new TreeMap <> ();
        solutionRoot = null;
    }

    public boolean run (MapHandler mapHandler, boolean priorityType, Random rng) {
        int k, l, value, interCount;
        short cell;
        short [] cellsAdjValues, stateCells;
        int   [] cellsAdjIndices;
        State state, oldState, finalState;
        State [] nextStates;
        CellsAdjacency cellsAdjacency;
        Comparator <State> stateComparator;
        long startTime, nextTime, currentTime, memoryLimit;

        if (priorityType) {
            stateComparator = new State .PushPriorityComparator ();
        } else {
            stateComparator = new State .MovePriorityComparator ();
        }
        statesQueue = new PriorityQueue <> (stateComparator);
        cellsAdjacency = mapHandler .getCellsAdjacency ();
        State .init (cellsAdjacency);
        statesCollection .clear ();
        statesQueue      .clear ();
        solutionRoot = null;

        cellsAdjValues  = cellsAdjacency .getValues ();
        cellsAdjIndices = cellsAdjacency .getIndices ();
        finalState = new State (mapHandler .getPorterCell (), mapHandler .getBoxCells ());
        stateCells = mapHandler .getTargetCells ();
        Arrays .sort (stateCells);

        for (k = 0; stateCells .length > k; ++k) {
            cell = stateCells [k];
            value = cellsAdjIndices [cell + 1];
            for (l = cellsAdjIndices [cell] + 1; value > l; l += 4) {
                cell = cellsAdjValues [l];
                if (0 > Arrays .binarySearch (stateCells, cell)) {
                    state = new State (cell, stateCells);
                    if (!statesCollection .containsKey (state)) {
                        statesCollection .put (state, state);
                        statesQueue      .add (state);
                    }
                }
            }
        }

        interCount = 0;
        startTime = System .currentTimeMillis ();
        nextTime = startTime + 500;
        memoryLimit = (long) ((1.0 - MEMORY_RESERVE_PERCENT / 100.0) * rt .maxMemory ());
        while (!statesQueue .isEmpty ()) {
            state = statesQueue .poll ();
            if (state .isObsolete ()) {
                continue;
            }
            if (null != solutionRoot && 0 >= stateComparator .compare (solutionRoot, state)) {
                continue;
            }
            nextStates = state .expandBack ();
            for (k = 0; nextStates .length > k; ++k) {
                state = nextStates [k];
                if (finalState .equals (state) && null == solutionRoot) {
                    solutionRoot = state;
                }
                if (statesCollection .containsKey (state)) {
                    oldState = statesCollection .get (state);
                    value = stateComparator .compare (oldState, state);
                    if (0 > value) {
                        continue;
                    }
                    if (0 == value) {
                        if (null == rng) {
                            oldState .updatePathCountWith (state);
                            continue;
                        }
                        state = oldState .selectRandomState (state, rng);
                        if (oldState == state) {
                            continue;
                        }
                    }
                    statesCollection .remove (oldState);
                    oldState .markObsolete ();
                }
                statesCollection .put (state, state);
                statesQueue      .add (state);
            }
            ++interCount;
            if (0 != (interCount & 1023)) {
                continue;
            }
            currentTime = System .currentTimeMillis ();
            if (nextTime > currentTime) {
                continue;
            }
            nextTime = currentTime + 500;
            if (memoryLimit > rt .totalMemory () - rt .freeMemory ()) {
                continue;
            }
            solutionRoot = null;
            return true;
        }

        solutionRoot = statesCollection .get (finalState);
        return false;
    }

    public String getSolutionString () {
        int move;
        StringBuilder moveSequence;
        State state, prevState;

        if (null == solutionRoot) {
            return null;
        }

        moveSequence = new StringBuilder ();
        state = solutionRoot;
        prevState = state .getPreviousState ();

        while (null != prevState) {
            move = state .getMove ();
            if (0 > move) {
                moveSequence .append (Character .toUpperCase (CellVector .rearMoveLetter (-move - 1)));
            } else {
                moveSequence .append (CellVector .rearMoveLetter (move));
            }
            state = prevState;
            prevState = state .getPreviousState ();
        }

        return moveSequence .toString ();
    }

    public void displaySolution () {
        int k, l, m, length;
        String moveSequence;

        if (null == solutionRoot) {
            System .out .println ();
            System .out .println ("No solution found.");
            return;
        }

        moveSequence = getSolutionString ();
        length = moveSequence .length ();

        System .out .println ();
        System .out .println (String .format ("Moves  number: %5d", solutionRoot .getMoveCount ()));
        System .out .println (String .format ("Pushes number: %5d", solutionRoot .getPushCount ()));
        System .out .println ();

        k = 0;
        m = 0;
        while (true) {
            l = Integer .min (k + 5, length);
            System .out .print (moveSequence .substring (k, l));
            k += 5;
            if (length <= k) {
                System .out .println ();
                break;
            }
            ++m;
            if (6 == m) {
                System .out .println ();
                m = 0;
            } else {
                System .out .print (" ");
            }
        }
        System .out .println ();
        System .out .println ("Total number of different solutions: " + (Long .MAX_VALUE == solutionRoot .getPathCount () ? "exceeded counter limit" : solutionRoot .getPathCount ()));
    }
}