Hashing in LexPermutationPDB for Large States is Faulty

[lior8]

The following code demonstrates that for large enough state spaces, the hash is no longer unique and when hashing a state and then trying to get it back from the PDB results in faulty states.

#include "PancakePuzzle.h"
#include "LexPermutationPDB.h"
#include <iostream>

int main(int argc, char *argv[]) {
    const int numPancakes = 30;
    PancakePuzzleState<numPancakes> state;
    PancakePuzzle<numPancakes> env;
    std::vector<int> bucketPattern;
    std::vector<int> dataPattern;
    for (int i = 0; i < numPancakes; i++) {
        if (i % 2 != 0) {
            dataPattern.push_back(i);
        } else {
            bucketPattern.push_back(i);
        }
    }

    srandom(0);
    for (int x = 0; x < numPancakes; x++) {
        std::swap(state.puzzle[x], state.puzzle[x + random() % (numPancakes - x)]);
    }

    LexPermutationPDB<PancakePuzzleState<numPancakes>, PancakePuzzleAction, PancakePuzzle<numPancakes>> bucketPdb(&env,  state, bucketPattern);
    LexPermutationPDB<PancakePuzzleState<numPancakes>, PancakePuzzleAction, PancakePuzzle<numPancakes>> dataPdb(&env, state, dataPattern);

    uint64_t bucketHash = bucketPdb.GetPDBHash(state);
    uint64_t dataHash = bucketPdb.GetPDBHash(state);

    PancakePuzzleState<numPancakes> dataState;
    PancakePuzzleState<numPancakes> bucketstate;
    bucketPdb.GetStateFromPDBHash(bucketHash, bucketstate);
    dataPdb.GetStateFromPDBHash(dataHash, dataState);
    std::cout << "State: " << state << std::endl;
    std::cout << "Bucket State: " << bucketstate << std::endl;
    std::cout << "Data State: " << dataState << std::endl;
}

Which gives the following output:

State: 13 10 11 28 5 15 16 8 2 19 12 20 26 4 17 6 1 27 22 9 21 29 7 25 0 23 3 24 18 14 
Bucket State: -1 8 0 -1 12 28 16 -1 -1 -1 -1 -1 -1 -1 2 4 -1 -1 -1 -1 18 22 14 26 10 24 20 -1 6 -1
Data State: -1 9 1 -1 13 29 17 -1 -1 -1 -1 -1 -1 -1 3 5 -1 -1 -1 -1 19 23 15 27 11 25 21 -1 7 -1