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

# # Week 4 Day 18 Supplementary Exercises
# 
# # The Adventures of Minitron Part III: Bomb Squad (Continued)
# #### Creators
# Abraham Kassahun Negash
# <br>
# Andrew Zuckerman
# 
# #### Reviewers
# Insert Reviewers
# 
# Our trusty Minitron has been tasked with the diffusion of a bomb. Minitron has never diffused a bomb before and has no idea how to do it. It is up to you to tell the robot how to proceed. However, there is one problem. The robot doesn't have enough memory to store all your instructions. So you decide to make your instruction as short as possible and take out the spaces. But now Minitron is receiving a string which it doesn't understand. Can you help Minitron be able to break the string into the original instructions. 

# 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[ ]:


def checkUnorderedList(actual, expected):
    
    if set(actual) == set(expected):
        print(f"Congratulations, the test case passed!")
    else:
        print(f"Your list is different from the solution list")
        print(f"Your list: {actual}")
        print(f"The true return value: {actual}")


# ## 4. Time is gold
# 
# 

# ### 4.1. Implement using DP 
# Can you rewrite your algorithm from problem 3 using a dynamic programming, bottom-up approach?

# In[ ]:


# Write your solution here
def recursiveBreakable(S, w):
  return False


# ### 4.2. Testing your solution
# Now test your algorithm on the same input from problem 2.3. Your input string is "icecreamcone" and your list of words is: "i", "ice", "cream", "cone", "con", "am", "ream" and "one".

# In[68]:


words = ["i", "ice", "cream", "cone", "con", "am", "ream", "one"]
check(dynamicBreakable("icecreamcone", words), True)


# In[69]:


# Let's modify words by deleting "ice" so that if you run your algorithm, it returns False
words = ["i", "cream", "cone", "con", "am", "ream", "one"]
words2 = ['It', 'is', 'one', 'am' , 'thing', 'to', 'hello', 'know', 'if', 'a', 'string', 'cream' , 'can', 'one' , 'be', 'broken', 'down', 'into', 'valid', 'words', 'but', 'can', 'we', 'also', 'know', 'the', 'exact', 'way']

check(dynamicBreakable("icecreamcone", words), False)
# Check
check(dynamicBreakable("Itisonethingtoknowifastringcanbebrokendownintovalidwordsbutcanwealsoknowtheexactway", words2), True)


# ### 4.2. How fast is it?
# What is the running time of this algorithm? Given a string of size <i>m</i> and a list of <i>n</i> words (where <i>s</i> is the size of the smallest word in your dictionary and <i>l</i> is the size of the longest word in your dicitonary)?

# In[ ]:


# Your answer here
O()


# ## 5. Breaking it Down
# It is one thing to know if a string can be broken down into valid words, but can we also know the exact way(s) to break it down? (Just like you did in problem 1.2)
# 
# Write a recursive algorithm that takes in a string `S` and a list of words `w` and outputs a list of strings that show all the way that `S` can be broken down into valid words (in no particular order). For example, given `S = "freshmango"` and `w=["fresh", "mango", "man" "go", "an"]`, your output should be a list such as `["fresh mango", "fresh man go"]`. If there are no valid ways to break apart the input string, return an empty list.

# In[ ]:


# Write your solution here (you may want to create a helper function!)
def recursiveWBSolutions(S, w):
    return []


# ### 5.1. Testing your solution

# In[ ]:


words = ["a", "b", "c", "d", "e", "bcd", "abc", "ab", "de"]
sol = ["abc de", "abc d e", "ab c de", "ab c d e", "a bcd e", "a b c de", "a b c d e"]

# Check
checkUnorderedList(recursiveWBSolutions("abcde", words), sol)


# ## And now to defuse the bomb!
# Run the below code and figure out which set of instructions makes the most sense :)

# In[ ]:


instructions = "openthebombcuttheredwireinserttheyellowtransistorsoldertheconnectionbacktogether"

