Einstein Rätsel

Stellt hier eure Projekte vor.
Internetseiten, Skripte, und alles andere bzgl. Python.
Antworten
BlackJack

Montag 22. August 2005, 23:18

In der deutschsprachigen Python Newsgroup wurde ein Link zum Einstein Rätsel veröffentlicht, verbunden mit der Frage, wie man das in Python lösen könnte. Hier ist meine Lösung, wobei der Haupteil der Arbeit von Gustavo Niemeyer's `constraint` Modul erledigt wird.

Code: Alles auswählen

#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""This module solves Einstein's riddle.

Requires Gustavo Niemeyer's `constraint` module.
"""
import time
import pickle
from constraint import Problem, AllDifferentConstraint

__author__ = "Marc 'BlackJack' Rintsch"
__version__ = '0.1.0'
__date__ = '$Date: 2005-08-22 13:20:15 +0200 (Mon, 22 Aug 2005) $'
__revision__ = '$Rev: 747 $'


def varnames(name):
    """Creates a list of variable names by adding a number suffix from 1 to 5
    to the `name`.
    """
    return ['%s_%d' % (name, i + 1) for i in xrange(5)]


def relates(value_a, value_b):
    """Returns a constraint function that tests if two variables from different
    domains but for the same house contain `value_a` and `value_b`.
    """
    def relates_constraint(*args):
        """Takes 10 arguments, 5 values for the first domain and 5 for the
        second.  The values are ordered by house number.
        """
        for item_a, item_b in zip(args[:5], args[5:]):
            if item_a == value_a and item_b == value_b:
                return True
        return False
    return relates_constraint


def neighbour(value_a, value_b):
    """Returns a constraint function that checks if the house that has
    `value_a` is next to a house that has `value_b`.
    """
    def neighbour_constraint(*args):
        """Takes 10 arguments, 5 values for the first domain and 5 for the
        second.  The values are ordered by house number.
        """
        a_values = args[:5]
        b_values = args[5:]
        for item_a, item_b in (zip(a_values, b_values[1:])
                               + zip(a_values[1:], b_values)):
            if item_a == value_a and item_b == value_b:
                return True
        return False
    return neighbour_constraint


def green_left_of_white(*args):
    """Tests if the green house has a lower house number than the white
    house.
    """
    house = dict((color, house_nr) for house_nr, color in enumerate(args))
    return house['green'] < house['white']


def main():
    """Main function."""
    # 
    # Variables.
    # 
    nationality_vars = varnames('nationality')
    color_vars = varnames('color')
    drink_vars = varnames('drink')
    cigarette_vars = varnames('cigarette')
    pet_vars = varnames('pet')

    # 
    # Domains.
    # 
    nationalities = ('british', 'danish', 'german', 'norwegian', 'swedish')
    colors = ('blue', 'green', 'red', 'white', 'yellow')
    drinks = ('beer', 'coffee', 'milk', 'tea', 'water')
    cigarettes = ('Dunhill', 'Pall Mall', 'Malboro', 'Rothmanns', 'Winfield')
    pets = ('bird', 'cat', 'dog', 'fish', 'horse')
    
    # 
    # Houston, we have a problem.
    # 
    problem = Problem()
    
    # 
    # Add the variables and their domains to the problem.
    # 
    for variables, domain in ((nationality_vars, nationalities),
                              (color_vars, colors),
                              (drink_vars, drinks),
                              (cigarette_vars, cigarettes),
                              (pet_vars, pets)):
        problem.addVariables(variables, domain)
    
    problem.addConstraint(AllDifferentConstraint())
    
    # 
    # The hints of the riddle as tuples of constraint function and sequence
    # of involved variables.
    # 
    constraints = ((relates('british', 'red'), nationality_vars + color_vars),
                   (relates('swedish', 'dog'), nationality_vars + pet_vars),
                   (relates('danish', 'tea'), nationality_vars + drink_vars),
                   (green_left_of_white, color_vars),
                   (relates('green', 'coffee'), color_vars + drink_vars),
                   (relates('Pall Mall', 'bird'), cigarette_vars + pet_vars),
                   (lambda a: a == 'milk', ['drink_3']),
                   (relates('yellow', 'Dunhill'), color_vars + cigarette_vars),
                   (lambda a: a == 'norwegian', ['nationality_1']),
                   (neighbour('Malboro', 'cat'), cigarette_vars + pet_vars),
                   (neighbour('horse', 'Dunhill'), pet_vars + cigarette_vars),
                   (relates('Winfield', 'beer'), cigarette_vars + drink_vars),
                   (neighbour('norwegian', 'blue'),
                    nationality_vars + color_vars),
                   (relates('german', 'Rothmanns'),
                    nationality_vars + cigarette_vars),
                   (neighbour('Malboro', 'water'), cigarette_vars + drink_vars))
    
    for constraint_func, variables in constraints:
        problem.addConstraint(constraint_func, variables)
    
    # 
    # Solve the problem and save the solutions as pickle.
    # 
    start_time = time.time()
    
    print 'Searching solutions...'
    solutions = list()
    for solution in problem.getSolutionIter():
        print solution
        solutions.append(solution)
    
    elapsed_time = time.time() - start_time
    print 'Found %d solutions in %d seconds.' % (len(solutions), elapsed_time)
    
    solution_file = open('solutions.dat', 'wb')
    pickle.dump(dict(solutions=solutions), solution_file)
    solution_file.close()


if __name__ == '__main__':
    main()
Qbi
User
Beiträge: 57
Registriert: Mittwoch 25. Juni 2003, 14:04
Kontaktdaten:

Donnerstag 8. September 2005, 16:31

BlackJack hat geschrieben:In der deutschsprachigen Python Newsgroup wurde ein Link zum Einstein Rätsel veröffentlicht, verbunden mit der Frage, wie man das in Python lösen könnte. Hier ist meine Lösung, wobei der Haupteil der Arbeit von Gustavo Niemeyer's `constraint` Modul erledigt wird.
Der ganze Fred kann auch direkt bei Google Groups nachgelesen werden.
Jens Kubieziel http://www.kubieziel.de
http://www.kubieziel.de/pythonwiki/
Antworten