MapHandler.java

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

import java.util.*;

public class MapHandler {

    private static final int CELLS_LIMIT = 10000;
    private static final int
            MAZE_CELL_EMPTY        =  0,
            MAZE_CELL_WALL         = -1,
            MAZE_CELL_UNREACHABLE  = -2,
            MAZE_CELL_EMPTY_MARKED = -3,
            MAZE_CELL_EMPTY_ANGLE  = -4,
            MAZE_CELL_WALL_MARKED  = -5;

    private boolean initFlag;
    private String errorMessage;
    private int mazeWidth, mazeHeight, boxesNumber, cellsNumber, activeCellsNumber;
    private int [] [] mazeMap, cellIndices;
    private boolean [] [] activeCellsMap;
    private CellVector porter;
    private ArrayList <CellVector> boxVectors, tgtVectors, cellVectors;

    public MapHandler () {
        initFlag = false;
        errorMessage = "Uninitialized.";
    }

    public boolean process (String [] mapLines) {

        initFlag = false;

        if (parseMapSource (mapLines)) {
            return true;
        }

        if (reworkMaze ()) {
            return true;
        }

        if (enumerateCells ()) {
            return true;
        }

        if (findActiveCells ()) {
            return true;
        }

        reenumerateCells ();

        initFlag = true;

        return false;
    }

    public String getErrorMessage () {
        return errorMessage;
    }

    public boolean isInitialised () {
        return initFlag;
    }

    public int getCellsNumber () {
        return cellsNumber;
    }

    public int getActiveCellsNumber () {
        return activeCellsNumber;
    }

    public int getBoxesNumber () {
        return boxesNumber;
    }

    public int getMazeWidth () {
        return mazeWidth;
    }

    public int getMazeHeight () {
        return mazeHeight;
    }

    public short getPorterCell () {
        return (short) porter .getCell (cellIndices);
    }

    public short [] getBoxCells () {
        short [] result = new short [boxesNumber];
        for (int k = 0; boxesNumber > k; ++k) {
            result [k] = (short) boxVectors .get (k) .getCell (cellIndices);
        }
        return result;
    }

    public short [] getTargetCells () {
        short [] result = new short [boxesNumber];
        for (int k = 0; boxesNumber > k; ++k) {
            result [k] = (short) tgtVectors .get (k) .getCell (cellIndices);
        }
        return result;
    }

    public CellsAdjacency getCellsAdjacency () {
        int k, l, size, value;
        ArrayList <Short> valuesList;
        ArrayList <Integer> indicesList;
        CellVector vector, nextVector;
        short [] values;
        int   [] indices;

        valuesList  = new ArrayList <> ();
        indicesList = new ArrayList <> ();

        size = cellVectors .size ();
        for (k = 0; size > k; ++k) {
            indicesList .add (valuesList .size ());
            vector = cellVectors .get (k);
            for (l = 0; 4 > l; ++l) {
                nextVector = vector .neighbour (l);
                value = nextVector .getCell (cellIndices);
                if (0 > value) {
                    continue;
                }
                valuesList .add ((short) l);
                valuesList .add ((short) value);
                nextVector = nextVector .neighbour (l);
                if (nextVector .getCell (activeCellsMap)) {
                    valuesList .add ((short) nextVector .getCell (cellIndices));
                } else {
                    valuesList .add ((short) -1);
                }
                nextVector = vector .rearNeighbour (l);
                if (nextVector .getCell (activeCellsMap) && vector .getCell (activeCellsMap)) {
                    valuesList .add ((short) nextVector .getCell (cellIndices));
                } else {
                    valuesList .add ((short) -1);
                }
            }
        }
        indicesList .add (valuesList .size ());

        size = valuesList .size ();
        values = new short [size];
        for (k = 0; size > k; ++k) {
            values [k] = valuesList .get (k);
        }

        size = indicesList .size ();
        indices = new int [size];
        for (k = 0; size > k; ++k) {
            indices [k] = indicesList .get (k);
        }

        return new CellsAdjacency (cellsNumber, activeCellsNumber, values, indices);
    }

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