englishDictionary = ['the', 'of', 'to', 'and', 'a', 'in', 'is', 'it', 'you', 'that', 'he', 'was', 'for', 'on', 'are', 'with', 'as', 'I', 'his', 'they', 'be', 'at', 'one', 'have', 'this', 'from', 'or', 'had', 'by', 'hot', 'word', 'but', 'what', 'some', 'we', 'can', 'out', 'other', 'were', 'all', 'there', 'when', 'up', 'use', 'your', 'how', 'said', 'an', 'each', 'she', 'which', 'do', 'their', 'time', 'if', 'will', 'way', 'about', 'many', 'then', 'them', 'write', 'would', 'like', 'so', 'these', 'her', 'long', 'make', 'thing', 'see', 'him', 'two', 'has', 'look', 'more', 'day', 'could', 'go', 'come', 'did', 'number', 'sound', 'no', 'most', 'people', 'my', 'over', 'know', 'water', 'than', 'call', 'first', 'who', 'may', 'down', 'side', 'been', 'now', 'find', 'any', 'new', 'work', 'part', 'take', 'get', 'place', 'made', 'live', 'where', 'after', 'back', 'little', 'only', 'round', 'man', 'year', 'came', 'show', 'every', 'good', 'me', 'give', 'our', 'under', 'name', 'very', 'through', 'just', 'form', 'sentence', 'great', 'think', 'say', 'help', 'low', 'line', 'differ', 'turn', 'cause', 'much', 'mean', 'before', 'move', 'right', 'boy', 'old', 'too', 'same', 'tell', 'does', 'set', 'three', 'want', 'air', 'well', 'also', 'play', 'small', 'end', 'put', 'home', 'read', 'hand', 'port', 'large', 'spell', 'add', 'even', 'land', 'here', 'must', 'big', 'high', 'such', 'follow', 'act', 'why', 'ask', 'men', 'change', 'went', 'light', 'kind', 'off', 'need', 'house', 'picture', 'try', 'us', 'again', 'animal', 'point', 'mother', 'world', 'near', 'build', 'self', 'earth', 'father', 'head', 'stand', 'own', 'page', 'should', 'country', 'found', 'answer', 'school', 'grow', 'study', 'still', 'learn', 'plant', 'cover', 'food', 'sun', 'four', 'between', 'state', 'keep', 'eye', 'never', 'last', 'let', 'thought', 'city', 'tree', 'cross', 'farm', 'hard', 'start', 'might', 'story', 'saw', 'far', 'sea', 'draw', 'left', 'late', 'run', "don't", 'while', 'press', 'close', 'night', 'real', 'life', 'few', 'north', 'open', 'seem', 'together', 'next', 'white', 'children', 'begin', 'got', 'walk', 'example', 'ease', 'paper', 'group', 'always', 'music', 'those', 'both', 'mark', 'often', 'letter', 'until', 'mile', 'river', 'car', 'feet', 'care', 'second', 'book', 'carry', 'took', 'science', 'eat', 'room', 'friend', 'began', 'idea', 'fish', 'mountain', 'stop', 'once', 'base', 'hear', 'horse', 'cut', 'sure', 'watch', 'color', 'face', 'wood', 'main', 'enough', 'plain', 'girl', 'usual', 'young', 'ready', 'above', 'ever', 'red', 'list', 'though', 'feel', 'talk', 'bird', 'soon', 'body', 'dog', 'family', 'direct', 'pose', 'leave', 'song', 'measure', 'door', 'product', 'black', 'short', 'numeral', 'class', 'wind', 'question', 'happen', 'complete', 'ship', 'area', 'half', 'rock', 'order', 'fire', 'south', 'problem', 'piece', 'told', 'knew', 'pass', 'since', 'top', 'whole', 'king', 'space', 'heard', 'best', 'hour', 'better', 'true', 'during', 'hundred', 'five', 'remember', 'step', 'early', 'hold', 'west', 'ground', 'interest', 'reach', 'fast', 'verb', 'sing', 'listen', 'six', 'table', 'travel', 'less', 'morning', 'ten', 'simple', 'several', 'vowel', 'toward', 'war', 'lay', 'against', 'pattern', 'slow', 'center', 'love', 'person', 'money', 'serve', 'appear', 'road', 'map', 'rain', 'rule', 'govern', 'pull', 'cold', 'notice', 'voice', 'unit', 'power', 'town', 'fine', 'certain', 'fly', 'fall', 'lead', 'cry', 'dark', 'machine', 'note', 'wait', 'plan', 'figure', 'star', 'box', 'noun', 'field', 'rest', 'correct', 'able', 'pound', 'done', 'beauty', 'drive', 'stood', 'contain', 'front', 'teach', 'week', 'final', 'gave', 'green', 'oh', 'quick', 'develop', 'ocean', 'warm', 'free', 'minute', 'strong', 'special', 'mind', 'behind', 'clear', 'tail', 'produce', 'fact', 'street', 'inch', 'multiply', 'nothing', 'course', 'transistor', 'stay', 'wheel', 'full', 'force', 'blue', 'object', 'decide', 'surface', 'deep', 'moon', 'island', 'foot', 'system', 'busy', 'test', 'record', 'boat', 'common', 'bomb', 'insert', 'gold', 'possible', 'plane', 'stead', 'dry', 'wonder', 'laugh', 'thousand', 'ago', 'ran', 'check', 'game', 'shape', 'equate', 'hot', 'miss', 'brought', 'heat', 'snow', 'tire', 'bring', 'yes', 'distant', 'fill', 'east', 'paint', 'language', 'among', 'grand', 'ball', 'yet', 'wave', 'drop', 'heart', 'am', 'present', 'heavy', 'dance', 'engine', 'position', 'arm', 'wide', 'sail', 'material', 'size', 'vary', 'settle', 'speak', 'weight', 'general', 'ice', 'matter', 'circle', 'pair', 'include', 'divide', 'syllable', 'felt', 'perhaps', 'pick', 'sudden', 'count', 'square', 'reason', 'length', 'represent', 'art', 'subject', 'region', 'energy', 'hunt', 'probable', 'bed', 'brother', 'egg', 'ride', 'cell', 'believe', 'fraction', 'forest', 'sit', 'race', 'window', 'store', 'summer', 'train', 'sleep', 'prove', 'lone', 'leg', 'exercise', 'wall', 'catch', 'mount', 'wish', 'sky', 'board', 'joy', 'winter', 'sat', 'written', 'wild', 'instrument', 'kept', 'glass', 'grass', 'cow', 'job', 'edge', 'sign', 'visit', 'past', 'soft', 'fun', 'bright', 'gas', 'weather', 'month', 'million', 'bear', 'finish', 'happy', 'hope', 'flower', 'clothe', 'strange', 'gone', 'jump', 'baby', 'eight', 'village', 'meet', 'root', 'buy', 'raise', 'solve', 'metal', 'whether', 'push', 'seven', 'paragraph', 'third', 'shall', 'held', 'hair', 'describe', 'cook', 'floor', 'either', 'result', 'burn', 'hill', 'safe', 'cat', 'century', 'consider', 'type', 'law', 'bit', 'coast', 'copy', 'phrase', 'silent', 'tall', 'sand', 'soil', 'roll', 'temperature', 'finger', 'industry', 'value', 'fight', 'lie', 'beat', 'excite', 'natural', 'view', 'sense', 'ear', 'else', 'quite', 'broke', 'case', 'middle', 'kill', 'son', 'lake', 'moment', 'scale', 'loud', 'spring', 'observe', 'child', 'straight', 'consonant', 'nation', 'dictionary', 'milk', 'speed', 'method', 'organ', 'pay', 'age', 'section', 'solder', 'connection', 'dress', 'cloud', 'surprise', 'quiet', 'stone', 'tiny', 'climb', 'cool', 'design', 'poor', 'lot', 'experiment', 'bottom', 'key', 'iron', 'single', 'stick', 'flat', 'twenty', 'skin', 'smile', 'crease', 'hole', 'trade', 'melody', 'trip', 'office', 'receive', 'row', 'mouth', 'exact', 'symbol', 'die', 'least', 'trouble', 'shout', 'except', 'wrote', 'seed', 'tone', 'join', 'suggest', 'clean', 'break', 'lady', 'yard', 'rise', 'bad', 'blow', 'oil', 'blood', 'touch', 'grew', 'cent', 'mix', 'team', 'wire', 'cost', 'lost', 'brown', 'wear', 'garden', 'equal', 'sent', 'choose', 'fell', 'fit', 'flow', 'fair', 'bank', 'collect', 'save', 'control', 'decimal', 'gentle', 'woman', 'captain', 'practice', 'separate', 'difficult', 'doctor', 'please', 'protect', 'noon', 'whose', 'locate', 'ring', 'character', 'insect', 'caught', 'period', 'indicate', 'radio', 'spoke', 'atom', 'human', 'history', 'effect', 'electric', 'expect', 'crop', 'modern', 'element', 'hit', 'student', 'corner', 'party', 'supply', 'bone', 'rail', 'imagine', 'provide', 'agree', 'thus', 'capital', "won't", 'chair', 'danger', 'fruit', 'rich', 'thick', 'soldier', 'process', 'operate', 'guess', 'necessary', 'sharp', 'wing', 'create', 'neighbor', 'wash', 'bat', 'rather', 'crowd', 'corn', 'compare', 'poem', 'string', 'bell', 'depend', 'meat', 'rub', 'tube', 'famous', 'dollar', 'stream', 'fear', 'sight', 'thin', 'triangle', 'planet', 'hurry', 'chief', 'colony', 'clock', 'mine', 'tie', 'enter', 'major', 'fresh', 'search', 'send', 'yellow', 'gun', 'allow', 'print', 'dead', 'spot', 'desert', 'suit', 'current', 'lift', 'rose', 'continue', 'block', 'chart', 'hat', 'sell', 'success', 'company', 'subtract', 'event', 'particular', 'deal', 'swim', 'term', 'opposite', 'wife', 'shoe', 'shoulder', 'spread', 'arrange', 'camp', 'invent', 'cotton', 'born', 'determine', 'quart', 'nine', 'truck', 'noise', 'level', 'chance', 'gather', 'shop', 'stretch', 'throw', 'shine', 'property', 'column', 'molecule', 'select', 'wrong', 'gray', 'repeat', 'require', 'broad', 'prepare', 'salt', 'nose', 'plural', 'anger', 'claim', 'continent', 'oxygen', 'sugar', 'death', 'pretty', 'skill', 'women', 'season', 'solution', 'magnet', 'silver', 'thank', 'branch', 'match', 'suffix', 'especially', 'fig', 'afraid', 'huge', 'sister', 'steel', 'discuss', 'forward', 'similar', 'guide', 'experience', 'score', 'apple', 'bought', 'led', 'pitch', 'coat', 'mass', 'card', 'band', 'rope', 'slip', 'win', 'dream', 'evening', 'condition', 'feed', 'tool', 'total', 'basic', 'smell', 'valley', 'nor', 'double', 'seat', 'arrive', 'master', 'track', 'parent', 'shore', 'division', 'sheet', 'substance', 'favor', 'connect', 'post', 'spend', 'chord', 'fat', 'glad', 'original', 'share', 'station', 'dad', 'bread', 'charge', 'proper', 'bar', 'offer', 'segment', 'slave', 'duck', 'instant', 'market', 'degree', 'populate', 'chick', 'dear', 'enemy', 'reply', 'drink', 'occur', 'support', 'speech', 'nature', 'range', 'steam', 'motion', 'path', 'liquid', 'log', 'meant', 'quotient', 'teeth', 'shell', 'neck']


