Skip to content

Instantly share code, notes, and snippets.

@dpk dpk/mccarthy.py
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
You can’t perform that action at this time.