Advertisement
hxrussia

Estimate of count of BF programs with defined length

Nov 20th, 2013
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.32 KB | None | 0 0
  1. #!/usr/bin/env python2
  2. # -*- coding: utf-8 -*-
  3.  
  4. import re
  5.  
  6. length = 7
  7.  
  8. def get_optimal_min_first(key_min, key_max, pos, changes):
  9.     code = '<' * (-key_min)
  10.     for pos in xrange(-key_min, key_max + 1):
  11.         try:
  12.             code += '+' * changes[pos] + '-' * (-changes[pos])
  13.         except KeyError:
  14.             pass
  15.         if pos != key_max:
  16.             code += '>'
  17.     code += '<' * (key_max - pos)
  18.     return code
  19.  
  20. def get_optimal_max_first(key_min, key_max, pos, changes):
  21.     code = '>' * key_max
  22.     for pos in xrange(key_max, key_min - 1, -1):
  23.         try:
  24.             code += '+' * changes[pos] + '-' * (-changes[pos])
  25.         except KeyError:
  26.             pass
  27.         if pos != key_min:
  28.             code += '<'
  29.     code += '>' * (pos - key_min)
  30.     return code
  31.  
  32. def check_optimal(linear):
  33.     pos = 0
  34.     changes = {0: 0}
  35.     for command in linear:
  36.         if command == '+':
  37.             changes[pos] += 1
  38.             continue
  39.         if command == '-':
  40.             changes[pos] -= 1
  41.             continue
  42.            
  43.         if command == '>':
  44.             pos += 1
  45.         elif command == '<':
  46.             pos -= 1
  47.         if not changes.has_key(pos):
  48.             changes[pos] = 0
  49.    
  50.     key_min = min(0, pos)
  51.     key_max = max(0, pos)
  52.     for key in changes:
  53.         if not changes[key]:
  54.             continue
  55.         if key < key_min:
  56.             key_min = key
  57.         if key > key_max:
  58.             key_max = key
  59.     value_change = sum(map(abs, changes.values()))
  60.    
  61.     optimal_min_first = get_optimal_min_first(key_min, key_max, pos, changes)
  62.     optimal_max_first = get_optimal_max_first(key_min, key_max, pos, changes)
  63.     if len(optimal_min_first) <= len(optimal_max_first):
  64.         return linear == optimal_min_first
  65.     else:
  66.         return linear == optimal_max_first
  67.  
  68. def check_program(program):
  69.     for linear in re.finditer(r'[+-<>]+', program):
  70.         if not check_optimal(linear.group()):
  71.             return False
  72.     return True
  73.  
  74. # If we want to quickly calculate this values,
  75. # we can write normal dynamic programming
  76. def f(program, brace_lev):
  77.     if len(program) == length:
  78.         if brace_lev or program[-1] in '<>':
  79.             return 0
  80.         if not check_program(program):
  81.             return 0
  82.         return 1
  83.     res = (
  84.         f(program + '+', brace_lev) +
  85.         f(program + '-', brace_lev) +
  86.         f(program + '<', brace_lev) +
  87.         f(program + '>', brace_lev)
  88.     )
  89.     if not program or program[-1] != ']':
  90.         res += f(program + '[', brace_lev + 1)
  91.     if brace_lev and program[-1] != '[':
  92.         res += f(program + ']', brace_lev - 1)
  93.     return res
  94.  
  95. # Example:
  96. # I. A + B (length 7)
  97. #    >[-<+>]
  98. print f('', 0)
  99.  
  100. '''
  101. For length 7:
  102. 1). Any symbols:
  103.    279936
  104. 2). [Added] Correct braces:
  105.    42508
  106. 3). [Added] No "+" after "-", "-" after "+", "<" after ">", ">" after "<",
  107.            "[" after "]":
  108.    15152
  109. 4). [Added] No "[]" combinations":
  110.    > Comment: Programs with infinite loops may be excluded from treatment.
  111.    11024
  112. 5). [Added] No "<" and ">" in the end of program:
  113.    6830
  114. 6). [Added] Only optimal by length and right ordered linear combinations
  115.            (except cycles):
  116.    3330
  117. Conclusion: Count of programs in bruteforce can be reduced by not less 84 times
  118.            for length 7.
  119. '''
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement