is31_shehet_05.py

from sys import argv
from math import factorial

a = 0.618034
collision = 0


def read(filename):
    a_list = []
    s_list = []
    with open(filename) as f:
        number_list = map(lambda x: int(x), f.readline().split(' '))
        for index, val in enumerate(f):
            if index < number_list[0]:
                a_list.append(int(val))
            elif index < number_list[0] + number_list[1]:
                s_list.append(int(val))
    return a_list, s_list


def div_hash_set(hash_list, val):
    cur_list = list(hash_list[val % len(hash_list)])
    cur_list.append(val)
    hash_list[val % len(hash_list)] = cur_list


def div_hash_get(hash_list, val):
    return filter(lambda x: x == val, hash_list[val % len(hash_list)])


def mult_hash_set(hash_list, val):
    global a
    cur_list = list(hash_list[int(((val*a) % 1) * len(hash_list))])
    cur_list.append(val)
    hash_list[int(((val*a) % 1) * len(hash_list))] = cur_list


def mult_hash_get(hash_list, val):
    global a
    return filter(lambda x: x == val, hash_list[int(((val*a) % 1) * len(hash_list))])


def chain_table(a_list, key):
    m = int(len(a_list) / 0.3)
    hash_list = [[]] * m
    for val in a_list:
        if key == 1:
            div_hash_set(hash_list, val)
        else:
            mult_hash_set(hash_list, val)
    return hash_list


def len_hash_set(hash_list, val, index):
    hash_index = ((val % len(hash_list)) + index) % len(hash_list)
    hash_list[hash_index] = val if hash_list[hash_index] == 0 else hash_list[hash_index]
    return hash_index


def hash_insert(hash_list, val, key):
    global collision
    index = {}
    index[3] = lambda x, y, z: ((y % len(x)) + z) % len(x)
    index[4] = lambda x, y, z: ((y % len(x)) + z*a + z*z*a) % len(x)
    index[5] = lambda x, y, z: ((y % len(x)) + z*((y % (len(x) - 1)))) % len(x)
    for i in range(len(hash_list)):
        j = int(index[key](hash_list, val, i))
        if hash_list[j] == 0:
            hash_list[j] = val
            return
        else: collision += 1


def search_insert(hash_list, val, key):
    global a
    index = {}
    index[3] = lambda x, y, z: ((y % len(x)) + z) % len(x)
    index[4] = lambda x, y, z: ((y % len(x)) + z*a + z*z*a) % len(x)
    index[5] = lambda x, y, z: ((y % len(x)) + z*((y % (len(x) - 1)))) % len(x)
    for i in range(len(hash_list)):
        j = int(index[key](hash_list, val, i))
        if hash_list[j] == val:
            return val
        elif hash_list[j] == 0:
            return 0
    return 0


def address_table(a_list, key):
    m = int(len(a_list) / 0.3)
    hash_list = [0] * m
    for val in a_list:
        hash_insert(hash_list, val, key)
    return hash_list


def create(a_list, key):
    if key == 1 or key == 2: return chain_table(a_list, key)
    else: return address_table(a_list, key)


def count_collision(hash_list):
    return reduce(lambda y, x:
                  y + (factorial(len(x))/(factorial(len(x) - 2)*factorial(2)) if len(x) > 2 else 1 if len(x) > 1 else 0),
                  hash_list, 0)


def search_table(hash_list, val, key):
    if key == 1:
        return div_hash_get(hash_list, val)
    elif key == 2:
        return mult_hash_get(hash_list, val)
    else:
        val = search_insert(hash_list, val, key)
        return [val] if val != 0 else []


def search(hash_list, a_list, s_list, key):
    search_dic = {}
    for s in s_list:
        search_dic[s] = [0, 0]
        for x in a_list:
            cur_search = search_table(hash_list, s - x, key)
            if len(cur_search):
                search_dic[s] = [x, cur_search[0]]
                break
    return search_dic


def write(text):
    filename = "is31_shehet_05_output.txt"
    f = open(filename, 'w')
    f.write(text)
    f.close()


def main():
    global collision
    a_list, s_list = read(argv[1])
    hash_list = create(a_list, int(argv[2]))
    collision = count_collision(hash_list) if int(argv[2]) < 3 else collision
    search_dic = search(hash_list, a_list, s_list, int(argv[2]))
    text = str(collision) + "\n"
    for item in s_list:
        cur = search_dic[item]
        text += " ".join(map(lambda x: str(x), cur)) + "\n"
    write(text)

main()