#!/usr/bin/env python
# coding: utf-8

# # Week 4 Day 16, Supplementary

# ## 1. Longest Increasing Subsequence 
# 
# Write a function ```lis(L)``` which takes as input a list of integers ```L``` and outputs the length of the longest increasing subsequence (lis) of ```L```. A subsequence of ```L``` is a sublist of ```L``` that does not have to be contiguous. For example, ```[1,5,9]``` is a subsequence of the list ```L = [1,2,3,4,5,6,7,8,9]``` since ```1,5,9``` appear in the list ```L``` in the same order (though just not in a row). ```9,5,1``` is not a subsequence of ```L``` since it does not appear in ```L``` in that order.
# 
# ### 1.1
# First implement ```lis``` using plain recursion.

# In[ ]:





# ## 1.2 
# Implement a faster version of `lis` using memoization.

# In[ ]:





# ## 2. Longest Common Subsequence 
# 
# Write the function `lcs(s1, s2)` which takes as an input two strings and outputs the length of the longest common substring between the two. A subsequence of string```s``` is a set of letters that does not have to be contiguous. For example, the longest common subsequence of `'apple'` and `'pimple'`  is `'pple'`, so the function would return `4`. 

# 

# ## 3. The Adventures of Mini-Tron Part I: The Origins
# Imagine you are a mechanical engineer working for the search and rescue team in Addis Ababa. You are are in charge of building *Mini-Tron*, a robot that will navigate its way around a minefield. You want to make sure that Mini-Tron is as fast and agile as possible. Thus, **your goal is to minimize the total weight of the robot.** You are given a collection of robotic parts, each part belongs to one of *n* different categories. **Your robot must be built from one part from each category.**
# 
# For instance, you can have 4 categories: wheels, batteries, processing unit, distance sensors. Thus your robot must contain 4 parts: a set of wheels, one battery, one processing unit, and one distance sensor. 
# 
# You are also given the weight and cost of each part. The parts are given as an array of $n$ lists. Each list will contain the parts of the category, represented as a tuple *(cost, weight)*. 
# 
# 
# For example, for a problem with 4 categories and 10 total parts (2 parts in the first category, 3 parts in the second category, 3 parts in the third category, and 2 parts in the fourth category), your input $p$ can look like this:
# 
# ```
# [[(5, 4), (3, 8)],
#  [(1, 10), (9, 1), (7, 5)], 
#  [(5, 12), (10, 7), (12, 5)],
#  [(20, 2), (12, 6)]]
# ```
# 
# And lastly, you have a total of $s$ birr to spend on the robot. 
# 
# Write a function that take as input three arguments: $n$ the number of categories, $p$ the list of parts, and $s$ the budget in birr, and outputs the minimum possible weight of the robot. If there is no solution, return -1.
# 
# For the above input and a budget of $30$ birr, your function should return $25$.
#  

# ## 3.1  Brute Force
# First write a brute force solution `robot_building_bf(p,s)` that takes a list $p$ and a budget (integer) $s$. Hint: you should use recursion.

# In[ ]:


def robot_building(p, s):
    pass


# ### Check your answer
# Test your brute force solution on the following test cases before moving on to Part 1.2.

# In[ ]:


def check(actual, expected):
    if expected != actual:
        print(f"Function should return the value {expected}, it is returning the value {actual}")
    else:
        print(f"Congratulations, the test case passed!")


# In[ ]:


#TEST_CASE
def test_small(function):
    def test_1():
        p = [[(5, 4), (3, 8)],
             [(1, 10), (9, 1), (7, 5)], 
             [(5, 12), (10, 7), (12, 5)],
             [(20, 2), (12, 6)]]
        check(function(p, 30), 25)

    def test_2():
        p = [[(5, 4), (3, 8)],
             [(1, 10), (9, 1), (7, 5)]] 
        check(function(p, 15), 5)

    def test_3():
        p = [[(5, 4), (3, 8)],
             [(1, 10), (9, 1), (7, 5)], 
             [(5, 12), (10, 7), (12, 5)],
             [(20, 2), (12, 6)]]
        check(function(p, 10), -1)
    
    test_1()
    test_2()
    test_3()

test_small(robot_building)


# ## 3.2 Memoization
# 
# Now, you should write a memoized solution.

# In[ ]:


def robot_building_mem(p, s):
    pass


# ## Check your answer here

# In[ ]:


test_small(robot_building_mem)


# In[ ]:


def test_long():
    objects = [[(19, 6), (17, 17), (13, 8)], [(14, 9), (3, 12), (9, 4)], [(9, 16), (14, 6), (18, 2)], [(3, 11), (8, 17), (13, 11), (12, 7), (17, 12), (10, 10)], [(3, 11), (2, 12), (16, 17), (15, 13), (13, 18)], [(17, 14), (6, 8), (8, 9), (6, 18), (12, 17), (19, 7), (11, 3)], [(5, 6), (13, 4), (2, 10), (14, 12)], [(5, 10), (16, 17), (11, 20), (6, 14), (9, 15), (19, 15), (15, 10), (20, 12), (2, 18)], [(9, 2), (6, 8), (5, 14), (15, 15), (11, 7), (13, 2), (5, 16), (11, 15), (10, 17), (9, 18)], [(10, 18), (2, 15), (13, 13), (5, 20), (6, 2), (15, 11), (12, 4), (15, 12), (15, 15)], [(5, 16), (6, 10), (2, 5)], [(20, 15), (9, 9)], [(13, 18), (3, 10), (5, 6), (16, 13), (11, 7), (15, 17), (15, 17)], [(3, 6), (8, 18), (16, 8), (14, 2), (20, 6), (15, 17), (3, 16), (17, 19), (8, 10)], [(8, 6), (2, 12)], [(4, 15), (8, 5), (13, 18), (12, 20), (20, 13)], [(17, 10), (4, 7), (3, 14), (17, 20), (16, 15)], [(5, 10), (12, 8)], [(18, 17), (7, 14), (4, 19), (10, 4), (11, 10), (9, 9), (4, 12), (14, 16), (13, 13), (19, 7)], [(14, 14), (12, 17), (16, 5), (4, 18), (2, 16), (20, 17), (9, 10)], [(6, 14), (8, 17), (6, 15), (3, 20), (9, 9), (12, 3), (13, 11), (9, 20), (18, 19)], [(16, 18), (16, 2)], [(8, 10), (9, 10), (5, 2)], [(15, 5), (10, 19), (18, 17), (20, 13), (19, 19), (19, 9), (14, 15), (15, 9), (6, 11), (5, 9)], [(10, 7), (19, 5), (16, 9), (2, 5), (11, 11), (7, 13), (9, 17), (9, 14), (10, 18)], [(3, 8), (2, 13), (12, 12), (17, 2), (13, 19), (17, 19)], [(8, 3), (5, 7), (12, 15), (11, 3)], [(6, 17), (15, 17), (18, 15), (12, 10)], [(6, 13), (13, 10), (12, 8), (18, 9), (16, 16), (17, 3)], [(10, 2), (6, 9), (14, 2), (9, 15), (5, 3), (11, 19), (12, 20)], [(4, 19), (19, 9)], [(3, 6), (7, 7), (8, 12), (3, 2), (16, 4), (4, 9), (6, 5)], [(3, 9), (8, 2), (9, 9), (8, 2), (14, 9), (9, 18)], [(18, 16), (6, 5), (11, 8), (6, 14)], [(13, 4), (11, 9), (19, 4), (9, 13), (18, 3), (20, 6), (7, 8), (14, 16)], [(5, 20), (12, 18), (15, 16), (4, 9), (4, 5), (17, 8), (7, 5), (13, 12)], [(5, 13), (4, 14), (3, 12), (9, 5)], [(11, 11), (9, 10), (10, 5), (6, 14), (10, 16), (3, 17), (17, 17)], [(17, 9), (3, 17)], [(17, 14), (17, 13), (18, 3), (10, 11), (13, 11)], [(14, 19), (8, 10), (13, 6), (8, 13)], [(3, 6), (12, 6), (12, 7), (15, 17), (5, 7), (13, 10), (7, 10), (7, 14), (16, 11), (14, 13)], [(4, 2), (15, 6), (14, 17), (17, 5), (8, 10), (13, 20), (16, 6), (3, 7)], [(16, 20), (18, 7), (7, 6)], [(2, 9), (16, 19), (8, 12), (16, 11), (5, 3)], [(11, 15), (8, 4), (15, 14), (2, 3), (4, 16), (8, 8)], [(9, 8), (15, 17), (10, 2)], [(7, 10), (18, 6), (17, 4), (4, 8), (4, 8), (6, 9)], [(8, 15), (18, 2), (6, 7), (4, 19), (16, 13), (16, 10), (9, 18), (12, 14)], [(7, 5), (2, 20), (2, 7), (18, 4), (11, 20)]]
    check(robot_building_mem(objects, 317), 334)
    
    objects2=[[(7, 13), (6, 6), (17, 10), (14, 5), (6, 11), (8, 10), (14, 10), (7, 5)], [(7, 7), (20, 18)], [(4, 17), (6, 18), (13, 11), (16, 8), (16, 12), (4, 10), (9, 9), (3, 10)], [(8, 10), (11, 11), (4, 6), (20, 18), (19, 20), (13, 19)], [(20, 7), (13, 12), (18, 10), (3, 11)], [(9, 10), (4, 11), (2, 11), (12, 18), (20, 11)], [(9, 5), (13, 2), (17, 2)], [(10, 19), (18, 4), (10, 13), (7, 7), (18, 4), (10, 18)], [(2, 10), (13, 14), (11, 2)], [(10, 4), (10, 13), (11, 9), (12, 15), (16, 18)], [(13, 10), (2, 14), (2, 5), (17, 3), (18, 19), (20, 12), (4, 15), (14, 20)], [(6, 7), (6, 11), (12, 14), (13, 14), (19, 6), (9, 9), (17, 15)], [(18, 14), (2, 15), (15, 2), (14, 18), (19, 14), (16, 7), (5, 17), (10, 3), (20, 17), (14, 11)], [(18, 9), (17, 11), (13, 5), (8, 2), (4, 2), (20, 17), (11, 15)], [(10, 11), (12, 4), (20, 5), (8, 16), (13, 4), (2, 9), (2, 20), (18, 15)], [(15, 7), (2, 2), (16, 17)], [(12, 20), (19, 9), (18, 10), (9, 4)], [(15, 6), (10, 11), (8, 6), (20, 10), (11, 20), (18, 5), (17, 12), (9, 20), (13, 4), (20, 20)], [(11, 17), (12, 18), (11, 5), (7, 6), (20, 15), (15, 9), (6, 17), (7, 10), (7, 11), (11, 19)], [(17, 15), (2, 3), (5, 10), (5, 5), (14, 9)], [(20, 3), (20, 3), (7, 5), (16, 10), (20, 13), (10, 18)], [(12, 12), (2, 12)], [(15, 8), (4, 18), (18, 2), (6, 18), (9, 16), (19, 9), (8, 18), (8, 7)], [(17, 14), (20, 4)], [(18, 13), (2, 7), (15, 11), (4, 2), (14, 4), (4, 13), (9, 15)], [(7, 3), (9, 18), (7, 14), (10, 10)], [(12, 18), (17, 16)], [(3, 15), (18, 12), (15, 15)], [(3, 17), (8, 4), (5, 19), (2, 9), (19, 18), (7, 13), (9, 5), (18, 11), (12, 4), (7, 5)], [(11, 3), (2, 15), (5, 12), (2, 4), (14, 11), (12, 13), (17, 4), (14, 8), (14, 13), (3, 10)], [(8, 9), (10, 9), (3, 13), (2, 5)], [(19, 20), (13, 20), (7, 5), (16, 12), (9, 14), (10, 16), (20, 16), (18, 10)], [(17, 15), (10, 7), (7, 17), (9, 14), (7, 17), (7, 9), (9, 4), (3, 11), (11, 16)], [(3, 20), (7, 12), (13, 18), (8, 19), (4, 16), (6, 9), (8, 10), (5, 19), (17, 11), (20, 16)], [(15, 10), (18, 18), (8, 9), (6, 12), (3, 15), (13, 18), (4, 9), (11, 14), (12, 5), (6, 4)], [(15, 18), (20, 7)], [(12, 20), (9, 8), (14, 5)], [(9, 18), (16, 18), (13, 9), (4, 4), (20, 19), (10, 8), (6, 7), (10, 6), (3, 20)], [(2, 13), (15, 12), (8, 9), (10, 6), (12, 16)], [(15, 16), (14, 10), (16, 5), (3, 5), (2, 13), (13, 8), (4, 13), (2, 4), (6, 17), (6, 5)], [(14, 16), (3, 13), (5, 18), (5, 19), (18, 4), (17, 6), (4, 6), (11, 11)], [(12, 16), (8, 13), (10, 20), (13, 20), (17, 15)], [(14, 14), (6, 12), (20, 7), (20, 11), (12, 8), (10, 17), (9, 9), (2, 6), (14, 2)], [(9, 8), (3, 16), (14, 11), (11, 16), (3, 6), (8, 6), (8, 13)], [(19, 2), (15, 12), (17, 18), (7, 4), (4, 7)], [(10, 13), (2, 11), (10, 13), (9, 12), (6, 18)], [(11, 12), (16, 6), (15, 3), (3, 19), (13, 8), (20, 6)], [(5, 5), (3, 10), (12, 12), (14, 17), (8, 11), (4, 20)], [(6, 14), (18, 3), (17, 12), (8, 9), (20, 17), (4, 14)], [(14, 4), (11, 4), (3, 20), (4, 19), (18, 17), (3, 6)], [(15, 4), (5, 7), (17, 16), (11, 12), (12, 3), (7, 15), (8, 20)], [(3, 18), (19, 12), (9, 19), (4, 10), (9, 7), (5, 9), (8, 6), (8, 3)], [(4, 11), (15, 17), (16, 4)], [(7, 8), (9, 15), (15, 9), (20, 17), (13, 15), (7, 20), (7, 3), (6, 2), (12, 4)], [(8, 6), (11, 11), (16, 7), (9, 8), (20, 17), (8, 12), (7, 5)], [(2, 5), (19, 11), (20, 12), (19, 10)], [(15, 20), (20, 9), (7, 14), (19, 11), (9, 13), (4, 15), (2, 19), (14, 8), (12, 6), (20, 16)], [(18, 4), (4, 16), (6, 11), (17, 16), (17, 6), (4, 3), (19, 8), (10, 11), (2, 16)], [(7, 6), (19, 15), (17, 11), (4, 11)], [(20, 6), (6, 10), (14, 20), (16, 16), (7, 4), (10, 15), (16, 10)], [(15, 10), (2, 5), (20, 17), (6, 13), (17, 3), (13, 12)], [(3, 4), (14, 20), (17, 7), (6, 3), (3, 2), (13, 17), (6, 18)], [(14, 6), (7, 15), (13, 2), (17, 7), (12, 3)], [(5, 12), (6, 7), (14, 4), (19, 17), (11, 11), (7, 10), (10, 5)], [(5, 11), (16, 18), (11, 3), (14, 12), (16, 3)], [(14, 15), (14, 17), (7, 3), (4, 12), (2, 20)], [(19, 8), (7, 15), (15, 4)], [(4, 16), (7, 11), (8, 20)], [(2, 3), (13, 16), (17, 16), (20, 10), (18, 10), (10, 12), (17, 5), (6, 5), (13, 11)], [(17, 6), (19, 17), (2, 5)]]
    check(robot_building_mem(objects2, 560), 362)


# In[ ]:


test_long()


# ## 3.3 Runtime Analysis
# What is the runtime of your memoized algorithm? Explain your reasoning. Also check with a teaching assistant.

# ### Solution
# Write your solution here