19
\$\begingroup\$

Einstein wrote a riddle. He said that 98% of the world could not solve it.

I solved this riddle in about 25 minutes while on the train to work. It's basically just deduction.

The riddle

There are 5 houses in 5 different colors in a row.
In each house lives a person with a different nationality.
The 5 owners drink a certain type of beverage, smoke a certain brand of cigar, and keep a certain pet.
No owners have the same pet, smoke the same brand of cigar, or drink the same beverage.
Question: Who owns the fish?

To solve this riddle Einstein provides 15 hints:

  1. The Brit lives in the red house.
  2. The Swede keeps dogs as pets.
  3. The Dane drinks tea.
  4. The green house is on the immediate left of the white house.
  5. The green house's owner drinks coffee.
  6. The owner who smokes Pall Mall rears birds.
  7. The owner of the yellow house smokes Dunhill.
  8. The owner living in the center house drinks milk.
  9. The Norwegian lives in the first house.
  10. The owner who smokes Blends lives next to the one who keeps cats.
  11. The owner who keeps the horse lives next to the one who smokes Dunhill.
  12. The owner who smokes Bluemasters drinks beer.
  13. The German smokes Prince.
  14. The Norwegian lives next to the blue house.
  15. The owner who smokes Blends lives next to the one who drinks water.

With these hints you can come to a solution.

Your task: Make a program that will solve this riddle for you. Hard coding the solution isn't allowed (duh)

It is allowed to hardcode the hints in any format.
Example format:

//Hints in order
(Nationality:Brit)==(Color:Red)
(Nationality:Swede)==(Pet:Dogs)
(Nationality:Dane)==(Drink: Tea)
(Color:Green)/(Color:White)
(Color:Green)==(Drink:Coffee)
(Smoke:PallMall)==(Pet:Birds)
(Color:Yellow)==(Smoke:Dunhill)
(House:3)==(Drink:Milk)
(Nationality:Norwegian)==(House:1)
(Smoke:Blend)/\(Pet:Cats)

== means equals to
/ means on left side of
\ means on right side of
/\ means left or right of

Like I said its allowed to either hardcode hints or have them as input.

Output: Output should be in the following format (With the correct values, just saying for the trolls ;) )

 _____________    _____________    _____________    _____________    _____________
|   Number    |  |   Number    |  |   Number    |  |   Number    |  |   Number    |
| Nationality |  | Nationality |  | Nationality |  | Nationality |  | Nationality |
|    Color    |  |    Color    |  |    Color    |  |    Color    |  |    Color    |
|    Drink    |  |    Drink    |  |    Drink    |  |    Drink    |  |    Drink    |
|    Smoke    |  |    Smoke    |  |    Smoke    |  |    Smoke    |  |    Smoke    |
|     Pet     |  |     Pet     |  |     Pet     |  |     Pet     |  |     Pet     |
---------------  ---------------  ---------------  ---------------  ---------------

The <Nationality> in the <Color> house owns the fish!

Ascii art boxes can be changed by you, as long as they are boxes, doesn't matter what symbols you use.

Any knowledge on this riddle and solution can not be used in the program. It should use pure logic and deduction to solve the riddle.

Tagged this as a codegolf but might be a code challenge, not sure. Any thoughts on winning criteria for a code challenge feel free to share :)

For now this is code-golf so the program with the lowest bytecount wins.

Good luck and Happy coding :)

\$\endgroup\$
  • 15
    \$\begingroup\$ The claims of the first paragraph are almost certainly false. \$\endgroup\$ – Peter Taylor May 9 '14 at 11:05
  • 1
    \$\begingroup\$ @PeterTaylor What do you mean? The 98% and the einstein bit? Wouldn't know it for sure, the interwebs say it and regardless, its fun for the background :) I felt special when I solved it, "yay im in those 2%" \$\endgroup\$ – Teun Pronk May 9 '14 at 11:09
  • 4
    \$\begingroup\$ Both of those bits. The interwebs also feature the Timecube, so you would be well advised not to believe everything they say, especially when they don't adduce any evidence. \$\endgroup\$ – Peter Taylor May 9 '14 at 11:45
  • 1
    \$\begingroup\$ @PeterTaylor Yes I know, but like I also said, its fun for the background anyhow and its not like the fact, or fiction, is essential for the given problem. Also wikipedia states there is no real evidence for it :) \$\endgroup\$ – Teun Pronk May 9 '14 at 11:53
  • 3
    \$\begingroup\$ I think solutions should be able to generalize to an arbitrary number of houses, properties, and hints. Then it would be a truly interesting question which you wouldn't have to throw in "no hardcoding" as a rule. Which in my experience always leads to a question of how much it really is hardcoding. \$\endgroup\$ – Cruncher May 14 '14 at 18:24
