Representar tabuleiro como um número

[leonaascimento]

Interpretando o tabuleiro como um vetor e transformando-o em um número de base 3 eu posso tranformá-lo em um número inteiro para tabuleiros suficientemente pequenos.

Faça @ ou + (sokoban) valer 2, $ ou * (caixa) valer 1 e o resto 0.

Para o level_00 eu tenho uma matriz 8x7, um vetor de 56 posições. Se meu sokoban está no final do tabuleiro minha representação em inteiro será perto de 7*10¹⁶, e ainda funciona. Mas, se a matriz for 8x8, a representação será perto de ULLONG_MAX. Para matrizes maiores, já era.

Se eu passar a representar o número como um array de inteiros, eu perco o "hash dado". Essa ideia parece pior do que usar char* para a representação.

Alguém interpretou a ideia do @francesquini diferente?

[francesquini]

Olá @leonaascimento,

Lembre-se também que falei sobre "dobrar" o número se ele ficar grande demais.

Para o seu exemplo de uma matriz 8x8. Teríamos 64 casas. Cada uma sendo um número base 3 então teríamos no total um número máximo de 3^64 = 3433683820292512484657849089281 que ocuparia teto(log2 3433683820292512484657849089281) bits ou 102 bits. Isso é maior do que o maior inteiro para grande parte das máquinas.

Vamos assumir que a máquina possua inteiros de 64 bits. Neste caso seriam necessários 2 deles (a e b) para representar todos os estados do tabuleiro. Para calcular um hash de 32 bits você poderia fazer algo nessa linha:

uint64_t a, b, c;
uint32_t d;
....
....

//Combina a e b
c = a ^ b;

/* pega os bits baixos (isso depende do compilador). 
    Outra opção mais portável: 
    d = (uint32_t)(c - ((c >> 32) << 32));
/*
d = (uint32_t)c; 

//Combina os bits altos de c com os bits baixos
d ^= (c >> 32); //combina com os bits baixos

d é o seu hash de 32 bits. Basta adaptar a ideia caso queira tamanhos diferentes de hash.