mccarthy.py

"""
McCarthy's amb operator (kind of) implemented in Python
ᚾᚪᚻᛏ᛫ᛁᛋ᛫ᚦᚱᚫᛞᛋᛁᚳᚩᚱ
very unoptimized, much slow, wow
"""

class amb:
    def __init__(self, *values):
        self.values = tuple(values)
        if len(self.values) < 2:
            raise ValueError('amb must have at least 2 options')
        
        self.value = self.values[0]
    
    def __iter__(self):
        for value in self.values:
            self.value = value
            yield value

class SolutionFound(Exception): pass
class NoSolutionFound(Exception): pass
class requirements:
    def __init__(self, variables):
        self.variables = list(variables)
        self.requirements = []
    
    def require(self, requirement):
        self.requirements.append(requirement)
    
    def resolved(self):
        return all(requirement() for requirement in self.requirements)
    
    def resolve(self):
        def resolve_variable(n):
            for value in self.variables[n]:
                if self.resolved():
                    raise SolutionFound
                elif n < (len(self.variables) - 1):
                    resolve_variable(n + 1)
        
        try:
            resolve_variable(0)
        except SolutionFound:
            return
        
        raise NoSolutionFound

multiple_dwelling.py

"""
the multiple-dwelling problem from SICP
"""

from mccarthy import amb, requirements

def distinctp(seq):
    return len(set(seq)) == len(seq)

def solve():
    people = {}
    for person in ('baker', 'cooper', 'fletcher', 'miller', 'smith'):
        people[person] = amb(1, 2, 3, 4, 5)
    puzzle = requirements(people.values())
    
    puzzle.require(lambda: distinctp([floor.value for floor in people.values()]))
    puzzle.require(lambda: people['baker'].value != 5)
    puzzle.require(lambda: people['cooper'].value != 1)
    puzzle.require(lambda: people['fletcher'].value not in {5, 1})
    puzzle.require(lambda: people['miller'].value > people['cooper'].value)
    puzzle.require(lambda: abs(people['smith'].value - people['fletcher'].value) != 1)
    puzzle.require(lambda: abs(people['fletcher'].value - people['cooper'].value) != 1)
    
    puzzle.resolve()
    return {name: floor.value for name, floor in people.items()}

if __name__ == '__main__':
    for name, floor in solve().items():
        print('%s: %d' % (name, floor))