与えた条件を満たす候補
Posted feedbacks - Python
お題の入力の条件を、'not'を削除すると3つの'or'または'and'からなるもの、と解釈しましたが違う？ 'not'の処理のみ最初に済ませ、あとはカッコで優先順位をかえたevalで手抜きしました。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | def f(a):
for i in range(16):
o = [i/8==0, (i%8)/4==0, (i%4)/2==0, i%2==0]
b = list(a)
x = list(o)
while 'not' in b:
i = b.index('not')
x[i] = not x[i]
b.pop(i)
if eval('(((%s %s %s) %s %s) %s %s)' % (x[0], b[0], x[1], b[1], x[2], b[2], x[3])):
print o
f(['and', 'or', 'not', 'and'])
f(['not', 'not', 'and', 'or', 'not', 'not', 'not', 'and'])
|
ん、任意の長さを処理する必要があるのか。 では、あらためて。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | def f2(i):
return [[x] + b for x in (True, False) for b in f2(i-1)] if i > 1 else [[True], [False]]
def f(a):
for o in f2(len(a)-a.count('not')+1):
b = list(a)
x = list(o)
while 'not' in b:
i = b.index('not')
x[i] = not x[i]
b.pop(i)
while b:
x = [(x[0] and x[1]) if b.pop(0) == 'and' else (x[0] or x[1])] + x[2:]
if x[0]:
print o
f(['and', 'or', 'not', 'and'])
f(['not', 'not', 'not'])
|
with文を使ってるので、Python2.5以降必須です。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | from __future__ import with_statement
from contextlib import contextmanager
def solve(exprs):
stack = []
def traverse(i, values):
# successive `not'
invert = False
while i > 0 and exprs[i - 1] == "not":
invert = not(invert)
i -= 1
@contextmanager
def append(value):
stack.append(value ^ invert)
yield
stack.pop()
if i == 0: # no expressions any more
for value in values:
with append(value):
print tuple(reversed(stack))
else: # and / or
which = {"and": True, "or": False}[exprs[i - 1]]
for value in values:
if which == value:
with append(which):
traverse(i - 1, (which,))
else:
with append(which):
traverse(i - 1, (not(which),))
with append(not(which)):
traverse(i - 1, (not(which), which))
traverse(len(exprs), (True,))
def main():
solve(['and', 'or', 'not', 'and'])
if __name__ == '__main__':
main()
|
演算子定義でごまかし。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | class Bit(object):
def __init__(self, value):
self.value = bool(value)
def __and__(self, other):
return Bit(self and other)
def __or__(self, other):
return Bit(self or other)
def __invert__(self):
return Bit(not self)
def __nonzero__(self):
return self.value
def __str__(self):
return str(self.value)
class BitSet(object):
def __init__(self, i, n):
self.i = i
self.n = n
def __getitem__(self, i):
return Bit(self.i & (1 << i))
def __str__(self):
return str(tuple([bool(self[i]) for i in xrange(self.n)]))
def build_exp(operators):
table = { 'and': '&', 'or': '|', 'not': '~' }
exp = []
i = 0
for op in operators:
if op != 'not':
exp.extend(('x[%d]' % (i), table[op]))
i += 1
else:
exp.append(table[op])
exp.append('x[%d]' % (1 << i))
i += 1
return (''.join(exp), i)
def solve(operators):
exp, n = build_exp(operators)
print exp
code = compile(exp, '', 'eval')
for i in xrange(1 << n):
x = BitSet(i, n)
if eval(code):
print x
if __name__ == '__main__':
solve('and or not and'.split())
|
もうひとつ
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | import itertools
def build_exp(operators):
if len(operators) == 0:
return '(x & 0x01)'
n = len(operators) - operators.count('not') + 1
stack = ['(x & 0x%02x)' % (1 << i) for i in xrange(n)]
offset = 0
for i in xrange(len(operators)):
if operators[i] == 'not':
stack[offset] = 'not %s' % stack[offset]
else:
offset += 1
stack.reverse()
for op in operators:
if op == 'not': continue
stack[-2:] = ['(%s %s %s)' % (stack[-1], op, stack[-2])]
return (stack[0], n)
def int2bools(i, n):
return [bool(i & (0x01 << b)) for b in xrange(n)]
def solve(operators):
exp, n = build_exp(operators)
code = compile(exp, '', 'eval')
for x in xrange(2 ** n):
if eval(code):
print tuple(int2bools(x, n))
if __name__ == '__main__':
solve('and or not and'.split())
|
にしお
#3399()
Rating0/0=0.00
元ネタの 充足可能性問題 - Wikipedia は、 同じリテラル(x1とかnot x2とか)が複数回出てくることを想定しているので、 今回の問題のようにそれぞれ別の変数でだと乗法標準形 - Wikipediaにした場合に、答えが…と色々悩みどころでした。
[ reply ]