Lecture "Dynamic programming algorithms", exercise 2

[essepuntato]

Write an algorithm for using the merge sort (introduced in the previous lecture) so as to use a dynamic programming approach in case the same list of books must be ordered twice or more times during the algorithm execution – see the informal example introduced in Section "Remembering solutions to sub-problems" of this lecture notes.

Accompany the implementation of the function with the appropriate test cases.

[simayguzel]

def test_merge_sort(input_list, expected):

    result = merge_sort(input_list)

    if result == expected:
        return True
    else:
        return False

def merge_sort(input_list):
    input_list_len = len(input_list)

    if len(input_list) <= 1:
        return input_list
    else:
        mid = input_list_len // 2
        l = (merge_sort(input_list[0:mid]))
        r = (merge_sort(input_list[mid:input_list_len]))
        return merge(l,r)

def merge(l,r):
    result = list()

    while len(l) > 0 and len(r) > 0:
        left_item = l[0]
        right_item = r[0]


        if left_item < right_item:
            result.append(left_item)
            l.remove(left_item)

        else:
            result.append(right_item)
            r.remove(right_item)

    
    result.extend(l)
    result.extend(r)

    return result


input_list = (["Coraline", "American Gods", "Neverwhere", "Neverwhere", "American Gods", "Coraline"])

print(test_merge_sort(["Coraline", "American Gods", "Neverwhere", "Neverwhere", "American Gods", "Coraline"],['American Gods', 'American Gods', 'Coraline', 'Coraline', 'Neverwhere', 'Neverwhere']))  #True

[EleonoraPeruch]

from merge import merge


# test for the algorithm
def test_merge_sort(books_list, expected, d=dict()):
    result = merge_sort(books_list, d=dict())
    if result == expected:
        return True
    else:
        return False

def merge_sort(books_list, d=dict()):
    books_list_len = len(books_list)  # base case
    if len(books_list)<= 1:
        return books_list
    else:
        mid = books_list_len // 2  # divide step
        left_books_list = books_list[0:mid]
        right_books_list = books_list[mid:books_list_len]

        # recursive step
        left = merge_sort(books_list[0:mid])
        right = merge_sort(books_list[mid:books_list_len])

        # dictionary used as input in case the same list of books must be ordered more than one time
        # dynamic programming approach
        if left_books_list == right_books_list:
            d[right] = left

        return merge(left, right) # combine

print(test_merge_sort(["Coraline", "American Gods", "Neverwhere", "Neverwhere", "American Gods", "Coraline"], ["American Gods", "American Gods", "Coraline", "Coraline", "Neverwhere", "Neverwhere"], ({})))
print(test_merge_sort(["Heart of Darkness", "Wuthering Heights", "Twelfth Night", "Twelfth Night", "Wuthering Heights", "Heart of Darkness"], ["Heart of Darkness", "Heart of Darkness", "Twelfth Night", "Twelfth Night", "Wuthering Heights", "Wuthering Heights"], ({})))

# True
# True

[SeverinJB]

Note:
This dynamic merge sort algorithm saves results for a partial list of an input list if the partial list itself was used as an input in the recursive part of the algorithm. For example, after having ordered [9, 6, 8, 7, 0], the result for the partial list [8, 7, 0] can be retrieved from the dictionary. However, the partial list [6, 8, 7] is not stored in the dictionary and has to be ordered itself. The difference is that the latter was never used as an input of the recursive merge_sort_dp(). Whereas the first partial list was used as an input.

+++ Dynamic Merge Sort with Test Cases +++

# Test Function
def test_merge_sort_dp(input_list, expected):
    return expected == merge_sort_dp(input_list)

# Merge Algorithm 
def merge_dp(left_list, right_list): 
    left = left_list.copy()
    right = right_list.copy()
    result = list()

    while len(left) > 0 and len(right) > 0:
        left_item = left[0] 
        right_item = right[0]
        
        if left_item < right_item:
            result.append(left_item)
            left.remove(left_item)
        else:
            result.append(right_item) 
            right.remove(right_item)
    
    result.extend(left)
    result.extend(right)
    return result

