在沒有被佔用的小陣列中尋找空間

Question

給出一個包含8個單元格的數組。您還會得到該數組的兩個隨機索引，例如A和B.您如何找到不是數組中A或B索引的單元格？

Answer 1

環E(A, B)&7對於某些E，那麼您可以搜索E來最小化操作次數。

這種方法找到一個解決方案：（！它具有很好的特性，即&7是沒有必要的）(A|1)^(B|2)

我們可以檢查，這是由A和B都爲0 < = A不同，B < = 7.

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) 

Answer 2

你可以通過陣列和輸入的第一個索引值。如果你開始的假設，公式裏的樣子，是不是A或B.

for (int i = 0; i < 8; ++i) 
    if (i != A && i != B) 
    { 
     array[i] = value_to_input; 
     break; 
    }