Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/usr/bin/env python2
- # -*- coding: utf-8 -*-
- import re
- length = 7
- def get_optimal_min_first(key_min, key_max, pos, changes):
- code = '<' * (-key_min)
- for pos in xrange(-key_min, key_max + 1):
- try:
- code += '+' * changes[pos] + '-' * (-changes[pos])
- except KeyError:
- pass
- if pos != key_max:
- code += '>'
- code += '<' * (key_max - pos)
- return code
- def get_optimal_max_first(key_min, key_max, pos, changes):
- code = '>' * key_max
- for pos in xrange(key_max, key_min - 1, -1):
- try:
- code += '+' * changes[pos] + '-' * (-changes[pos])
- except KeyError:
- pass
- if pos != key_min:
- code += '<'
- code += '>' * (pos - key_min)
- return code
- def check_optimal(linear):
- pos = 0
- changes = {0: 0}
- for command in linear:
- if command == '+':
- changes[pos] += 1
- continue
- if command == '-':
- changes[pos] -= 1
- continue
- if command == '>':
- pos += 1
- elif command == '<':
- pos -= 1
- if not changes.has_key(pos):
- changes[pos] = 0
- key_min = min(0, pos)
- key_max = max(0, pos)
- for key in changes:
- if not changes[key]:
- continue
- if key < key_min:
- key_min = key
- if key > key_max:
- key_max = key
- value_change = sum(map(abs, changes.values()))
- optimal_min_first = get_optimal_min_first(key_min, key_max, pos, changes)
- optimal_max_first = get_optimal_max_first(key_min, key_max, pos, changes)
- if len(optimal_min_first) <= len(optimal_max_first):
- return linear == optimal_min_first
- else:
- return linear == optimal_max_first
- def check_program(program):
- for linear in re.finditer(r'[+-<>]+', program):
- if not check_optimal(linear.group()):
- return False
- return True
- # If we want to quickly calculate this values,
- # we can write normal dynamic programming
- def f(program, brace_lev):
- if len(program) == length:
- if brace_lev or program[-1] in '<>':
- return 0
- if not check_program(program):
- return 0
- return 1
- res = (
- f(program + '+', brace_lev) +
- f(program + '-', brace_lev) +
- f(program + '<', brace_lev) +
- f(program + '>', brace_lev)
- )
- if not program or program[-1] != ']':
- res += f(program + '[', brace_lev + 1)
- if brace_lev and program[-1] != '[':
- res += f(program + ']', brace_lev - 1)
- return res
- # Example:
- # I. A + B (length 7)
- # >[-<+>]
- print f('', 0)
- '''
- For length 7:
- 1). Any symbols:
- 279936
- 2). [Added] Correct braces:
- 42508
- 3). [Added] No "+" after "-", "-" after "+", "<" after ">", ">" after "<",
- "[" after "]":
- 15152
- 4). [Added] No "[]" combinations":
- > Comment: Programs with infinite loops may be excluded from treatment.
- 11024
- 5). [Added] No "<" and ">" in the end of program:
- 6830
- 6). [Added] Only optimal by length and right ordered linear combinations
- (except cycles):
- 3330
- Conclusion: Count of programs in bruteforce can be reduced by not less 84 times
- for length 7.
- '''
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement