Skip to content

Instantly share code, notes, and snippets.

@dpk
Last active Aug 29, 2015
Embed
What would you like to do?
"""
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
"""
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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment