Jump to content
Warrior

[6] - Who owns the Zebra?

Recommended Posts

Warrior

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/

Share this post


Link to post
Share on other sites
Betovsky

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


"Give a man a fish and he will eat for a day; Teach a man to fish and he will eat for a lifetime. The moral? READ THE MANUAL !"

Sign on a computer system consultant's desk

Share this post


Link to post
Share on other sites
bioshock

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

Share this post


Link to post
Share on other sites
joelbrito

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.


Engenharia de Sistemas Informáticos @ IPCA

"Estou convencido de que cerca de metade do que separa os empreendedores de sucesso daqueles malsucedidos é a pura perseverança." - Steve Jobs

Share this post


Link to post
Share on other sites
Warrior

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.

Share this post


Link to post
Share on other sites
joelbrito

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


Engenharia de Sistemas Informáticos @ IPCA

"Estou convencido de que cerca de metade do que separa os empreendedores de sucesso daqueles malsucedidos é a pura perseverança." - Steve Jobs

Share this post


Link to post
Share on other sites
jpedro20

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

Edited by jpedro20

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.