24
\$\begingroup\$

Prolog - 954 Characters

m(A,Z):-member(A,Z).
e:-e(Z),w(Z).
e(Z):-Z=[[1,A,F,K,P,U],[2,B,G,L,Q,V],[3,C,H,M,R,W],[4,D,I,N,S,X],[5,E,J,O,T,Y]],m([_,b,r,_,_,_],Z),m([_,s,_,d,_,_],Z),m([_,d,_,_,t,_],Z),m([WH,_,w,_,_,_],Z),m([GH,_,g,_,_,_],Z),GH=:=WH-1,m([_,_,g,_,c,_],Z),m([_,_,_,b,_,p],Z),m([_,_,y,_,_,d],Z),m([3,_,_,_,m,_],Z),m([1,n,_,_,_,_],Z),m([BH,_,_,_,_,b],Z),m([CH,_,_,c,_,_],Z),(BH=:=CH+1;BH=:=CH-1),m([DH,_,_,_,_,d],Z),m([HH,_,_,h,_,_],Z),(HH=:=DH+1;HH=:=DH-1),m([_,_,_,_,b,l],Z),m([_,g,_,_,_,r],Z),m([NH,n,_,_,_,_],Z),m([YH,_,b,_,_,_],Z),(NH=:=YH+1;NH=:=YH-1),m([SH,_,_,_,_,b],Z),m([XH,_,_,_,w,_],Z),(SH=:=XH+1;SH=:=XH-1),p([n,d,b,g,s],[A,B,C,D,E]),p([y,b,r,g,w],[F,G,H,I,J]),p([c,h,b,f,d],[K,L,M,N,O]),p([w,t,m,c,b],[P,Q,R,S,T]),p([d,b,p,r,l],[U,V,W,X,Y]).
t(X,[X|R],R).
t(X,[F|R],[F|S]):-t(X,R,S).
p([W|X],Y):-p(X,V),t(W,Y,V).
p([],[]).
b:-write('+--+--+--+--+--+--+'),nl.
z(A):-writef('|%2L|%2L|%2L|%2L|%2L|%2L|',A),nl.
w([A,B,C,D,E]):-b,z(A),z(B),z(C),z(D),z(E),b.

Output

+--+--+--+--+--+--+
|1 |n |y |c |w |d |
|2 |d |b |h |t |b |
|3 |b |r |b |m |p |
|4 |g |g |f |c |r |
|5 |s |w |d |b |l |
+--+--+--+--+--+--+

Key:

  • First column is house number;
  • Second column is nationality;
  • Third column is favorite color;
  • Fourth column is pet;
  • Fifth column is drink; and
  • Sixth column is cigarette (r = prince, l = bluemaster).
\$\endgroup\$
  • 9
    \$\begingroup\$ This is the right language for the job. \$\endgroup\$ – marinus May 10 '14 at 16:48
  • \$\begingroup\$ Shouldn't you spell out the names to make the golf numbers comparable? \$\endgroup\$ – blabla999 May 17 '14 at 9:56
5
\$\begingroup\$

Ruby 322 + input 442

Brute force search of nearly 25 billion possible answers.
My computer would take about 75 days to run this program.
I never verified if this program prints a correct answer!

Run as ruby riddle.rb < riddle.in

riddle.rb (332 bytes)

g=readlines
v=g.shift(5).map &:split
c,*d=v.map{|a|[*a.permutation]}
c.product(*d){|a|(f=eval a.map{|b|b.each_with_index.map{|s,i|"#{s}=#{i}\n"}.join}.join+'g.map{|h|eval h}.all?&&fish')&&(r=['-----------']*5
puts [r,[*0..4],*a,r].map{|s|s.map{|t|'|%11s|'%t}.join},"The #{a[0][f]} in the #{a[1][f]} house owns the fish!")}

riddle.in (442 bytes)

brit dane german norwegian swede
blue green red white yellow
beer coffee milk tea water
blends bluemasters dunhill pall_mall prince
birds cats dogs fish horse
brit==red
swede==dogs
dane==tea
green==white-1
green==coffee
pall_mall==birds
yellow==dunhill
2==milk
norwegian==0
blends==cats-1||blends==cats+1
horse==dunhill-1||horse==dunhill+1
bluemasters==beer
german==prince
norwegian==blue-1||norwegian==blue+1
blends==water-1||blends==water+1

The input file must contain 5 lines of names, followed by lines of logical expressions. House numbers are 0 to 4. There must be a fish.

The program calls Array#permutation five times to find all ways to order the arrays of nationalities, colors, drinks, smokes and pets. The long loop is c.product(*d){|a|...}, calling Array#product to iterate nearly 25 billion possible answers. The loop body has the form (f=eval ...)&&(...). The eval ... part evaluates the logical expressions. If all are true, then f is the house number of the fish and the &&(...) part prints the answer. House number 0 is true in Ruby.

Code golf means not adding code for speed! But I lack 75 days to run the program!

\$\endgroup\$
  • 1
    \$\begingroup\$ Even using one or two clues instead of brute force would save lots of searching. \$\endgroup\$ – qwr May 10 '14 at 6:47
  • \$\begingroup\$ I don't know Ruby, but the Internet says that it is slow. I bet that if you translated your answer to compiled language and then optimized it even slightly, you might get close(r?) to the 5000% speedup you need to verify correctness in a reasonable amount of time. If you wrote even the crudest, but well-documented, Java translation, I would be happy to optimize it for you and then verify correctness. \$\endgroup\$ – Rainbolt May 12 '14 at 16:00
4
\$\begingroup\$

Prolog, 653 characters

a([],L,L).
a([H|T],L2,[H|L3]):-a(T,L2,L3).
m(X,L):-a(_,[X|_],L).
r(X,Y,L):-a(_,[X,Y|_],L).
n(X,Y,L):-r(X,Y,L);r(Y,X,L).
s:-s(S),w(S).
s(S):-length(S,5),m([b,r,_,_,_],S),m([s,_,_,_,d],S),m([d,_,t,_,_],S),r([_,g,_,_,_],[_,w,_,_,_],S),m([_,g,c,_,_],S),m([_,_,_,p,b],S),m([_,y,_,d,_],S),S=[_,_,[_,_,m,_,_],_,_],S=[[n,_,_,_,_],_,_,_,_],n([_,_,_,b,_],[_,_,_,_,c],S),n([_,_,_,d,_],[_,_,_,_,h],S),m([_,_,b,l,_],S),m([g,_,_,r,_],S),n([n,_,_,_,_],[_,b,_,_,_],S),n([_,_,_,b,_],[_,_,w,_,_],S),m([_,_,_,_,f],S).
b:-write('----------------+'),nl.
z(Y,A):-write(Y),writef('|%2L|%2L|%2L|%2L|%2L|',A),nl.
w([S1,S2,S3,S4,S5]):-b,z(1,S1),z(2,S2),z(3,S3),z(4,S4),z(5,S5),b.
\$\endgroup\$
  • 1
    \$\begingroup\$ I took the liberty of removing unnecessary spaces and linebreaks in your code, which gets it down to 653 characters. \$\endgroup\$ – Fatalize Jun 11 '16 at 21:10
  • 1
    \$\begingroup\$ Tested on SWI-Prolog , Just type ?- s. \$\endgroup\$ – ej8000 Jun 12 '16 at 18:29
3
\$\begingroup\$

Smalltalk 1332 chars

Using plain Smalltalk:

|n c v g p t r|n:=#(Brit Swede Dane Norwegian German
Red Green White Yellow Blue
Tea Coffee Milk Beer Water
PallMall Dunhill Blends Bluemasters Prince
Dogs Birds Cats Horses Fish).
v:=Dictionary new.n do:[:n|v at:n put:nil].g:=n splitForSize:5.
c:={{[:b :r|b==r].#Brit.#Red}.{[:s :d|s==d].#Swede.#Dogs}.{[:d :t|d==t].#Dane.#Tea}.
{[:g :w|g==(w-1)].#Green.#White}.{[:g :c|g==c].#Green.#Coffee}.
{[:p :b|p==b].#PallMall.#Birds}.{[:y :d|y==d].#Yellow.#Dunhill}.
{[:m|m==3].#Milk}.{[:n|n==1].#Norwegian}.{[:b :c|(b-c)abs==1].#Blends.#Cats}.
{[:h :d|(h-d)abs==1].#Horses.#Dunhill}.{[:m :b|m==b].#Bluemasters.#Beer}.
{[:g :p|g==p].#German.#Prince}.{[:n :b|(n-b)abs==1].#Norwegian.#Blue}.
{[:b :w|(b-w)abs==1].#Blends.#Water}}.
t:=[:c|x:=(c from:2collect:[:n|v at:n]).(x includes:nil)or:[c first valueWithArguments:x]].
p:=[|f|(((''-'',* 16),'' ''),*5)printCR.g do:[:n||w|w:=n collect:[:n|v at:n].w sortWith:n.
n do:[:n|''|''print.(n centerPaddedTo:14)print.''| ''print].''''printCR.].(((''-'',* 16),'' ''),*5)printCR.
f:=v at:#Fish.(''The %1 in the %2 house owns the fish''bindWith:(g first detect:[:n|(v at:n)==f])with:((g at:2) detect:[:n|(v at:n)==f]))printCR].
r:=[:gi|gi==0ifTrue:p ifFalse:[#(1 2 3 4 5)permutationsDo:[:perm|v declareAll:(g at:gi)from:perm.
(c conform:t)ifTrue:[r value:gi-1]].v declareAll:(g at:gi)from:#(nil),*5]].
r value:g size.

Output:

---------------- ---------------- ---------------- ---------------- ---------------- 
|  Norwegian   | |     Dane     | |     Brit     | |    German    | |    Swede     | 
|    Yellow    | |     Blue     | |     Red      | |    Green     | |    White     | 
|    Water     | |     Tea      | |     Milk     | |    Coffee    | |     Beer     | 
|   Dunhill    | |    Blends    | |   PallMall   | |    Prince    | | Bluemasters  | 
|     Cats     | |    Horses    | |    Birds     | |     Fish     | |     Dogs     | 
---------------- ---------------- ---------------- ---------------- ----------------
The German in the Green house owns the fish

As the golfed version is almost unreadable, here is the developer's code with proper names, indentation and spaces for readability:

|names constraints foundSolution v groups printSolution testC test try|

names := #(Brit Swede Dane Norwegian German
 Red Green White Yellow Blue
 Tea Coffee Milk Beer Water
 PallMall Dunhill Blends Bluemasters Prince
 Dogs Birds Cats Horses Fish).

v := Dictionary new.
names do:[:n | v at:n put:nil].
groups := names splitForSize:5.

constraints := {
        {[:b :r | b==r] . #Brit . #Red   }.          "/ The Brit lives in the red house.
        {[:s :d | s==d] . #Swede . #Dogs }.          "/ The Swede keeps dogs as pets.
        {[:d :t | d==t] . #Dane . #Tea   }.          "/ The Dane drinks tea.
        {[:g :w | g==(w-1)] . #Green . #White }.     "/ The green house is on the immediate left of the white house.
        {[:g :c | g==c] . #Green . #Coffee}.         "/ The green house's owner drinks coffee.
        {[:p :b | p==b] . #PallMall . #Birds}.       "/ The owner who smokes Pall Mall rears birds.
        {[:y :d | y==d] . #Yellow . #Dunhill}.       "/ The owner of the yellow house smokes Dunhill.
        {[:m | m==3] . #Milk}.                       "/ The owner living in the center house drinks milk.
        {[:n | n==1] . #Norwegian }.                 "/ The Norwegian lives in the first house.
        {[:b :c | (b-c)abs==1] . #Blends . #Cats}.   "/ The owner who smokes Blends lives next to the one who keeps cats.
        {[:h :d | (h-d)abs==1] . #Horses . #Dunhill}."/ The owner who keeps the horse lives next to the one who smokes Dunhill.
        {[:m :b | m==b] . #Bluemasters . #Beer}.     "/ The owner who smokes Bluemasters drinks beer.
        {[:g :p | g==p] . #German . #Prince}.        "/ The German smokes Prince.
        {[:n :b | (n-b)abs==1] . #Norwegian . #Blue}."/ The Norwegian lives next to the blue house.
        {[:b :w | (b-w)abs==1] . #Blends . #Water}.  "/ The owner who smokes Blends lives next to the one who drinks water.
}.
testC := [:c | vi:=((c from:2) collect:[:n|v at:n]). (vi includes:nil) or:[c first valueWithArguments:vi]].
test := [constraints conform:testC].

printSolution :=
 [  |f|
    ((('-',* 16),' '),*5) printCR.
    groups do:[:names|
         |values|
         values := names collect:[:nm|v at:nm].
         values sortWith:names.
         names do:[:n| '|'print. (n centerPaddedTo:14)print.'| ' print].
         '' printCR.
    ].
    ((('-',* 16),' '),*5) printCR.
    f := v at:#Fish.
    ('The %1 in the %2 house owns the fish'
        bindWith:((groups at:1) detect:[:n|(v at:n)==f])
        with:((groups at:2) detect:[:n|(v at:n)==f]))printCR
 ].


try := [:gi |
    gi == 0 
     ifTrue: printSolution
     ifFalse:[
        (1 to:5) asArray permutationsDo:[:perm |
            v declareAll:(groups at:gi) from:perm.
            test value ifTrue:[
                try value:(gi-1).
            ].
        ].
        v declareAll:(groups at:gi) from:#(nil nil nil nil nil).
    ].
].
try value:groups size.

Using a constraint solver library:

Using a constraint solver library, which is very similar to the one described in the OZ/Mozart manual. As I expect you will complain this being not valid for the contest ;-), it is added for your amusement and inspiration only (look for a contraint package in your language), ungolfed, and not counting chars.

|solution|

solution := Solver
    anySolutionFor:[
        |Brit Swede Dane Norwegian German
         Red Green White Yellow Blue
         PallMall Dunhill Prince Blends Bluemasters
         Tea Coffee Water Beer Milk
         Dogs Birds Cats Horses Fish|

        Brit        := (1 %% 5) name:#Brit.
        Swede       := (1 %% 5) name:#Swede.
        Dane        := (1 %% 5) name:#Dane.
        Norwegian   := (1 %% 5) name:#Norwegian.
        German      := (1 %% 5) name:#German.

        Red     := (1 %% 5) name:#Red.
        Green   := (1 %% 5) name:#Green.
        White   := (1 %% 5) name:#White.
        Yellow  := (1 %% 5) name:#Yellow.
        Blue    := (1 %% 5) name:#Blue.

        PallMall     := (1 %% 5) name:#PallMall.
        Dunhill      := (1 %% 5) name:#Dunhill.
        Prince       := (1 %% 5) name:#Prince.
        Blends       := (1 %% 5) name:#Blends.
        Bluemasters  := (1 %% 5) name:#Bluemasters.

        Tea    := (1 %% 5) name:#Tea.
        Coffee := (1 %% 5) name:#Coffee.
        Milk   := (1 %% 5) name:#Milk.
        Water  := (1 %% 5) name:#Water.
        Beer   := (1 %% 5) name:#Beer.

        Dogs         := (1 %% 5) name:#Dogs.
        Birds        := (1 %% 5) name:#Birds.
        Cats         := (1 %% 5) name:#Cats.
        Horses       := (1 %% 5) name:#Horses.
        Fish         := (1 %% 5) name:#Fish.

        Solver allDistinct:{ Brit . Swede . Dane . Norwegian . German. }.
        Solver allDistinct:{ Red. Green. White. Yellow. Blue. }.
        Solver allDistinct:{ PallMall. Dunhill. Prince. Blends. Bluemasters. }.
        Solver allDistinct:{ Tea. Coffee. Milk. Water. Beer }.
        Solver allDistinct:{ Dogs. Birds. Cats. Horses. Fish. }.

        Brit       =: Red.           "/ The Brit lives in the red house.
        Swede      =: Dogs.          "/ The Swede keeps dogs as pets.
        Dane       =: Tea.           "/ The Dane drinks tea.
        Green =: (White - 1).        "/ The green house is on the immediate left of the white house.
        Green =: Coffee.             "/ The green house's owner drinks coffee.
        PallMall   =: Birds.         "/ The owner who smokes Pall Mall rears birds.
        Yellow =: Dunhill.           "/ The owner of the yellow house smokes Dunhill.
        Milk =: 3.                   "/ The owner living in the center house drinks milk.
        Norwegian =: 1.              "/ The Norwegian lives in the first house.
        (Blends - Cats) abs =: 1.    "/ The owner who smokes Blends lives next to the one who keeps cats.
        (Horses - Dunhill) abs =: 1. "/ The owner who keeps the horse lives next to the one who smokes Dunhill.
        Bluemasters =: Beer.         "/ The owner who smokes Bluemasters drinks beer.
        German =: Prince.            "/ The German smokes Prince.
        (Norwegian - Blue) abs =: 1. "/ The Norwegian lives next to the blue house.
        (Blends - Water) abs =: 1.   "/ The owner who smokes Blends lives next to the one who drinks water.
    ].

solution printCR.

Notice the "=:" operator, which means "unify with". The solver uses a backtracking algorithm on the set of constraints defined in the problem block. The remaining code prints the solution into boxes:

    |pLine pSorted f |

    pLine := [ 
        (1 to:5) do:[:i | ('-' ,* 15) print] separatedBy:[' ' print].
        '' printCR.
    ].
    pSorted := [:keys |
        |items t|

        items := keys collect:[:k| solution at:k].
        t := keys copy. items values sortWith:t. 
        pLine value:(t collect:[:x | '| ',(x centerPaddedTo:11),' |']).
    ].

    pLine value.
    pSorted value:#( Brit Swede Dane Norwegian German ).
    pSorted value:#( Red Green White Yellow Blue ).
    pSorted value:#( Tea Coffee Milk Water Beer ).
    pSorted value:#( PallMall Dunhill Prince Blends Bluemasters ).
    pSorted value:#( Dogs Birds Cats Horses Fish ).
    pLine value.

    f := solution at:'Fish'.
    ('The %1 in the %2 house owns the fish!'
        bindWith:(#( Brit Swede Dane Norwegian German ) detect:[:n| (solution at:n) == f])
        with:(#( Red Green White Yellow Blue ) detect:[:n| (solution at:n) == f])
            ) printCR.

Output:

Solution(Brit->3 Swede->5 Dane->2 Norwegian->1 German->4 Red->3 Green->4
 White->5 Yellow->1 Blue->2 PallMall->3 Dunhill->1 Prince->4 Blends->2
 Bluemasters->5 Tea->2 Coffee->4 Milk->3 Water->1 Beer->5 Dogs->5 Birds->3
 Cats->1 Horses->2 Fish->4)
--------------- --------------- --------------- --------------- ---------------
|  Norwegian  | |    Dane     | |    Brit     | |   German    | |    Swede    |
|   Yellow    | |    Blue     | |     Red     | |    Green    | |    White    |
|    Water    | |     Tea     | |    Milk     | |   Coffee    | |    Beer     |
|   Dunhill   | |   Blends    | |  PallMall   | |   Prince    | | Bluemasters |
|    Cats     | |   Horses    | |    Birds    | |    Fish     | |    Dogs     |
--------------- --------------- --------------- --------------- ---------------
The German in the Green house owns the fish!

Edit: oops - I forgot to print the "who owns the fish" line in the plain version.

\$\endgroup\$
3
\$\begingroup\$

Ruby 1166 characters

Edit: Updated for correct output format

Runs consistently in under 0.2 seconds on a MBP i5.

Source: View On Github

One-liner:

def q(a);a.permutation;end;def z(a,b,c,d);l(a,b,c,d)||l(c,d,a,b);end;def l(a,b,c,d);(0..4).any?{|i|a[i]==b&&c[i+1]==d};end;def i(a,b,c,d);(0..4).any?{|i|a[i]==b&&c[i]==d};end;def t(i);['White','Yellow','Blue','Red','Green','German','Swede','Brit','Norwegian','Dane','Birds','Cats','Horses','Fish','Dogs','Beer','Water','Tea','Milk','Coffee','Blends','PallMall','Prince','Bluemasters','Dunhill'][i];end;def y(s);l=13-s.length;'|'+' '*(l/2.0).floor+s+' '*(l/2.0).ceil+'|';end;def d(s);b=[' '+(0..4).map{'_'*13}.join(' '*4)];u='  ';b<<[1,2,3,4,5].map{|i|y(i.to_s)}.join(u);s.each{|i|b<<i.map{|j|y(t(j))}.join(u)};b<<(0..4).map{'-'*15}.join(u);b<<'';z=s[4].index(13);b<<"The #{t s[0][z]} in the #{t s[1][z]} house owns the fish!";b.join "\n";end;q([0,1,2,3,4]).each{|c|l(c,4,c,0)||next;q([5,6,7,8,9]).each{|n|i(n,7,c,3)||next;n[0]==8||next;z(n,8,c,2)||next;q([10,11,12,13,14]).each{|a|i(n,6,a,14)||next;q([15,16,17,18,19]).each{|d|d[2]==18||next;i(c,4,d,19)||next;i(n,9,d,17)||next;q([20,21,22,23,24]).each{|s|z(a,12,s,24)||next;i(s,21,a,10)||next;z(s,20,d,16)||next;z(s,20,a,11)||next;i(n,5,s,22)||next;i(c,1,s,24)||next;i(s,23,d,15)||next;puts d([n,c,d,s,a]);exit}}}}}

Padded with newlines to fit the page:

def q(a);a.permutation;end;def z(a,b,c,d);l(a,b,c,d)||l(c,d,a,b);end
def l(a,b,c,d);(0..4).any?{|i|a[i]==b&&c[i+1]==d};end;def i(a,b,c,d);
(0..4).any?{|i|a[i]==b&&c[i]==d};end;def t(i);['White','Yellow','Blue',
'Red','Green','German','Swede','Brit','Norwegian','Dane','Birds',
'Cats','Horses','Fish','Dogs','Beer','Water','Tea','Milk','Coffee',
'Blends','PallMall','Prince','Bluemasters','Dunhill'][i];end;def y(s);
l=13-s.length;'|'+' '*(l/2.0).floor+s+' '*(l/2.0).ceil+'|';end;
def d(s);b=[' '+(0..4).map{'_'*13}.join(' '*4)];u='  ';
b<<[1,2,3,4,5].map{|i|y(i.to_s)}.join(u);s.each{|i|b<<i.map{|j|
y(t(j))}.join(u)};b<<(0..4).map{'-'*15}.join(u);b<<'';
z=s[4].index(13);
b<<"The #{t s[0][z]} in the #{t s[1][z]} house owns the fish!";
b.join "\n";end;q([0,1,2,3,4]).each{|c|l(c,4,c,0)||next;
q([5,6,7,8,9]).each{|n|i(n,7,c,3)||next;n[0]==8||next;z(n,8,c,2)||next;
q([10,11,12,13,14]).each{|a|i(n,6,a,14)||next;
q([15,16,17,18,19]).each{|d|d[2]==18||next;i(c,4,d,19)||next;
i(n,9,d,17)||next;q([20,21,22,23,24]).each{|s|z(a,12,s,24)||next;
i(s,21,a,10)||next;z(s,20,d,16)||next;z(s,20,a,11)||next;i(n,5,s,22)||next;
i(c,1,s,24)||next;i(s,23,d,15)||next;puts d([n,c,d,s,a]);exit}}}}}

Outputs:

 _____________    _____________    _____________    _____________    _____________
|      1      |  |      2      |  |      3      |  |      4      |  |      5      |
|  Norwegian  |  |    Dane     |  |    Brit     |  |   German    |  |    Swede    |
|   Yellow    |  |    Blue     |  |     Red     |  |    Green    |  |    White    |
|    Water    |  |     Tea     |  |    Milk     |  |   Coffee    |  |    Beer     |
|   Dunhill   |  |   Blends    |  |  PallMall   |  |   Prince    |  | Bluemasters |
|    Cats     |  |   Horses    |  |    Birds    |  |    Fish     |  |    Dogs     |
---------------  ---------------  ---------------  ---------------  ---------------

The German in the Green house owns the fish!

Ungolfed Code

@colors        = [:white, :yellow, :blue, :red, :green].shuffle.permutation
@cigars        = [:blends, :pall_mall, :prince, :bluemasters, :dunhill].shuffle.permutation
@nationalities = [:german, :swedish, :british, :norwegian, :danish,].shuffle.permutation
@drinks        = [:beer, :water, :tea, :milk, :coffee].shuffle.permutation
@pets          = [:birds, :cats, :horses, :fish, :dogs].shuffle.permutation

def next_to?(set_a, val_a, set_b, val_b)
  left_of?(set_a, val_a, set_b, val_b) ||
  left_of?(set_b, val_b, set_a, val_a)
end

def left_of?(set_a, val_a, set_b, val_b)
  (0..4).any? do |i|
    set_a[i]   == val_a &&
    set_b[i+1] == val_b
  end
end

def implies?(set_a, val_a, set_b, val_b)
  (0..4).any? do |i|
    set_a[i] == val_a &&
    set_b[i] == val_b
  end
end

def solve
  i = 0
  @colors.each do |colors|
    i += 1
    next unless left_of?(colors, :green, colors, :white)
    @nationalities.each do |nationalities|
      i += 1
      next unless implies?(nationalities, :british, colors, :red)
      next unless nationalities[0] == :norwegian
      next unless next_to?(nationalities, :norwegian, colors, :blue)
      @pets.each do |pets|
        i += 1
        next unless implies?(nationalities, :swedish, pets, :dogs) 
        @drinks.each do |drinks|
          i += 1
          next unless drinks[2] == :milk
          next unless implies?(colors, :green, drinks, :coffee)
          next unless implies?(nationalities, :danish, drinks, :tea)
          @cigars.each do |cigars|
            i += 1
            next unless next_to?(pets, :horses, cigars, :dunhill)
            next unless implies?(cigars, :pall_mall, pets, :birds)
            next unless next_to?(cigars, :blends, drinks, :water)
            next unless next_to?(cigars, :blends, pets, :cats)
            next unless implies?(nationalities , :german, cigars, :prince)
            next unless implies?(colors, :yellow, cigars, :dunhill)
            next unless implies?(cigars, :bluemasters,  drinks, :beer)
            return [colors, nationalities, pets, drinks, cigars], i
          end
        end
      end
    end
  end
end

class Symbol
  def humanize
    result = self.to_s
    result.gsub!('_', ' ')
    result.split(' ').collect{|part| part.capitalize }.join(' ')
  end
end

solution, attempts = solve

puts "\nSolved in #{attempts} attempts.\n\n"

for i in (0..4)
  number, color, nationality, cigar, drink, pet = i+1, solution[0][i], solution[1][i].humanize, solution[4][i].humanize, solution[3][i], solution[2][i]
  puts "House #{number} is #{color}. The owner is #{nationality}, smokes #{cigar}, drinks #{drink}, and keeps #{pet}."
end

puts "\n"

Outputs:

Solved in 37663 attempts.

House 1 is yellow. The owner is Norwegian, smokes Dunhill, drinks water, and keeps cats.
House 2 is blue. The owner is Danish, smokes Blends, drinks tea, and keeps horses.
House 3 is red. The owner is British, smokes Pall Mall, drinks milk, and keeps birds.
House 4 is green. The owner is German, smokes Prince, drinks coffee, and keeps fish.
House 5 is white. The owner is Swedish, smokes Bluemasters, drinks beer, and keeps dogs.

The use of shuffle in the initial setup ensures unique solution paths every time. You can see this by the number of attempts altering between runs. This mitigates the need to feed in the input separately, though altering the code to do so would be trivial.

\$\endgroup\$
  • 2
    \$\begingroup\$ The output does not match the required format. \$\endgroup\$ – Mego Nov 10 '15 at 7:32
  • \$\begingroup\$ Here at PPCG, it's not enough to have the right solution. Answers must match the specification, which includes formatting it the right way. \$\endgroup\$ – El'endia Starman Nov 10 '15 at 9:53
  • 2
    \$\begingroup\$ Ok. Original post updated with formatting code to meet the challenge spec. \$\endgroup\$ – seanh Nov 10 '15 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.