package knight;


import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;

public class PrecalculatedPaths {
    private static final Logger logger = LoggerFactory.getLogger(PrecalculatedPaths.class);

    static final int [] STEP_DELTA_X = {1, 2, 2, 1, -1, -2, -2, -1};
    static final int [] STEP_DELTA_Y = {2, 1, -1, -2, -2, -1, 1, 2};

    static final int BOARD_WIDHT = 8;
    static final int BOARD_HEIGHT = 8;
    static final int DEPTH = 4;

    // first index: position on chess board (index = x * BOARD_WIDHT + y)
    // second index: array of paths from each position (first index) in binary format
    // bit at position boardWidth * BOARD_HEIGHT - 1 (63) represents state of cell x=0, y=0 and equals 1 if cell is used and 0 otherwise;
    // bit at position boardWidth * BOARD_HEIGHT - 2 (62) represents cell x=1, y=0

    static final long[][] POSSIBLE_STEP_POSITIONS;
    static final Map<Long, List<Position>> PATH_BY_BINARY_POS;


    static {
        logger.info("Building static paths");

        POSSIBLE_STEP_POSITIONS = new long[BOARD_HEIGHT * BOARD_WIDHT][];
        PATH_BY_BINARY_POS = new HashMap<>();

        long positionsInBinaryFormat;

        for(int x = 0; x < BOARD_WIDHT; x++ ) {
            for(int y = 0; y < BOARD_HEIGHT; y++) {

                List<List<Position>> paths = explore(x, y, DEPTH);

                int pathCount = paths.size();
                POSSIBLE_STEP_POSITIONS[x * BOARD_WIDHT + y] = new long[pathCount];

                for(int i = 0; i < pathCount; i++) {
                    //Compact to binary format
                    List<Position> path = paths.get(i);
                    positionsInBinaryFormat = toBinaryPositions(path);

                    POSSIBLE_STEP_POSITIONS[x * BOARD_WIDHT + y][i] = positionsInBinaryFormat;

                    PATH_BY_BINARY_POS.put(positionsInBinaryFormat, path);
                }
            }
        }
    }


    /**
     * Get pre-calculated paths DEPTH deep for position on the board x, y and
     * current board state (board[][] contains cells states: 1 when cell is used and 0 when it is free)
     *
     * @param xPos x position on the board
     * @param yPos y position on the board
     * @param board chess board cells state (0 is free, 1 is used)
     * @return
     */
    public List<List<Position>> getPrecalculatedPaths(int xPos, int yPos, int[][] board) {
        List<List<Position>> validPaths = null;

        long boardState = 0L;

        //Create board state in binary format (or use binary format in input parameters)
        for(int x = 0; x < board.length; x++) {
            for(int y = 0; y < board[x].length; y++) {
                if(board[x][y] == 1) {
                    boardState = boardState & (1 << boardPositionToBinaryShift(x, y));
                }
            }
        }

        int flatIndex = boardPositionToBinaryShift(xPos, yPos);

        long[] paths = POSSIBLE_STEP_POSITIONS[flatIndex];

        //CAM can be used here to skip loop
        for(int i = 0; i < paths.length; i++) {
             if((paths[i] & boardState) == 0L) {
                 //If no intersections found, add path as valid
                 if(validPaths == null) {
                     validPaths = new ArrayList<>();
                 }

                 validPaths.add(PATH_BY_BINARY_POS.get(paths[i]));
             }
         }


        return validPaths;
    }

    private static long toBinaryPositions(List<Position> path) {
        long binaryPositions = 0L;

        for(Position position : path) {
            binaryPositions = binaryPositions & (1 << boardPositionToBinaryShift(position.x, position.y));
        }

        return binaryPositions;
    }

    private static int boardPositionToBinaryShift(int x, int y) {
        return x * BOARD_WIDHT + y;
    }

    private static List<List<Position>> explore(int x, int y, int maxSteps) {

        List<Position> startPath =  new ArrayList<>();
        startPath.add(new Position(x, y));

        List<List<Position>> possiblePaths =  new ArrayList<>();
        possiblePaths.add(startPath);

        for(int i = 0; i < maxSteps; i++) {
            possiblePaths = exploreLevel(possiblePaths);
        }

        return possiblePaths;
    }

    private static List<List<Position>> exploreLevel(List<List<Position>> parentPaths) {
        List<List<Position>> levelPaths =  new ArrayList<>();

        for(List<Position> parentPath : parentPaths) {
            List<List<Position>> childrenPaths =  new ArrayList<>();
            Position parentPos = parentPath.get(parentPath.size() - 1);
            HashSet<Position> usedPositions = new HashSet<>(parentPath);

            for (int i = 0; i < 8; i++) {
                Position candidate = new Position(parentPos.x + STEP_DELTA_X[i], parentPos.y + STEP_DELTA_Y[i]);

                if (usedPositions.contains(candidate) || (candidate.x < 0 || candidate.x > 7) || (candidate.y < 0 || candidate.y > 7)) {
                    continue;
                }

                List<Position> levelPath = new ArrayList<>();
                Collections.copy(levelPath, parentPath);

                levelPath.add(candidate);

                childrenPaths.add(levelPath);
            }

            //If nothing found, return input
            if (childrenPaths.isEmpty()) {
                childrenPaths.add(parentPath);
            }

            levelPaths.addAll(childrenPaths);
        }

        return levelPaths;
    }


}