Desafio de programação: resolvendo Lights Off

By On · 16 Comments · In Sem categoria

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 ;-) )

Posts Relacionados

Tagged with: • • • • • •  
Share →

  • Pingback: Tropeçando 23 | Rafael Bernard Araujo

  • http://www.taiar.com.br 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´?

  • http://dnunes.com 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.

  • http://www.gratuidade.com/ 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.

  • http://www.taiar.com.br André Taiar

    Viva!! :D 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.

  • http://elcio.com.br 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.

  • http://ferrari.eti.br 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…

  • http://elcio.com.br 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ê.

  • http://www.taiar.com.br/ André Taiar

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

  • http://www.taiar.com.br/ 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.

  • 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

  • http://elcio.com.br 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.

  • http://ferrari.eti.br 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!…

  • http://elcio.com.br 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 ;-)

  • http://www.taiar.com.br 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!!!

  • Pingback: Twitter Trackbacks for fechaTag - Desafio de programação: resolvendo Lights Off [elcio.com.br] on Topsy.com