Solução Pilha de Dados

Solução por Rogério Júnior

Para ver o problema original, clique aqui.

O problema é uma função recursiva muito simples. O estado da recursão será a posição do dado da pilha que estamos olhando (onde o topo é 1) e e qual a face dele que está virada para cima ($$solve(pos,cima)$$), e ela retornará o maior valor de um lado da sub-pilha formada por este dados e os abaixo dele. Sabendo a face de cima de um dado, sabemos qual a de baixo pelo desenho. Chamaremos faces A, B, …, F de faces 1, 2, …, 6, onde $$dado[pos][i]$$ guarda qual o número da face $$i$$ no dado na posição $$pos$$.

Para um estado, percorreremos todas as faces que não são topo ou cima e usaremos a melhor para o lado da pilha que terá valor máximo. Chamaremos este valor de $$bestface$$. Se o dado olhado for o último, retornamos $$bestface$$. Olharemos o próximo dado, procurando qual de duas faces tem o mesmo valor da face de baixo do dado $$pos$$ (seja ela $$new_cima$$), e chamaremos a recursão agora com esta sendo a face de cima ($$solve(pos+1,new_cima)$$).

No final, chamamos a recursão para cada uma das possíveis faces de cima do primeiro dado. Note que a melhor resposta da recursão para o primeiro dado soluciona o problema. Segue o código para melhor entendimento:

https://gist.github.com/rogerioagjr/301f78edc160528badc45c69ca168570