Zebra puzzle: Difference between revisions
Content deleted Content added
No edit summary |
Added Uiua solution |
||
(21 intermediate revisions by 9 users not shown) | |||
Line 15:
:# The green house is immediately to the left of the white house.
:# They drink coffee in the green house.
:# The man who smokes Pall Mall has
:# In the yellow house they smoke Dunhill.
:# In the middle house they drink milk.
:# The Norwegian lives in the first house.
:# The
:# In a house next to the house
:# The man who smokes Blue Master drinks beer.
:# The German smokes Prince.
Line 26:
:# They drink water in a house next to the house where they smoke Blend.
<br>The question is, who owns the zebra? For clarity, each of the five houses is painted a different color, and their inhabitants are of different nationalities, own different pets, drink different beverages and smoke different brands of cigarettes.
Additionally, list the solution for all the houses.
Line 39:
=={{header|Ada}}==
Not the prettiest Ada, but it's simple and very fast. Similar to my Dinesman's code; uses enums to keep things readable.
<
procedure Zebra is
type Content is (Beer, Coffee, Milk, Tea, Water,
Line 144:
end loop; end loop;
Solve (myAlley, 0, 5); -- start at test 0 with 5 options
end Zebra;</
{{out}}
<pre>ONE: DRINK=WATER PERSON=NORWEGIAN COLOR=YELLOW SMOKE=DUNHILL PET=CAT
Line 154:
=={{header|ALGOL 68}}==
Attempts to find solutions using the rules.
<
# attempt to solve Einstein's Riddle - the Zebra puzzle #
INT unknown = 0, same = -1;
Line 294:
print( ( "solutions: ", whole( solutions, 0 ), newline ) )
END
</syntaxhighlight>
{{out}}
<pre>
Line 305:
solutions: 1
</pre>
=={{header|AppleScript}}==
<syntaxhighlight lang="applescript">on zebraPuzzle()
-- From statement 10, the Norwegian lives in the first house,
-- so from statement 15, the blue house must be the second one.
-- From these and statements 5, 6, and 9, the green and white houses can only be the 4th & 5th,
-- and the Englishman's red house (statement 2) must be the middle one, where (9) they drink
-- milk. This only leaves the first house to claim the yellow colour and the Dunhill smokers
-- (statement 8), which means the second house must have the the horse (statement 12).
-- Initialise the house data accordingly.
set mv to missing value
set streetTemplate to {¬
{resident:"Norwegian", colour:"yellow", pet:mv, drink:mv, smoke:"Dunhill"}, ¬
{resident:mv, colour:"blue", pet:"horse", drink:mv, smoke:mv}, ¬
{resident:"Englishman", colour:"red", pet:mv, drink:"milk", smoke:mv}, ¬
{resident:mv, colour:"green", pet:mv, drink:"coffee", smoke:mv}, ¬
{resident:mv, colour:"white", pet:mv, drink:mv, smoke:mv} ¬
}
-- Test all permutations of the remaining values.
set solutions to {}
set drinkPermutations to {{"beer", "water"}, {"water", "beer"}}
set residentPermutations to {{"Swede", "Dane", "German"}, {"Swede", "German", "Dane"}, ¬
{"Dane", "German", "Swede"}, {"Dane", "Swede", "German"}, ¬
{"German", "Swede", "Dane"}, {"German", "Dane", "Swede"}}
set petPermutations to {{"birds", "cats", "ZEBRA"}, {"birds", "ZEBRA", "cats"}, ¬
{"cats", "ZEBRA", "birds"}, {"cats", "birds", "ZEBRA"}, ¬
{"ZEBRA", "birds", "cats"}, {"ZEBRA", "cats", "birds"}}
set smokePermutations to {{"Pall Mall", "Blend", "Blue Master"}, {"Pall Mall", "Blue Master", "Blend"}, ¬
{"Blend", "Blue Master", "Pall Mall"}, {"Blend", "Pall Mall", "Blue Master"}, ¬
{"Blue Master", "Pall Mall", "Blend"}, {"Blue Master", "Blend", "Pall Mall"}}
repeat with residentPerm in residentPermutations
-- Properties associated with resident.
copy streetTemplate to sTemplate2
set {r, OK} to {0, true}
repeat with h in {2, 4, 5} -- House numbers with unknown residents.
set thisHouse to sTemplate2's item h
set r to r + 1
set thisResident to residentPerm's item r
if (thisResident is "Swede") then
if (thisHouse's pet is not mv) then
set OK to false
exit repeat
end if
set thisHouse's pet to "dog"
else if (thisResident is "Dane") then
if (thisHouse's drink is not mv) then
set OK to false
exit repeat
end if
set thisHouse's drink to "tea"
else
set thisHouse's smoke to "Prince"
end if
set thisHouse's resident to thisResident
end repeat
-- Properties associated with cigarette brand.
if (OK) then
repeat with smokePerm in smokePermutations
-- Fit in this permutation of smokes.
copy sTemplate2 to sTemplate3
set s to 0
repeat with thisHouse in sTemplate3
if (thisHouse's smoke is mv) then
set s to s + 1
set thisHouse's smoke to smokePerm's item s
end if
end repeat
repeat with drinkPerm in drinkPermutations
-- Try to fit this permutation of drinks.
copy sTemplate3 to sTemplate4
set {d, OK} to {0, true}
repeat with h from 1 to 5
set thisHouse to sTemplate4's item h
if (thisHouse's drink is mv) then
set d to d + 1
set thisDrink to drinkPerm's item d
if (((thisDrink is "beer") and (thisHouse's smoke is not "Blue Master")) or ¬
((thisDrink is "water") and not ¬
(((h > 1) and (sTemplate4's item (h - 1)'s smoke is "Blend")) or ¬
((h < 5) and (sTemplate4's item (h + 1)'s smoke is "Blend"))))) then
set OK to false
exit repeat
end if
set thisHouse's drink to thisDrink
end if
end repeat
if (OK) then
repeat with petPerm in petPermutations
-- Try to fit this permutation of pets.
copy sTemplate4 to sTemplate5
set {p, OK} to {0, true}
repeat with h from 1 to 5
set thisHouse to sTemplate5's item h
if (thisHouse's pet is mv) then
set p to p + 1
set thisPet to petPerm's item p
if ((thisPet is "birds") and (thisHouse's smoke is not "Pall Mall")) or ¬
((thisPet is "cats") and not ¬
(((h > 1) and (sTemplate5's item (h - 1)'s smoke is "Blend")) or ¬
((h < 5) and (sTemplate5's item (h + 1)'s smoke is "Blend")))) then
set OK to false
exit repeat
end if
set thisHouse's pet to thisPet
end if
end repeat
if (OK) then set end of solutions to sTemplate5
end repeat
end if
end repeat
end repeat
end if
end repeat
set solutionCount to (count solutions)
set owners to {}
repeat with thisSolution in solutions
repeat with thisHouse in thisSolution
if (thisHouse's pet is "zebra") then
set owners's end to thisHouse's resident
exit repeat
end if
end repeat
end repeat
return {zebraOwners:owners, numberOfSolutions:solutionCount, solutions:solutions}
end zebraPuzzle
zebraPuzzle()</syntaxhighlight>
{{output}}
<syntaxhighlight lang="applescript">{zebraOwners:{"German"}, numberOfSolutions:1, solutions:{{{resident:"Norwegian", colour:"yellow", pet:"cats", drink:"water", smoke:"Dunhill"}, {resident:"Dane", colour:"blue", pet:"horse", drink:"tea", smoke:"Blend"}, {resident:"Englishman", colour:"red", pet:"birds", drink:"milk", smoke:"Pall Mall"}, {resident:"German", colour:"green", pet:"ZEBRA", drink:"coffee", smoke:"Prince"}, {resident:"Swede", colour:"white", pet:"dog", drink:"beer", smoke:"Blue Master"}}}}</syntaxhighlight>
=={{header|AutoHotkey}}==
Line 311 ⟶ 443:
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<
DIM Drink$(4), Nation$(4), Colr$(4), Smoke$(4), Animal$(4)
Drink$() = "Beer", "Coffee", "Milk", "Tea", "Water"
Line 411 ⟶ 543:
j% -= 1
ENDWHILE
= TRUE</
'''Output:'''
<pre>
Line 426 ⟶ 558:
=={{header|Bracmat}}==
<
(red green white yellow blue,(red.English.))
(dog birds cats horse zebra,(dog.?.Swede.))
Line 508 ⟶ 640:
& props$(!properties...)
& done
);</
Output:
<pre> Solution
Line 519 ⟶ 651:
=={{header|C}}==
<
#include <string.h>
Line 756 ⟶ 888:
return 0;
}</
{{out}}
<pre>% gcc -Wall -O3 -std=c99 zebra.c -o zebra && time ./zebra
Line 770 ⟶ 902:
I'll be the first to admit the following doesn't quite look like a C program. It's in fact in Perl, which outputs a C source, which in turn solves the puzzle. If you think this is long, wait till you see the C it writes.
<
use utf8;
Line 945 ⟶ 1,077:
# write C code. If it's ugly to you: I didn't write; Perl did.
make_c;</
output (ran as <code>perl test.pl | gcc -Wall -x c -; ./a.out</code>):<pre>
0 dunhill cats yellow water Norske
Line 959 ⟶ 1,091:
<!-- By Martin Freedman, 17/01/2018 -->
This is adapted from a solution to a similar problem by Peter Norvig in his [https://www.udacity.com/course/design-of-computer-programs--cs212 Udacity course CS212], originally written in Python. This is translated from [https://github.com/exercism/python/blob/master/exercises/zebra-puzzle/example.py example python solution on exercism]. This is a Generate-and-Prune Constraint Programming algorithm written with Linq. (See Benchmarks below)
<
using System.Collections.Generic;
using System.Linq;
Line 1,043 ⟶ 1,175:
Read();
}
}</
Produces:
<pre>
Line 1,062 ⟶ 1,194:
This is a different type of generate-and-prune compared to Norvig. The Norvig solution generates each attribute for 5 houses, then prunes and repeats with the next attribute. Here all houses with possible attributes are first generated and pruned to 78 candidates. The second phase proceeds over the combination of 5 houses from that 78, generating and pruning 1 house at a time. (See Benchmarks below)
<
using System.Collections.Generic;
using System.Linq;
Line 1,170 ⟶ 1,302:
}
}
}</
Produces
<pre>The zebra owner is German
Line 1,186 ⟶ 1,318:
{{works with|C sharp|C#|7.1}}
<!-- By Martin Freedman, 9/02/2018 -->
<
using System;
using System.Collections.Generic;
Line 1,271 ⟶ 1,403:
Read();
}
}</
Produces
<pre>The zebra owner is German
Line 1,287 ⟶ 1,419:
{{libheader|Microsoft Solver Foundation}}
<!-- By Martin Freedman, 19/01/2018 based on MS example code-->
<
using System.Collections.Generic;
using System.Linq;
Line 1,399 ⟶ 1,531:
Read();
}
}</
Produces:
<pre>
Line 1,428 ⟶ 1,560:
This is a modification of the C submission that uses rule classes and reduces the number of permutations evaluated.
<
#include <stdio.h>
#include <string.h>
Line 1,576 ⟶ 1,708:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,596 ⟶ 1,728:
=={{header|Clojure}}==
This solution uses the contributed package ''clojure.core.logic'' (with ''clojure.tools.macro''), a mini-Kanren based logic solver. The solution is basically the one in [http://github.com/swannodette/logic-tutorial Swannodette's logic tutorial], adapted to the problem statement here.
<
(:refer-clojure :exclude [==])
(:use [clojure.core.logic]
Line 1,638 ⟶ 1,770:
(println "full solution (in house order):")
(doseq [h soln] (println " " h)))
</syntaxhighlight>
{{output}}
<pre>solution count: 1
Line 1,656 ⟶ 1,788:
This is adapted from a solution to a similar problem by Peter Norvig in his [https://www.udacity.com/course/design-of-computer-programs--cs212 Udacity course CS212], originally written in Python but equally applicable in any language with for-comprehensions.
<
(:require [clojure.math.combinatorics :as c]))
Line 1,703 ⟶ 1,835:
(println (apply format "%5s %-11s %-7s %-7s %-12s %-6s"
(map #(% i) (cons inc solution)))))))
</syntaxhighlight>
{{output}}
<pre>user=> (time (zebra/-main))
Line 1,721 ⟶ 1,853:
=={{header|Crystal}}==
{{trans|Ruby}}
<
Nationality: %i[English Swedish Danish Norwegian German],
Colour: %i[Red Green White Blue Yellow],
Line 1,778 ⟶ 1,910:
end
solve_zebra_puzzle</
=={{header|Curry}}==
{{Works with|PAKCS}}
<
import Findall (findall)
Line 1,824 ⟶ 1,956:
main = findall $ \(hs,who) -> houses hs & H _ who Zebra _ _ `member` hs</
{{Output}} Using [http://www-ps.informatik.uni-kiel.de/~pakcs/webpakcs/main.cgi web interface].
<pre>Execution time: 180 msec. / elapsed: 180 msec.
Line 1,832 ⟶ 1,964:
{{trans|Ada}}
Most foreach loops in this program are static.
<
enum Content { Beer, Coffee, Milk, Tea, Water,
Line 1,926 ⟶ 2,058:
solve(M, Test.Drink, 5);
}</
{{out}}
<pre> One: Water Norwegian Yellow Dunhill Cat
Line 1,938 ⟶ 2,070:
{{trans|Python}}
This requires the module of the first D entry from the Permutations Task.
<
uint factorial(in uint n) pure nothrow @nogc @safe
Line 2,037 ⟶ 2,169:
writeln;
}
}</
{{out}}
<pre>Found a solution:
Line 2,052 ⟶ 2,184:
{{trans|PicoLisp}}
This requires the module of the second D entry from the Permutations Task.
<
import std.stdio, std.algorithm, permutations2;
Line 2,084 ⟶ 2,216:
nextTo(drinks, Water, smokes, Blend))
writefln("%(%10s\n%)\n", [houses, persons, drinks, pets, smokes]);
}</
{{out}}
<pre>[ Yellow, Blue, Red, Green, White]
Line 2,095 ⟶ 2,227:
=={{header|EchoLisp}}==
We use the '''amb''' library to solve the puzzle. The number of tries - calls to zebra-puzzle - is only 1900, before finding all solutions. Note that there are no declarations for things (cats, tea, ..) or categories (animals, drinks, ..) which are discovered when reading the constraints.
<
(lib 'hash)
(lib 'amb)
Line 2,168 ⟶ 2,300:
(amb-fail) ;; will ensure ALL solutions are printed
)
</syntaxhighlight>
{{out}}
<
(define (task)
(amb-run zebra-puzzle (amb-make-context) (iota 5)))
Line 2,184 ⟶ 2,316:
→ #f
</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Ruby}}
<
defp adjacent?(n,i,g,e) do
Enum.any?(0..3, fn x ->
Line 2,261 ⟶ 2,393:
Smoke: ~w[PallMall Dunhill BlueMaster Prince Blend]a ]
ZebraPuzzle.solve(content)</
{{out}}
Line 2,278 ⟶ 2,410:
=={{header|Erlang}}==
This solution generates all houses that fits the rules for single houses, then it checks multi-house rules. It would be faster to check multi-house rules while generating the houses. I have not added this complexity since the current program takes just a few seconds.
<syntaxhighlight lang="erlang">
-module( zebra_puzzle ).
Line 2,396 ⟶ 2,528:
is_rule_16_ok( _House1, _House2, _House3, #house{drink=water}, #house{smoke=blend} ) -> true;
is_rule_16_ok( _House1, _House2, _House3, _House4, _House5 ) -> false.
</syntaxhighlight>
{{out}}
<pre>
Line 2,410 ⟶ 2,542:
=={{header|ERRE}}==
<syntaxhighlight lang="erre">
PROGRAM ZEBRA_PUZZLE
Line 2,516 ⟶ 2,648:
PRINT("Number of solutions=";SOLUTIONS%)
PRINT("Solved in ";TIMER-T1;" seconds")
END PROGRAM</
{{out}}
<pre>
Line 2,531 ⟶ 2,663:
=={{header|F_Sharp|F#}}==
This task uses [[Permutations_by_swapping#F.23]]
<
(*Here I solve the Zebra puzzle using Plain Changes, definitely a challenge to some campanoligist to solve it using Grandsire Doubles.
Nigel Galloway: January 27th., 2017 *)
Line 2,573 ⟶ 2,705:
|Some(nn) -> nn.Gz |> Array.iteri(fun n g -> if (g = G.Zebra) then printfn "\nThe man who owns a zebra is %A\n" nn.Nz.[n]); printfn "%A" nn
|None -> printfn "No solution found"
</syntaxhighlight>
{{out}}
<pre>
Line 2,586 ⟶ 2,718:
=={{header|FormulaOne}}==
<syntaxhighlight lang="formulaone">
// First, let's give some type-variables some values:
Nationality = Englishman | Swede | Dane | Norwegian | German
Line 2,763 ⟶ 2,895:
house_order(house1) = neighbour1 & house_order(house2) = neighbour2 &
house1 = house2 - 1
</syntaxhighlight>
{{out}}
<pre>
Line 2,774 ⟶ 2,906:
=={{header|GAP}}==
<
local i;
for i in [1..4] do
Line 2,834 ⟶ 2,966:
Print(cigars,"\n");
od;od;od;od;od;
</syntaxhighlight>
=={{header|Go}}==
<
import (
Line 3,130 ⟶ 3,262:
fmt.Println(n, "solution found")
fmt.Println(sol)
}</
{{out}}
<pre>Generated 51 valid houses
Line 3,148 ⟶ 3,280:
=={{header|Haskell}}==
<
import Control.Applicative ((<$>), (<*>))
Line 3,238 ⟶ 3,370:
leftOf p q
| (_:h:_) <- dropWhile (not . p) solution = q h
| otherwise = False</
{{out}}
<pre>House {color = Yellow, man = Nor, pet = Cats, drink = Water, smoke = Dunhill}
Line 3,253 ⟶ 3,385:
(a little faster version)
<
import Data.List
Line 3,312 ⟶ 3,444:
print [nation | (nation, _, Zebra, _, _) <- answer]
putStrLn "" )
putStrLn "No more solutions!"</
Output:
Line 3,327 ⟶ 3,459:
Propositions 1 .. 16 without 9,10 and15
<
cr=: (('English';'red') 0 3} ehs);<('Dane';'tea') 0 2}ehs
Line 3,339 ⟶ 3,471:
next=: <((<'Blend') 4 }ehs);<(<'water')2}ehs
next=: next,<((<'Blend') 4 }ehs);<(<'cats')1}ehs
next=: next,<((<'Dunhill') 4}ehs);<(<'horse')1}ehs</
'''Example'''
<
┌─────────────────┬───────────┐
│┌┬┬──────┬─────┬┐│┌┬┬┬─────┬┐│
││││coffee│green│││││││white│││
│└┴┴──────┴─────┴┘│└┴┴┴─────┴┘│
└─────────────────┴───────────┘</
Collections of all variants of the propositions:
<
hcs=:~. (A.~i.@!@#)cs,2$<ehs
hlof=:(-i.4) |."0 1 lof,3$<ehs
hnext=: ,/((i.4) |."0 1 (3$<ehs)&,)"1 ;(,,:|.)&.> next</
We start the row of houses with fixed properties 9, 10 and 15.
<
{{out}}
<
┌───────────────┬──────────┬──────────┬──────┬──────┐
│┌─────────┬┬┬┬┐│┌┬┬┬────┬┐│┌┬┬────┬┬┐│┌┬┬┬┬┐│┌┬┬┬┬┐│
││Norwegian││││││││││blue││││││milk││││││││││││││││││
│└─────────┴┴┴┴┘│└┴┴┴────┴┘│└┴┴────┴┴┘│└┴┴┴┴┘│└┴┴┴┴┘│
└───────────────┴──────────┴──────────┴──────┴──────┘</
Set of proposition variants:
<
The worker and its helper verbs
<
filter=: #~*./@:(2>#S:0)"1
compose=: [: filter f. [: ,/ select f. L:0"1"1 _
Line 3,376 ⟶ 3,508:
z=.(#~1=[:+/"1 (0=#)S:0"1) h=.~. h
end.
)</
{{out}}
<
┌─────────┬─────┬──────┬──────┬──────────┐
│Norwegian│cats │water │yellow│Dunhill │
Line 3,389 ⟶ 3,521:
├─────────┼─────┼──────┼──────┼──────────┤
│Swede │dog │beer │white │BlueMaster│
└─────────┴─────┴──────┴──────┴──────────┘</
So, the German owns the zebra.
'''Alternative'''
<br>A longer running solver by adding the zebra variants.
<
solve3=: 4 :0
Line 3,401 ⟶ 3,533:
z=. f^:(3>[:#(#~p"1)&>)^:_ <,:x
>"0 (#~([:*./[:;[:<@({.~:}.)\.;)"1)(#~p"1); z
)</
{{out}}
<
┌─────────┬─────┬──────┬──────┬──────────┐
│Norwegian│cats │water │yellow│Dunhill │
Line 3,414 ⟶ 3,546:
├─────────┼─────┼──────┼──────┼──────────┤
│Swede │dog │beer │white │BlueMaster│
└─────────┴─────┴──────┴──────┴──────────┘</
=={{header|Java}}==
Line 3,423 ⟶ 3,555:
* The Solver
<
import java.util.Arrays;
Line 3,853 ⟶ 3,985:
}
}
}</
{{out}}
<pre>
Line 3,877 ⟶ 4,009:
'''Part 1''': Generic filters for unification and matching
<syntaxhighlight lang="jq">
# Attempt to unify the input object with the specified object
def unify( object ):
Line 3,899 ⟶ 4,031:
| if $ans then .[i] = $ans else empty end
else empty
end ;</
'''Part 2''': Zebra Puzzle
<
# { "number": _, "nation": _, "owns": _, "color": _, "drinks": _, "smokes": _}
Line 3,960 ⟶ 4,092:
;
zebra</
{{Out}}
<div style="overflow:scroll; height:400px;">
<
[
{
Line 4,010 ⟶ 4,142:
real 0m0.284s
user 0m0.260s
sys 0m0.005s</
=={{header|Julia}}==
<syntaxhighlight lang="julia">
# Julia 1.0
using Combinatorics
Line 4,073 ⟶ 4,205:
end
</syntaxhighlight>
{{out}}
Line 4,087 ⟶ 4,219:
===Constraint Programming Version===
Using the rules from https://github.com/SWI-Prolog/bench/blob/master/programs/zebra.pl
<
using JuMP
using GLPK
Line 4,163 ⟶ 4,295:
drinks=getindex.(m, 4),
smokes=getindex.(m, 5))
</syntaxhighlight>
{{out}}
Line 4,178 ⟶ 4,310:
=={{header|Kotlin}}==
<
fun nextPerm(perm: IntArray): Boolean {
Line 4,291 ⟶ 4,423:
val plural = if (solutions == 1) "" else "s"
println("$solutions solution$plural found")
}</
{{out}}
Line 4,311 ⟶ 4,443:
The Logtalk distribution includes a solution for a variant of this puzzle (here reproduced with permission):
<
/* Houses logical puzzle: who owns the zebra and who drinks water?
Line 4,388 ⟶ 4,520:
:- end_object.
</syntaxhighlight>
Sample query:
<
| ?- houses::(houses(S), print(S)).
h(norwegian,fox,kool,water,yellow)
Line 4,400 ⟶ 4,532:
S = [h(norwegian,fox,kool,water,yellow),h(ukrainian,horse,chesterfield,tea,blue),h(english,snake,winston,milk,red),h(japonese,zebra,kent,coffee,green),h(spanish,dog,lucky,juice,white)]
</syntaxhighlight>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Line 4,432 ⟶ 4,564:
This should be read as follows: Each column shows (in blocks of 5) the possible candidates of each kind (beverage, animal, smoke...)
We solve it now in a 'sudoku' way: We remove candidates iteratively until we are left with 1 candidate of each kind for each house.
<
EliminatePoss[ct_, key1_, key2_] := Module[{t = ct, poss1, poss2, poss, notposs},
poss1 = Position[t, key1];
Line 4,545 ⟶ 4,677:
bigtable = FixedPoint[FilterPuzzle, bigtable];
TableForm[DeleteCases[bigtable\[Transpose], Null, \[Infinity]], TableHeadings -> {Range[5], None}]</
Using the command FixedPoint, we iteratively filter out these candidates, until we are (hopefully) left with 1 candidate per kind per house.
{{out}}
Line 4,555 ⟶ 4,687:
=={{header|Mercury}}==
<
:- interface.
Line 4,734 ⟶ 4,866:
write_string("No solution found.\n", !IO)
).
</syntaxhighlight>
{{out}}
<pre>--------
Line 4,767 ⟶ 4,899:
parliament - japanese</pre>
=={{header|MiniZinc}}==
<syntaxhighlight lang="minizinc">
%Solve Zebra Puzzle. Nigel Galloway, August 27th., 2019
include "alldifferent.mzn";
Line 4,797 ⟶ 4,929:
solve satisfy;
output ["The "++show(Nz[n])++" owns the zebra"++"\n\n"++show(Nz)++"\n"++show(Iz)++"\n"++show(Gz)++"\n"++show(Ez)++"\n"++show(Lz)++"\n"];
</syntaxhighlight>
{{out}}
<pre>
Line 4,817 ⟶ 4,949:
be pasted into the REPL.
<syntaxhighlight lang="nial">
remove is op x xs {filter (not (x =)) xs}
Line 4,873 ⟶ 5,005:
abs(time - (run; time))
</syntaxhighlight>
{{out}}
Line 4,895 ⟶ 5,027:
Using the same order for test of criteria as in Kotlin solution.
<
type
Line 4,964 ⟶ 5,096:
let owner = sol.filterIt(it.pet == Zebra)[0].person
echo &"\nThe {owner} owns the zebra."</
{{out}}
Line 4,979 ⟶ 5,111:
The German owns the zebra.</pre>
=={{header|
<syntaxhighlight lang="none">
perm(arr) = {
n=#arr;i=n-1;
Line 5,032 ⟶ 5,164:
for(i=1,5,printf("House:%s %6s %10s %10s %10s %10s\n",i,colors[c][i],nations[n][i],pets[p][i],drinks[d][i],smokes[s][i]));\
)))))))));
</syntaxhighlight>
{{out}}
Line 5,048 ⟶ 5,180:
=={{header|Perl}}==
Basically the same idea as C, though of course it's much easier to have Perl generate Perl code.
<
use utf8;
Line 5,151 ⟶ 5,283:
pair qw( water blend -1 1 );
$solve->();</
Incidentally, the same logic can be used to solve the dwelling problem, if somewhat awkwardly:
<
# property names and values
setprops
Line 5,174 ⟶ 5,306:
pair qw(cooper fletcher 4 3 2 -2 -3 -4);
$solve->();</
=={{header|Phix}}==
<!--
<syntaxhighlight lang="phix">
--enum colour, nationality, drink, smoke, pet -- (now implicit)
enum red,white,green,yellow,blue
enum English,Swede,Dane,Norwegian,German
enum tea,coffee,milk,beer,water
enum PallMall,Dunhill,Blend,BlueMaster,Prince
enum dog,birds,cats,horse,zebra
constant colours = {"red","white","green","yellow","blue"},
nationalities = {"English","Swede","Dane","Norwegian","German"},
drinks = {"tea","coffee","milk","beer","water"},
smokes = {"Pall Mall","Dunhill","Blend","Blue Master","Prince"},
pets = {"dog","birds","cats","horse","zebra"},
sets = {colours,nationalities,drinks,smokes,pets}
constant p5 = permutes(tagset(5)), -- all permutes of {1,2,3,4,5},
lp = length(p5) -- (== factorial(5), ie 120)
// In the following, c1,c2 are indexes to p5, for colour..pet,
// and v1,v2 are from their corresponding enums, so eg p5[c1]
// might be {1,4,3,2,5} for the colours of 1..5 and finding
// v1 in that gives us a house number. Checking the specified
// condition, eg [h] == green && [h+1] == white is then easy.
function left_of(integer c1, v1, c2, v2)
integer h = find(v1,p5[c1])
return h<=4 and p5[c2][h+1]=v2
end function
function same_house(integer c1, v1, c2, v2)
integer h = find(v1,p5[c1])
return p5[c2][h]=v2
end function
function next_to(integer c1, v1, c2, v2)
integer h1 = find(v1,p5[c1]),
h2 = find(v2,p5[c2])
return abs(h1-h2)=1
end function
procedure print_house(integer n, sequence perm)
sequence args = {n}
for i,p in perm do
args = append(args,sets[i][p5[p][n]])
end for
printf(1,"House %d: %|7s %|10s %|6s %|12s %=6s\n",args)
end procedure
integer ns = 0
atom t0 = time()
for colour=1 to lp do
if left_of(colour,green,colour,white) then
for nationality=1 to lp do
if p5[nationality][1]=Norwegian -- Norwegian lives in 1st house
and same_house(nationality,English,colour,red)
and next_to(nationality,Norwegian,colour,blue) then
for drink=1 to lp do
if same_house(nationality,Dane,drink,tea)
and same_house(drink,coffee,colour,green)
and p5[drink][3]=milk then -- middle house drinks milk
for smoke=1 to lp do
if same_house(colour,yellow,smoke,Dunhill)
and same_house(nationality,German,smoke,Prince)
and
and next_to(drink,water,smoke,Blend) then
for pet=1 to lp do
if
print_house(i,{colour,nationality,drink,smoke,pet})
end for
integer z = p5[nationality][find(zebra,p5[pet])]
printf(1,"The %s owns the Zebra\n",{nationalities[z]})
ns += 1
end if
end for
end if
end for
end if
end for
end if
end for
end if
end for
printf(1,"%d solution%s found (%3.3fs).\n",{ns,iff(ns>1,"s",""),time()-t0})
</syntaxhighlight>
{{out}}
<pre>
House 1: yellow
House 2: blue
House 3: red
House 4: green
House 5: white
The German owns the Zebra
1 solution found (0.000s).
</pre>
=={{header|Picat}}==
<
main =>
Line 5,319 ⟶ 5,457:
writef("The %w owns the zebra\n", ZebraOwner),
writeln(L).
</syntaxhighlight>
{{out}}
<pre>
Line 5,327 ⟶ 5,465:
=={{header|PicoLisp}}==
<
(permute (red blue green yellow white) @House)
(left-of @House white @House green)
Line 5,367 ⟶ 5,505:
(be next-to (@X @A @Y @B) (right-of @X @A @Y @B))
(be next-to (@X @A @Y @B) (left-of @X @A @Y @B))</
Test:
<
(let Fmt (-8 -11 -8 -7 -11)
(tab Fmt "HOUSE" "PERSON" "DRINKS" "HAS" "SMOKES")
(mapc '(@ (pass tab Fmt))
@House @Person @Drink @Pet @Cigarettes ) ) )</
Output:
<pre>HOUSE PERSON DRINKS HAS SMOKES
Line 5,386 ⟶ 5,524:
In Prolog we can specify the domain by selecting elements from it, making mutually exclusive choices for efficiency:
<
select([],_).
Line 5,406 ⟶ 5,544:
:- ?- time(( zebra(Who, HS), maplist(writeln,HS), nl, write(Who), nl, nl, fail
; write('No more solutions.') )).</
Output:
Line 5,429 ⟶ 5,567:
Using extensible records, letting the houses' attributes be discovered from rules, ''not'' predetermined by a programmer (as any ''"a house has five attributes"'' solution is doing).
<
attrs( H, [N-V | R]) :- !, memberchk( N-X, H), X = V, (R = [], ! ; attrs( H, R)).
attrs( HS, AttrsL) :- maplist( attrs, HS, AttrsL).
Line 5,458 ⟶ 5,596:
, [[drink -water ], [smoke-'Blend' ]] % 16
] ),
in( Houses, [owns-zebra, nation-Owner]).</
[http://ideone.com/wcwXfZ Output]:
<
maplist(writeln,S),nl,writeln(Z)), false ; writeln('No More Solutions'))).
Line 5,472 ⟶ 5,610:
german
No More Solutions
% 263,486 inferences, 0.047 CPU in 0.063 seconds (74% CPU, 5630007 Lips)</
===Alternative version===
{{Works with|GNU Prolog}}
{{Works with|SWI Prolog}}
<
Line 5,522 ⟶ 5,660:
main :- findall(_, (zebra(_), nl), _), halt.
</syntaxhighlight>
{{Output}}
<pre>h(yellow,nvg,cats,water,dh)
Line 5,536 ⟶ 5,674:
{{Works with|SWI Prolog}}
Original source code is 'ECLiPSe ( http://eclipseclp.org/ )' example: http://eclipseclp.org/examples/zebra.ecl.txt
<
zebra :-
Line 5,590 ⟶ 5,728:
format(Fmt, PetNames),
format(Fmt, DrinkNames).
</syntaxhighlight>
{{Output}}
<pre>
Line 5,603 ⟶ 5,741:
{{trans|Clojure}}
Using 'logpy': https://github.com/logpy/logpy
<
from logpy import *
from logpy.core import lall
Line 5,677 ⟶ 5,815:
for line in solutions[0]:
print str(line)
</syntaxhighlight>
===Alternative Version===
{{trans|D}}
<
class Content: elems= """Beer Coffee Milk Tea Water
Line 5,781 ⟶ 5,919:
solve(M, Test.Drink, 5)
main()</
{{out}}
<pre> One: Water Norwegian Yellow Dunhill Cat
Line 5,790 ⟶ 5,928:
Runtime about 0.18 seconds.
===Alternative Version===
<
class Number:elems= "One Two Three Four Five".split()
Line 5,840 ⟶ 5,978:
print
main()</
Output:
<pre>Found a solution:
Line 5,853 ⟶ 5,991:
Using 'python-constraint': http://labix.org/python-constraint,
Original source code is 'ECLiPSe ( http://eclipseclp.org/ )' example: http://eclipseclp.org/examples/zebra.ecl.txt
<syntaxhighlight lang
Improved version: Instead of simple variables (a, b),
more intelligible and readable (?) variables are employed.
'''
def doc1():
'''
There are five houses.
The English man lives in the red house.
The Swede has a dog.
The Dane drinks tea.
The green house is immediately to the left of the white house.
They drink coffee in the green house.
The man who smokes Pall Mall has a bird.
In the yellow house they smoke Dunhill.
In the middle house they drink milk.
The Norwegian lives in the first house.
The man who smokes Blend lives in the house next to the house with a cat.
In a house next to the house where they have a horse, they smoke Dunhill.
The man who smokes Blue Master drinks beer.
The German smokes Prince.
The Norwegian lives next to the blue house.
They drink water in a house next to the house where they smoke Blend.
The solution:
Nation: Norwegian Dane
Color:
Smoke: Dunhill Blend PallMall Prince BlueMaster
Drink:
'''
import os
print(os.system('cls') if os.name == 'nt' else os.system('clear'))
print(doc1.__doc__)
input('<key>')
from constraint import *
p = Problem()
Nation = ['Englishman', 'Dane', 'German', 'Norwegian', 'Swede']
Color = [ 'Blue', 'Green', 'Red', 'White', 'Yellow']
Smoke = [ 'Blend', 'BlueMaster', 'Dunhill', 'PallMall', 'Prince']
Pet = [ 'Bird', 'Cat', 'Dog', 'Horse', 'Zebra']
Drink = [ 'Beer', 'Coffee', 'Milk', 'Tea', 'Water']
# add variables: house numbers 1 to 5
# add constraint: the values in each list are exclusive
# add constraint: actual constraints
# The English man lives in the red house.
p.addConstraint(
lambda house_englishman, red:
house_englishman is red,
['Englishman', 'Red'])
# The Swede has a dog.
p.addConstraint(
lambda pet_swede, dog:
['Swede', 'Dog'])
# The Dane drinks tea.
p.addConstraint(
lambda drink_dane, tea:
drink_dane is tea,
['Dane', 'Tea'])
# The green house is immediately to the left of the white house.
p.addConstraint(
lambda green_house, white_house:
# Houses 1 .. 5 -> green house is 1 lower than white house
green_house is white_house - 1,
['Green', 'White'])
# They drink coffee in the green house.
p.addConstraint(
lambda drink_green_house, coffee:
drink_green_house is coffee,
['Green', 'Coffee'])
# The man who smokes Pall Mall has a bird.
p.addConstraint(
lambda pet_of_pallmall_smoker, a_bird:
pet_of_pallmall_smoker is a_bird,
['PallMall', 'Bird'])
# In the yellow house they smoke Dunhill.
p.addConstraint(
lambda owner_yellow_house, dunhill_smoker:
owner_yellow_house is dunhill_smoker,
['Yellow', 'Dunhill'])
# In the middle house they drink milk.
p.addConstraint(
lambda house_number_milk_drinker:
house_number_milk_drinker is 3,
['Milk'])
# The Norwegian lives in the first house.
p.addConstraint(
lambda house_number_norwegian:
house_number_norwegian is 1,
['Norwegian'])
# The man who smokes Blend lives in the house next to the house with a cat.
p.addConstraint(
lambda house_number_blend_smoker, number_of_house_with_cat:
# next -> housenumber +/- 1
house_number_blend_smoker is number_of_house_with_cat + 1 or
house_number_blend_smoker is number_of_house_with_cat - 1,
['Blend', 'Cat'])
# In a house next to the house where they have a horse, they smoke Dunhill.
p.addConstraint(
lambda house_number_dunhill_smoker, number_of_house_with_horse:
# next -> housenumber +/- 1
house_number_dunhill_smoker is number_of_house_with_horse + 1 or
house_number_dunhill_smoker is number_of_house_with_horse - 1,
['Dunhill', 'Horse'])
# The man who smokes Blue Master drinks beer.
p.addConstraint(
lambda drink_bluemaster_smoker, beer:
drink_bluemaster_smoker is beer,
['BlueMaster', 'Beer'])
# The German smokes Prince.
p.addConstraint(
lambda prince_smoker, german:
prince_smoker is german,
['Prince', 'German'])
# The Norwegian lives next to the blue house.
p.addConstraint(
lambda house_number_norwegian, house_number_blue_house:
house_number_norwegian is house_number_blue_house + 1 or
house_number_norwegian is house_number_blue_house - 1,
['Norwegian', 'Blue'])
# They drink water in a house next to the house where they smoke Blend.
p.addConstraint(
lambda house_number_water_drinker, house_number_blend_smoker:
house_number_water_drinker is house_number_blend_smoker + 1 or
house_number_water_drinker is house_number_blend_smoker - 1,
['Water', 'Blend'])
# get solution
sol =
# print the answers
nation = [
color = [
smoke = [
pet = [
drink = [
for n in Nation: nation[sol[n]] = n
for n in Color: color[sol[n]] = n
for n in
for n in
for n in
# put the answers in the correct order of solution
print('\n\n', 'The calculated solution:', '\n')
for
print(f'{r[0]:>13s}: ', end='')
for i in range(1, 6):
print(f'{r[i]:>14s}',end='')
print()
print()
</syntaxhighlight>
Output:
<pre>
</pre>
=={{header|R}}==
{{libheader|combinat}}<
library(combinat)
Line 6,004 ⟶ 6,267:
}
}</
{{out}}
<pre>
Line 6,019 ⟶ 6,282:
{{trans|Prolog}}
<
(require racklog)
Line 6,075 ⟶ 6,338:
(%member (list (_) Owns 'zebra (_) (_)) HS)]))
(%which (Who HS) (%zebra Who HS))</
Output:
Line 6,091 ⟶ 6,354:
(formerly Perl 6)
A rule driven approach:
<syntaxhighlight lang="raku"
my @facts = (
Line 6,167 ⟶ 6,430:
! %props.first: {%house{.key} && %house{.key} ne .value };
}
</syntaxhighlight>
{{out}}
<pre>
Line 6,183 ⟶ 6,446:
{{trans|BBC BASIC}}
Permutations algorithm taken from REXX
<
* Solve the Zebra Puzzle
*--------------------------------------------------------------------*/
Line 6,351 ⟶ 6,614:
out:
Say arg(1)
Return</
{{out}}
<pre>House Drink Nation Colour Smoke Animal
Line 6,363 ⟶ 6,626:
=={{header|Ruby}}==
<
Nationality: %i[English Swedish Danish Norwegian German],
Colour: %i[Red Green White Blue Yellow],
Line 6,416 ⟶ 6,679:
end
solve_zebra_puzzle</
{{out}}
Line 6,432 ⟶ 6,695:
===Another approach===
<
class String; def brk; split(/(?=[A-Z])/); end; end
men,drinks,colors,pets,smokes = "NorwegianGermanDaneSwedeEnglish
Line 6,457 ⟶ 6,720:
puts "The #{x.find{|y|y[0]=="Zebra"}[1]} owns the zebra.",
x.map{|y| y.map{|z| z.ljust(11)}.join}}}}}}
</syntaxhighlight>
Output:
<pre>
Line 6,470 ⟶ 6,733:
=={{header|Scala}}==
===Idiomatic (for comprehension)===
<
*
* It can further concluded that:
Line 6,547 ⟶ 6,810:
members.foreach(solution => solution.zipWithIndex.foreach(h => println(s"House ${h._2 + 1} ${h._1}")))
}
} // loc 58</
{{Out}}See it in running in your browser by [https://scalafiddle.io/sf/h5Y98te/0 ScalaFiddle (JavaScript executed in browser)] or by [https://scastie.scala-lang.org/fJZRog4xQ9aAV4D3crM1gQ Scastie (remote JVM)].{{out}}
<pre> The German is the owner of the zebra.
Line 6,559 ⟶ 6,822:
===Scala Alternate Version (Over-engineered)===
<
object Einstein extends App {
Line 6,642 ⟶ 6,905:
}
}// loc 38</
{{Out}}Experience running it in your browser by [https://scalafiddle.io/sf/hJgtjYG/1 ScalaFiddle (JavaScript executed in browser)] or by [https://scastie.scala-lang.org/ajeuRgDSQKyVv4Jd6SPfVQ Scastie (remote JVM)].
{{out}}
Line 6,657 ⟶ 6,920:
=={{header|Sidef}}==
{{trans|Ruby}}
<
:House => nil,
:Nationality => [:English, :Swedish, :Danish, :Norwegian, :German],
Line 6,708 ⟶ 6,971:
say "The Zebra is owned by the man who is #{res[0][res[2].first_index(:Zebra)]}\n"
say (fmt % keys..., "\n", fmt % width.map{|w| "-"*w }...)
res[0].indices.map{|i| res.map{|a| a[i] }}.each_kv {|k,v| say fmt%(k,v...) }</
{{out}}
<pre>
Line 6,725 ⟶ 6,988:
{{works with|SML/NJ}}
{{trans|C++}}(This implementation uses the search algorithm of the C++ implementation, but the rules check algorithm is different.)
<
(* Attributes and values *)
val str_attributes = Vector.fromList ["Color", "Nation", "Drink", "Pet", "Smoke"]
Line 6,975 ⟶ 7,238:
else print "No solution found!\n"
end
</syntaxhighlight>
{{out}}
Line 6,992 ⟶ 7,255:
===General solver with relational algebra===
A general solver for this type of puzzle, using relational algebra. This solver can also be used for "Dinesman's multiple-dwelling problem"
<
processor EinsteinSolver
@: [{|{}|}]; // A list of possible relations, start with one relation with an empty tuple
$ -> \(
Line 7,017 ⟶ 7,280:
@EinsteinSolver: [$@EinsteinSolver... -> \(
def in: $;
def temp: {| $... -> {$, ES_temp__: ($(byField)::raw)"1"} |};
def numbers: [$temp({ES_temp__:})... -> $.ES_temp__];
$numbers... -> \(
def aNumber: $;
def bNumbers: [$bMinusA... -> ($ + $aNumber)"1"];
def new: ($temp matching {| {$a, ES_temp__: $aNumber} |});
@: ($new union (($temp notMatching {| $a |}) notMatching {| {ES_temp__: $aNumber} |}));
Line 7,088 ⟶ 7,351:
'No more solutions
' -> !OUT::write
</syntaxhighlight>
{{out}}
Line 7,107 ⟶ 7,370:
{{trans|C#}}
The streaming syntax of Tailspin lends itself naturally to this solution
<
templates permutations
when <=1> do [1] !
Line 7,160 ⟶ 7,423:
-> \[i]('$i;: $;'! \) -> '$... -> '$;$#10;';$#10;'
-> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
Line 7,173 ⟶ 7,436:
=={{header|Tcl}}==
{{trans|Python}}
{{tcllib|struct::list}}<
# Implements the constants by binding them directly into the named procedures.
Line 7,288 ⟶ 7,551:
initConstants isPossible
main</
{{out}}
<pre>
Line 7,300 ⟶ 7,563:
</pre>
=={{header|Uiua}}==
Usese the same re-ordering of rules as a lot of other approaches. Builds and filters the list as it goes.
<syntaxhighlight lang="uiua">
Perms ← ☇1⍉∧(≡↻⇡⟜↯+1⟜⊂):¤¤°⊂⇡
Ps ← ≡⊏⊙¤Perms ⧻.
Ps "BGRWY" # Col = 0
▽⊸(=-1⊃(⊗@W|⊗@G)) # W right of G
/⊂⊞⊟ :Ps "DEGNS" # Nation = 1
▽⊸≡(=@N⊡0⊡1) # Norwegian in pos 0
▽⊸≡(=⊃(⊗@E⊡1|⊗@R⊡0)) # Red == English
▽⊸≡(=1⌵-⊃(⊗@N⊡1|⊗@B⊡0)) # Blue next to Norwegian
/⊂⊞⊂ :Ps"BCDHZ" # Pets = 2
▽⊸≡(=⊃(⊗@D⊡2|⊗@S⊡1)) # Swede owns dog
/⊂⊞⊂ :Ps"BCMTW" # Drinks = 3
▽⊸≡(=@M⊡2⊡3) # Milk in pos 2
▽⊸≡(=⊃(⊗@T⊡3|⊗@D⊡1)) # Dane drinks tea
▽⊸≡(=⊃(⊗@C⊡3|⊗@G⊡0)) # Green = Coffee
/⊂⊞⊂ :Ps"BbDpP" # Cigs = 4
▽⊸≡(=⊃(⊗@p⊡4|⊗@B⊡2)) # PallMall = Birds
▽⊸≡(=⊃(⊗@D⊡4|⊗@Y⊡0)) # Dunhill = Yellow
▽⊸≡(=⊃(⊗@b⊡4|⊗@B⊡3)) # BlueM = Beer
▽⊸≡(=⊃(⊗@P⊡4|⊗@G⊡1)) # Prince = German
▽⊸≡(=1⌵-⊃(⊗@B⊡4|⊗@C⊡2)) # Cat next to Blend
▽⊸≡(=1⌵-⊃(⊗@D⊡4|⊗@H⊡2)) # Horse next to Dunhill
▽⊸≡(=1⌵-⊃(⊗@B⊡4|⊗@W⊡3)) # Water next to Blend
&p $"Solutions found: _" ⧻.
&p$"_ owns the Z"⊡:⊡1,⊗@Z⊡2.⊢
&p"One line per house: "
&p"Col\tNat\tPet\tDrink\tCig"
≡(&p/(⊂⊂)"\t")⍉
</syntaxhighlight>
{{out}}
<pre>
Solutions found: 1
G owns the Z
One line per house:
Col Nat Pet Drink Cig
Y N C W D
B D H T B
R E B M p
G G Z C P
W S D B b
</pre>
=={{header|VBA}}==
{{trans|Phix}}
<
Public Enum attr
Colour = 1
Line 7,466 ⟶ 7,777:
Debug.Print "The " & Nationalities(perm(Nationality)(house(Pet, Zebra))) & " owns the Zebra"
Next i
End Sub</
<pre>1: yellow Norwegian water Dunhill cats
2: blue Dane tea Blend horse
Line 7,476 ⟶ 7,787:
The German owns the Zebra</pre>
=={{header|V (Vlang)}}==
{{trans|Go}}
<syntaxhighlight lang="v (vlang)">type HouseSet = []House
struct House {
n Nationality
Line 7,749 ⟶ 8,060:
println("$n solution found")
println(sol)
}</
{{out}}
Line 7,767 ⟶ 8,078:
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<
var colors = ["Red", "Green", "White", "Yellow", "Blue"]
Line 7,881 ⟶ 8,192:
var solutions = fillHouses.call()
var plural = (solutions == 1) ? "" : "s"
System.print("%(solutions) solution%(plural) found")</
{{out}}
Line 7,902 ⟶ 8,213:
Lists are used as associated arrays rather than hash tables. With only five entries, it doesn't really matter.
<
fcn c2 { people.find(English)==houses.find(Red) }
fcn c3 { people.find(Swede)==pets.find(Dog) }
Line 7,962 ⟶ 8,273:
.zip(titles,names))
{ println(list.apply(names.get):fmt(title,_.xplode())) }
}</
{{out}}
<pre>
|