// Find the max number of moves for a given shape

#include <algorithm>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stdint.h>
#include <string>
#include <time.h>
#include <vector>
#include <windows.h>

// Define the shape (could be done on command line, or in main?)
#define HH 4
#define WW 5
#define SHAPE "...##....##....##..."

typedef unsigned char byte;

struct Moves {
    int nMoves;
    std::vector<byte> moves;
};

struct SokobanSolver {
    static void printGrid(uint64_t state, uint64_t shape_position) {
        int player = findPlayer(state);
        std::cout << "+";
        for (int j=0; j<WW; j++) std::cout << "-";
        std::cout << "+\n";
        for (int i=0; i<HH; i++) {
            std::cout << "|";
            for (int j=0; j<WW; j++) {
                if (getPosition(shape_position, i*WW+j) > 0) {
                    std::cout << "#";
                } else if (i*WW+j == player) {
                    std::cout << "@";
                } else if (getPosition(state, i*WW+j) > 0) {
                    std::cout << "*";
                } else {
                    std::cout << " ";
                }
            }
            std::cout << "|\n";
        }
        std::cout << "+";
        for (int j=0; j<WW; j++) std::cout << "-";
        std::cout << "+\n";
    }

    static uint64_t findPlayer(uint64_t state) {
        return state & ((uint64_t)63);
    }

    static uint64_t getPosition(uint64_t state, int position) {
        return state & (((uint64_t)64) << position);
    }

    static uint64_t setPlayer(uint64_t state, int position) {
        return (state & ~((uint64_t)63)) | ((uint64_t)position);
    }

    static uint64_t togglePosition(uint64_t state, int position) {
        return state ^ (((uint64_t)64) << position);
    }

    // can we apply this move to this piece?
    static bool isValid(int move, int n, uint64_t shape_position) {
        int w = n + moveAddition(move);
        if (w>=0 && w<62 && (shape_position & (64<<w))) {
            return false;
        }
        if (move == 0) {
            return (n >= WW);
        } else if (move == 1) {
            return (n < WW*(HH-1));
        } else if (move == 2) {
            return (n%WW != 0);
        } else {
            return (n%WW != WW-1);
        }
    }

    static uint64_t applyMove(int mov, uint64_t position, uint64_t shape_position) {
        int submov = mov&3;
        int player = findPlayer(position);
        int delta = moveAddition(submov);

        if (!isValid(submov, player, shape_position)) return 0;
        if (getPosition(position, player+delta) > 0) return 0;

        if (mov>3 && (!isValid(submov^1, player, shape_position) || getPosition(position, player-delta) == 0)) return 0;
        uint64_t newPosition = setPlayer(position, player+delta);
        if (mov>3) {
            newPosition = togglePosition(togglePosition(newPosition, player), player-delta);
        }
        return newPosition;
    }

    static int moveAddition(int mov) {
        // -16, 16, -1, 1
        if (mov == 0) {
            return -WW;
        } else if (mov == 1) {
            return WW;
        } else if (mov == 2) {
            return -1;
        } else if (mov == 3) {
            return 1;
        } else {
            return 0;
        }
    }

    // solve by enumerating every position with one map per depth
    static int mapSolve(uint64_t puzzle, uint64_t shape_position) {
        // start with empty maps (state -> <depth, movestring>)
        std::set<uint64_t> positions;
        std::set<uint64_t> nextPositions;
        std::set<uint64_t> curPositions;

        // get starting positions
        for (int i=0; i<HH*WW; i++) {
            if (getPosition(puzzle, i) > 0) {
                // try placing player around this
                for (int j=0; j<4; j++) {
                    int add = moveAddition(j);
                    if (!isValid(j, i, shape_position)) continue;
                    if (getPosition(puzzle, i+add) == 0) {
                        positions.insert(setPlayer(puzzle, i+add));
                        nextPositions.insert(setPlayer(puzzle, i+add));
                    }
                }
            }
        }

        int main_depth = 0;

        while (!nextPositions.empty()) {
            // swap maps
            std::swap(curPositions, nextPositions);
            nextPositions.clear();

            // iterate over map
            for (std::set<uint64_t>::iterator it=curPositions.begin(); it!=curPositions.end(); ++it) {
                uint64_t position = *it;

                // loop through moves
                for (int mov = 0; mov < 8; mov++) {
                    uint64_t newPosition = applyMove(mov, position, shape_position);
                    if (newPosition != 0) {
                        if (positions.count(newPosition) == 0) {
                            positions.insert(newPosition);
                            nextPositions.insert(newPosition);
                        }
                    }
                }
            }

            if (nextPositions.empty()) {
                return main_depth;
            }

            main_depth++;
        }
        return -1;
    }

    static int rotate(int num) {
        int rot = 0;
        for (int i=0; i<HH; i++) {
            for (int j=0; j<HH; j++) {
                int digit = i*HH + j;
                if ((num & 1<<digit) != 0) {
                    rot += 1<<(j*HH + HH-1 - i);
                }
            }
        }
        return rot;
    }
    static int flip(int num) {
        int rot = 0;
        for (int i=0; i<HH; i++) {
            for (int j=0; j<WW; j++) {
                int digit = i*WW + j;
                if ((num & (1<<digit)) != 0) {
                    rot += 1<<(i*WW + WW-1 - j);
                }
            }
        }
        return rot;
    }
    static int flip2(int num) {
        int rot = 0;
        for (int i=0; i<HH; i++) {
            for (int j=0; j<WW; j++) {
                int digit = i*WW + j;
                if ((num & (1<<digit)) != 0) {
                    rot += 1<<((HH-1-i)*WW + j);
                }
            }
        }
        return rot;
    }
    // uflip and uflip2 - flip uint64_t without a player
    static uint64_t uflip(uint64_t num) {
        uint64_t rot = 0;
        for (int i=0; i<HH; i++) {
            for (int j=0; j<WW; j++) {
                int digit = i*WW + j;
                if ((num & (((uint64_t)1)<<digit)) != 0) {
                    rot += ((uint64_t)1)<<(i*WW + WW-1 - j);
                }
            }
        }
        return rot;
    }
    static uint64_t uflip2(uint64_t num) {
        uint64_t rot = 0;
        for (int i=0; i<HH; i++) {
            for (int j=0; j<WW; j++) {
                int digit = i*WW + j;
                if ((num & (((uint64_t)1)<<digit)) != 0) {
                    rot += ((uint64_t)1)<<((HH-1-i)*WW + j);
                }
            }
        }
        return rot;
    }

    // moveAddition to array?

    static int solve() {
        clock_t startTime = clock();
        //int maxMoves = 0;
        //int h = 4;
        //int w = 5;
        //uint64_t basePuzzle = 63;

        // process shape into a puzzle or whatever
        uint64_t shape_position = 0;
        for (int i=0; i<(HH*WW); i++) {
            if (SHAPE[i] == '#') {
                shape_position += (64LL << i);
            }
        }

        int overallMax = 0;

        for (int nCrates=1; nCrates<(HH*WW); nCrates++) {
            std::cout << "Trying " << nCrates << " crates\n";
            int max = 0;
            uint64_t position = (((uint64_t)1) << nCrates) - ((uint64_t)1);
            // generate all possible moves for every position?
            // for each position with this number of crates...
            while (position < (((uint64_t)1) << (HH*WW))) {
                uint64_t curPosition = position;
                // get next
                // https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
                uint64_t t = (position | (position - 1)) + 1;
                uint64_t ww = t | ((((t & -t) / (position & -position)) >> 1) - 1);
                position = ww;
                // check that curPosition is ok
                if ((curPosition*64) & shape_position) continue;
                // solve
                int z = mapSolve(curPosition*64, shape_position);
                // print maximum
                if (z > max) {
                    max = z;
                    if (z > overallMax) {
                        overallMax = z;
                        double secs = double(clock() - startTime) / (double)CLOCKS_PER_SEC;
                        std::cout << "Puzzle " << curPosition << " solved in " << z << " moves (" << secs << ")\n"  << std::flush;
                        printGrid(curPosition*64+63, shape_position);
                    }
                }
            }
            std::cout << nCrates << " crates had max of " << max << " moves\n";
        }

        double secs = double(clock() - startTime) / (double)CLOCKS_PER_SEC;
        std::cout << "Done (" << secs << ")\n" << std::flush;
        std::cout << "Overall max moves was " << overallMax << "\n" << std::flush;

        return EXIT_SUCCESS;
    }
};

// g++ sokoban_4x4_bb2dt_shape.cpp -o sokoban_4x4_bb2dt_shape.exe -Wall -O3 --std=c++0x
int main(int argc, char *argv[]) {
    SokobanSolver::solve();
}