stegastrat.py

import random

def draw_hand():
    hand = set()
    while len(hand) < 8:
        hand.add(random.randrange(40000))
    return list(hand)

def encode_perm(l, x):
    l = list(l)
    out = []
    while l:
        i = x % len(l)
        x //= len(l)
        out.append(l[i])
        del l[i]
    return out

def decode_perm(l):
    out = 0
    prod = 1
    for i, v in enumerate(l):
        out += prod * sum(w < v for w in l[i + 1:])
        prod *= len(l) - i
    return out

def alice(hand):
    hand.sort()

    pick = sum(hand) % 8
    picked = hand[pick]
    del hand[pick]

    counter = 0

    for i in range(picked):
        if i in hand:
            continue
        if sorted(hand + [i])[(sum(hand) + i) % 8] == i:
            counter += 1

    return encode_perm(hand, counter)

def alice_fast(hand):
    hand.sort()
    orig_hand = list(hand)

    pick = sum(hand) % 8
    picked = hand[pick]
    del hand[pick]

    counter = 0

    hs = sum(hand)

    lo = -1
    for pos, hi in enumerate(orig_hand):
        delta = (7 + hs - pos) % 8
        counter += (hi + delta) // 8
        counter -= (lo + 1 + delta) // 8
        if hi == picked:
            break
        lo = hi

    return encode_perm(hand, counter)

def bob(hand):
    counter = decode_perm(hand)

    for i in range(40000):
        if i in hand:
            continue
        if sorted(hand + [i])[(sum(hand) + i) % 8] == i:
            if counter == 0:
                return i
            counter -= 1

def bob_fast(hand):
    target = decode_perm(hand)

    hand.sort()

    hs = sum(hand)
    lo = -1

    for pos, hi in enumerate(hand + [40000]):
        delta = (7 + hs - pos) % 8
        target -= (hi + delta) // 8
        target += (lo + 1 + delta) // 8
        if target < 0:
            f = hi + target * 8
            f -= (f + 7 + hs - pos) % 8
            f += 7
            return f

        lo = hi


def test():
    hand = draw_hand()
    passed = alice_fast(list(hand))

    if len(passed) != 7:
        return 'wrong number of passed'

    if len(set(passed)) < len(passed):
        return 'duplicates'
    if not set(passed) < set(hand):
        return 'not a proper subset'

    removed = next(iter(set(hand) - set(passed)))

    if bob_fast(passed) != removed:
        return 'not reconstructed'

if __name__ == '__main__':
    j = 0
    while True:
        for i in range(1000):
            res = test()
            if res:
                print(res)
                break
        j += 1
        print(j)