    private boolean parseMapSource (String [] mapSource) {
        int k, l, m, value;
        String rowString;
        CellVector vector;

        errorMessage = "No errors.";
        mazeHeight = mapSource .length;
        mazeWidth  = 0;

        for (k = 0; mazeHeight > k; ++k) {
            value = mapSource [k] .length ();
            if (mazeWidth < value) {
                mazeWidth = value;
            }
        }

        value = mazeWidth + 2;
        mazeMap = new int [mazeHeight + 2] [value];
        Arrays .fill (mazeMap [0],              MAZE_CELL_WALL);
        Arrays .fill (mazeMap [mazeHeight + 1], MAZE_CELL_WALL);
        porter = null;
        boxVectors = new ArrayList <> ();
        tgtVectors = new ArrayList <> ();

        for (k = 1; mazeHeight >= k; ++k) {
            rowString = mapSource [k - 1];
            mazeMap [k] [0] = MAZE_CELL_WALL;
            for (l = 0, m = 1; rowString .length () > l; l = m, ++m) {
                vector = new CellVector (m, k);
                vector .setCell (mazeMap, MAZE_CELL_EMPTY);
                switch (rowString .charAt (l)) {
                case '$':
                    boxVectors .add (vector);
                    break;
                case '*':
                    boxVectors .add (vector);
                case '.':
                    tgtVectors .add (vector);
                    break;
                case '+':
                    tgtVectors .add (vector);
                case '@':
                    if (null != porter) {
                        errorMessage = "Duplicate porter marker.";
                        return true;
                    }
                    porter = vector;
                    break;
                case '#':
                    vector .setCell (mazeMap, MAZE_CELL_WALL);
                case ' ':
                    break;
                default:
                    errorMessage = "Unknown map marker.";
                    return true;
                }
            }
            ++l;
            for (; value > l; ++l) {
                mazeMap [k] [l] = MAZE_CELL_WALL;
            }
        }

        return false;
    }

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

    private boolean reworkMaze () {
        int k, l, m, n, minX, maxX, minY, maxY;
        Queue <CellVector> queue;
        CellVector vector, newVector;
        Iterator <CellVector> vectorIterator;
        int [] [] oldMap;

        queue = new ArrayDeque <> ();
        porter .setCell (mazeMap, MAZE_CELL_EMPTY_MARKED);
        queue .add (porter);
        minX = porter .getX ();
        maxX = porter .getX ();
        minY = porter .getY ();
        maxY = porter .getY ();

        while (!queue .isEmpty ()) {
            vector = queue .poll ();
            for (k = 0; 4 > k; ++k) {
                newVector = vector .neighbour (k);
                switch (newVector .getCell (mazeMap)) {
                case MAZE_CELL_EMPTY:
                case MAZE_CELL_EMPTY_ANGLE:
                    newVector .setCell (mazeMap, MAZE_CELL_EMPTY_MARKED);
                    queue .add (newVector);
                    break;
                case MAZE_CELL_WALL:
                    newVector .setCell (mazeMap, MAZE_CELL_WALL_MARKED);
                case MAZE_CELL_WALL_MARKED:
                case MAZE_CELL_EMPTY_MARKED:
                    break;
                default:
                    throw new IllegalArgumentException ("\n\nImpossible error: unknown maze cell type.\n");
                }
                if (minX > newVector .getX ()) {
                    minX = newVector .getX ();
                }
                if (maxX < newVector .getX ()) {
                    maxX = newVector .getX ();
                }
                if (minY > newVector .getY ()) {
                    minY = newVector .getY ();
                }
                if (maxY < newVector .getY ()) {
                    maxY = newVector .getY ();
                }
            }
            for (; 8 > k; ++k) {
                newVector = vector .neighbour (k);
                switch (newVector .getCell (mazeMap)) {
                case MAZE_CELL_EMPTY:
                    newVector .setCell (mazeMap, MAZE_CELL_EMPTY_ANGLE);
                    break;
                case MAZE_CELL_WALL:
                    newVector .setCell (mazeMap, MAZE_CELL_WALL_MARKED);
                case MAZE_CELL_WALL_MARKED:
                case MAZE_CELL_EMPTY_MARKED:
                case MAZE_CELL_EMPTY_ANGLE:
                    break;
                default:
                    throw new IllegalArgumentException ("\n\nImpossible error: unknown maze cell type.\n");
                }
            }
        }

        vectorIterator = boxVectors .iterator ();
        while (vectorIterator .hasNext ()) {
            if (MAZE_CELL_EMPTY_MARKED != vectorIterator .next () .getCell (mazeMap)) {
                vectorIterator .remove ();
            }
        }

        vectorIterator = tgtVectors .iterator ();
        while (vectorIterator .hasNext ()) {
            if (MAZE_CELL_EMPTY_MARKED != vectorIterator .next () .getCell (mazeMap)) {
                vectorIterator .remove ();
            }
        }

        boxesNumber = boxVectors .size ();
        if (boxesNumber != tgtVectors .size ()) {
            errorMessage = "Numbers of reachable boxes and targets do not agree.";
            return true;
        }

        vector = new CellVector (-minX, -minY);
        porter = porter .sumWith (vector);

        for (k = 0; boxesNumber > k; ++k) {
            boxVectors .set (k, boxVectors .get (k) .sumWith (vector));
            tgtVectors .set (k, tgtVectors .get (k) .sumWith (vector));
        }

        mazeWidth  = maxX - minX + 1;
        mazeHeight = maxY - minY + 1;
        oldMap  = mazeMap;
        mazeMap = new int [mazeHeight] [mazeWidth];

        for (k = minY, m = 0; maxY >= k; ++k, ++m) {
            for (l = minX, n = 0; maxX >= l; ++l, ++n) {
                switch (oldMap [k] [l]) {
                case MAZE_CELL_WALL:
                case MAZE_CELL_EMPTY:
                    mazeMap [m] [n] = MAZE_CELL_UNREACHABLE;
                    break;
                case MAZE_CELL_WALL_MARKED:
                case MAZE_CELL_EMPTY_ANGLE:
                    mazeMap [m] [n] = MAZE_CELL_WALL;
                    break;
                case MAZE_CELL_EMPTY_MARKED:
                    mazeMap [m] [n] = MAZE_CELL_EMPTY;
                    break;
                default:
                    throw new IllegalArgumentException ("\n\nImpossible error: unknown maze cell type.\n");
                }
            }
        }

        /*
        System .out .println ();
        boxVectors .forEach (p -> System .out .println (p .toString ()));
        System .out .println ();
        tgtVectors .forEach (p -> System .out .println (p .toString ()));
        //*/

        return false;
    }

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

    private boolean enumerateCells () {
        int k, l;
        CellVector vector;

        cellIndices = new int [mazeHeight] [mazeWidth];
        cellVectors = new ArrayList <> ();
        cellsNumber = 0;

        for (k = 0; mazeHeight > k; ++k) {
            for (l = 0; mazeWidth > l; ++l) {
                vector = new CellVector (l, k);
                switch (vector .getCell (mazeMap)) {
                case MAZE_CELL_EMPTY:
                    vector .setCell (cellIndices, cellsNumber);
                    ++cellsNumber;
                    if (CELLS_LIMIT < cellsNumber) {
                        errorMessage = "Number of cells exceeds limit.";
                        return true;
                    }
                    cellVectors .add (vector);
                    break;
                case MAZE_CELL_WALL:
                case MAZE_CELL_UNREACHABLE:
                    vector .setCell (cellIndices, -1);
                    break;
                default:
                    throw new IllegalArgumentException ("\n\nImpossible error: unknown maze cell type.\n");
                }
            }
        }

        return false;
    }

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

    private boolean findActiveCells () {
        int k, l;
        boolean [] forwardFlags, backwardFlags;
        boolean [] [] stateFlags;
        Queue <SingleBoxState> queue;
        SingleBoxState state, newState;
        CellVector porterVector, boxVector, newPorterVector, newBoxVector, vector;

        forwardFlags  = new boolean [cellsNumber];
        stateFlags    = new boolean [cellsNumber] [cellsNumber];
        queue = new ArrayDeque <> ();

        for (k = 0; boxesNumber > k; ++k) {
            state = new SingleBoxState (
                            porter              .getCell (cellIndices),
                            boxVectors .get (k) .getCell (cellIndices));
            queue .add (state);
            state .flagState (stateFlags);
            state .flagBox (forwardFlags);
        }

        while (!queue .isEmpty ()) {
            state = queue .poll ();
            //System .out .println ("State: " + state .porter + ", " + state .box);
            porterVector = cellVectors .get (state .porter);
            boxVector    = cellVectors .get (state .box);
            for (k = 0; 4 > k; ++k) {
                newPorterVector = porterVector .neighbour (k);
                if (MAZE_CELL_EMPTY != newPorterVector .getCell (mazeMap)) {
                    continue;
                }
                if (boxVector .equals (newPorterVector)) {
                    newBoxVector = boxVector .neighbour (k);
                    if (MAZE_CELL_EMPTY != newBoxVector .getCell (mazeMap)) {
                        continue;
                    }
                } else {
                    newBoxVector = boxVector;
                }
                newState = new SingleBoxState (
                                    newPorterVector .getCell (cellIndices),
                                    newBoxVector    .getCell (cellIndices));
                if (newState .isStateFlagged (stateFlags)) {
                    continue;
                }
                queue .add (newState);
                newState .flagState (stateFlags);
                newState .flagBox (forwardFlags);
            }
        }

        //displayMazeFlagged (forwardFlags);

        backwardFlags = new boolean [cellsNumber];
        stateFlags    = new boolean [cellsNumber] [cellsNumber];
        queue = new ArrayDeque <> ();

        for (k = 0; boxesNumber > k; ++k) {
            boxVector = tgtVectors .get (k);
            for (l = 0; 4 > l; ++l) {
                porterVector = boxVector .neighbour (l);
                if (MAZE_CELL_EMPTY != porterVector .getCell (mazeMap)) {
                    continue;
                }
                state = new SingleBoxState (
                                porterVector .getCell (cellIndices),
                                boxVector    .getCell (cellIndices));
                queue .add (state);
                state .flagState (stateFlags);
                state .flagBox (backwardFlags);
            }
        }

        while (!queue .isEmpty ()) {
            state = queue .poll ();
            //System .out .println ("State: " + state .porter + ", " + state .box);
            porterVector = cellVectors .get (state .porter);
            boxVector    = cellVectors .get (state .box);
            for (k = 0; 4 > k; ++k) {
                newPorterVector = porterVector .neighbour (k);
                if (MAZE_CELL_EMPTY != newPorterVector .getCell (mazeMap)) {
                    continue;
                }
                if (boxVector .equals (newPorterVector)) {
                    continue;
                }
                newState = new SingleBoxState (
                                    newPorterVector .getCell (cellIndices),
                                    boxVector       .getCell (cellIndices));
                if (!newState .isStateFlagged (stateFlags)) {
                    queue .add (newState);
                    newState .flagState (stateFlags);
                    //System .out .println ("  new state: " + newState .porter + ", " + newState .box);
                }
                newBoxVector = boxVector .neighbour (k);
                if (!porterVector .equals (newBoxVector)) {
                    continue;
                }
                newState = new SingleBoxState (
                                    newPorterVector .getCell (cellIndices),
                                    newBoxVector    .getCell (cellIndices));
                if (newState .isStateFlagged (stateFlags)) {
                    continue;
                }
                queue .add (newState);
                newState .flagState (stateFlags);
                newState .flagBox (backwardFlags);
                //System .out .println ("  new state: " + newState .porter + ", " + newState .box + " *");
            }
        }

        //displayMazeFlagged (backwardFlags);

        activeCellsMap = new boolean [mazeHeight] [mazeWidth];

        for (k = 0; cellsNumber > k; ++k) {
            vector = cellVectors .get (k);
            vector .setCell (activeCellsMap, forwardFlags [k] && backwardFlags [k]);
        }

        //displayMazeActiveCells ();

        for (k = 0; boxesNumber > k; ++k) {
            if (!boxVectors .get (k) .getCell (activeCellsMap)) {
                errorMessage = "Some boxes are placed in dead cells.";
                return true;
            }
            if (!tgtVectors .get (k) .getCell (activeCellsMap)) {
                errorMessage = "Some target cells are unreachable by boxes.";
                return true;
            }
        }

        return false;
    }

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

