« 言語占い | Main | IT技術者として生き抜くための十ヶ条 »

2008.04.01

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で確定。

|

« 言語占い | Main | IT技術者として生き抜くための十ヶ条 »

Comments

Post a comment



(Not displayed with comment.)




TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/18154/40716010

Listed below are links to weblogs that reference Python でSICP4.3 Nondeterministic Computing:

« 言語占い | Main | IT技術者として生き抜くための十ヶ条 »