Если вы намерены применить операцию к определенному классу объектов, вы можете просто переопределить оператор, который соответствует вашей функции, ближайший ... например, переопределение __eq__()
переопределит оператор ==
, чтобы вернуть все, что вы хотеть. Это работает практически для всех операторов.
Вот решение в Python на основе программирования с использованием ограничительного языка:
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()
Вывод:
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
требуется 0,6 секунды (ЦП 1.5 ГГц) для нахождения решения.
ответ является "немецким языком, владеет зеброй".
Для установки constraint
модуль через pip
: победите ограничение Python установки
Для установки вручную:
загрузка:
(Linux/Mac/BSD):
$ bzip2 - CD python-constraint-1.2.tar.bz2 | tar xvf -
извлечение (Windows, с 7zip ):
> 7z e python-constraint-1.2.tar.bz2
> 7z установка e python-constraint-1.2.tar
:
Python cd python-constraint-1.2
$ $ setup.py установка
Вот то, как я пошел бы об этом. Сначала я генерировал бы все заказанные n-кортежи
(housenumber, color, nationality, pet, drink, smoke)
5^6 тех, 15625, легко управляемый. Затем я отфильтровал бы простые булевы условия. существует десять из них, и каждый из тех, которые Вы ожидали бы отфильтровывать 8/25 условий (1/25 условий содержат шведа с собакой, 16/25, содержит нешведа с несобакой). Конечно, они весьма зависят, но после фильтрации их там не должны быть многие оставленные.
После этого, у Вас есть хорошая проблема графика. Создайте график с каждым узлом, представляющим один из остающихся n-кортежей. Добавьте края к графику, если два конца содержат дубликаты в некотором положении n-кортежа или нарушают какие-либо 'позиционные' ограничения (существует пять из тех). Оттуда Вы почти домой, ищете график независимый набор пяти узлов (ни с одним из узлов, соединенных краями). Если нет слишком многих, Вы могли бы возможно просто исчерпывающе генерировать все 5 кортежей n-кортежей и просто отфильтровать их снова.
Это могло быть хорошим кандидатом на гольф кода. Кто-то может, вероятно, решить его в одной строке с чем-то как haskell :)
запоздалая мысль: начальная передача фильтра может также устранить информацию из позиционных ограничений. Не много (1/25), но все еще значительный.
Один плакат уже упомянул, что Пролог является потенциальным решением. Это верно, и это - решение, которое я использовал бы. В более общих чертах это - идеальная проблема для автоматизированной системы вывода. Пролог является языком логического программирования (и связанный интерпретатор), которые формируют такую систему. Это в основном позволяет завершать фактов от операторов, сделанных с помощью Логика первого порядка . FOL является в основном более усовершенствованной формой логики высказываний. Если Вы решаете, что не хотите использовать Пролог, Вы могли бы использовать аналогичную систему своего собственного создания с помощью техники такой в качестве утверждающий модус для выполнения делать выводы.
необходимо будет, конечно, добавить некоторые правила о зебрах, так как это не упоминается нигде... Я полагаю, что намерение состоит в том, что можно выяснить другие 4 домашних животных и таким образом вывести последнее, зебра? Вы захотите добавить, управляет тем государством, зебра является одним из домашних животных, и каждый дом может только иметь одно домашнее животное. Получение этого вида "разумного" знания в систему вывода является главным препятствием к использованию техники как истинный AI. Существуют некоторые исследовательские проекты, такие как Cyc, которые пытаются дать такую общепринятую истину через грубую силу. Они встретились с интересной суммой успеха.
Вот выборка от полное решение использование NSolver, отправленный в Загадка Einstein’s в 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));
Это - действительно ограничительная проблема решения. Можно сделать это с обобщенным видом ограничительного распространения в логическом программировании как языки. У нас есть демонстрация специально для проблемы Зебры под мухой (припишите логический механизм), система:
http://www.cs.toronto.edu/~gpenn/ale.html
Вот ссылка на кодирование упрощенной загадки Зебры:
http://www.cs.toronto.edu/~gpenn/ale/files/grammars/baby.pl
, Чтобы сделать это эффективно - другой вопрос.