<jupyter_start><jupyter_text>Data Structures Expanding on our knowledge from the data types introduced last session, this class we make our code more pythonic by introducing advanced methods and tools. Covers list and dict comprehensions, the iterator toolkit for efficient looping, and how to create generators. You’ll learn how to import other libraries, write anonymous functions with lambdas, and go on a rudimentary exploration of the functional programming paradigm with the map, filter, and reduce functions.At the end of this class you’ll be able to choose the right data structures to represent your problem and use efficient methods to stream your data through your script.  Agenda      2.0 While Loops     2.1 List Comprehensions     2.2 Set Comprehensions     2.3 Dictionaries     2.4 Dictionary Comprehension     2.5 Collections     2.6 Python Execution Environment       While We covered 'for' loops in the previous session, but Python also allows you to construct while loops. The syntax for while statement is like ```pythonwhile condition:    statement1    statement2``` The code we want to reuse must be indented properly under the while statement. They will be executed if the condition is true. Again like in if-else statement any non zero value is true. Let us write a simple code to print numbers 0 to 10<jupyter_code>n = 0
while n < 11:
    print(n)
    n += 1<jupyter_output>0
1
2
3
4
5
6
7
8
9
10<jupyter_text>break Let us write a program to evaluate the power series. The series looks like $e**x =1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} +....+ \frac{x^n}{n!} $ where $0 < x < 1$<jupyter_code>x = float(input("Enter the value of x: "))
n = term = num = 1
summation = 1.0
while n <= 100:
    term *= x / n
    summation += term
    n += 1
    if term < 0.0001:
        break
print("No of Times= {} and Sum= {}".format(n, summation))<jupyter_output>Enter the value of x: 1
No of Times= 9 and Sum= 2.71827876984127<jupyter_text>What break does is stop the innermost loop. In this example we are using break under the if statement. This means if the value of term is less than 0.0001 then get out of the loop.  continue Just like break we have another statement, continue, which skips the execution of the code after itself and goes back to the start of the loop. That means it will help you to skip a part of the loop. In the below example we will ask the user to input an integer, if the input is negative then we will ask again, if positive then we will square the number. To get out of the infinite loop user must input 0.<jupyter_code>while True:
    n = int(input("Please enter an Integer: "))
    if n < 0:
        continue # this will take the execution back to the starting of the loop
    elif n == 0:
        break
    print("Square is ", n ** 2)
print("Goodbye")<jupyter_output>Please enter an Integer: 1
Square is  1
Please enter an Integer: 2
Square is  4
Please enter an Integer: 3
Square is  9
Please enter an Integer: 4
Square is  16
Please enter an Integer: 4
Square is  16
Please enter an Integer: 5
Square is  25
Please enter an Integer: 5
Square is  25<jupyter_text>**Problem** : Game of Sticks<jupyter_code>sticks = 21

print("There are 21 sticks, you can take 1-4 number of sticks at a time.")
print("Whoever will take the last stick will loose")

while True:
    print("Sticks left: " , sticks)
    sticks_taken = int(input("Take sticks(1-4):"))
    if sticks == 1:
        print("You took the last stick, you loose")
        break
    if sticks_taken >= 5 or sticks_taken <= 0:
        print("Wrong choice")
        continue
    print("Computer took: " , (5 - sticks_taken) , "\n")
    sticks -= 5<jupyter_output>There are 21 sticks, you can take 1-4 number of sticks at a time.
Whoever will take the last stick will loose
Sticks left:  21
Take sticks(1-4):1
Computer took:  4 

Sticks left:  16
Take sticks(1-4):2
Computer took:  3 

Sticks left:  11
Take sticks(1-4):4
Computer took:  1 

Sticks left:  6
Take sticks(1-4):1
Computer took:  4 

Sticks left:  1
Take sticks(1-4):1
You took the last stick, you loose<jupyter_text>Can you figure out how to win?  What if you were a programmer?  List Comprehensions List Comprehensions provide a concise way of creating lists. Many times a complex task can be modelled in a single line. Here are some simple examples for transforming a list.<jupyter_code>a = range(10)
a
[x for x in a]
[x+1 for x in a]<jupyter_output><empty_output><jupyter_text>It is also possible to filter a list using if inside a list comprehension.<jupyter_code>a = range(10)
[x for x in a if x % 2 == 0]
[x*x for x in a if x%2 == 0]<jupyter_output><empty_output><jupyter_text>It is possible to iterate over multiple lists using the built-in function zip.<jupyter_code>a = [1, 2, 3, 4]
b = [2, 3, 5, 7]
zip(a, b)
[x+y for x, y in zip(a, b)]<jupyter_output><empty_output><jupyter_text>we can use multiple for clauses in single list comprehension.<jupyter_code>[(x, y) for x in range(5) for y in range(5) if (x+y)%2 == 0]
[(x, y) for x in range(5) for y in range(5) if (x+y)%2 == 0 and x != y]
[(x, y) for x in range(5) for y in range(x) if (x+y)%2 == 0]<jupyter_output><empty_output><jupyter_text>The following example finds all Pythagorean triplets using numbers below 25. (x, y, z) is a called pythagorean triplet if `x*x + y*y == z*z`.<jupyter_code>n = 25
[(x, y, z) for x in range(1, n) for y in range(x, n) for z in range(y, n) if x*x + y*y == z*z]<jupyter_output><empty_output><jupyter_text>**Problem** : Provide an implementation for zip function using list comprehensions.<jupyter_code>zip([1, 2, 3], ["a", "b", "c"])<jupyter_output><empty_output><jupyter_text>**Problem** : Python provides a built-in function map that applies a function to each element of a list. Provide an implementation for map using list comprehensions.<jupyter_code>def square(x): return x * x
list(map(square, [1,2,3,4,5]))<jupyter_output><empty_output><jupyter_text>Set Comprehension Set comprehensions allow sets to be constructed using the same principles as list comprehensions, the only difference is that resulting sequence is a set. Say we have a list of names. The list can contain names which only differ in the case used to represent them, duplicates and names consisting of only one character. We are only interested in names longer then one character and wish to represent all names in the same format: The first letter should be capitalised, all other characters should be lower case.<jupyter_code># Given the list 
names = [ 'Bob', 'JOHN', 'alice', 'bob', 'ALICE', 'J', 'Bob' ]
# We require the set:
{ 'Bob', 'John', 'Alice' }<jupyter_output><empty_output><jupyter_text>Note the syntax for denoting a set. Members are enclosed in curly braces.The following set comprehension accomplishes this:<jupyter_code>{ name[0].upper() + name[1:].lower() for name in names if len(name) > 1 }<jupyter_output><empty_output><jupyter_text>DictionariesOne of the most loved data structures in Computer Science!!What makes them so cool? Dictionaries are like lists, but they can be indexed with non integer keys also. Unlike lists, dictionaries are not ordered.<jupyter_code>a = {'x': 1, 'y': 2, 'z': 3}
a['x']
a['z']
b = {}
b['x'] = 2
b[2] = 'foo'
b[(1, 2)] = 3
b<jupyter_output><empty_output><jupyter_text>The del keyword can be used to delete an item from a dictionary.<jupyter_code>a = {'x': 1, 'y': 2, 'z': 3}
del a['x']<jupyter_output><empty_output><jupyter_text>The keys method returns all keys in a dictionary, the values method returns all values in a dictionary and items method returns all key-value pairs in a dictionary.<jupyter_code>a.keys()
a.values()
a.items()<jupyter_output><empty_output><jupyter_text>The for statement can be used to iterate over a dictionary.<jupyter_code>for key in a: print(key)
for key, value in a.items(): print(key, value)<jupyter_output>y 2
z 3<jupyter_text>Presence of a key in a dictionary can be tested using in operator or has_key method.<jupyter_code>'x' in a
'p' in a
'g' in a.keys()<jupyter_output><empty_output><jupyter_text>Other useful methods on dictionaries are get and setdefault.<jupyter_code>d = {'x': 1, 'y': 2, 'z': 3}
d.get('x', 5)
d.get('p', 5)
d.setdefault('x', 0)
d.setdefault('p', 0)<jupyter_output><empty_output><jupyter_text>Dictionaries can be used in string formatting to specify named parameters.<jupyter_code>'hello %(name)s' % {'name': 'python'}
'Tutorial %(index)d: %(name)s' % {'index': 2, 'name': 'Data Structures'}<jupyter_output><empty_output><jupyter_text>Example: Word Frequency Suppose we want to find number of occurrences of each word in a file. Dictionary can be used to store the number of occurrences for each word.Lets first write a function to count frequency of words, given a list of words.<jupyter_code>def word_frequency(words):
    """Returns frequency of each word given a list of words.

        >>> word_frequency(['a', 'b', 'a'])
        {'a': 2, 'b': 1}
    """
    frequency = {}
    for w in words:
        try:
            frequency[w] += 1
        except KeyError:
            frequency[w] = 1
        
    return frequency<jupyter_output><empty_output><jupyter_text>**Problem** : How could we have used the .get() method to avoid the try execpt clause?<jupyter_code># solution('ZnJlcXVlbmN5W3ddID0gZnJlcXVlbmN5LmdldCh3LCAwKSArIDE=')<jupyter_output><empty_output><jupyter_text>Getting words from a file is very trivial.<jupyter_code>def read_words(filename):
    return open(filename).read().split()<jupyter_output><empty_output><jupyter_text>We can combine these two functions to find frequency of all words in a file.<jupyter_code>def main(filename):
    frequency = word_frequency(read_words(filename))
    for word, count in frequency.items():
        print(word.lower(), count)
        
# In a Python Script, you'd add this to the bottom to make it run from the command line
# while also taking in a single argument referring to the filename.
# 
# if __name__ == "__main__":
#     import sys
#     main(sys.argv[1])
main('files/straight_outta_compton.txt')<jupyter_output>you 3
are 3
now 1
about 3
to 7
witness 2
the 33
strength 1
of 11
street 2
knowledge 1
verse 3
one: 1
ice 3
cube 3
straight 3
outta 6
compton, 5
crazy 4
motherfucker 5
named 1
from 1
gang 1
called 3
niggaz 2
with 1
attitudes 1
when 1
i'm 16
off, 1
i 19
got 3
a 38
sawed 1
off 4
squeeze 1
trigger, 1
and 11
bodies 1
hauled 1
too, 1
boy, 2
if 4
ya 2
fuck 5
with 6
me 7
the 3
police 1
gonna 1
hafta 1
come 2
get 5
off 1
yo 4
ass, 1
that's 6
how 1
goin 1
out 3
for 2
punk 2
motherfuckers 2
showin 2
start 1
mumble, 1
they 3
wanna 1
rumble 1
mix 1
em 3
cook 1
in 6
pot 1
like 7
gumbo 1
goin 1
on 3
that 5
gat 1
pointed 1
at 2
ass 4
so 4
give 4
it 3
up 3
smooth 1
ain't 1
no 3
tellin 1
when 6
down 2
for 2
jack 1
move 1
here's 1
murder 1
rap 1
keep 1
dancin 1
crime 1
record 1
charles 1
manson 1
ak-47 1
is 12
tool 1
don't 1
make 4
act 1
motherfuckin 3
fool 1
me 1
you 8
can 1
go 2
toe 1
toe, 1
maybe 1
knockin 1
niggaz 2
tha 2
box, 1
daily 1
weekly, 1
monthly 1
yearly 1
until 1
them 1
dumb 2
see 4
clearly[...]<jupyter_text>**Problem **: Improve the above program to print the words in the descending order of the number of occurrences.<jupyter_code># Tip : List compresension to the rescue!<jupyter_output><empty_output><jupyter_text>Dictionary Comprehension Say we have a dictionary the keys of which are characters and the values of which map to the number of times that character appears in some text. The dictionary currently distinguishes between upper and lower case characters.We require a dictionary in which the occurrences of upper and lower case characters are combined:<jupyter_code>mcase = {'a':10, 'b': 34, 'A': 7, 'Z':3}

mcase_frequency = { k.lower() : mcase.get(k.lower(), 0) + mcase.get(k.upper(), 0) for k in mcase.keys() }

# mcase_frequency == {'a': 17, 'z': 3, 'b': 34}<jupyter_output><empty_output><jupyter_text>Instead of a list comprehension, we could have simply used a dict comprehension in the last problem.<jupyter_code>a_dict = {'a': 1, 'b': 2, 'c': 3}
{value:key for key, value in a_dict.items()}<jupyter_output><empty_output><jupyter_text>Of course, this only works if the values of the dictionary are immutable, like strings or tuples. If you try this with a dictionary that contains lists, it will fail most spectacularly.<jupyter_code>a_dict = {'a': [1, 2, 3], 'b': 4, 'c': 5}
# {value:key for key, value in a_dict.items()}<jupyter_output><empty_output><jupyter_text>Collections This sectioncovers a module called Collections which implements some nice data structures which will help you to solve various real life problems.<jupyter_code>import collections<jupyter_output><empty_output><jupyter_text>Counter Counter is a dict subclass which helps to count hashable objects. Inside it elements are stored as dictionary keys and counts are stored as values which can be zero or negative.<jupyter_code>from collections import Counter
import re
path = 'files/straight_outta_compton.txt'
# let's be a bit more precise about what we mean by 'words'
words = re.findall('\w+', open(path).read().lower())
Counter(words).most_common(10)<jupyter_output><empty_output><jupyter_text>Print out the methods available to you<jupyter_code># dir(Counter)
[n for n in dir(Counter) if '__' not in n]<jupyter_output><empty_output><jupyter_text>Counter objects has a method called elements which returns an iterator over elements repeating each as many times as its count. Elements are returned in arbitrary order.<jupyter_code>c = Counter(a=4, b=2, c=0, d=-2)
list(c.elements())<jupyter_output><empty_output><jupyter_text>most_common is a method which returns most common elements and their counts from the most common to the least.<jupyter_code>Counter('abracadabra').most_common(3)<jupyter_output><empty_output><jupyter_text>Default Dictionary A defaultdict is a dictionary with a default value for keys, so that keys for which no value has been explicitly defined can be accessed without errors. Let’s see it in action. Using defaultdict is faster than doing the same using dict.set_default method.  Word Frequency Revisited We previously used a try/except clause to word around the missing starting value in the dict.<jupyter_code>def word_frequency(words):
    frequency = {}
    for w in words:
        try:
            frequency[w] += 1
        except KeyError:
            frequency[w] = 1<jupyter_output><empty_output><jupyter_text>A defaultdict is just like a regular Python dict, except that it supports an additional argument at initialization: a function. If someone attempts to access a key to which no value has been assigned, that function will be called (without arguments) and its return value is used as the default value for the key.  Going back to our example, we want the default value to be 0, so we pass the built-in function int()to the defaultdict constructor. When called without arguments, the int() function simply returns 0.<jupyter_code>from collections import defaultdict

def word_frequency(words):
    frequency = defaultdict(int)
    for w in words:
        frequency[w] += 1<jupyter_output><empty_output><jupyter_text>Ordered dictionaries  Named Tuple Named tuples helps to have meaning of each position in a tuple and allow us to code with better readability and self-documenting code. You can use them in any place where you are using tuples. In the example we will create a namedtuple to show hold information for points.<jupyter_code>from collections import namedtuple

Point = namedtuple('Point', ['x', 'y'])
p = Point(10, y=20)
p
Point(x=10, y=20)
p.x + p.y
p[0] + p[1]  # Accessing the values in normal way
x, y = p     # Unpacking the tuple
x
y<jupyter_output><empty_output><jupyter_text>Python Execution Environment Python stores the variables we use as a dictionary. The globals() function returns all the globals variables in the current environment.<jupyter_code>globals()
x = 1
globals()
x = 1
globals()['x'] = 3
x<jupyter_output><empty_output><jupyter_text>Just like globals python also provides a function locals which gives all the local variables in a function.<jupyter_code>def f(a, b): print(locals())<jupyter_output><empty_output><jupyter_text>One more example:<jupyter_code>def f(name):
    return "Hello %(name)s!" % locals()
