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:

  1. Vale o primeiro comentário. Mesmo que você comente de madrugada e eu demore a moderar, ganha quem comentar primeiro.
  2. O solucionador tem que ser escrito em Javascript. Você pode copiar minha versão do jogo e desenvolver em cima dela.
  3. 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 ;-))


17 respostas para “Desafio de programação: resolvendo Lights Off”

  1. […] fechaTag – Desafio de programação: resolvendo Lights Off […]

  2. […] fechaTag – Desafio de programação: resolvendo Lights Off […]

  3. Avatar de André Taiar

    “. . 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´?

  4. Avatar de diego nunes

    . . 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.

  5. Avatar de Gratuidade

    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.

  6. Avatar de André Taiar

    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.

  7. Avatar de Elcio

    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.

  8. Avatar de Carlos André Ferrari

    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…

  9. Avatar de Elcio

    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ê.

  10. Avatar de André Taiar

    Tô precisando de um curso de DOM + Javascript + DHTML da Visie, num tô?? 😀

  11. Avatar de André Taiar

    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.

  12. Avatar de Adriano Machado
    Adriano Machado

    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

  13. Avatar de Elcio

    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.

  14. Avatar de Carlos André Ferrari

    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!…

  15. Avatar de Elcio

    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 😉

  16. Avatar de André Taiar

    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!!!

  17. […] 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 […]

Deixe um comentário

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *