Mind blowing Puzzle Game!

The other day I was having a drink in the usual café and realized that the owner had put some mind games for the customers to experiment. Games such as the classic Rubik’s Cube and other puzzle games.

Most of the games were quite easy to solve, usually taking about 5 minutes. There was one though that blew my mind away. I spent more than 40 minutes trying out different approaches and none of them seem to get me anywhere else than frustration.

The game consisted in 13 pieces, that look like Tetris pieces, that one had to combine in order to and fit them inside a small squared board (8x8 individual positions).

Since I wasn’t going anywhere with the manual approach I thought:
- I’ll outsmart you, you little bastard, I make a program to solve you! And so, I copied the pieces onto a paper napkin and left home to program the solution (at 2 AM).

First I thought, this is a typical genetic algorithm (GA) kind of problem but I had no good GA libraries at hand, so I decided to do a full combinational approach, brute force that is. Trying all the possible combinations of all the pieces in all positions, in all possible rotations, and mirrored, adding up 13*4*2*8*8 = 6656 distinct pieces.

How wrong was I! The software takes roughly millions of years to compute all the solutions. We’re talking about 13^6656 possible combinations. It’s just too much, so I begun optimizing. I started by removing the pieces that were repeated due to equivalent rotations or mirroring, reducing the number of pieces to 2285. Then I created some methods to evaluate the viability of reaching a solution right after inserting each piece. This means that after inserting a piece on the board the algorithm tests if there are any holes on the board that will never be filled because they’re too small to fit any left over piece this way eliminating unnecessary tests.

Even so, the algorithm takes too much time to calculate a single solution (I’m interested in getting all the possible solutions). I can’t predict how much time it will take, since the combination cutting routine makes it very hard to compute how many interactions I have eliminated.

What I want from you is some suggestions on how to reach a solution in useful time (let’s say 24 hours). I'm sure it would be possible. We have reached the moon for god sake!

All the 13 puzzle pieces:







Due to lack of time I still havent finished the programs. The algorithms I have implemented are almost done, but some tiny bug is stopping the algorithms to reach a solution. Feel free to experiment. A graphical board with animation is included.

• Recursive Implementation
• Genetic Algorithms Implementation

Good luck.

Cheers.

Non-trivial SQL problem...

Recentemente, deparei-me com um problema que, embora pareça trivial, a sua solução é tudo menos directa.
Imaginemos uma tabela de uma BD onde se encontram registados os items que cada utilizador de um site de comercio electrónico comprou ao longo do tempo.

eperson_id, item_id
-----------------------
1 1
1 2
2 1
3 1
3 2
3 3

A questão é tão simples como:
- Que utilizadores compraram o item 1 e 2?
Ou seja, imaginemos que todas as compras de um utilizador podem ser representadas por um cabaz. Eu quero saber que utilizadores possuem ambos os items (1 e 2) no seu cabaz (obviamente poderiam existir outros dentro do cabaz).

Para o exemplo apresentado a resposta seria:

eperson_id
----------------
1
3

Entrentanto já arranjei uma solução para o problema, mas não estou muito satisfeito, pois exige a realização de N+1 subqueries, sendo N o número de items a encontrar no cabaz.
Se conseguirem arranjar uma solução optimizada para este problema, agradecia que me enviassem o SQL correspondente.

Obrigado.

Solving Geek Problems is now open...

This weblog was created to solve your daily geek problems. Anyone is free to post a geek question as everone is invited to come up with an answer.

PS: can't rememeber anything else to say!