f("Guido")<jupyter_output><empty_output><jupyter_text>Python String Formatting  Number Formatting The following table shows various ways to format numbers using python's newish str.format(), examples for both float formatting and integers.To run examples use print("FORMAT".format(NUMBER)); So to get the output of the first example, you would run: print("{:.2f}".format(3.1415926)); | Number     | Format  | Output    | Description                                   ||------------|---------|-----------|-----------------------------------------------|| 3.1415926  | {:.2f}  | 3.14      | 2 decimal places                              || 3.1415926  | {:+.2f} | +3.14     | 2 decimal places with sign                    || -1         | {:+.2f} | -1.00     | 2 decimal places with sign                    || 2.71828    | {:.0f}  | 3         | No decimal places                             || 5          | {:0>2d} | 05        | Pad number with zeros (left padding, width 2) || 5          | {:x<4d} | 5xxx      | Pad number with x's (right padding, width 4)  || 10         | {:x<4d} | 10xx      | Pad number with x's (right padding, width 4)  || 1000000    | {:,}    | 1,000,000 | Number format with comma separator            || 0.25       | {:.2%}  | 25.00%    | Format percentage                             || 1000000000 | {:.2e}  | 1.00e+09  | Exponent notation                             || 13         | {:10d}  | 13        | Right aligned (default, width 10)             || 13         | {:<10d} | 13        | Left aligned (width 10)                       || 13         | {:^10d} | 13        | Center aligned (width 10)                     |  string.format() basics Here are a couple of example of basic string substitution, the {} is the placeholder for the substituted variables. If no format is specified, it will insert and format as a string.<jupyter_code>s1 = "so much depends upon {}".format("a red wheel barrow")
s2 = "glazed with {} water beside the {} chickens".format("rain", "white")<jupyter_output><empty_output><jupyter_text>You can also use the numeric position of the variables and change them in the strings, this gives some flexibility when doing the formatting, if you made a mistake in the order you can easily correct without shuffling all variables around.<jupyter_code>s1 = " {0} is better than {1} ".format("emacs", "vim")
s2 = " {1} is better than {0} ".format("emacs", "vim")<jupyter_output><empty_output><jupyter_text>The format() function offers a fair amount of additional features and capabilities, here are a few useful tips and tricks using .format()  Named Arguments You can use the new string format as a templating engine and use named arguments, instead of requiring a strict order.<jupyter_code>" I {verb} the {object} off the {place} ".format(verb="took", object="cheese", place="table")<jupyter_output><empty_output><jupyter_text>Reuse Same Variable Multiple Times The .format() method allows you to put them in any order as we saw above in the basics, but also allows for reuse.<jupyter_code>"Oh {0}, {0}! wherefore art thou {0}?".format("Romeo")<jupyter_output><empty_output><jupyter_text>Convert Values to different Bases You can use the following letters to convert a number to their bases, decimal, hex, octal, binary<jupyter_code>print("{0:d} - {0:x} - {0:o} - {0:b} ".format(21))<jupyter_output>21 - 15 - 25 - 10101<jupyter_text>Use Format as a Function You can use .format as a function which allows for some separation of text and formatting from code. For example at the beginning of your program you could include all your formats and then use later. This also could be a nice way to handle internationalization which not only requires different text but often requires different formats for numbers.<jupyter_code>## defining formats
email_f = "Your email address was {email}".format