# Merge Sort Algorithm
def merge_sort_dp(input_list, d=dict()):
    input_list_len = len(input_list)
    key = ''.join(map(str, input_list))

    if key not in d:
        if len(input_list) <= 1:
            d[key] = input_list
        else:
            mid = input_list_len // 2
            left = merge_sort_dp(input_list[0:mid])
            right = merge_sort_dp(input_list[mid:input_list_len])
            d[key] = merge_dp(left, right)

    return d[key]
    
# Test Cases 
print(test_merge_sort_dp([3,4,1,5,2,9,6,8,7,0],[0,1,2,3,4,5,6,7,8,9]))
print(test_merge_sort_dp([9, 6, 8, 7, 0],[0, 6, 7, 8, 9]))
print(test_merge_sort_dp([8, 7, 0],[0, 7, 8]))
print(test_merge_sort_dp([3, 4, 1, 5, 2],[1, 2, 3, 4, 5]))
print(test_merge_sort_dp([3,4,1,5,2,9,6,8,7,0],[0,1,2,3,4,5,6,7,8,9]))
print(test_merge_sort_dp(["B","C","F","A","G","E","H","J","D","I"],["A","B","C","D","E","F","G","H","I","J"]))
print(test_merge_sort_dp(["B","C","A","E","D"],["A","B","C","D","E"]))

[delfimpandiani]

Note:
This dynamic merge sort algorithm saves results for a partial list of an input list if the partial list itself was used as an input in the recursive part of the algorithm. For example, after having ordered [9, 6, 8, 7, 0], the result for the partial list [8, 7, 0] can be retrieved from the dictionary. However, the partial list [6, 8, 7] is not stored in the dictionary and has to be ordered itself. The difference is that the latter was never used as an input of the recursive merge_sort_dp(). Whereas the first partial list was used as an input.

+++ Dynamic Merge Sort with Test Cases +++

# Test Function
def test_merge_sort_dp(input_list, expected):
    return expected == merge_sort_dp(input_list)

# Merge Algorithm 
def merge_dp(left_list, right_list): 
    left = left_list.copy()
    right = right_list.copy()
    result = list()

    while len(left) > 0 and len(right) > 0:
        left_item = left[0] 
        right_item = right[0]
        
        if left_item < right_item:
            result.append(left_item)
            left.remove(left_item)
        else:
            result.append(right_item) 
            right.remove(right_item)
    
    result.extend(left)
    result.extend(right)
    return result

# Merge Sort Algorithm
def merge_sort_dp(input_list, d=dict()):
    input_list_len = len(input_list)
    key = ''.join(map(str, input_list))

    if key not in d:
        if len(input_list) <= 1:
            d[key] = input_list
        else:
            mid = input_list_len // 2
            left = merge_sort_dp(input_list[0:mid])
            right = merge_sort_dp(input_list[mid:input_list_len])
            d[key] = merge_dp(left, right)

    return d[key]
    
# Test Cases 
print(test_merge_sort_dp([3,4,1,5,2,9,6,8,7,0],[0,1,2,3,4,5,6,7,8,9]))
print(test_merge_sort_dp([9, 6, 8, 7, 0],[0, 6, 7, 8, 9]))
print(test_merge_sort_dp([8, 7, 0],[0, 7, 8]))
print(test_merge_sort_dp([3, 4, 1, 5, 2],[1, 2, 3, 4, 5]))
print(test_merge_sort_dp([3,4,1,5,2,9,6,8,7,0],[0,1,2,3,4,5,6,7,8,9]))
print(test_merge_sort_dp(["B","C","F","A","G","E","H","J","D","I"],["A","B","C","D","E","F","G","H","I","J"]))
print(test_merge_sort_dp(["B","C","A","E","D"],["A","B","C","D","E"]))

@SeverinJB Sevi, could you explain your thinking process behind editing the merge() algorithm definition, when you added

left = left_list.copy()
right = right_list.copy()

in its definition? I am trying to understand why this is necessary to make your merge_sort_dp() work. As I tried your code without editing merge() in the way you did, and it doesn't work.
Would be awesome if you could explain your thinking process also in general!

[delfimpandiani]

My approach, based on a mix of Severin's and Eleonora's approaches but with a focus on labelling each of the 5 steps of dynamic programming.
STEP 1: base case - solution already exists
STEP 2: base case - easy-to-solve, approach directly
STEP 3: divide
STEP 4: conquer
STEP 5: combine
STEP 6: memorize

I created an ancillary function list_to_key() to handle the key label creations for each element in the dictionary separately.

# ____________MERGE_________________________
def merge(left_list, right_list):    
    left = left_list.copy()
    right = right_list.copy()
    result = list()

    while len(left) > 0 and len(right) > 0:
        left_item = left[0] 
        right_item = right[0]
        
        if left_item < right_item:
            result.append(left_item)
            left.remove(left_item)
        else:
            result.append(right_item) 
            right.remove(right_item)
    
    result.extend(left)
    result.extend(right)
    return result

#_______ANCILLARY FUNCT: LIST_TO_KEY()_______
def list_to_key(input_list):
    key_list = list() 
    for item in input_list:
        str_item = str(item)
        key_list.append(str_item)
    key_name = ""
    for i in key_list:
        key_name += str(i)
    return key_name

#__________TEST_DYNAMIC _MSORT_________________
def test_dynamic_msort(input_list, expected, d=dict()):
    result = dynamic_msort(input_list, d=dict())
    if result == expected:
        return True
    else:
        return False
        
#_____________DYNAMIC _MSORT_________________
def dynamic_msort(input_list, d=dict()):
    len_input_list = len(input_list)
    key = list_to_key(input_list)
    
    if key in d: # STEP 1-base case: solution exists
        return d[key]
    elif len_input_list <= 1: # STEP 2-base case: address directly
        d[key] = input_list
        return d[key]
    else: #recursive step
        mid = len_input_list // 2  # STEP 3- divide
        left_list = input_list[0:mid]
        right_list = input_list[mid:len_input_list]
        left = dynamic_msort(left_list) # STEP 4-conquer
        right = dynamic_msort(right_list) # STEP 4conquer
        merged_list = merge(left, right) # STEP 5 -combine
        d[key] = merged_list # STEP 6- memorize
        return d[key]


print(test_dynamic_msort([3,4,1,5,2,9,6,8,7,0],[0,1,2,3,4,5,6,7,8,9]))
print(test_dynamic_msort([9, 6, 8, 7, 0],[0, 6, 7, 8, 9]))
print(test_dynamic_msort([8, 7, 0],[0, 7, 8]))
print(test_dynamic_msort([3, 4, 1, 5, 2],[1, 2, 3, 4, 5]))
print(test_dynamic_msort([3,4,1,5,2,9,6,8,7,0],[0,1,2,3,4,5,6,7,8,9]))
print(test_dynamic_msort(["B","C","F","A","G","E","H","J","D","I"],["A","B","C","D","E","F","G","H","I","J"]))
print(test_dynamic_msort(["B","C","A","E","D"],["A","B","C","D","E"]))

# True
# True
# True
# True
# True
# True
# True

@SeverinJB I figured it out the merge() edit on my own! We need to use copies of the lists, because otherwise our dictionaries are corrupted every time we run the merge() function.

[SeverinJB]

@SeverinJB Sevi, could you explain your thinking process behind editing the merge() algorithm definition, when you added

left = left_list.copy()
right = right_list.copy()

@SeverinJB I figured it out the merge() edit on my own! We need to use copies of the lists, because otherwise our dictionaries are corrupted every time we run the merge() function.

Hi @delfimpandiani,

Sorry for not coming back to your questions earlier.

For clarification:
With copy_list = main_list only the reference is copied. It's like the computer is storing the list with a generic name "281x829yez", but there are now two human-readable names (copy_list and main_list) which can be used to address the list. Hence, when copy_list is modified main_list is simultaneously modified! The additional "copy()" in copy_list = main_list.copy() creates an actual copy of main_list and stores this copy in copy_list.

Hopefully, this helps.

[essepuntato]

Hi all,

Here my take on the exercise - source codes available online.

# Import the function 'merge' from the module 'merge' (file 'merge.py')
from merge import merge


# Test case for the algorithm
def test_merge_sort_dp(input_list, expected):
    result = merge_sort_dp(input_list)
    if expected == result:
        return True
    else:
        return False


# Code of the algorithm
def merge_sort_dp(input_list, prev_l=list()):
    result = find_solution(input_list, prev_l)

    if result is None:
        if len(input_list) <= 1:
            result = input_list
            store_solution(result, prev_l)
        else:
            input_list_len = len(input_list)
            mid = input_list_len // 2

            left = merge_sort_dp(input_list[0:mid], prev_l)
            right = merge_sort_dp(input_list[mid:input_list_len], prev_l)
            result = merge(left, right)
            store_solution(result, prev_l)
    return result


def find_solution(input_list, sol_list):
    input_dic = create_list_dict(input_list)
    for d, sol in sol_list:
        if input_dic == d:
            return list(sol)


def store_solution(input_list, solution_list):
    d = create_list_dict(input_list)
    solution_list.append((d, list(input_list)))


def create_list_dict(input_list):
    d = {}
    for el in input_list:
        if el not in d:
            d[el] = 0
        d[el] = d[el] + 1
    return d


print(test_merge_sort_dp([], []))
print(test_merge_sort_dp([1], [1]))
print(test_merge_sort_dp([3, 4, 1, 2, 9, 8, 2], [1, 2, 2, 3, 4, 8, 9]))
print(test_merge_sort_dp(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"],
                         ["American Gods", "Coraline", "Good Omens", "Neverwhere", "The Graveyard Book"]))
print(test_merge_sort_dp(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere", "American Gods",
                          "American Gods", "Good Omens", "The Graveyard Book", "American Gods", "Neverwhere", "Coraline"],
                         ["American Gods", "American Gods","American Gods", "American Gods", "Coraline", "Coraline",
                          "Good Omens", "Good Omens", "Neverwhere",  "Neverwhere", "The Graveyard Book", "The Graveyard Book"]))

[MilenaCorbellini]

I didn't see the solution of the exercise again. I tried to create an algoritm but I'm not sure of the efficiency, because it returns the result, but maybe it iterates in an unneccessary way. Could it work?

def test_merge(left_list, right_list, expected):
    result = merge(left_list, right_list)
    if expected == result:
        return True
    else:
        return False

def merge(left_list, right_list):
    result = list()

    while len(left_list) > 0 and len(right_list) > 0:
        left_item = left_list[0]
        right_item = right_list[0]


        if left_item < right_item:
            result.append(left_item)
            left_list.remove(left_item)

        else:
            result.append(right_item)
            right_list.remove(right_item)

    result.extend(left_list)
    result.extend(right_list)

    return result


def test_merge_sort(input_list, expected, d):
    if merge_sort(input_list, d) == expected:
        return True
    else:
        return False

def merge_sort(input_list, d):
    input_list_len = len(input_list)
    for item in input_list:
        if item not in d:
            if input_list_len <= 1:
                d[merge] = input_list



            else:
                mid = input_list_len // 2

                left = merge_sort(input_list[0:mid], d)
                right = merge_sort(input_list[mid:input_list_len], d)
                d[merge] = merge(left, right)

            return d[merge]


print(test_merge_sort(["Coraline", "American Gods", "Neverwhere", "Neverwhere", "American Gods", "Coraline"],
                      ['American Gods', 'American Gods', 'Coraline', 'Coraline', 'Neverwhere', 'Neverwhere'], ({})))