c - 在小数组中查找未被占用的空间

Question

You are given an array which contains 8 cells. You are also given two random indices of that array, for example A and B. How would you find a cell that isn't the index of A or B in an array?

Answer 1

如果您首先假设公式将类似于 E(A, B)&7对于某些E，那么你可以搜索使操作次数最少的E。

此方法找到了解决方案:(A|1)^(B|2) (它有一个很好的特性，即 &7 不是必需的!)

我们可以检查这与所有 0 <= A, B <= 7 的 A 和 B 不同。

for A in xrange(8):
    for B in xrange(8):
        r = (A|1)^(B|2)
        print A, B, r
        assert r != A and r != B

很容易看出表达式的工作原理:最低位始终与 B 的最低位不同，第二最低位始终与 A 的第二最低位不同。

这是搜索 E 的代码。它是一个小型堆栈机，会尝试每种合法的操作组合。当它运行时，它偶尔会打印反例，并定期显示所有工作表达式。

import random

def hash_ok(ops):
    h = make_hash(ops)
    for i in xrange(8):
        for j in xrange(8):
            try:
                r = h(i, j)
            except Exception as e:
                return False, '%d, %d: %s -> %s' % (i, j, ops, e)
            if r == i or r == j:
                return False, '%d, %d: %s -> %d' % (i, j, ops, r)
    return True, None

ops = [
  ('a', 0, 1), ('b', 0, 1), ('+', 2, 1), ('-', 2, 1), ('*', 2, 1), ('/', 2, 1), ('%', 2, 1),
  ('|', 2, 1), ('&', 2, 1), ('^', 2, 1), ('~', 1, 1), ('neg', 1, 1), ('<<', 2, 1), ('>>', 2, 1)] + [
    (str(n), 0, 1) for n in xrange(0, 3)]

op_by_arity = {0: [], 1: [], 2: []}
arity = dict()

for op, a, n in ops:
    op_by_arity[a].append((op, n))
    arity[op] = a

def print_ops(ops):
    s = []
    for o in ops:
        if arity[o] == 0:
            s.append(o)
        elif arity[o] == 1:
            s.append('%s(%s)' % (o, s.pop()))
        else:
            y, x = s.pop(), s.pop()
            s.append('(%s %s %s)' % (x, o, y))
    return s[0]

print op_by_arity

def make_hash(ops):
    def f(a, b):
        s = []
        for o in ops:
            if o == 'a':
                s.append(a)
            elif o=='b': 
                s.append(b)
            elif o=='>>':
                y, x = s.pop(), s.pop()
                s.append(x>>y)
            elif o=='<<':
                y, x = s.pop(), s.pop()
                s.append(x<<y)
            elif o=='+':
                s.append(s.pop()+s.pop())
            elif o=='-':
                s.append(-(s.pop()-s.pop()))
            elif o=='*':
                s.append(s.pop()*s.pop())
            elif o=='/':
                y, x = s.pop(), s.pop()
                s.append(x//y)
            elif o=='%':
                y, x = s.pop(), s.pop()
                s.append(x%y)
            elif o=='|':
                s.append(s.pop()|s.pop())
            elif o=='&':
                s.append(s.pop()&s.pop())
            elif o=='^':
                s.append(s.pop()^s.pop())
            elif o=='~':
                s.append(~s.pop())
            elif o=='neg':
                s.append(-s.pop())
            elif o >= '0' and o <= '9':
                s.append(int(o))
            elif o[0] == '-':
                s.append(int(o))
            else:
                raise Exception('bogus op %s' % o)
        assert len(s) == 1
        return (s[0] % 8)
    return f

def enumerate_ops(n, s):
    if n == 0:
        if s == 1:
            yield []
        return
    for a, aops in op_by_arity.iteritems():
        if a > s:
            continue
        for op, add in aops:
            for seq in enumerate_ops(n - 1, s - a + add):
                yield [op] + seq

winners = []

for i, ops in enumerate(enumerate_ops(7, 0)):
    ok, err = hash_ok(ops)
    if ok:
        print print_ops(ops)
        winners.append(ops)
    if random.randrange(100000) == 1:
        print err
    if i % 1000000 == 0:
        for w in winners:
            print print_ops(w)

print

for w in winners:
    print print_ops(w)