language agnostic - Resolviendo programáticamente "¿Quién posee la cebra?
language-agnostic logic (14)
ES6 (Javascript) solución
Con muchos generadores ES6 y un poco de lodash . Necesitarás a Babel para ejecutar esto.
var _ = require(''lodash'');
function canBe(house, criteria) {
for (const key of Object.keys(criteria))
if (house[key] && house[key] !== criteria[key])
return false;
return true;
}
function* thereShouldBe(criteria, street) {
for (const i of _.range(street.length))
yield* thereShouldBeAtIndex(criteria, i, street);
}
function* thereShouldBeAtIndex(criteria, index, street) {
if (canBe(street[index], criteria)) {
const newStreet = _.cloneDeep(street);
newStreet[index] = _.assign({}, street[index], criteria);
yield newStreet;
}
}
function* leftOf(critA, critB, street) {
for (const i of _.range(street.length - 1)) {
if (canBe(street[i], critA) && canBe(street[i+1], critB)) {
const newStreet = _.cloneDeep(street);
newStreet[i ] = _.assign({}, street[i ], critA);
newStreet[i+1] = _.assign({}, street[i+1], critB);
yield newStreet;
}
}
}
function* nextTo(critA, critB, street) {
yield* leftOf(critA, critB, street);
yield* leftOf(critB, critA, street);
}
const street = [{}, {}, {}, {}, {}]; // five houses
// Btw: it turns out we don''t need uniqueness constraint.
const constraints = [
s => thereShouldBe({nation: ''English'', color: ''red''}, s),
s => thereShouldBe({nation: ''Swede'', animal: ''dog''}, s),
s => thereShouldBe({nation: ''Dane'', drink: ''tea''}, s),
s => leftOf({color: ''green''}, {color: ''white''}, s),
s => thereShouldBe({drink: ''coffee'', color: ''green''}, s),
s => thereShouldBe({cigarettes: ''PallMall'', animal: ''birds''}, s),
s => thereShouldBe({color: ''yellow'', cigarettes: ''Dunhill''}, s),
s => thereShouldBeAtIndex({drink: ''milk''}, 2, s),
s => thereShouldBeAtIndex({nation: ''Norwegian''}, 0, s),
s => nextTo({cigarettes: ''Blend''}, {animal: ''cats''}, s),
s => nextTo({animal: ''horse''}, {cigarettes: ''Dunhill''}, s),
s => thereShouldBe({cigarettes: ''BlueMaster'', drink: ''beer''}, s),
s => thereShouldBe({nation: ''German'', cigarettes: ''Prince''}, s),
s => nextTo({nation: ''Norwegian''}, {color: ''blue''}, s),
s => nextTo({drink: ''water''}, {cigarettes: ''Blend''}, s),
s => thereShouldBe({animal: ''zebra''}, s), // should be somewhere
];
function* findSolution(remainingConstraints, street) {
if (remainingConstraints.length === 0)
yield street;
else
for (const newStreet of _.head(remainingConstraints)(street))
yield* findSolution(_.tail(remainingConstraints), newStreet);
}
for (const streetSolution of findSolution(constraints, street)) {
console.log(streetSolution);
}
Resultado:
[ { color: ''yellow'',
cigarettes: ''Dunhill'',
nation: ''Norwegian'',
animal: ''cats'',
drink: ''water'' },
{ nation: ''Dane'',
drink: ''tea'',
cigarettes: ''Blend'',
animal: ''horse'',
color: ''blue'' },
{ nation: ''English'',
color: ''red'',
cigarettes: ''PallMall'',
animal: ''birds'',
drink: ''milk'' },
{ color: ''green'',
drink: ''coffee'',
nation: ''German'',
cigarettes: ''Prince'',
animal: ''zebra'' },
{ nation: ''Swede'',
animal: ''dog'',
color: ''white'',
cigarettes: ''BlueMaster'',
drink: ''beer'' } ]
El tiempo de ejecución es de 2.5 segundos para mí, pero esto se puede mejorar mucho cambiando el orden de las reglas. Decidí mantener el orden original para mayor claridad.
Gracias, ¡este fue un gran desafío!
Editar: este rompecabezas también se conoce como "Eidtein''s Riddle"
The Who''s the Zebra (puedes probar la versión en línea aquí ) es un ejemplo de un conjunto clásico de acertijos y apuesto a que la mayoría de la gente en Stack Overflow puede resolverlo con lápiz y papel. Pero, ¿cómo sería una solución programática?
De acuerdo con las pistas enumeradas a continuación ...
- Hay cinco casas
- Cada casa tiene su propio color único.
- Todos los dueños de casas son de diferentes nacionalidades.
- Todos tienen diferentes mascotas.
- Todos beben diferentes bebidas.
- Todos fuman cigarrillos diferentes.
- El inglés vive en la casa roja.
- El sueco tiene un perro.
- El danés toma té.
- La casa verde está en el lado izquierdo de la casa blanca.
- Beben café en la casa verde.
- El hombre que fuma Pall Mall tiene pájaros.
- En la casa amarilla, fuman Dunhill.
- En la casa del medio beben leche.
- El noruego vive en la primera casa.
- El hombre que fuma Blend vive en la casa junto a la casa con gatos.
- En la casa al lado de la casa donde tienen un caballo, fuman Dunhill.
- El hombre que fuma Blue Master bebe cerveza.
- El alemán fuma Prince.
- El noruego vive al lado de la casa azul.
- Beben agua en la casa al lado de la casa donde fuman Blend.
... ¿a quién pertenece la Zebra?
Aquí hay un extracto de la solución completa que usa NSolver , publicado en Einstein''s Riddle in C # :
// The green house''s owner drinks coffee
Post(greenHouse.Eq(coffee));
// The person who smokes Pall Mall rears birds
Post(pallMall.Eq(birds));
// The owner of the yellow house smokes Dunhill
Post(yellowHouse.Eq(dunhill));
Aquí hay una solución directa en CLP (FD) (vea también clpfd ):
:- use_module(library(clpfd)).
solve(ZebraOwner) :-
maplist( init_dom(1..5),
[[British, Swedish, Danish, Norwegian, German], % Nationalities
[Red, Green, Blue, White, Yellow], % Houses
[Tea, Coffee, Milk, Beer, Water], % Beverages
[PallMall, Blend, Prince, Dunhill, BlueMaster], % Cigarettes
[Dog, Birds, Cats, Horse, Zebra]]), % Pets
British #= Red, % Hint 1
Swedish #= Dog, % Hint 2
Danish #= Tea, % Hint 3
Green #= White - 1 , % Hint 4
Green #= Coffee, % Hint 5
PallMall #= Birds, % Hint 6
Yellow #= Dunhill, % Hint 7
Milk #= 3, % Hint 8
Norwegian #= 1, % Hint 9
neighbor(Blend, Cats), % Hint 10
neighbor(Horse, Dunhill), % Hint 11
BlueMaster #= Beer, % Hint 12
German #= Prince, % Hint 13
neighbor(Norwegian, Blue), % Hint 14
neighbor(Blend, Water), % Hint 15
memberchk(Zebra-ZebraOwner, [British-british, Swedish-swedish, Danish-danish,
Norwegian-norwegian, German-german]).
init_dom(R, L) :-
all_distinct(L),
L ins R.
neighbor(X, Y) :-
(X #= (Y - 1)) #// (X #= (Y + 1)).
Al ejecutarlo, produce:
3? - tiempo (resolver (Z)).
% 111,798 inferencias, 0.016 CPU en 0.020 segundos (78% CPU, 7166493 labios)
Z = alemán.
Aquí hay una solución en Python basada en la programación de restricciones:
from constraint import AllDifferentConstraint, InSetConstraint, Problem
# variables
colors = "blue red green white yellow".split()
nationalities = "Norwegian German Dane Swede English".split()
pets = "birds dog cats horse zebra".split()
drinks = "tea coffee milk beer water".split()
cigarettes = "Blend, Prince, Blue Master, Dunhill, Pall Mall".split(", ")
# There are five houses.
minn, maxn = 1, 5
problem = Problem()
# value of a variable is the number of a house with corresponding property
variables = colors + nationalities + pets + drinks + cigarettes
problem.addVariables(variables, range(minn, maxn+1))
# Each house has its own unique color.
# All house owners are of different nationalities.
# They all have different pets.
# They all drink different drinks.
# They all smoke different cigarettes.
for vars_ in (colors, nationalities, pets, drinks, cigarettes):
problem.addConstraint(AllDifferentConstraint(), vars_)
# In the middle house they drink milk.
#NOTE: interpret "middle" in a numerical sense (not geometrical)
problem.addConstraint(InSetConstraint([(minn + maxn) // 2]), ["milk"])
# The Norwegian lives in the first house.
#NOTE: interpret "the first" as a house number
problem.addConstraint(InSetConstraint([minn]), ["Norwegian"])
# The green house is on the left side of the white house.
#XXX: what is "the left side"? (linear, circular, two sides, 2D house arrangment)
#NOTE: interpret it as ''green house number'' + 1 == ''white house number''
problem.addConstraint(lambda a,b: a+1 == b, ["green", "white"])
def add_constraints(constraint, statements, variables=variables, problem=problem):
for stmt in (line for line in statements if line.strip()):
problem.addConstraint(constraint, [v for v in variables if v in stmt])
and_statements = """
They drink coffee in the green house.
The man who smokes Pall Mall has birds.
The English man lives in the red house.
The Dane drinks tea.
In the yellow house they smoke Dunhill.
The man who smokes Blue Master drinks beer.
The German smokes Prince.
The Swede has a dog.
""".split("/n")
add_constraints(lambda a,b: a == b, and_statements)
nextto_statements = """
The man who smokes Blend lives in the house next to the house with cats.
In the house next to the house where they have a horse, they smoke Dunhill.
The Norwegian lives next to the blue house.
They drink water in the house next to the house where they smoke Blend.
""".split("/n")
#XXX: what is "next to"? (linear, circular, two sides, 2D house arrangment)
add_constraints(lambda a,b: abs(a - b) == 1, nextto_statements)
def solve(variables=variables, problem=problem):
from itertools import groupby
from operator import itemgetter
# find & print solutions
for solution in problem.getSolutionIter():
for key, group in groupby(sorted(solution.iteritems(), key=itemgetter(1)), key=itemgetter(1)):
print key,
for v in sorted(dict(group).keys(), key=variables.index):
print v.ljust(9),
print
if __name__ == ''__main__'':
solve()
Salida:
1 yellow Norwegian cats water Dunhill
2 blue Dane horse tea Blend
3 red English birds milk Pall Mall
4 green German zebra coffee Prince
5 white Swede dog beer Blue Master
Tarda 0.6 segundos (CPU 1.5GHz) para encontrar la solución.
La respuesta es "El alemán posee cebra".
Para instalar el módulo de constraint través de pip : pip install python-constraint
Para instalar manualmente:
descargar:
extracto (Linux / Mac / BSD):
$ bzip2 -cd python-constraint-1.2.tar.bz2 | tar xvf -
extracto (Windows, con 7zip ):
> 7z e python-constraint-1.2.tar.bz2
> 7z e python-constraint-1.2.tarinstalar:
$ cd python-constraint-1.2
$ python setup.py install
Así es como lo haría. Primero generaría todas las n-tuplas ordenadas
(housenumber, color, nationality, pet, drink, smoke)
5 ^ 6 de esos, 15625, fácilmente manejables. Luego filtraría las condiciones booleanas simples. hay diez de ellos, y cada uno de ellos esperaría filtrar 8/25 de las condiciones (1/25 de las condiciones contienen un sueco con un perro, 16/25 contienen un no sueco con un no perro) . Por supuesto que no son independientes, pero después de filtrarlos no deberían quedar muchos.
Después de eso, tienes un buen problema gráfico. Crea un gráfico con cada nodo representando una de las n-tuplas restantes. Agregue bordes al gráfico si los dos extremos contienen duplicados en alguna posición n-tupla o si viola cualquier restricción "posicional" (hay cinco de ellos). Desde allí estás casi en casa, busca en el gráfico un conjunto independiente de cinco nodos (sin ninguno de los nodos conectados por los bordes). Si no hay demasiados, posiblemente podrías generar exhaustivamente todas las 5 tuplas de n-tuplas y simplemente filtrarlas nuevamente.
Este podría ser un buen candidato para el código de golf. Alguien puede probablemente resolverlo en una línea con algo así como Haskell :)
Pensamiento de último momento: el pase de filtro inicial también puede eliminar información de las restricciones de posición. No mucho (1/25), pero aún significativo.
Compatible con SWI-Prolog:
% NOTE - This may or may not be more efficent. A bit verbose, though.
left_side(L, R, [L, R, _, _, _]).
left_side(L, R, [_, L, R, _, _]).
left_side(L, R, [_, _, L, R, _]).
left_side(L, R, [_, _, _, L, R]).
next_to(X, Y, Street) :- left_side(X, Y, Street).
next_to(X, Y, Street) :- left_side(Y, X, Street).
m(X, Y) :- member(X, Y).
get_zebra(Street, Who) :-
Street = [[C1, N1, P1, D1, S1],
[C2, N2, P2, D2, S2],
[C3, N3, P3, D3, S3],
[C4, N4, P4, D4, S4],
[C5, N5, P5, D5, S5]],
m([red, english, _, _, _], Street),
m([_, swede, dog, _, _], Street),
m([_, dane, _, tea, _], Street),
left_side([green, _, _, _, _], [white, _, _, _, _], Street),
m([green, _, _, coffee, _], Street),
m([_, _, birds, _, pallmall], Street),
m([yellow, _, _, _, dunhill], Street),
D3 = milk,
N1 = norwegian,
next_to([_, _, _, _, blend], [_, _, cats, _, _], Street),
next_to([_, _, horse, _, _], [_, _, _, _, dunhill], Street),
m([_, _, _, beer, bluemaster], Street),
m([_, german, _, _, prince], Street),
next_to([_, norwegian, _, _, _], [blue, _, _, _, _], Street),
next_to([_, _, _, water, _], [_, _, _, _, blend], Street),
m([_, Who, zebra, _, _], Street).
En el intérprete:
?- get_zebra(Street, Who).
Street = ...
Who = german
El ejemplo de Microsoft Solver Foundation de: https://msdn.microsoft.com/en-us/library/ff525831%28v=vs.93%29.aspx?f=255&MSPPError=-2147217396
delegate CspTerm NamedTerm(string name);
public static void Zebra() {
ConstraintSystem S = ConstraintSystem.CreateSolver();
var termList = new List<KeyValuePair<CspTerm, string>>();
NamedTerm House = delegate(string name) {
CspTerm x = S.CreateVariable(S.CreateIntegerInterval(1, 5), name);
termList.Add(new KeyValuePair<CspTerm, string>(x, name));
return x;
};
CspTerm English = House("English"), Spanish = House("Spanish"),
Japanese = House("Japanese"), Italian = House("Italian"),
Norwegian = House("Norwegian");
CspTerm red = House("red"), green = House("green"),
white = House("white"),
blue = House("blue"), yellow = House("yellow");
CspTerm dog = House("dog"), snails = House("snails"),
fox = House("fox"),
horse = House("horse"), zebra = House("zebra");
CspTerm painter = House("painter"), sculptor = House("sculptor"),
diplomat = House("diplomat"), violinist = House("violinist"),
doctor = House("doctor");
CspTerm tea = House("tea"), coffee = House("coffee"),
milk = House("milk"),
juice = House("juice"), water = House("water");
S.AddConstraints(
S.Unequal(English, Spanish, Japanese, Italian, Norwegian),
S.Unequal(red, green, white, blue, yellow),
S.Unequal(dog, snails, fox, horse, zebra),
S.Unequal(painter, sculptor, diplomat, violinist, doctor),
S.Unequal(tea, coffee, milk, juice, water),
S.Equal(English, red),
S.Equal(Spanish, dog),
S.Equal(Japanese, painter),
S.Equal(Italian, tea),
S.Equal(1, Norwegian),
S.Equal(green, coffee),
S.Equal(1, green - white),
S.Equal(sculptor, snails),
S.Equal(diplomat, yellow),
S.Equal(3, milk),
S.Equal(1, S.Abs(Norwegian - blue)),
S.Equal(violinist, juice),
S.Equal(1, S.Abs(fox - doctor)),
S.Equal(1, S.Abs(horse - diplomat))
);
bool unsolved = true;
ConstraintSolverSolution soln = S.Solve();
while (soln.HasFoundSolution) {
unsolved = false;
System.Console.WriteLine("solved.");
StringBuilder[] houses = new StringBuilder[5];
for (int i = 0; i < 5; i++)
houses[i] = new StringBuilder(i.ToString());
foreach (KeyValuePair<CspTerm, string> kvp in termList) {
string item = kvp.Value;
object house;
if (!soln.TryGetValue(kvp.Key, out house))
throw new InvalidProgramException(
"can''t find a Term in the solution: " + item);
houses[(int)house - 1].Append(", ");
houses[(int)house - 1].Append(item);
}
foreach (StringBuilder house in houses) {
System.Console.WriteLine(house);
}
soln.GetNext();
}
if (unsolved)
System.Console.WriteLine("No solution found.");
else
System.Console.WriteLine(
"Expected: the Norwegian drinking water and the Japanese with the zebra.");
}
En Prolog, podemos instanciar el dominio simplemente seleccionando elementos de él :) (tomando decisiones mutuamente excluyentes , para mayor eficiencia). Usando SWI-Prolog,
select([A|As],S):- select(A,S,S1),select(As,S1).
select([],_).
left_of(A,B,C):- append(_,[A,B|_],C).
next_to(A,B,C):- left_of(A,B,C) ; left_of(B,A,C).
zebra(Owns, HS):- % house: color,nation,pet,drink,smokes
HS = [ h(_,norwegian,_,_,_), h(blue,_,_,_,_), h(_,_,_,milk,_), _, _],
select([ h(red,brit,_,_,_), h(_,swede,dog,_,_),
h(_,dane,_,tea,_), h(_,german,_,_,prince)], HS),
select([ h(_,_,birds,_,pallmall), h(yellow,_,_,_,dunhill),
h(_,_,_,beer,bluemaster)], HS),
left_of( h(green,_,_,coffee,_), h(white,_,_,_,_), HS),
next_to( h(_,_,_,_,dunhill), h(_,_,horse,_,_), HS),
next_to( h(_,_,_,_,blend), h(_,_,cats, _,_), HS),
next_to( h(_,_,_,_,blend), h(_,_,_,water,_), HS),
member( h(_,Owns,zebra,_,_), HS).
Funciona bastante al instante:
?- time( (zebra(Who,HS), writeln(Who), nl, maplist(writeln,HS), nl, false
; writeln(''no more solutions!'') )).
german
h( yellow, norwegian, cats, water, dunhill )
h( blue, dane, horse, tea, blend )
h( red, brit, birds, milk, pallmall )
h( green, german, zebra, coffee, prince ) % formatted by hand
h( white, swede, dog, beer, bluemaster)
no more solutions!
% 1,706 inferences, 0.000 CPU in 0.070 seconds (0% CPU, Infinite Lips)
true.
Esta es una solución MiniZinc para el rompecabezas de cebra como se define en Wikipedia:
include "globals.mzn";
% Zebra puzzle
int: nc = 5;
% Colors
int: red = 1;
int: green = 2;
int: ivory = 3;
int: yellow = 4;
int: blue = 5;
array[1..nc] of var 1..nc:color;
constraint alldifferent([color[i] | i in 1..nc]);
% Nationalities
int: eng = 1;
int: spa = 2;
int: ukr = 3;
int: nor = 4;
int: jap = 5;
array[1..nc] of var 1..nc:nationality;
constraint alldifferent([nationality[i] | i in 1..nc]);
% Pets
int: dog = 1;
int: snail = 2;
int: fox = 3;
int: horse = 4;
int: zebra = 5;
array[1..nc] of var 1..nc:pet;
constraint alldifferent([pet[i] | i in 1..nc]);
% Drinks
int: coffee = 1;
int: tea = 2;
int: milk = 3;
int: orange = 4;
int: water = 5;
array[1..nc] of var 1..nc:drink;
constraint alldifferent([drink[i] | i in 1..nc]);
% Smokes
int: oldgold = 1;
int: kools = 2;
int: chesterfields = 3;
int: luckystrike = 4;
int: parliaments = 5;
array[1..nc] of var 1..nc:smoke;
constraint alldifferent([smoke[i] | i in 1..nc]);
% The Englishman lives in the red house.
constraint forall ([nationality[i] == eng <-> color[i] == red | i in 1..nc]);
% The Spaniard owns the dog.
constraint forall ([nationality[i] == spa <-> pet[i] == dog | i in 1..nc]);
% Coffee is drunk in the green house.
constraint forall ([color[i] == green <-> drink[i] == coffee | i in 1..nc]);
% The Ukrainian drinks tea.
constraint forall ([nationality[i] == ukr <-> drink[i] == tea | i in 1..nc]);
% The green house is immediately to the right of the ivory house.
constraint forall ([color[i] == ivory -> if i<nc then color[i+1] == green else false endif | i in 1..nc]);
% The Old Gold smoker owns snails.
constraint forall ([smoke[i] == oldgold <-> pet[i] == snail | i in 1..nc]);
% Kools are smoked in the yellow house.
constraint forall ([smoke[i] == kools <-> color[i] == yellow | i in 1..nc]);
% Milk is drunk in the middle house.
constraint drink[3] == milk;
% The Norwegian lives in the first house.
constraint nationality[1] == nor;
% The man who smokes Chesterfields lives in the house next to the man with the fox.
constraint forall ([smoke[i] == chesterfields -> (if i>1 then pet[i-1] == fox else false endif // if i<nc then pet[i+1] == fox else false endif) | i in 1..nc]);
% Kools are smoked in the house next to the house where the horse is kept.
constraint forall ([smoke[i] == kools -> (if i>1 then pet[i-1] == horse else false endif // if i<nc then pet[i+1] == horse else false endif)| i in 1..nc]);
%The Lucky Strike smoker drinks orange juice.
constraint forall ([smoke[i] == luckystrike <-> drink[i] == orange | i in 1..nc]);
% The Japanese smokes Parliaments.
constraint forall ([nationality[i] == jap <-> smoke[i] == parliaments | i in 1..nc]);
% The Norwegian lives next to the blue house.
constraint forall ([color[i] == blue -> (if i > 1 then nationality[i-1] == nor else false endif // if i<nc then nationality[i+1] == nor else false endif) | i in 1..nc]);
solve satisfy;
Solución:
Compiling zebra.mzn
Running zebra.mzn
color = array1d(1..5 ,[4, 5, 1, 3, 2]);
nationality = array1d(1..5 ,[4, 3, 1, 2, 5]);
pet = array1d(1..5 ,[3, 4, 2, 1, 5]);
drink = array1d(1..5 ,[5, 2, 3, 4, 1]);
smoke = array1d(1..5 ,[2, 3, 1, 4, 5]);
----------
Finished in 47msec
Este es realmente un problema de resolución de restricciones. Puede hacerlo con un tipo generalizado de propagación de restricciones en programación lógica, como los lenguajes. Tenemos una demostración específicamente para el problema de Zebra en el sistema ALE (motor de lógica de atributos):
http://www.cs.toronto.edu/~gpenn/ale.html
Aquí está el enlace a la codificación de un rompecabezas Zebra simplificado:
http://www.cs.toronto.edu/~gpenn/ale/files/grammars/baby.pl
Hacer esto de manera eficiente es otro asunto.
La forma más fácil de resolver dichos problemas mediante programación es utilizar ciclos anidados en todas las permutaciones y verificar si el resultado satisface los predicados en la pregunta. Muchos de los predicados se pueden izar desde el bucle interno a bucles externos con el fin de reducir drásticamente la complejidad computacional hasta que la respuesta se pueda calcular en un tiempo razonable.
Aquí hay una solución simple de F # derivada de un artículo en la Revista F # :
let rec distribute y xs =
match xs with
| [] -> [[y]]
| x::xs -> (y::x::xs)::[for xs in distribute y xs -> x::xs]
let rec permute xs =
match xs with
| [] | [_] as xs -> [xs]
| x::xs -> List.collect (distribute x) (permute xs)
let find xs x = List.findIndex ((=) x) xs + 1
let eq xs x ys y = find xs x = find ys y
let nextTo xs x ys y = abs(find xs x - find ys y) = 1
let nations = ["British"; "Swedish"; "Danish"; "Norwegian"; "German"]
let houses = ["Red"; "Green"; "Blue"; "White"; "Yellow"]
let drinks = ["Milk"; "Coffee"; "Water"; "Beer"; "Tea"]
let smokes = ["Blend"; "Prince"; "Blue Master"; "Dunhill"; "Pall Mall"]
let pets = ["Dog"; "Cat"; "Zebra"; "Horse"; "Bird"]
[ for nations in permute nations do
if find nations "Norwegian" = 1 then
for houses in permute houses do
if eq nations "British" houses "Red" &&
find houses "Green" = find houses "White"-1 &&
nextTo nations "Norwegian" houses "Blue" then
for drinks in permute drinks do
if eq nations "Danish" drinks "Tea" &&
eq houses "Green" drinks "Coffee" &&
3 = find drinks "Milk" then
for smokes in permute smokes do
if eq houses "Yellow" smokes "Dunhill" &&
eq smokes "Blue Master" drinks "Beer" &&
eq nations "German" smokes "Prince" &&
nextTo smokes "Blend" drinks "Water" then
for pets in permute pets do
if eq nations "Swedish" pets "Dog" &&
eq smokes "Pall Mall" pets "Bird" &&
nextTo pets "Cat" smokes "Blend" &&
nextTo pets "Horse" smokes "Dunhill" then
yield nations, houses, drinks, smokes, pets ]
El resultado obtenido en 9ms es:
val it :
(string list * string list * string list * string list * string list) list =
[(["Norwegian"; "Danish"; "British"; "German"; "Swedish"],
["Yellow"; "Blue"; "Red"; "Green"; "White"],
["Water"; "Tea"; "Milk"; "Coffee"; "Beer"],
["Dunhill"; "Blend"; "Pall Mall"; "Prince"; "Blue Master"],
["Cat"; "Horse"; "Bird"; "Zebra"; "Dog"])]
Otra solución Python, esta vez usando PyKE Python (Python Knowledge Engine). Por supuesto, es más detallado que utilizar el módulo de "restricción" de Python en la solución de @JFSebastian, pero ofrece una comparación interesante para cualquiera que busque un motor de conocimiento sin procesar para este tipo de problema.
clues.kfb
categories( POSITION, 1, 2, 3, 4, 5 ) # There are five houses.
categories( HOUSE_COLOR, blue, red, green, white, yellow ) # Each house has its own unique color.
categories( NATIONALITY, Norwegian, German, Dane, Swede, English ) # All house owners are of different nationalities.
categories( PET, birds, dog, cats, horse, zebra ) # They all have different pets.
categories( DRINK, tea, coffee, milk, beer, water ) # They all drink different drinks.
categories( SMOKE, Blend, Prince, ''Blue Master'', Dunhill, ''Pall Mall'' ) # They all smoke different cigarettes.
related( NATIONALITY, English, HOUSE_COLOR, red ) # The English man lives in the red house.
related( NATIONALITY, Swede, PET, dog ) # The Swede has a dog.
related( NATIONALITY, Dane, DRINK, tea ) # The Dane drinks tea.
left_of( HOUSE_COLOR, green, HOUSE_COLOR, white ) # The green house is on the left side of the white house.
related( DRINK, coffee, HOUSE_COLOR, green ) # They drink coffee in the green house.
related( SMOKE, ''Pall Mall'', PET, birds ) # The man who smokes Pall Mall has birds.
related( SMOKE, Dunhill, HOUSE_COLOR, yellow ) # In the yellow house they smoke Dunhill.
related( POSITION, 3, DRINK, milk ) # In the middle house they drink milk.
related( NATIONALITY, Norwegian, POSITION, 1 ) # The Norwegian lives in the first house.
next_to( SMOKE, Blend, PET, cats ) # The man who smokes Blend lives in the house next to the house with cats.
next_to( SMOKE, Dunhill, PET, horse ) # In the house next to the house where they have a horse, they smoke Dunhill.
related( SMOKE, ''Blue Master'', DRINK, beer ) # The man who smokes Blue Master drinks beer.
related( NATIONALITY, German, SMOKE, Prince ) # The German smokes Prince.
next_to( NATIONALITY, Norwegian, HOUSE_COLOR, blue ) # The Norwegian lives next to the blue house.
next_to( DRINK, water, SMOKE, Blend ) # They drink water in the house next to the house where they smoke Blend.
relations.krb
#############
# Categories
# Foreach set of categories, assert each type
categories
foreach
clues.categories($category, $thing1, $thing2, $thing3, $thing4, $thing5)
assert
clues.is_category($category, $thing1)
clues.is_category($category, $thing2)
clues.is_category($category, $thing3)
clues.is_category($category, $thing4)
clues.is_category($category, $thing5)
#########################
# Inverse Relationships
# Foreach A=1, assert 1=A
inverse_relationship_positive
foreach
clues.related($category1, $thing1, $category2, $thing2)
assert
clues.related($category2, $thing2, $category1, $thing1)
# Foreach A!1, assert 1!A
inverse_relationship_negative
foreach
clues.not_related($category1, $thing1, $category2, $thing2)
assert
clues.not_related($category2, $thing2, $category1, $thing1)
# Foreach "A beside B", assert "B beside A"
inverse_relationship_beside
foreach
clues.next_to($category1, $thing1, $category2, $thing2)
assert
clues.next_to($category2, $thing2, $category1, $thing1)
###########################
# Transitive Relationships
# Foreach A=1 and 1=a, assert A=a
transitive_positive
foreach
clues.related($category1, $thing1, $category2, $thing2)
clues.related($category2, $thing2, $category3, $thing3)
check unique($thing1, $thing2, $thing3) /
and unique($category1, $category2, $category3)
assert
clues.related($category1, $thing1, $category3, $thing3)
# Foreach A=1 and 1!a, assert A!a
transitive_negative
foreach
clues.related($category1, $thing1, $category2, $thing2)
clues.not_related($category2, $thing2, $category3, $thing3)
check unique($thing1, $thing2, $thing3) /
and unique($category1, $category2, $category3)
assert
clues.not_related($category1, $thing1, $category3, $thing3)
##########################
# Exclusive Relationships
# Foreach A=1, assert A!2 and A!3 and A!4 and A!5
if_one_related_then_others_unrelated
foreach
clues.related($category, $thing, $category_other, $thing_other)
check unique($category, $category_other)
clues.is_category($category_other, $thing_not_other)
check unique($thing, $thing_other, $thing_not_other)
assert
clues.not_related($category, $thing, $category_other, $thing_not_other)
# Foreach A!1 and A!2 and A!3 and A!4, assert A=5
if_four_unrelated_then_other_is_related
foreach
clues.not_related($category, $thing, $category_other, $thingA)
clues.not_related($category, $thing, $category_other, $thingB)
check unique($thingA, $thingB)
clues.not_related($category, $thing, $category_other, $thingC)
check unique($thingA, $thingB, $thingC)
clues.not_related($category, $thing, $category_other, $thingD)
check unique($thingA, $thingB, $thingC, $thingD)
# Find the fifth variation of category_other.
clues.is_category($category_other, $thingE)
check unique($thingA, $thingB, $thingC, $thingD, $thingE)
assert
clues.related($category, $thing, $category_other, $thingE)
###################
# Neighbors: Basic
# Foreach "A left of 1", assert "A beside 1"
expanded_relationship_beside_left
foreach
clues.left_of($category1, $thing1, $category2, $thing2)
assert
clues.next_to($category1, $thing1, $category2, $thing2)
# Foreach "A beside 1", assert A!1
unrelated_to_beside
foreach
clues.next_to($category1, $thing1, $category2, $thing2)
check unique($category1, $category2)
assert
clues.not_related($category1, $thing1, $category2, $thing2)
###################################
# Neighbors: Spatial Relationships
# Foreach "A beside B" and "A=(at-edge)", assert "B=(near-edge)"
check_next_to_either_edge
foreach
clues.related(POSITION, $position_known, $category, $thing)
check is_edge($position_known)
clues.next_to($category, $thing, $category_other, $thing_other)
clues.is_category(POSITION, $position_other)
check is_beside($position_known, $position_other)
assert
clues.related(POSITION, $position_other, $category_other, $thing_other)
# Foreach "A beside B" and "A!(near-edge)" and "B!(near-edge)", assert "A!(at-edge)"
check_too_close_to_edge
foreach
clues.next_to($category, $thing, $category_other, $thing_other)
clues.is_category(POSITION, $position_edge)
clues.is_category(POSITION, $position_near_edge)
check is_edge($position_edge) and is_beside($position_edge, $position_near_edge)
clues.not_related(POSITION, $position_near_edge, $category, $thing)
clues.not_related(POSITION, $position_near_edge, $category_other, $thing_other)
assert
clues.not_related(POSITION, $position_edge, $category, $thing)
# Foreach "A beside B" and "A!(one-side)", assert "A=(other-side)"
check_next_to_with_other_side_impossible
foreach
clues.next_to($category, $thing, $category_other, $thing_other)
clues.related(POSITION, $position_known, $category_other, $thing_other)
check not is_edge($position_known)
clues.not_related($category, $thing, POSITION, $position_one_side)
check is_beside($position_known, $position_one_side)
clues.is_category(POSITION, $position_other_side)
check is_beside($position_known, $position_other_side) /
and unique($position_known, $position_one_side, $position_other_side)
assert
clues.related($category, $thing, POSITION, $position_other_side)
# Foreach "A left of B"...
# ... and "C=(position1)" and "D=(position2)" and "E=(position3)"
# ~> assert "A=(other-position)" and "B=(other-position)+1"
left_of_and_only_two_slots_remaining
foreach
clues.left_of($category_left, $thing_left, $category_right, $thing_right)
clues.related($category_left, $thing_left_other1, POSITION, $position1)
clues.related($category_left, $thing_left_other2, POSITION, $position2)
clues.related($category_left, $thing_left_other3, POSITION, $position3)
check unique($thing_left, $thing_left_other1, $thing_left_other2, $thing_left_other3)
clues.related($category_right, $thing_right_other1, POSITION, $position1)
clues.related($category_right, $thing_right_other2, POSITION, $position2)
clues.related($category_right, $thing_right_other3, POSITION, $position3)
check unique($thing_right, $thing_right_other1, $thing_right_other2, $thing_right_other3)
clues.is_category(POSITION, $position4)
clues.is_category(POSITION, $position5)
check is_left_right($position4, $position5) /
and unique($position1, $position2, $position3, $position4, $position5)
assert
clues.related(POSITION, $position4, $category_left, $thing_left)
clues.related(POSITION, $position5, $category_right, $thing_right)
#########################
fc_extras
def unique(*args):
return len(args) == len(set(args))
def is_edge(pos):
return (pos == 1) or (pos == 5)
def is_beside(pos1, pos2):
diff = (pos1 - pos2)
return (diff == 1) or (diff == -1)
def is_left_right(pos_left, pos_right):
return (pos_right - pos_left == 1)
driver.py (realmente más grande, pero esta es la esencia)
from pyke import knowledge_engine
engine = knowledge_engine.engine(__file__)
engine.activate(''relations'')
try:
natl = engine.prove_1_goal(''clues.related(PET, zebra, NATIONALITY, $nationality)'')[0].get(''nationality'')
except Exception, e:
natl = "Unknown"
print "== Who owns the zebra? %s ==" % natl
Muestra de salida:
$ python driver.py
== Who owns the zebra? German ==
# Color Nationality Pet Drink Smoke
=======================================================
1 yellow Norwegian cats water Dunhill
2 blue Dane horse tea Blend
3 red English birds milk Pall Mall
4 green German zebra coffee Prince
5 white Swede dog beer Blue Master
Calculated in 1.19 seconds.
Fuente: https://github.com/DreadPirateShawn/pyke-who-owns-zebra
Un cartel ya mencionó que Prolog es una solución potencial. Esto es cierto, y es la solución que usaría. En términos más generales, este es un problema perfecto para un sistema de inferencia automática. Prolog es un lenguaje de programación lógica (e intérprete asociado) que forma dicho sistema. Básicamente permite la conclusión de hechos a partir de declaraciones hechas usando la Lógica de primer orden . FOL es básicamente una forma más avanzada de lógica proposicional. Si decides que no quieres usar Prolog, puedes usar un sistema similar de tu propia creación usando una técnica como modus ponens para realizar las conclusiones.
Por supuesto, necesitarás agregar algunas reglas sobre las cebras, ya que no se menciona en ninguna parte ... Creo que la intención es que puedas descubrir las otras 4 mascotas y así deducir que la última es la cebra. Deberá agregar reglas que indiquen que una cebra es una de las mascotas, y que cada casa solo puede tener una mascota. Obtener este tipo de conocimiento de "sentido común" en un sistema de inferencia es el mayor obstáculo para usar la técnica como una verdadera IA. Hay algunos proyectos de investigación, como Cyc, que intentan dar ese conocimiento común a través de la fuerza bruta. Se han encontrado con una cantidad interesante de éxito.