Sokoban Polyomino checker (128 bit)

// Sokoban n-squares search program, now 128 bit

// g++ sokoban_polyomino.cpp -o sokoban_polyomino.exe -Wall -O3 --std=c++0x
// sokoban_polyonino.exe < poly_16.txt

#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>

typedef unsigned char byte;
typedef unsigned __int128 uint128_t;

inline int moveAddition(int mov, int HH, int WW) {
    // -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;
    }
}

inline uint128_t findPlayer(uint128_t state) {
    return state & ((uint128_t)127);
}

inline uint128_t getPosition(uint128_t state, int position) {
    return state & (((uint128_t)128) << position);
}

inline uint128_t setPlayer(uint128_t state, int position) {
    return (state & ~((uint128_t)127)) | ((uint128_t)position);
}

inline uint128_t togglePosition(uint128_t state, int position) {
    return state ^ (((uint128_t)128) << position);
}

// can we apply this move to this piece?
inline bool isValid(int move, int n, uint128_t shape_position, int HH, int WW) {
    int w = n + moveAddition(move, HH, WW);
    if (w>=0 && w<126 && (shape_position & (((uint128_t)128)<<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);
    }
}

inline void printGrid(uint128_t state, uint128_t shape_position, int HH, int WW) {
    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";
}

uint128_t applyMove(int mov, uint128_t position, uint128_t shape_position, int HH, int WW) {
    int submov = mov&3;
    int player = findPlayer(position);
    int delta = moveAddition(submov, HH, WW);

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

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

// solve by enumerating every position with one map per depth
int mapSolve(uint128_t puzzle, uint128_t shape_position, int HH, int WW) {
    // start with empty maps (state -> <depth, movestring>)
    std::set<uint128_t> positions;
    std::set<uint128_t> nextPositions;
    std::set<uint128_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, HH, WW);
                if (!isValid(j, i, shape_position, HH, WW)) 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<uint128_t>::iterator it=curPositions.begin(); it!=curPositions.end(); ++it) {
            uint128_t position = *it;

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

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

        main_depth++;
    }
    return -1;
}

inline uint128_t parse_grid(std::string input) {
    uint128_t shape_position = 0;
    int idx = 0;
    int len = (int) input.length();
    for (int i=0; i<len; i++) {
        if (input[i] == '|') continue;
        if (input[i] == '#') {
            shape_position += (((uint128_t)128) << idx);
        }
        idx++;
    }
    return shape_position;
}

int solve() {
    clock_t startTime = clock();

    uint128_t overallMaxPosition = 0;
    uint128_t overallMaxShape = 0;
    int overallHH = 0;
    int overallWW = 0;
    int overallMax = 0;
    int HH = 0;
    int WW = 0;

    // get and print puzzle
    std::string input;
    int position_number = 0;
    while (getline(std::cin, input)) {
        // get next polyomino
        if (input == "") {
            break;
        }
        int len = input.length();
        HH = std::count(input.begin(), input.end(), '|') + 1;
        if (HH == 1) {
            WW = len;
        } else {
            WW = (int) input.find('|');
        }
        uint128_t shape_position = parse_grid(input);

        // find locations of the empty spaces
        std::vector<int> space_locations;
        for (int i=0; i<(HH*WW); i++) {
            if (getPosition(shape_position, i) == 0) {
                space_locations.push_back(i);
            }
        }
        int space_location_size = space_locations.size();

        // loop number of crates
        for (int nCrates=1; nCrates<space_location_size; nCrates++) {
            uint128_t position = (((uint128_t)1) << nCrates) - ((uint128_t)1);
            // generate all possible moves for every position?
            // for each position with this number of crates...
            while (position < (((uint128_t)1) << space_location_size)) {
                // convert position (a permutation) into a block layout
                uint128_t curPosition = 0;
                for (int i=0; i<space_location_size; i++) {
                    if (position & (((uint128_t)1) << i)) {
                        curPosition += (((uint128_t)1) << space_locations[i]);
                    }
                }

                // get next permutation
                // https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
                uint128_t t = (position | (position - 1)) + 1;
                uint128_t w = t | ((((t & -t) / (position & -position)) >> 1) - 1);
                position = w;

                // solve
                int z = mapSolve(curPosition*128, shape_position, HH, WW);
                // print maximum
                if (z > overallMax) {
                    overallMax = z;
                    double secs = double(clock() - startTime) / (double)CLOCKS_PER_SEC;
                    std::cout << "Puzzle solved in " << z << " moves (" << secs << ")\n"  << std::flush;
                    overallMaxPosition = curPosition*128+127;
                    overallMaxShape = shape_position;
                    overallHH = HH;
                    overallWW = WW;
                    printGrid(curPosition*128+127, shape_position, HH, WW);
                }
            }
        }
        if ((position_number % 100) == 0) {
            std::cout << "Done with position " << position_number << "\n";
        }
        position_number++;
    }

    // finish
    double secs = double(clock() - startTime) / (double)CLOCKS_PER_SEC;
    std::cout << "Done (" << secs << ")\n" << std::flush;
    std::cout << "Overall max moves was " << overallMax << "\n";
    printGrid(overallMaxPosition, overallMaxShape, overallHH, overallWW);

    return EXIT_SUCCESS;
}

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