Geeks and computers in the movies
Hi,
These are three funny articles about geeks, computers and code in the movies.
Top 20 Hackers in Film History
Servers in the Movies - Our Top Ten
What code DOESN'T do in real life (that it does in the movies)
Hi,
These are three funny articles about geeks, computers and code in the movies.
Top 20 Hackers in Film History
Servers in the Movies - Our Top Ten
What code DOESN'T do in real life (that it does in the movies)
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.
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).
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.
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.
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!