• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Warrior

[6] - Who owns the Zebra?

12 mensagens neste tópico

Este famoso puzzle foi publicado na revista Life a 17 de Dezembro, 1962. Foi atribuído várias vezes a Albert Einstein e Lewis Carroll, mas o verdadeiro autor não é conhecido.

Há várias versões, esta é a original da revista:

1. Existem 5 casas.

2. O Ingês mora na casa vermelha

3. O Espanhol tem um cão.

4. O café é bebido na casa verde.

5. O Ucraniano bebe chá.

6. A casa verde está imediatamente à direita da casa de marfim.

7. O fumador de Old Gold é dono de caracóis.

8. Kools são fumados na casa amarela.

9. Leite é bebido na casa do meio.

10. O Norueguês vive na primeira casa.

11. O homem que fuma Chesterfields vive na casa ao lado do homem com a raposa.

12. Kools são fumados na casa ao lado daquela onde o cavalo é guardado.

13. O fumador de Lucky Strike bebe sumo de laranja.

14. O Japonês fuma Parliaments.

15. O Norueguês vive ao lado da casa azul.

Em interesse da claridade, deve ser acrescentado que cada uma das 5 casas está pintada com uma cor diferente, os seus habitantes são de diferentes nacionalidades, donos de diferentes animais, bebem bebidas diferentes e fumam marcas diferentes de cigarros.

A tua tarefa é fazer um programa para resolver o puzzle e determinar: Quem bebe água? Quem é dono da zebra?

Source: http://programmingpraxis.com/2009/06/16/who-owns-the-zebra/

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Acho que vou tentar fazer em Prolog. :)

Fazes bem. Parece um excelente exercício para treinar Prolog.

Eu como sempre vou tentar em Haskell :D


Já está feito. Não está lá muito bonito, não sou grande apreciador de usar lets mas funciona bem e é praticamente instantâneo.

import Data.List
import Control.Monad

infixr 5 +++

data Casa    = Vermelha  | Azul     | Verde         | Marfim      | Amarela     deriving (Eq, Show)
data Pais    = Noruegues | Ingles   | Espanhol      | Ucraniano   | Japones     deriving (Eq, Show)
data Bebida  = Cafe      | Cha      | Leite         | Sumo        | Agua        deriving (Eq, Show)
data Cigarro = OldGold   | Kools    | Chesterfields | LuckyStrike | Parliaments deriving (Eq, Show)
data Animal  = Cao       | Caracois | Raposa        | Cavalo      | Zebra       deriving (Eq, Show)

main = mapM_ showIt solveIt

showIt = putStrLn . unlines . map unwords

solveIt = do
   paises <- permutations [ingles, Espanhol, Ucraniano, Noruegues, Japones]
   guard (Noruegues == head paises)

   bebidas <- permutations [Cafe, Cha, Leite, Sumo, Agua]
   guard (Leite == bebidas !! 2)
   guard (elemIndex Ucraniano paises == elemIndex Cha bebidas)

   casas <- permutations [Vermelha, Verde, Marfim, Amarela, Azul]
   guard ([Marfim, Verde] == (take 2 $ dropWhile (/=Marfim) casas))
   guard (elemIndex Ingles paises == elemIndex Vermelha casas)
   guard (elemIndex Cafe bebidas == elemIndex Verde casas)
   guard (Azul == casas !! 1)

   animais <- permutations [Cao, Caracois, Raposa, Cavalo, Zebra]
   guard (elemIndex Espanhol paises == elemIndex Cao animais)

   cigarros <- permutations [OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]
   guard (elemIndex OldGold cigarros == elemIndex Caracois animais)
   guard (elemIndex Kools cigarros == elemIndex Amarela casas)
   let (Just iChesterfields) = elemIndex Chesterfields cigarros
   let (Just iRaposa) = elemIndex Raposa animais
   guard (iChesterfields == (iRaposa + 1) || (iChesterfields + 1) == iRaposa)
   let (Just iKools) = elemIndex Kools cigarros
   let (Just iCavalo) = elemIndex Cavalo animais
   guard (iKools == (iCavalo + 1) || (iKools + 1) == iCavalo)
   guard (elemIndex LuckyStrike cigarros == elemIndex Sumo bebidas)
   guard (elemIndex Japones paises == elemIndex Parliaments cigarros)

   return $ transpose $ casas +++ paises +++ bebidas +++ cigarros +++ animais +++ []

(+++) :: (Show a) => [a] -> [[string]] -> [[string]]
a +++ b = (map show a) : b

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

sim eu sei, mas podem ver o exemplo que se encontra conline.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tenho um amigo meu que já fez isso em VbNet e até ficou porreiro :(

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não queria estar a "desenterrar" este tópico, mas...

Quase consegui resolver o enigma em java, aliás consegui resolve-lo mas com uma pequena "batota" (Linhas 378 a 384).

Já dei umas voltas e ainda não consegui perceber porque não consigo chegar á solução.

Deixo o código:

EinsteinsRiddle.java

Permute.java

Faço todas as permutações possíveis e guardo-as em listas separadas.

Depois percorro todas as regras para ir eliminando as possíveis soluções até que fico com 2 para as cores, 7 para as nacionalidades, 12 para os animais, 4 para as bebidas e 14 para os cigarros.

Depois só consegui a solução eliminando uma das cores e no ciclo depois uma bebida.

Se alguém me puder dar uma dica, agradecia.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O teu código é demasiado grande para eu estar a ler com atenção, mas implementaste bem todas as regras?

A tua abordagem parece-me correcta, fazer todas as permutações e depois testar se violam alguma das regras ou não.

Mas deixo aqui um conselho: isto parece-me um excelente exemplo de como não devemos escolher primeiro a linguagem e depois o problema. O problema dita SEMPRE qual a linguagem mais adequada e este é um caso claro em que uma linguagem como Prolog se sobressai de (todas as) outras. Pondera aprender a linguagem e resolver novamente este problema. Aliás, eu aprenderia a linguagem a tentar resolver este problema.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O teu código é demasiado grande para eu estar a ler com atenção, mas implementaste bem todas as regras?

A tua abordagem parece-me correcta, fazer todas as permutações e depois testar se violam alguma das regras ou não.

Verifiquei as regras e parece-me tudo bem.

Mas entretanto recomecei tudo e adoptei um estratégia diferente. Desta vez já funciona direito.

Deixo a solução:

EinsteinsRiddle2.java

Permute2.java

       _             _             _             _             _
      / \           / \           / \           / \           / \
     /   \         /   \         /   \         /   \         /   \
    /     \       /     \       /     \       /     \       /     \
   /       \     /       \     /       \     /       \     /       \
  /    1    \   /    2    \   /    3    \   /    4    \   /    5    \
/           \ /           \ /           \ /           \ /           \
-----------------------------------------------------------------------
|      AMARELA|         AZUL|     VERMELHA|       MARFIM|        VERDE|
|    NORUEGUES|    UCRANIANO|       INGLES|     ESPANHOL|      JAPONES|
|       RAPOSA|       CAVALO|     CARACOIS|          CAO|        ZEBRA|
|         AGUA|          CHA|        LEITE|         SUMO|         CAFE|
|        KOOLS|CHESTERFIELDS|      OLDGOLD|  LUCKYSTRIKE|  PARLIAMENTS|
-----------------------------------------------------------------------
Quem bebe água?
NORUEGUES
Quem é o dono da zebra?
JAPONES


Resultado numero: 1

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Deixo aqui a minha solução em Prolog:

/* casa(cor, nacionalidade, bebida, tabaco, animal) */

esquerda(X, Y, [X,Y|_]).
esquerda(X, Y, [_|R]) :- esquerda(X, Y, R).

direita(X, Y, [Y,X|_]).
direita(X, Y, [_|R]) :- direita(X, Y, R).

vizinho(X, Y, R) :-
   esquerda(X, Y, R);
   direita(X, Y, R).

corresponde(X, [X|_]).
corresponde(X, [_|R]) :- corresponde(X, R).

resolve(Casas) :-
   C1 = casa(_, noruegues, _, _, _),
   C3 = casa(_, _, leite, _, _),
   Casas = [C1, _, C3, _, _],

   corresponde(casa(vermelha, ingles, _, _, _), Casas),
   corresponde(casa(_, espanhol, _, _, cao), Casas),
   corresponde(casa(verde, _, cafe, _, _), Casas),
   corresponde(casa(_, ucraniano, cha, _, _), Casas),
   corresponde(casa(_, _, _, oldgold, caracol), Casas),
   corresponde(casa(amarela, _, _, kools, _), Casas),
   corresponde(casa(_, _, sumolaranja, luckystrike, _), Casas),
   corresponde(casa(_, japones, _, parliaments, _), Casas),
   corresponde(casa(_, _, agua, _, _), Casas),
   corresponde(casa(_, _, _, _, zebra), Casas),
   vizinho(casa(_, noruegues, _, _, _), casa(azul, _, _, _, _), Casas),
   vizinho(casa(_, _, _, chesterfields, _), casa(_, _, _, _, raposa), Casas),
   vizinho(casa(_, _, _, kools, _), casa(_, _, _, _, cavalo), Casas),
   direita(casa(verde, _, _, _, _), casa(marfim, _, _, _, _), Casas).

E o resultado:

| ?- resolve(Casas).
Casas = [casa(amarela,noruegues,agua,kools,raposa),casa(azul,ucraniano,cha,chesterfields,cavalo),casa(vermelha,ingles,leite,oldgold,caracol),casa(marfim,espanhol,sumolaranja,luckystrike,cao),casa(verde,japones,cafe,parliaments,zebra)]

Editado por jpedro20
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora