Python でSICP4.3 Nondeterministic Computing
あれ、思ったより綺麗に書けたぞ。
# Amb evaluator
# See http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#%_sec_4.3
# Global variable for amb evaluator
amb_variable_name = []
amb_possible = []
def comb(lol):
"""
make all combination from a list of lists
"""
if not lol:
yield []
else:
for x in lol[0]:
for y in comb(lol[1:]):
yield [x] + y
def amb(v, l):
"""
set global variable for amb evaluator
"""
amb_variable_name.append(v)
amb_possible.append(l)
return
def ambeval():
"""
amb evaluator
"""
for tp in comb(amb_possible):
# set variables
# ex: exec("baker = 0")
for i in range(len(amb_variable_name)):
s = amb_variable_name[i] + "= " + str(tp[i])
exec(s)
# check requirements
# ex: eval("baker != 5")
met = True
for f in require:
if not eval(f):
met = False
break
# all requiements met
if met:
yield tp
### USER FUNCTION ###
def make_distinct(list):
"""
make string like distinct?
(See http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#call_footnote_Temp_609 )
"""
s = ""
for i in range(len(list)):
for j in range(len(list)):
if i <= j:
continue
s += list[i] + " != " + list[j] + " and "
s += "True"
return s
### main
amb('baker', (1,2,3,4,5))
amb('cooper', (1,2,3,4,5))
amb('fletcher',(1,2,3,4,5))
amb('miller', (1,2,3,4,5))
amb('smith', (1,2,3,4,5))
require = ["baker != 5",
"cooper != 1",
"fletcher != 5",
"fletcher != 1",
"miller > cooper",
"abs(smith - fletcher) != 1",
"abs(fletcher - cooper) != 1",
]
# make_distinct resturns the string
# cooper != baker and fletcher != baker and fletcher != cooper and miller != baker and miller != cooper and miller != fletcher and smith != baker and smith != cooper and smith != fletcher and smith != miller and True
distinct = make_distinct(('baker','cooper','fletcher','miller','smith'),)
require.append(distinct)
# solve the problem!
for result in ambeval():
print "baker = %d, " % int(result[0]),
print "copper = %d, " % int(result[1]),
print "fletcher = %d, " % int(result[2]),
print "miller = %d, " % int(result[3]),
print "smith = %d" % int (result[4])
実行結果がこれ
YUKI.N>python dwelling.py
baker = 3, copper = 2, fletcher = 4, miller = 5, smith = 1
実際にかかった時間が2時間くらい。大半がgeneratorの勘違いで時間を食った。再帰呼び出しをしている中でyieldすると、再帰を一個戻るだけなんだ。ツリーの一番下でyieldしたら、一気に値を返してくれると思って、すごく悩んだ。分かってしまえば当たり前の話。
いらいらしていたら、回答を教えてくれた@kana1さんに感謝。
対話的環境は無いが、SICPのあのごちゃごちゃしたソースが、組み合わせを作るcomb、amb評価器を生成するamb、条件から解を求めるambevalの3つの関数だけでできるんだからたいした物だ。条件も、そのままPythonの文字列書けば良いんだし。Python恐るべし。
言語占いの問い1はYesで確定。