    private class SingleBoxState {

        public int porter, box;

        public SingleBoxState (int porter, int box) {
            this .porter = porter;
            this .box    = box;
        }

        public void flagState (boolean [] [] stateFlags) {
            stateFlags [porter] [box] = true;
        }

        public boolean isStateFlagged (boolean [] [] stateFlags) {
            return stateFlags [porter] [box];
        }

        public void flagBox (boolean [] boxFlags) {
            boxFlags [box] = true;
        }
    }

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

    private void reenumerateCells () {
        int k, l, index;
        CellVector vector;

        cellIndices = new int [mazeHeight] [mazeWidth];
        cellVectors = new ArrayList <> ();
        index = 0;

        for (k = 0; mazeHeight > k; ++k) {
            for (l = 0; mazeWidth > l; ++l) {
                vector = new CellVector (l, k);
                if (!vector .getCell (activeCellsMap)) {
                    continue;
                }
                vector .setCell (cellIndices, index);
                ++index;
                cellVectors .add (vector);
            }
        }

        activeCellsNumber = index;

        for (k = 0; mazeHeight > k; ++k) {
            for (l = 0; mazeWidth > l; ++l) {
                vector = new CellVector (l, k);
                switch (vector .getCell (mazeMap)) {
                case MAZE_CELL_EMPTY:
                    if (!vector .getCell (activeCellsMap)) {
                        vector .setCell (cellIndices, index);
                        ++index;
                        cellVectors .add (vector);
                    }
                    break;
                case MAZE_CELL_WALL:
                case MAZE_CELL_UNREACHABLE:
                    vector .setCell (cellIndices, -1);
                    break;
                default:
                    throw new IllegalArgumentException ("\n\nImpossible error: unknown maze cell type.\n");
                }
            }
        }
    }

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

    public void displayMaze () {
        int k, l;

        System .out .println ();
        for (k = 0; mazeHeight > k; ++k) {
            for (l = 0; mazeWidth > l; ++l) {
                switch (mazeMap [k] [l]) {
                case MAZE_CELL_EMPTY:
                    System .out .print ('.');
                    break;
                case MAZE_CELL_WALL:
                    System .out .print ('#');
                    break;
                default:
                    System .out .print (' ');
                    break;
                }
            }
            System .out .println ();
        }
    }

    public void displayMazeFlagged (boolean [] flags) {
        int k, l;

        System .out .println ();
        for (k = 0; mazeHeight > k; ++k) {
            for (l = 0; mazeWidth > l; ++l) {
                switch (mazeMap [k] [l]) {
                case MAZE_CELL_EMPTY:
                    if (flags [cellIndices [k] [l]]) {
                        System .out .print (',');
                    } else {
                        System .out .print ('.');
                    }
                    break;
                case MAZE_CELL_WALL:
                    System .out .print ('#');
                    break;
                default:
                    System .out .print (' ');
                    break;
                }
            }
            System .out .println ();
        }
    }

    public void displayMazeWithActiveCells () {
        int k, l;

        System .out .println ();
        for (k = 0; mazeHeight > k; ++k) {
            for (l = 0; mazeWidth > l; ++l) {
                switch (mazeMap [k] [l]) {
                case MAZE_CELL_EMPTY:
                    if (activeCellsMap [k] [l]) {
                        System .out .print (',');
                    } else {
                        System .out .print ('.');
                    }
                    break;
                case MAZE_CELL_WALL:
                    System .out .print ('#');
                    break;
                default:
                    System .out .print (' ');
                    break;
                }
            }
            System .out .println ();
        }
    }

    public void displayState (State state, boolean flag) {
        int k, l;
        char [] [] tempMap = new char [mazeHeight] [mazeWidth];
        short [] stateCells = state .getStateCells ();

        for (k = 0; mazeHeight > k; ++k) {
            for (l = 0; mazeWidth > l; ++l) {
                switch (mazeMap [k] [l]) {
                case MAZE_CELL_EMPTY:
                    tempMap [k] [l] = '.';
                    break;
                case MAZE_CELL_WALL:
                    tempMap [k] [l] = '#';
                    break;
                default:
                    tempMap [k] [l] = ' ';
                    break;
                }
            }
        }

        for (k = 0; stateCells .length > k; ++k) {
            cellVectors .get (stateCells [k]) .setCell (tempMap, '$');
        }
        cellVectors .get (state .getPorterCell ()) .setCell (tempMap, '@');

        System .out .println ();
        if (flag) {
            System .out .println (String .format ("Moves: %d, pushes: %d", state .getMoveCount (), state .getPushCount ()));
        }

        for (k = 0; mazeHeight > k; ++k) {
            System .out .println (new String (tempMap [k]));
        }
    }
}