#include <unordered_set>
#include <iostream>
#define MAX_LEN 18
unsigned long long prime_hash(const unsigned int *arr, size_t len)
{
/* first 2 * MAX_LEN primes */
static const unsigned long long p[2 * MAX_LEN] = {
2, 3, 5, 7, 11, 13, 17, 19, 23,
29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97, 101, 103,
107, 109, 113, 127, 131, 137, 139, 149, 151
};
unsigned long long h = 1;
for (size_t i = 0; i < len; i++)
h *= p[2 * i] * (arr[i] ? p[2 * i + 1] : 1);
return h;
}
unsigned long long ternary_hash(const unsigned int *arr, size_t len)
{
static const unsigned long long p3[MAX_LEN] = {
1, 3, 9, 27,
81, 243, 729, 2187,
6561, 19683, 59049, 177147,
531441, 1594323, 4782969, 14348907,
43046721, 129140163
};
unsigned long long h = 0;
for (size_t i = 0; i < len; i++)
if (arr[i])
h += p3[i];
for (size_t i = len; i < MAX_LEN; i++)
h += 2 * p3[i];
return h;
}
void int2barr(unsigned int *dst, unsigned long long n, size_t len)
{
for (size_t i = 0; i < len; i++) {
dst[i] = n & 1;
n >>= 1;
}
}
int main()
{
std::unordered_set<unsigned long long> phashes, thashes;
/* generate all possible bool-arrays from length 0 to length 18 */
/* first, we checksum the only 0-element array */
phashes.insert(prime_hash(NULL, 0));
thashes.insert(ternary_hash(NULL, 0));
/* then we checksum the arrays of length 1...18 */
for (size_t len = 1; len <= MAX_LEN; len++) {
unsigned int bits[len];
for (unsigned long long i = 0; i < (1 << len); i++) {
int2barr(bits, i, len);
phashes.insert(prime_hash(bits, len));
thashes.insert(ternary_hash(bits, len));
}
}
std::cout << "prime hashes: " << phashes.size() << std::endl;
std::cout << "ternary hashes: " << thashes.size() << std::endl;
return 0;
}
I2luY2x1ZGUgPHVub3JkZXJlZF9zZXQ+CiNpbmNsdWRlIDxpb3N0cmVhbT4KCiNkZWZpbmUgTUFYX0xFTiAxOAoKdW5zaWduZWQgbG9uZyBsb25nIHByaW1lX2hhc2goY29uc3QgdW5zaWduZWQgaW50ICphcnIsIHNpemVfdCBsZW4pCnsKICAgIC8qIGZpcnN0IDIgKiBNQVhfTEVOIHByaW1lcyAqLwoJc3RhdGljIGNvbnN0IHVuc2lnbmVkIGxvbmcgbG9uZyBwWzIgKiBNQVhfTEVOXSA9IHsgCgkJICAyLCAgIDMsICAgNSwgICA3LCAgMTEsICAxMywgIDE3LCAgMTksICAyMywKCQkgMjksICAzMSwgIDM3LCAgNDEsICA0MywgIDQ3LCAgNTMsICA1OSwgIDYxLAoJCSA2NywgIDcxLCAgNzMsICA3OSwgIDgzLCAgODksICA5NywgMTAxLCAxMDMsCgkJMTA3LCAxMDksIDExMywgMTI3LCAxMzEsIDEzNywgMTM5LCAxNDksIDE1MQoJfTsKCgl1bnNpZ25lZCBsb25nIGxvbmcgaCA9IDE7Cglmb3IgKHNpemVfdCBpID0gMDsgaSA8IGxlbjsgaSsrKQoJCWggKj0gcFsyICogaV0gKiAoYXJyW2ldID8gcFsyICogaSArIDFdIDogMSk7CgoJcmV0dXJuIGg7Cn0KCnVuc2lnbmVkIGxvbmcgbG9uZyB0ZXJuYXJ5X2hhc2goY29uc3QgdW5zaWduZWQgaW50ICphcnIsIHNpemVfdCBsZW4pCnsKCXN0YXRpYyBjb25zdCB1bnNpZ25lZCBsb25nIGxvbmcgcDNbTUFYX0xFTl0gPSB7CgkJICAgICAgIDEsICAgICAgICAgICAgMywgICAgICAgICAgICA5LCAgICAgICAgICAgMjcsCgkJICAgICAgODEsICAgICAgICAgIDI0MywgICAgICAgICAgNzI5LCAgICAgICAgIDIxODcsICAgICAgICAgCgkJICAgIDY1NjEsICAgICAgICAxOTY4MywgICAgICAgIDU5MDQ5LCAgICAgICAxNzcxNDcsCgkJICA1MzE0NDEsICAgICAgMTU5NDMyMywgICAgICA0NzgyOTY5LCAgICAgMTQzNDg5MDcsCgkJNDMwNDY3MjEsICAgIDEyOTE0MDE2MwoJfTsKCgl1bnNpZ25lZCBsb25nIGxvbmcgaCA9IDA7Cglmb3IgKHNpemVfdCBpID0gMDsgaSA8IGxlbjsgaSsrKQoJCWlmIChhcnJbaV0pCgkJCWggKz0gcDNbaV07CgoJZm9yIChzaXplX3QgaSA9IGxlbjsgaSA8IE1BWF9MRU47IGkrKykKCQloICs9IDIgKiBwM1tpXTsKCglyZXR1cm4gaDsKfQoKdm9pZCBpbnQyYmFycih1bnNpZ25lZCBpbnQgKmRzdCwgdW5zaWduZWQgbG9uZyBsb25nIG4sIHNpemVfdCBsZW4pCnsKCWZvciAoc2l6ZV90IGkgPSAwOyBpIDwgbGVuOyBpKyspIHsKCQlkc3RbaV0gPSBuICYgMTsKCQluID4+PSAxOwoJfQp9CgppbnQgbWFpbigpCnsKCXN0ZDo6dW5vcmRlcmVkX3NldDx1bnNpZ25lZCBsb25nIGxvbmc+IHBoYXNoZXMsIHRoYXNoZXM7CgoKCS8qIGdlbmVyYXRlIGFsbCBwb3NzaWJsZSBib29sLWFycmF5cyBmcm9tIGxlbmd0aCAwIHRvIGxlbmd0aCAxOCAqLwoKCS8qIGZpcnN0LCB3ZSBjaGVja3N1bSB0aGUgb25seSAwLWVsZW1lbnQgYXJyYXkgKi8KCXBoYXNoZXMuaW5zZXJ0KHByaW1lX2hhc2goTlVMTCwgMCkpOwoJdGhhc2hlcy5pbnNlcnQodGVybmFyeV9oYXNoKE5VTEwsIDApKTsKCgkvKiB0aGVuIHdlIGNoZWNrc3VtIHRoZSBhcnJheXMgb2YgbGVuZ3RoIDEuLi4xOCAqLwoJZm9yIChzaXplX3QgbGVuID0gMTsgbGVuIDw9IE1BWF9MRU47IGxlbisrKSB7CgkJdW5zaWduZWQgaW50IGJpdHNbbGVuXTsKCQlmb3IgKHVuc2lnbmVkIGxvbmcgbG9uZyBpID0gMDsgaSA8ICgxIDw8IGxlbik7IGkrKykgewoJCQlpbnQyYmFycihiaXRzLCBpLCBsZW4pOwoKCQkJcGhhc2hlcy5pbnNlcnQocHJpbWVfaGFzaChiaXRzLCBsZW4pKTsKCQkJdGhhc2hlcy5pbnNlcnQodGVybmFyeV9oYXNoKGJpdHMsIGxlbikpOwoJCX0KCX0KCglzdGQ6OmNvdXQgPDwgInByaW1lIGhhc2hlczogIiA8PCBwaGFzaGVzLnNpemUoKSA8PCBzdGQ6OmVuZGw7CglzdGQ6OmNvdXQgPDwgInRlcm5hcnkgaGFzaGVzOiAiIDw8IHRoYXNoZXMuc2l6ZSgpIDw8IHN0ZDo6ZW5kbDsKCglyZXR1cm4gMDsKfQo=