## use elsewhere
print(email_f(email="<EMAIL>"))<jupyter_output>Your email address was <EMAIL><jupyter_text>Oh, and if you need to use braces when using str.format(), just double up<jupyter_code>" The {} set is often represented as {{0}}".format("empty")<jupyter_output><empty_output><jupyter_text>For a more detailed treatment of string formating, please visit [pyformat.info](https://pyformat.info/number_padding)  Challenges<jupyter_code>import sys, os
from base64 import b64encode, b64decode
from TestFramework.TestFramework import Test

def solution(enc):
    print(str(b64decode(enc), 'utf-8'))<jupyter_output><empty_output><jupyter_text>Enough is enough! Alice and Bob were on a holiday. Both of them took many pictures of the places they've been, and now they want to show Charlie their entire collection. However, Charlie doesn't like this sessions, since the motive usually repeats. He isn't fond of seeing the Eiffel tower 40 times. He tells them that he will only sit during the session if they show the same motive at most N times. Luckily, Alice and Bob are able to encode the motive as a number. Can you help them to remove numbers such that their list contains each number only up to N times, without changing the order?TaskGiven a list lst and a number `N`, create a new list that contains each number of lst at most `N` times without reordering. For example if `N = 2`, and the input is `[1,2,3,1,2,1,2,3]`, you take `[1,2,3,1,2]`, drop the next `[1,2]` since this would lead to `1` and `2` being in the result `3` times, and then take `3`, which leads to `[1,2,3,1,2,3]`. Example delete_nth ([1,1,1,1],2)  return [1,1]delete_nth ([20,37,20,21],1)  return [20,37,21]  Solution<jupyter_code>##Your code
def delete_nth(order,max_e):
    pass
test = Test()
test.assert_equals([20,37,21], delete_nth([20,37,20,21], 1))
test.assert_equals([1, 1, 3, 3, 7, 2, 2, 2], delete_nth([1,1,3,3,7,2,2,2,2], 3))<jupyter_output>*** ERROR: None should be [20, 37, 21]
*** ERROR: None should be [1, 1, 3, 3, 7, 2, 2, 2]<jupyter_text>Sample Solution<jupyter_code># solution('IyNTb2x1dGlvbgpkZWYgZGVsZXRlX250aChvcmRlcixtYXhfZSk6CiAgICByZXN1bHQgPSBbXQogICAgZm9yIG51bSBpbiBvcmRlcjoKICAgICAgICBpZiByZXN1bHQuY291bnQobnVtKSA+PSBtYXhfZToKICAgICAgICAgICAgcGFzcwogICAgICAgIGVsc2U6CiAgICAgICAgICAgIHJlc3VsdC5hcHBlbmQobnVtKQogICAgcmV0dXJuKHJlc3VsdCk=')<jupyter_output><empty_output><jupyter_text>Which are in? Given two list of strings a1 and a2 return a sorted array the strings of a1 which are substrings of strings of a2. Return the list in lexicographical order and without duplicates.Example: a1 = ["arp", "live", "strong"]a2 = ["lively", "alive", "harp", "sharp", "armstrong"]returns ["arp", "live", "strong"]a1 = ["tarp", "mice", "bull"]a2 = ["lively", "alive", "harp", "sharp", "armstrong"]returns []  Solution<jupyter_code>##Your code
def in_list(list_1, list_2):
    pass
test = Test()
a1 = ["live", "arp", "strong"] 
a2 = ["lively", "alive", "harp", "sharp", "armstrong"]
r1 = ['arp', 'live', 'strong']
test.assert_equals(r1, in_list(a1, a2))

a3 = ["tarp", "mice", "bull"]
a4 = ["lively", "alive", "harp", "sharp", "armstrong"]
r2 = []
test.assert_equals(r2, in_list(a3, a4))

a5 = ["tarp", "mst", "har"]
a6 = ["lively", "alive", "harp", "sharp", "armstrong"]
r3 = ['har', 'mst']
test.assert_equals(r3, in_list(a5, a6))<jupyter_output>*** ERROR: None should be ['arp', 'live', 'strong']
*** ERROR: None should be []
*** ERROR: None should be ['har', 'mst']<jupyter_text>Sample Solution<jupyter_code># solution('<KEY>')<jupyter_output><empty_output><jupyter_text>Midpoint Sum For a given list of integers, return the index of the element where the sums of the integers to the left and right of the current element are equal.Ex:<jupyter_code>ints = [4, 1, 7, 9, 3, 9]
# Since 4 + 1 + 7 = 12 and 3 + 9 = 12, the returned index would be 3

ints = [1, 0, -1]
# Returns -1
# are no indices where the left and right sums are equal<jupyter_output><empty_output><jupyter_text>Here are the 2 important rules:The element at the index to be returned is not included in either of the sum calculations!Both the first and last index cannot be considered as a "midpoint" (So None for [X] and [X, X])  Solution<jupyter_code>##Your code
def midpoint_sum(ints):
    pass
test = Test()
test.describe("Normal Cases")
test.expect(midpoint_sum([1, 0, -1]) == -1, "[1, 0, -1] should return -1")
test.expect(midpoint_sum([4,1,7,9,3,9]) == 3, "[4,1,7,9,3,9] should return 3")
test.expect(midpoint_sum([1,0,1]) == 1, "[1,0,1] should equal 1")
test.expect(midpoint_sum([9,0,1,2,3,4]) == 2, "[9,0,1,2,3,4] should equal 2")
test.expect(midpoint_sum([0,0,4,0]) == 2, "[0,0,4,0] should equal 2")
test.expect(midpoint_sum([-10,3,7,8,-6,-13,21]) == 4, "[-10,3,7,8,-6,-13,21] should equal 4")
test.expect(midpoint_sum([1,1,1,1,-5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]) ==  52, "Large valid sequence: [1,1,1,1,-5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] should equal 52")<jupyter_output>Normal Cases
*** ERROR: [1, 0, -1] should return -1
*** ERROR: [4,1,7,9,3,9] should return 3
*** ERROR: [1,0,1] should equal 1
*** ERROR: [9,0,1,2,3,4] should equal 2
*** ERROR: [0,0,4,0] should equal 2
*** ERROR: [-10,3,7,8,-6,-13,21] should equal 4
*** ERROR: Large valid sequence: [1,1,1,1,-5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] should equal 52<jupyter_text>Sample Solution<jupyter_code>#  solution('<KEY>')<jupyter_output><empty_output><jupyter_text>Homework This week's homework is to create a proof of concept backend for a predictive keyboard. Sounds fancy right? But you can already do this! The idea is that just like the Android keyboard, once you have completed a word, it will recommend three words which it thinks you'll want to type next.We are going to seed our model by reading in 100.000 emails from the [Enron Email Dataset](https://www.cs.cmu.edu/~./enron/). This represents our baseline for how we expect people to use language. We all went to talk like the smartest guys in the room, right?Your solution will consist of two functions. The first function reads in the email data to build up a probabilistic collocation model, i.e. how likely is one word to follow another word. Once you've prepared this model, the second function takes in a string, and based on that string (word, sub-word or phrase) used the language model you've created to return a tuple of the three most likely auto-complete options. Please [download](http://python-intro.s3.amazonaws.com/data/email.txt) the cleaned up dataset<jupyter_code>def auto_complete_candidates(txt,no_candidates=3):
    """Auto complete candidates based on text input

    Consults a language model to predict the most likely candidates
    for a keyboard's auto-complete functionality.

    By default returns the best three candidates.

    Args:
        txt (str): word or phrase to base autocomplete on
        no_candidates (int): number of candidates to reutrn

    Returns:
        tuple: Best candidate autocompletions
    """
    return txt<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11465871486235864, 'fraction_numerical': 0.042074257245718026, 'mean_word_length': 4.468283953072182, 'pattern_counts': {'":': 1, '<': 224, '<?xml version=': 0, '>': 220, 'https://': 2, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '55', 'dir': 'jupyter-structured-clean-dedup', 'id': '36231', 'license': 'CC-BY-3.0', 'n_tokens_mistral': 9839, 'n_tokens_neox': 9109, 'n_words': 3515, 'path': '02b - Python Basics (More on Data Structures).ipynb', 'repo_name': 'shivam6294/python-tutorials', 'size': '28825'}