## Friday, February 26, 2016

### Problem 103 -- Something happened

A long time ago, I decided to solve the few problems beyond the boundary of where I had worked. Problem 103, though it has been a while, I recall being a bit annoying, especially as the whole computation ended up only confirming that the given heuristic they have, which isn't true in general, still would have solved this problem. But oh well, here is what I did. A lot of bit-shifting silliness for efficient set implementations (and efficiently iterating over sets with a certain number of elements out of the universe).
```N = 47
K = 7

def F(c):
a = c & -c
b = a + c
return (((b ^ c) >> 2)//a) | b

def getSet(s):
a = []
k = 1
while s != 0:
if (s & 1) == 1: a.append(k)
k += 1
s >>= 1
return a

def getSubSet(s, set):
a = []
k = 0
while s != 0:
if (s & 1) == 1: a.append(set[k])
k += 1
s >>= 1
return a

S = sum

def hasProp(set):
if (set < K): return False

for i in range(1, K//2):
if S(set[0:i+1]) <= S(set[K-1:K]):
return False

for n in range(1, len(set)):
s = (1 << n) - 1
while s < (1 << len(set)) - 1:
A = getSubSet(s, set)
for m in range(n, len(set)):
t = (1 << m) - 1
while t < (1 << len(set)) - 1:
B = getSubSet(t, set);
if ((S(A) == S(B)) or ((m > n)  and (S(A) >  S(B)))) and (A != B):
return False
t = F(t)
s = F(s)
return True

minsum = 115 + (7 * 19)
minset = []
s = (1 << K) - 1
while s < (1 << N) - 1:
sp = getSet(s)
#print(sp)
SUM = S(sp)
if SUM < minsum and hasProp(sp):
minset = sp
minsum = SUM
s = F(s)
print(minset)

```