TSabc 発言

¤³¤ó¤Ë¤Á¤Ï¡¢

| ¡¡¸½ºß¡¢²ÝÂê 1 ¤ËÂФ¹¤ë²òÅú¤ò Web ¾å¤Ë¸ø³«¤·¤Æ¤¤¤Þ¤¹¤¬
| 
|   http://rakunet.org/TSNET/topics/samp.html
| 
| ¤»¤Ã¤«¤¯¤Ê¤Î¤Ç¡¢²ÝÂê 2-4 ¤Î²òÅú¤Ë¤Ä¤¤¤Æ¤â¡¢Æ±ÍͤÎÊýË¡¤Ç¸ø³«¤·¤¿¤¤¤È»×¤¤
| ¤Þ¤¹¡£¤Þ¤º¤¤¤È¤«¡¢¤³¤ÎÉôʬ¤Ï¸ø³«¤·¤Ê¤¤¤Ç¤Û¤·¤¤¤È¤¤¤¦¤³¤È¤¬¤¢¤ì¤Ð¸À¤Ã¤Æ¤¯
| ¤À¤µ¤¤¡£
| 

¤³¤¤¤Ä¤â´õ˾¤·¤Þ¤¹¡£¡Ê¤ªÂꤽ¤Î£´¡Ë

step1.0 -- ¥Ç¡¼¥¿¤ÎʤӤòÊѹ¹¤·¤Ê¤¤ÈÇ
step1.1 -- step3¤Ç³èÍѤ·¤Æ¤¤¤ëparse_expr()¤Èformat_expr()¤ÎÆ°ºî³ÎǧÈÇ
           (Æ°ºî·ë²Ì¤Ïstep1.0¤ÈƱ¤¸)
step2 -- Á´¤Æ¤ÎʤӤò¥Á¥§¥Ã¥¯¤·¤Æ¤¤¤ëÈÇ¡£
step3 -- step2¤«¤é¸ò´¹Ë¡Â§¤Ë½¾¤¤½ÅÊ£¥Á¥§¥Ã¥¯¤ò¤·¤Æ¤¤¤ëÈÇ
         (¤Ç¤â¡¢ÉÔ´°Á´)

--^ ticket5.py
_chk = {}
def result(number):
  if number == 10: return 1
  else: return 0
def exists(expr):
  if _chk.has_key(expr): return 0
  for e in generate_line(expr):
    _chk[tuple(e)] = 1
  return 1
def format_expr(expr):
  rtn = []
  for e in expr:
    if e[0] == '-':
      rtn = rtn+list(e)
    else:
      rtn = rtn+['+']+list(e)
  return rtn[1:]
def parse_expr(expr):
  expr = ['+']+expr+['+']
  rtn = []
  wrk = []
  for e in expr:
    if e in ('+','-'):
      if wrk:
        rtn.append(tuple(wrk))
        wrk = []
      if e == '-':
        wrk.append(e)
    else:
      wrk.append(e)
  return tuple(rtn)
def calculate(expr):
  rtn = 0
  for e in expr:
    try:
      rtn = rtn + eval(' '.join(e))
    except Exception,err:
      print err,e
  return rtn
def generate_expr(list):
  expr = []
  if len(list) <= 1: return [[list[0]]]
  for op in ('*','/','+','-'):
    expr += [ [list[0]]+[op]+e for e in generate_expr(list[1:]) ]
  return expr
def generate_line(list):
  line = []
  if len(list) == 1: return [[list[0]]]
  for i in xrange(len(list)):
    line += [ [list[i]]+e for e in generate_line(list[:i]+list[i+1:]) ]
  return line
  
if __name__ == '__main__':
  problem = ['8.0','4.0','2.0','1.0']
  print '#### step1.0 #### begin'
  for expr in generate_expr(problem):
    if result(eval(' '.join(expr))):
      print '10 =',' '.join(expr)
  print '#### step1.1 #### begin'
  for expr in map(parse_expr,generate_expr(problem)):
    if result(calculate(expr)):
      print '10 =',' '.join(format_expr(expr))
  print '#### step1 #### end'
  buf = raw_input('--- hit key ---')
  print '#### step2 #### begin'
  for line in generate_line(problem):
    for expr in generate_expr(line):
      if result(eval(' '.join(expr))):
        print '10 =',' '.join(expr)
  print '#### step2 #### end'
  buf = raw_input('--- hit key ---')
  print '#### step3 #### begin'
  for line in generate_line(problem):
    for expr in filter(exists,map(parse_expr,generate_expr(line))):
      if result(calculate(expr)):
        print '10 =',' '.join(format_expr(expr))
  print '#### step3 #### end'
  buf = raw_input('--- all done ---')
--$