base16 game

from itertools import permutations
from collections import defaultdict
import array
import timeit

def find_sum_equal_n_16bit():
    solutions = set()
    best = 10**6
    num1, num2 = split_list(16)
    list_perm2 = list(permutations(num2))
    for perm1 in permutations(num1):
        for perm2 in list_perm2:
            perm = perm1 + perm2
            tple = product_sum(perm)
            temp_best = abs(product_num(tple))
            if temp_best <= best:
                print perm
                display_tuple(tuple_2_16bit(perm))
                best = temp_best
                if temp_best == 0:
                    solutions.add(perm)
    return list(solutions)


def split_list(n):
    # Greedy algorithm to divide the list into two
    num = range(1, n)
    high = [num.pop(1)]
    low = []
    while len(num) > 0:
        while sum(high) >= sum(low) and len(num) > 0:
            low.append(num.pop())
        temp_high = high
        high = low
        low = temp_high
    if len(high) > len(low):
        low.append(0)
    else:
        high.append(0)
    return high, low


def product_sum(tple):
    lst = list(tple)
    num1 = sum(k*16**(4-i) for i, k in enumerate(lst[0:5]))
    num2 = sum(k*16**(2-i) for i, k in enumerate(lst[5:8]))
    num3 = sum(k*16**(4-i) for i, k in enumerate(lst[8:13]))
    num4 = sum(k*16**(2-i) for i, k in enumerate(lst[13:16]))
    return (num1, num2, num3, num4)


def product_num(tple):
    total = tple[0]*tple[1] - tple[2]*tple[3]
    return total


def tuple_2_16bit(tple):
    key1 = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
    key = key1 + ['A', 'B', 'C', 'D', 'E', 'F']
    lst = [str(key[i]) for i in tple]
    return (''.join(lst[0: 5]), ''.join(lst[5: 8]), ''.join(lst[8: 13]), ''.join(lst[13: 16]))


def display_tuple(tple):
    print '   ' + tple[0] + ' x ' + tple[1]
    print ' - ' + tple[2] + ' x ' + tple[3]
    print ' = ', int(tple[0], 16)*int(tple[1], 16) - int(tple[2], 16)*int(tple[3], 16)

if __name__ == '__main__':

    print find_sum_equal_n_16bit()