A ver posts de Junho de 2015

Rabiscos

Num destes últimos fins-de-semana, em descanso por terras de onde sou natural, dei um salto ao Yours. O Yours é um bar calmo, com bastante atenção aos detalhes, onde é fácil passar-se horas a conversar (e a beber – com baldes de 5 minis, não consegues beber só uma).

Publicidades à parte, o dono deve ter uma predilecção especial por quebra-cabeças – começou por trazer-nos alguns dos mais clássicos com palitos, mas depois subiu a parada com Logicubes.


TL;DR:

Fiz um jogo. Ide jogar.


Eu não consegui encontrar grande informação sobre este jogo; o máximo que cheguei foi ao site do inventor, Ili Kaufman, onde o próprio vende uma versão do jogo, e a esta loja alemã, que vende uma versão diferente. Nenhuma destas versões é igual (nos símbolos – deduzo que a lógica subjacente seja igual) à que encontrei no Yours.

O objectivo do jogo é colocar quatro cubos em fila, em que cada lado terá quatro símbolos diferentes. Parece fácil o suficiente. Os desdobramentos dos cubos são os seguintes (as imagens foram adaptadas, mas são semelhantes):

Desdobramento logicubes

Eu e a V. ainda tentámos algumas coisas durante uns 10 minutos, mas como estava a ficar para o tarde e estas coisas entranham-se-me na cabeça, acabei por copiar o esquema dos cubos para a factura, onde até já estavam algumas contas (erradas) e um esboço do plano lógico de resolução (é a imagem que está ao topo deste post).

Uma solução puramente por força bruta estava fora de questão. Se cada cubo tiver 24 posições possíveis (cada uma das seis faces possíveis virada para a frente a multiplicar pelas quatro rotações possíveis em que pode estar sem mexer essa face), as combinações totais a testar seriam 244 = 331.776. Mesmo dividindo por 4 (porque uma determinada posição corresponde a três outras iguais, rodando toda a fila pelo seu eixo), são 82.944. Ainda que conseguíssemos verificar uma a cada dois segundos, demoraríamos um pouquinho mais que 48 horas. Pois…

Uma das coisas que topámos logo foi que havia mais símbolos do que sítios onde os pôr. Se cada cubo tem seis lados, há um total 24 faces possíveis, mas como só contam as 4 faces da fila de cubos, só há 16 posições – quer dizer que tem de se eliminar 8 posições. Essas posições correspondem aos dois topos da fila, e às faces dos cubos que ficam encostadas nas junções. Não esquecendo que cada símbolo tem que aparecer exactamente quatro vezes e contando quantas vezes aparecia cada símbolo nos cubos (bolas pretas, bolas brancas, zig-zags e escuras), foi fácil verificar quantos símbolos deveriam ser cortados:

  • p: 5 - 4 = 1
  • b: 7 - 4 = 3
  • z: 6 - 4 = 2
  • e: 6 - 4 = 2

As faces a cortar em cada cubo têm de pertencer, obviamente, ao mesmo eixo; cada cubo tem três eixos (vamos ignorar, por enquanto, se uma determinada face é cortada à esquerda ou à direita), o que vem a dar 34 = 81 combinações de corte. Supondo que muitas dessas combinações serão inválidas, isto já se aproximava de algo que pudesse ser resolvido com papel e caneta em tempo útil.

Até aqui chegámos; daqui não passámos, que a noite já ia longa – mas estas coisas ficam-me cravadas na tola e, entre as milhentas coisas que tenho para fazer, fui conseguindo roubar 10 minutinhos todas as noites para pensar no assunto.

A forma de resolver isto é com um grafo, especificamente, com uma árvore. No primeiro nível da árvore temos os três cortes possíveis do primeiro cubo, [p, z], [b, b] e [b, e]. De cada um desses vértices, partem três ramos, para os três cortes possíveis do segundo cubo ([z, e], [p, b] e [z, b]), deixando o segundo nível da árvore com 9 vértices. Logo aqui, podemos verificar que não vale a pena prosseguirmos com o ramo iniciado em [p, z] e passando por [p, b], visto que já eliminámos dois p – o que é impossível pelas condições impostas acima. É só continuar a construir a árvore nos mesmos moldes, o que daria os tais 81 vértices no quarto nível, se muitos ramos não fossem ficando pelo caminho (que ficam).

Anyway, estas coisas não se fazem à mão – pelo menos, não é à mão que um programador faz estas coisas (um programador perde 20 minutos a implementar um bash script para um problema que iria demorar 15 a resolver à mão). Mas volto a ressalvar: é perfeitamente possível resolver isto com papel e caneta. Posto isto, este sub-problema tem cinco soluções, a saber:

  • [[b, e], [z, b], [e, b], [p, z]]
  • [[b, e], [z, b], [e, z], [b, p]]
  • [[b, b], [z, e], [e, b], [p, z]]
  • [[b, b], [z, e], [e, z], [b, p]]
  • [[b, b], [z, b], [p, z], [e, e]]

Chegando a esta fase, é conveniente fazermos um ponto da situação. Temos cinco soluções. Cada cubo, em cada solução, pode ter duas posições de corte (tal como está, ou invertido). Em cada posição de corte, cada cubo pode ter 4 rotações. Por isso: 5 x 24 x 44 = 20.480. Dividindo pelas tais quatro soluções iguais em volta do eixo da fila, são 5.120. Voltando ao antigo cenário de um teste a cada dois segundos, já dá pouco menos de 3 horas.

Confesso que aqui atingi uma parede. Não consegui descortinar nenhuma solução puramente lógica para o problema. A única solução que se me afigura é mesmo um ataque de força bruta – quase 3 horas, no pior dos cenários.

Obviamente que implementei uma solução de força bruta, mas não manual, claro. Afinal, sou programador.

Incrivelmente, da forma como postulei o problema, se tivesse tentado manualmente, ia mesmo demorar as tais 3 horas – é que as soluções válidas (que é só uma com diferentes rotações) estão todas no 5º parcial anterior! É que é preciso ter sorte…

Como uma coisa leva a outra (de uma solução puramente analítica passei para a necessidade de uma visualização de grafos, depois para uma visualização em realidade virtual e finalmente já queria era mexer nos cubos), acabei por reconstruir o jogo por completo em ambiente web (because… reasons). Quem quiser, pode ir brincar com os cubos. Quando se fartarem, podem carregar na prendinha para ver a solução.

Nos próximos dias hei-de escrever dois ou três posts técnicos, porque aprendi umas coisas novas ao construir esse micro-site. Por agora, é tudo.

Comentários Nenhum comentário Continuar a ler Continuar a ler »
 Categorias
 Arquivo
 Projectos em Destaque
 Últimas Postas no Blog
 Últimos Comentários do Blog