# In[ ]:


# Figure out the instructions!
recursiveWBSolutions(instructions, englishDictionary)


# ## Moving On
# Minitron has now understood your instructions and has performed it admirably. But now it is time to say goodbye. Sadness is in the air because this maybe the last time you go on an adventure together. Solving one last problem might lift everyone's spirits.

# ## 6. Longest Increasing Subsequence (Challenge)
# 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.

# ### 6.1
# First implement `lis` using plain recursion

# In[ ]:





# #### 6.2
# Implement a faster version of `lis` using memoization

# In[ ]:





# ### 6.3 Check

# In[ ]:


# Check your solutions
check(lis([]), 0)
check(lis([1]), 1)
check(lis([5,4,3,2,1]), 1)
check(lis([1,1,1]), 1)
check(lis([1,1,1,2,2,2]), 2)
check(lis([1,1,1,6,2,2,2]), 2)
check(lis([1,2,3,4,5]), 5)
check(lis([1,2,2,3,4,5]), 5)
check(lis([1,3,2,3,4,5]), 5)
check(lis([1,2,5,2,3,8,5,6,9]), 6)
check(lis([1,6,7,8,2,3,4,5,6]), 6)
check(lis([4,6,7,8,9,10,1,2,3,4,5,1,1,2,2,8,8,9,9]), 7)
check(lis([0, -4, 10, 2, 4, 8, 11, 13, -8, 1, 2, 3, 5, 15]), 7)
check(lis([59, 20, 30, 28, 7, 65, 33, 67, 77, 46, 83, 93, 54, 22, 71, 91, 44, 99, 37, 47, 2, 82, 25, 61, 16, 12, 75, 80, 99, 19, 60, 78, 38, 1, 59, 31, 71, 93, 37, 17, 28, 2, 75, 60, 53, 82, 31, 18, 65, 29, 97, 27, 34, 92, 20, 36, 90, 48, 60, 100, 21, 63, 19, 97, 84, 47, 80, 6, 62, 35, 79, 99, 36, 61, 44, 81, 78, 64, 59, 93, 85, 75, 21, 29, 42, 71, 82, 19, 81, 23, 47, 42, 16, 52, 43, 42, 81, 97, 32, 45]),14)


# In[ ]: