Desafio de programação: resolvendo Lights Off

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

Publicado por

Elcio

Elcio é sócio fundador da Visie Padrões Web. Pioneiro no uso e divulgação dos padrões do W3C no Brasil, Elcio já treinou equipes de dezenas de empresas como Globo.com, Terra, Petrobras, iG e Locaweb. Além disso, tem dirigido as equipes da Visie no desenvolvimento de projetos web para marcas como Brastemp, Itaú Unibanco, Johnson & Johnson e Rede Globo.

17 comentários em “Desafio de programação: resolvendo Lights Off”

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

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

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

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

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

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

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

Deixe um comentário

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