# Skeleton file for HW3 - Spring 2020 - extended intro to CS

# Add your implementation to this file

# You may add other utility functions to this file,
# but you may NOT change the signature of the existing ones.

# Change the name of the file to include your ID number (hw3_ID.py).

#Enter all IDs of participating students as strings, separated by commas.
#For example: SUBMISSION_IDS = ["123456", "987654"] if submitted in a pair or SUBMISSION_IDS = ["123456"] if submitted alone.

import random


############
# QUESTION 2
############

def text_2_16bits(text):
    return ''.join(['0' * (16 - len(bin(ord(c))[2:])) +
                    bin(ord(c))[2:] for c in text])

# Q2 - A, b
def bits_2_text(b_text):
    sep_bits = [b_text[i:i + 16] for i in range(0, len(b_text), 16)]
    return ''.join([chr(int(c, 2)) for c in sep_bits])

# Q2 - B
def float_add(a, b):
    exp1, exp2, = int(a[1:12], 2), int(b[1:12], 2)
    bfrac1_1, bfrac2_1 = '1' + a[12:-1], '1' + b[12:-1]
    shift = exp1 - exp2
    frac1_1 = -int(('0' * -shift + bfrac1_1)[:52], 2) if int(a[0]) \
          else int(('0' * -shift + bfrac1_1)[:52], 2)
    frac2_1 = -int(('0' * shift + bfrac2_1)[:52], 2) if int(b[0]) \
          else int(('0' * shift + bfrac2_1)[:52], 2)
    frac_sol_1 = frac1_1 + frac2_1
    bfrac_sol_1 = bin(abs(frac_sol_1))[2:]
    bfrac_sol = bfrac_sol_1[1:52] + '0' * (52 - len(bfrac_sol_1[1:52]))
    bsgn_sol = '1' if frac_sol_1 < 0 else '0'
    exp_sol = max(exp1, exp2)
    for i in range(len(bfrac_sol_1) - 52):
        exp_sol += 1
    bexp_sol = '0' * (11 - len(bin(exp_sol)[2:])) + bin(exp_sol)[2:]
    return bsgn_sol + bexp_sol + bfrac_sol


############
# QUESTION 3
############

# a
def swap(lst, i, j):
    tmp = lst[i]
    lst[i] = lst[j]
    lst[j] = tmp


def selection_sort(lst):
    """ sort lst (in-place) """
    n = len(lst)
    for i in range(n):
        m_index = i
        for j in range(i + 1, n):
            if lst[m_index] > lst[j]:
                m_index = j
        swap(lst, i, m_index)
    return None


def generate_sorted_blocks(lst, k):
    n = len(lst)
    if k > n:
        raise ValueError('k parameter needs to be less or equal to the ' +
                         'length of lst parameter')
    sub_k_lists = []
    for i in range(0, n, k):
        sub_k_list = lst[i:i + k]
        selection_sort(sub_k_list)
        sub_k_lists.append(sub_k_list)
    return sub_k_lists


def merge(A, B):
    """ merging two lists into a sorted list
        A and B must be sorted! """
    n = len(A)
    m = len(B)
    C = [0 for i in range(n + m)]

    a = 0
    b = 0
    c = 0
    while a < n and b < m:  # more element in both A and B
        if A[a] < B[b]:
            C[c] = A[a]
            a += 1
        else:
            C[c] = B[b]
            b += 1
        c += 1

    C[c:] = A[a:] + B[b:]  # append remaining elements (one of those is empty)

    return C


# c
def merge_sorted_blocks(lst):
    i = 0
    while len(lst) != 1:
        while i < len(lst) - 1:
            lst[i] = merge(lst[i], lst[i + 1])
            lst.pop(i + 1)
            i += 1
        i = 0
    return lst[0]


def sort_by_block_merge(lst, k):
    return merge_sorted_blocks(generate_sorted_blocks(lst, k))


############
# QUESTION 4
############

def find(lst, s):
    n = len(lst)
    left = 0
    right = n - 1
    if n == 2:
        return 0 if lst[0] == s else 1 if lst[1] == s else None
    while left <= right:
        mid = (left + right) // 2  # middle rounded down
        if left == right:
            return mid if lst[mid] == s else None
        if s == lst[mid]:  # item found
            return mid
        if s == lst[mid - 1]:
            return mid - 1
        if s == lst[mid + 1]:
            return mid + 1
        elif s < lst[mid - 1]:  # item cannot be in top half
            right = mid - 2
        else:
            left = mid + 2
    return None


def sort_from_almost(lst):
    for i in range(len(lst) - 1):
        if lst[i + 1] < lst[i]:
            tmp = lst[i]
            lst[i] = lst[i + 1]
            lst[i + 1] = tmp
    return None

def find_local_min(lst):
    n = len(lst)
    if n == 1:
        return 0
    for i in range((n - 1) // 2 + 1):
        if lst[i] <= lst[i + 1] or lst[n - 2 - i] >= lst[n - 1 - i]:
            return i if lst[i] <= lst[i + 1] else n - 1 - i


############
# QUESTION 5
############

# a
def string_to_int(s):
    keys = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4}
    sol = 0
    for i in range(len(s)):
        sol += keys[s[i]] * 5 ** (len(s) - 1 - i)
    return sol


# b
def int_to_string(k, n):
    assert 0 <= n <= 5 ** k - 1
    alphabet = 'abcde'
    s = []
    while n:
        s.insert(0, alphabet[n % 5])
        n //= 5
    s = ''.join(s)
    s = 'a' * (k - len(s)) + s
    return s


# c
def sort_strings1(lst, k):
    sol = []
    aux_lst = [0 for i in range(5 ** k)]
    for st in lst:
        aux_lst[string_to_int(st)] += 1
    for i in range(len(aux_lst)):
        while aux_lst[i]:
            sol.append(int_to_string(k, i))
            aux_lst[i] -= 1
    return sol


# e
def sort_strings2(lst, k):
    n = len(lst)
    sol = []
    for i in range(5 ** k):
        for j in range(n):
            if string_to_int(lst[j]) == i:
                sol.append(int_to_string(k, i))
    return sol


########
# Tester
########

def test():
    # q2 - a
    
    text = "Hi There"
    text_bits = text_2_16bits(text)
    if bits_2_text(text_bits) != text:
        print("error in text reconstruction")
        
    if text_bits.count("0") + text_bits.count("1") != len(text_bits):
        print("error: non binary characters in text_2_16bits")

    if len(text_bits) % 16 != 0:
        print("error wrong length for text_2_16bits output")

    # q2 - b
    a = "0100000000101000000000000000000000000000000000000000000000000000"
    b = "0011111111101000000000000000000000000000000000000000000000000000"
    res = "0100000000101001100000000000000000000000000000000000000000000000"
    if float_add(a, b) != res:
        print("error in float_add of 12 + 0.75")
        
    # q3
    lst = [610, 906, 308, 759, 15, 389, 892, 939, 685, 565]
    if generate_sorted_blocks(lst, 2) != \
            [[610, 906], [308, 759], [15, 389], [892, 939], [565, 685]]:
        print("error in generate_sorted_blocks")
    if generate_sorted_blocks(lst, 3) != \
            [[308, 610, 906], [15, 389, 759], [685, 892, 939], [565]]:
        print("error in generate_sorted_blocks")
    if generate_sorted_blocks(lst, 10) != \
            [[15, 308, 389, 565, 610, 685, 759, 892, 906, 939]]:
        print("error in generate_sorted_blocks")

    block_lst1 = [[610, 906], [308, 759], [15, 389], [892, 939], [565, 685]]
    if merge_sorted_blocks(block_lst1) != \
            [15, 308, 389, 565, 610, 685, 759, 892, 906, 939]:
        print("error in merge_sorted_blocks")
    block_lst2 = [[308, 610, 906], [15, 389, 759], [685, 892, 939], [565]]
    if merge_sorted_blocks(block_lst2) != \
            [15, 308, 389, 565, 610, 685, 759, 892, 906, 939]:
        print("error in merge_sorted_blocks")

    # q4
    almost_sorted_lst = [2, 1, 3, 5, 4, 7, 6, 8, 9]

    if find(almost_sorted_lst, 5) != 3:
        print("error in find")

    if find(almost_sorted_lst, 50) != None:
        print("error in find")

    sort_from_almost(almost_sorted_lst)
    if almost_sorted_lst != sorted(almost_sorted_lst):
        print("error in sort_from_almost")
    
    lst = [5, 6, 7, 5, 1, 1, 99, 100]
    pos = find_local_min(lst)
    if pos not in (0, 4, 5):
        print("error in find_local_min")

    # q5
    lst_num = [random.choice(range(5 ** 4)) for i in range(15)]
    for i in lst_num:
        s = int_to_string(4, i)
        if s is None or len(s) != 4:
            print("error in int_to_string")
        if (string_to_int(s) != i):
            print("error in int_to_string or in string_to_int")

    lst1 = ['aede', 'adae', 'dded', 'deea', 'cccc', 'aacc', 'edea', 'becb', 'daea', 'ccea']
    if sort_strings1(lst1, 4) \
            != ['aacc', 'adae', 'aede', 'becb', 'cccc', 'ccea', 'daea', 'dded', 'deea', 'edea']:
        print("error in sort_strings1")

    if sort_strings2(lst1, 4) \
            != ['aacc', 'adae', 'aede', 'becb', 'cccc', 'ccea', 'daea', 'dded', 'deea', 'edea']:
        print("error in sort_strings2")
