Fiz essa versão do clássico joguinho Lights Off:
O jogo é simples, e o objetivo é apenas apagar todas as luzes. Por curiosidade, fiz também o algoritmo que resolve o jogo:
O desafio está lançado. O primeiro que colocar nos comentários a URL de uma página com um botão “solve” como o meu ganha uma entrada para o Codeshow. Importante:
- Vale o primeiro comentário. Mesmo que você comente de madrugada e eu demore a moderar, ganha quem comentar primeiro.
- O solucionador tem que ser escrito em Javascript. Você pode copiar minha versão do jogo e desenvolver em cima dela.
- Não pode resolver na base da tentativa e erro. Tem que ser uma boa solução, que resolva qualquer estado do tabuleiro em 20 passos ou menos.
Divirtam-se!
(O pessoal da Visie, se quiser participar, pode. Só não vai ganhar nada 
)
Posts Relacionados
Se você gostou, compartilhe.
[...] fechaTag – Desafio de programação: resolvendo Lights Off [...]
“. . A idéia do pré-processamento e “tentativa e erro” me soa brute force demais.”
A solução não tem nada de “tentativa e erro”, muito pelo contrário: é uma heurística com um pequeno princípio de programação dinâmica.
A solução dele também tem um graaande e elegante princípio de programação dinâmica, porém, não é nada eficiente, uma vez que precisamos calcular um sistema linear e o resultado de 25 equações lineares pelo método de Gauss (que é O(n³) para o pior caso). Não é tentativa e erro mas não é nada eficiente computacionalmente.
O que seria uma matriz mais `séria´?
. . A idéia do pré-processamento e “tentativa e erro” me soa brute force demais. Idealmente a gente teria uma matriz mais séria de resolução pra não precisar da passagem dupla pelo algoritmo de redução.
. . Um cara com muito tempo livre fez isso: http://aix1.uottawa.ca/~jkhoury/gamesolution.htm
. . Loucura. Eu ficaria com essa solução mais simples, apesar de tecnicamente nem sempre ser a solução mínima.
Agora com tudo resolvido parece tão fácil. Mesmo que não tivesse prêmio valeu este post. Gastei meu tico e teco aqui por um tempo.
Viva!!
Gostei do desenvolvimento em equipe, hehehe! Muito obrigado, Carlos, pela ajuda, estudarei direito a sua forma de animar e mostrar a solução passo a passo!
Muito obrigado, Élcio, pela oportunidade! Estou no aguardo do contato.
Resolvido, desafio solucionado, e o prêmio é do André!
André, amanhã alguém aqui vai te procurar para acertar os detalhes.
Parabéns a todos.
Como eu sou malvado, dei um merge da minha ideia com a solução perfeita do André Taiar..!
http://ferrari.eti.br/elcio/desafio2.htm
Bom, se tudo estiver ok agora @elcio, por favor, dê o prêmio ao André Taiar ai, afinal, a solução perfeita foi ele que encontrou.. eu só fiz o negocio ficar animado.
Abração a todos e tenham um excelente codeshow!…
ps. o @Elcio apelou nesse desafio…
Adriano, não consegui ver a diferença. Para mim, parece que o jogo que você indicou está funcionando igualzinho ao meu…
André, pega o código do Carlos como referência (ele não vai poder vir ao Codeshow mesmo…) Tendo chegado onde você chegou, vai ser muito chato se alguém resolver isso antes de você.
Tô precisando de um curso de DOM + Javascript + DHTML da Visie, num tô??
Consegui fazer uma versão otimizada que pré-processa a matriz antes de começar a iterar sobre ela.
Em todos os meus testes, não passaram de 15 passos para resolver!
http://taiar.com.br/lightsoff/
Porém, continua sem animação… Pesquisei pra tentar fazer isso mas não consegui.
Seus cantos “baixo/esquerdo” e “cima/direito” estão com bug na lógica ou regra diferente da que eu conheço, pois eles não apagam quando clico em cima.
neste site eu clico e altera a cor normal.
http://www.owensworld.com/flashgames/play-152.htm
Agora estamos mais perto de uma boa ressposta! Carlos e André, a solução de vocês resolve alguns casos em bem mais de 20 movimentos. Por exemplo, o tabuleiro cheio é resolvido em 25 lances. E esse tabuleiro:
XXXXX
XXXXX
XXXXX
_XXX_
_XXX_
É resolvido em 26.
Ainda não valeu o prêmio, mas estamos progredindo.
Olá, como me deparei com o problema soh bem tarde, ficou pronto agora… 2am ><..
a solução está longe de ser a mais elegante mas funciona muito bem… eu uso uma solução similar a solução do André, porém, eu gravo os movimentos e executo animando depois.
http://ferrari.eti.br/elcio/desafio.htm
se ninguém mandou antes de mim e esta solução for válida… infelizmente eu não poderei ir ao Codeshow =/ então fica a seu critério… eu fiz só pelo desafio
abraço!…
André,
Se a visualização interativa, é difícil demonstrar que sue algoritmo realmente funciona e não está apenas marcando tudo como apagado.
Não valeu. Mas está quase
http://taiar.com.br/lightsoff/
Consegui uma solução e o resultado sai quase sempre com menos de 20 passos.
Por falta de conhecimentos melhores em Javascript, não consegui fazer uma visualização iterativa da coisa, porém, ao final da execução, é exibido um contador de passos.
Deu certinho!
(yn)
Abração, Élcio!!!
[...] fechaTag – Desafio de programação: resolvendo Lights Off blog.elcio.com.br/desafio-de-programacao-resolvendo-lights-off – view page – cached Fiz essa versão do clássico joguinho Lights Off: O jogo é simples, e o objetivo é apenas apagar todas as luzes. Por curiosidade, fiz também o algoritmo que resolve o jogo: … Filter tweets [...]