<jupyter_start><jupyter_text>Lab 2: Welcome to Python + Data Structures  OverviewWelcome to your first lab! Labs in CS41 are designed to be your opportunity to experiment with Python and gain hands-on experience with the language.The primary goal of the first half is to ensure that your Python installation process went smoothly, and that there are no lingering Python installation bugs floating around.The second half focuses more on using data structures to solve some interesting problems.You're welcome to work in groups or individually. Remember to have some fun! Make friends and maybe relax a little too. If you want to cue up any songs to the CS41 playlist, let us know or add them yourself at [this link](https://open.spotify.com/playlist/1pn8cUoKsLlOfX7WEEARz4?si=jKogUQTsSDmqu6RbSBGfGA)!**Note: These labs are *designed* to be long! You shouldn't be able to finish all the problems in one class period. Work through as much as you can in the time allotted, but also feel free to skip from question to question freely. Part II is intended to be extra practice, if you want to hone your Python skills even more.**Above all, have fun playing with Python! Enjoy. Running this notebookTo run a Jupyter notebook, first change directories (`cd`) to wherever you've downloaded the notebook. Then, from a command line, activate the CS41 environment (usually `source ~/cs41-env/bin/activate`) and run:```shell(cs41-env) $ jupyter notebook```You might need to `pip install jupyterlab` from within your virtual environment if you haven't yet.   Zen of PythonRun the following code cell by selecting the cell and pressing Shift+Enter.<jupyter_code>import this<jupyter_output><empty_output><jupyter_text>Hello WorldEdit the following cell so that it prints `"Hello, world!"` when executed, and then run the cell to confirm.<jupyter_code># Edit me so that I print out "Hello, world!" when run!<jupyter_output><empty_output><jupyter_text>Warmup Problems! 🦄  Fizz, Buzz, FizzBuzz!If we list all of the natural numbers under 41 that are a multiple of 3 or 5, we get``` 3,  5,  6,  9, 10, 12, 15,18, 20, 21, 24, 25, 27, 30,33, 35, 36, 39, 40```The sum of these numbers is 408.Find the sum of all the multiples of 3 or 5 below 1001. As a sanity check, the last two digits of the sum should be `68`.<jupyter_code>def fizzbuzz(n):
    """Returns the sum of all numbers less than n divisible by 3 or 5."""
    pass

print(fizzbuzz(41))  # => 408
print(fizzbuzz(1001))<jupyter_output><empty_output><jupyter_text>Collatz SequenceDepending on from whom you took CS106A, you may have seen this problem before.The *Collatz sequence* is an iterative sequence defined on the positive integers by:```n -> n / 2    if n is evenn -> 3n + 1   if n is odd```For example, using the rule above and starting with 13 yields the sequence:```13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1```It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although unproven, it it hypothesized that all starting numbers finish at 1.What is the length of the longest chain which has a starting number under 1000?**Challenge**: Same question, but for any starting number under 1,000,000. What about for any starting number under 10,000,000? You may need to implement a cleverer-than-naive algorithm.    Hints (click to expand):            You can implement collatz_len really elegantly using recursion, but you don't need that! You can also use a while loop.        (for the challenge) You don't need to do any complicated math to get the cleverer-than-naive algorithm! Just try to improve efficiency when your code encounters a Collatz sequence that it's already encountered.    *NOTE: Once the chain starts the terms are allowed to go above one thousand.*<jupyter_code>def collatz_len(n):
    """Computes the length of the Collatz sequence starting at n."""
    pass

def max_collatz_len(n):
    """Computes the longest Collatz sequence length for starting numbers less than n"""
    pass

print(collatz_len(13))  # => 10
print(max_collatz_len(1000))

# Challenge: Only attempt to solve these if you feel very comfortable with this material.
# print(max_collatz_len(1000000))
# print(max_collatz_len(100000000))<jupyter_output><empty_output><jupyter_text>Zen PrintingWrite a program using `print()` that, when run, prints out a tic-tac-toe board.``` X | . | . ----------- . | O | . ----------- . | O | X ```You may find the optional arguments to `print()` useful, which you can read about [here](https://docs.python.org/3/library/functions.htmlprint). In no more than five minutes, try to use these optional arguments to print out this particular tic-tac-toe board.<jupyter_code># Print a tic-tac-toe board using optional arguments.
def print_tictactoe():
    """Print out a specific partially-filled tic-tac-toe board."""
    pass<jupyter_output><empty_output><jupyter_text>Maybe you were able to print out the tic-tac-toe board. Maybe not. In the five minutes you've been working on that, I've gotten bored with normal tic-tac-toe (too many ties!) so now, I want to play SUPER tic-tac-toe.Write a program that prints out a SUPER tic-tac-toe board.```  |  |  H  |  |  H  |  |  --+--+--H--+--+--H--+--+--  |  |  H  |  |  H  |  |  --+--+--H--+--+--H--+--+--  |  |  H  |  |  H  |  |  ========+========+========  |  |  H  |  |  H  |  |  --+--+--H--+--+--H--+--+--  |  |  H  |  |  H  |  |  --+--+--H--+--+--H--+--+--  |  |  H  |  |  H  |  |  ========+========+========  |  |  H  |  |  H  |  |  --+--+--H--+--+--H--+--+--  |  |  H  |  |  H  |  |  --+--+--H--+--+--H--+--+--  |  |  H  |  |  H  |  |  ```You'll find that there might be many ways to solve this problem. Which do you think is the most 'pythonic?' Talk to someone next to you about your approach to this problem. Remember the Zen of Python!**Hint:** To find the most Pythonic way to do this, think about what you'd do if I said you have 10 seconds to write code that prints out the list.<jupyter_code>def print_super_tictactoe():
    """Print an empty SUPER tic-tac-toe board."""
    pass<jupyter_output><empty_output><jupyter_text>Data Structures, whooo!If you've gotten this far, you're already above and beyond! Our recommendation at this point is to pick out the most interesting of the following problems and solve those![Optional Reading on Standard Types - check out Sequence types and Mapping types](https://docs.python.org/3/library/stdtypes.html)  Tuples and Dicts: CachingIn this problem, we'll use tuples and dicts to memoize a recursive function.*Note*: In general, we try to keep this class as self-contained as possible and don't ask that you know too much computer science outside of CS41. For this problem, though, you will use recursion. If you aren't super comfortable with recursion or recursive memoization, feel free to skip ahead!This problem is called **lattice paths**. Starting in the top left corner of a $2 \times 2$ grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.![2x2 paths](https://projecteuler.net/project/images/p015.png)Write a recursive (non-memoized) function to calculate the number of paths from the top left of an $m \times n$ grid ($m$ rows and $n$ columns) to the bottom right corner.Notice that the problem seems very similar to itself... At every point in the grid, you only have two moves: down and left.    Hints (click to expand):            The recursive base case is a grid where either the number of rows is zero or the number of columns is zero. How many paths are there in this case? Notice that programming it this way also prevents $m$ or $n$ from being negative.        Suppose you move down. Then, the remaining problem is still to count the number of paths from the top left of a grid to the bottom right, but now the grid is a different size.        If you move down, the problem becomes counting the number of paths from the top left of a grid of size $(m-1) \times n$ to the bottom right of that grid.<jupyter_code>def lattice_paths(m, n):
    pass

print(lattice_paths(2, 2)) # => 6
print(lattice_paths(6, 6)) # => 924
#print(lattice_paths(20, 20)) # => this takes too long without memoization!
#print(lattice_paths(40, 40)) # => this takes WAY too long without memoization!<jupyter_output><empty_output><jupyter_text>Notice that the way that our code is constructed results in a lot of repeated calls to the same functions. For example, if you start at the top of a $20 \times 20$ grid and go down, then right, you'll make a function call for a $19 \times 19$ grid. But you'll also make that call if you go right and *then* down. This is where memoization comes in. We'll store the output of `lattice_paths` in a dictionary the first time that we call it and then the second time, we'll just immediately return the value from the dictionary so that we won't make calls twice.Let's memoize `lattice_paths` by adding its output to a dictionary. This dictionary should have keys that are tuples $(m,n)$ and values that are the output `lattice_paths(m,n)`. Make sure to check if the tuple `(m,n)` is in the memoization dictionary at the beginning of the function execution.<jupyter_code>memoization_dict = {}

def lattice_paths_memoized(m, n, memoization_dict):
    pass

print(lattice_paths_memoized(2, 2, memoization_dict))   # => 6
print(lattice_paths_memoized(6, 6, memoization_dict))   # => 924
print(lattice_paths_memoized(20, 20, memoization_dict)) # => sanity check: ends with 8820
print(lattice_paths_memoized(40, 40, memoization_dict)) # => sanity check: ends with 1620

memoization_dict.clear()<jupyter_output><empty_output><jupyter_text>ListsPredict what the following lines of Python will do. Then, run the code block below to see if they match what you expect:```Pythons = [0] * 3print(s)s[0] += 1print(s)s = [''] * 3print(s)s[0] += 'a'print(s)s = [[]] * 3print(s)s[0] += [1]print(s)```<jupyter_code># Explore the elements of lists. Is the output what you expect?
s = [0] * 3
print(s)
s[0] += 1
print(s)
s = [''] * 3
print(s)
s[0] += 'a'
print(s)
s = [[]] * 3
print(s)
s[0] += [1]
print(s)<jupyter_output><empty_output><jupyter_text>Let's investigate... why is this happening? Strategies for investigation (that you can use to understand this situation better):1. We'll use the `id` function to investigate further. 2. Think about when Python creates a copy of objects and when it doesn't... does this help explain the behavior in the examples?3. What happens when we replace the second-to-last line with `s[0] = s[0] + [1]`? What if we replace the line with `s[0].append(1)`?<jupyter_code>s_int = [0] * 3
s_str = [''] * 3
s_lst = [[]] * 3

print(s_int[0] is s_int[1] is s_int[2])
print(s_str[0] is s_str[1] is s_str[2])
print(s_lst[0] is s_lst[1] is s_lst[2])<jupyter_output><empty_output><jupyter_text>Okay, this is how the lists are initialized... so when does this change?<jupyter_code>s_int[0] += 1
print(id(s_int[0]))
print(id(s_int[1]))
print(id(s_int[2]))
s_str[0] += 'a'
print(id(s_str[0]))
print(id(s_str[1]))
print(id(s_str[2]))
s_lst[0] += [[1]]
print(id(s_lst[0]))
print(id(s_lst[1]))
print(id(s_lst[2]))<jupyter_output><empty_output><jupyter_text>**WOW**! What does that tell you about the way that Python treats ints vs. strings vs. lists? Tell your neighbor, in an excited tone of voice (or a Barack Obama impression)!Based on that, predict what this function is going to do...<jupyter_code>lst = ['I', 'know', "you'll", 'think', "I'm", 'like', 'the', 'others']
s = "Who saw your name and number on the "
i = 8675308

def sing(lst, s, i):
    lst += ['before']
    s += 'wall'
    i += 1

sing(lst, s, i)
print(' '.join(lst))
print(s)
print(i)<jupyter_output><empty_output><jupyter_text>Jenny, Jenny, who can I turn to... (Jenny may be ignoring you, but Python's always got your back 😉)  TuplesWrite a function to compute the [GCD](https://en.wikipedia.org/wiki/Greatest_common_divisor) of two positive integers. You can freely use the fact that `gcd(a, b)` is mathematically equal to `gcd(b, a % b)`, and that `gcd(a, 0) == a`.You can assume that `a >= b` if you'd like.It is possible to accomplish this in three lines of Python code (or with extra cleverness, even fewer!). Consider exploiting tuple packing and unpacking!*Note: The standard library has a `gcd` function. Avoid simply importing that function and using it here - the goal is to practice with tuple packing and unpacking!*<jupyter_code>def gcd(a, b):
    """Compute the GCD of two positive integers."""
    pass  # Your implementation here
    
gcd(10, 25) # => 5
gcd(14, 15) # => 1
gcd(3, 9) # => 3
gcd(1, 1) # => 1<jupyter_output><empty_output><jupyter_text>Flipping DictionariesI asked our course staff what their favorite animal is and they gave me these answers:```pythonfav_animals = {    'parth': 'unicorn',    'michael': 'elephant',    'sam': 'ox',    'zheng': 'tree',    'theo': 'puppy',    'alex': 'dog',    'nick': 'daisy'}```I know that, realistically, they're lying to themselves. In fact, the dict probably looks more like this:```pythonfav_animals = {    'parth': 'unicorn',    'michael': 'unicorn',    'sam': 'unicorn',    'zheng': 'tree',    'theo': 'unicorn',    'alex': 'dog',    'nick': 'daisy'}```In this problem, we'll reverse the `fav_animals` dictionary to create a new dictionary which associates animals to a list of people for whom that animal is their favorite. More precisely, write a function that properly reverses the keys and values of a dictionary - each key (originally a value) should map to a collection of values (originally keys) that mapped to it. For example,```pythonflip_dict({"CA": "US", "NY": "US", "ON": "CA"}) => {"US": ["CA", "NY"], "CA": ["ON"]}```Note: there is a data structure in the `collections` module from the standard library called `defaultdict` which provides exactly this sort of functionality. You provide it a factory method for creating default values in the dictionary (in this case, a list.) You can read more about `defaultdict` and other `collections` data structures [here](https://docs.python.org/3/library/collections.html).<jupyter_code>fav_animals = {
    'parth': 'unicorn',
    'michael': 'unicorn',
    'sam': 'unicorn',
    'zheng': 'tree',
    'theo': 'unicorn',
    'alex': 'dog',
    'nick': 'daisy'
}

def flip_dict(d):
    pass

print(flip_dict(fav_animals))
# {'unicorn': ['parth', 'michael', 'sam', 'theo'], 'tree': ['zheng'], 'dog': ['alex'], 'daisy': ['nick']}<jupyter_output><empty_output><jupyter_text>Bonus ProblemsDon't worry about doing these bonus problems. In most cases, bonus questions ask you to think more critically or use more advanced algorithms.In this case, we'll use list comprehensions to solve some interesting problems.  Pascal's TriangleWrite a function that generates the next level of [Pascal's triangle](https://en.wikipedia.org/wiki/Pascal%27s_triangle) given a list that represents a row of Pascal’s triangle.```generate_pascal_row([1, 2, 1]) -> [1, 3, 3, 1]generate_pascal_row([1, 4, 6, 4, 1]) -> [1, 5, 10, 10, 5, 1]generate_pascal_row([]) -> [1]```As a reminder, each element in a row of Pascal's triangle is formed by summing the two elements in the previous row directly above (to the left and right) that elements. If there is only one element directly above, we only add that one. For example, the first 5 rows of Pascal's triangle look like:```    1   1 1  1 2 1 1 3 3 11 4 6 4 1```You could solve this problem with `enumerate` or look up the `zip` function for an even more Pythonic solution (use iPython, perhaps?)! Avoid using a loop of the form `for i in len(range(row)):`.*Hint: Check out the diagram below. How could you use this insight to help complete this problem?*```  0 1 3 3 1+ 1 3 3 1 0-----------  1 4 6 4 1```<jupyter_code>def generate_pascal_row(row):
    """Generate the next row of Pascal's triangle."""
    pass

generate_pascal_row([1, 2, 1])  # => [1, 3, 3, 1]
generate_pascal_row([1, 4, 6, 4, 1])  # => [1, 5, 10, 10, 5, 1]
generate_pascal_row([])  # => [1]<jupyter_output><empty_output><jupyter_text>Cyclone Phrases (challenge)For the following problem, we describe a criterion that makes a word (or phrase!) special, similarly to our "Efficient Words" from lecture.Before that, though, we need to load up a list of all of the words in the English language to see which words fit the criterion.If you are using macOS or Linux, you should have a dictionary file available at `/usr/share/dict/words`, a 2.5M text file containing over 200 thousand English words, one per line. However, we've also mirrored this file at `https://stanfordpython.com/res/misc/words`, so you can download the dictionary from there if your computer doesn't have this dictionary file readily available.What would be an appropriate data structure in which to store the English words?Write the method `load_english` to load English words from this file. How many English words are there in this file?<jupyter_code># If you downloaded words from the course website,
# change me to the path to the downloaded file.
DICTIONARY_FILE = '/usr/share/dict/words'

def load_english():
    """Load and return a collection of english words from a file."""
    pass

english = load_english()
print(len(english))<jupyter_output><empty_output><jupyter_text>Cyclone words are English words that have a sequence of characters in alphabetical order when following a cyclic pattern. For example:![Cyclone Phrases](http://i.stack.imgur.com/4XBV3.png)Write a function that to determine whether an entire phrase passed into a function is made of cyclone words. You can assume that all words are made of only alphabetic characters, and are separated by whitespace.```is_cyclone_phrase("adjourned")  => Trueis_cyclone_phrase("settled")  => Falseis_cyclone_phrase("all alone at noon")  => Trueis_cyclone_phrase("by myself at twelve pm")  => Falseis_cyclone_phrase("acb")  => Trueis_cyclone_phrase("")  => True```Generate a list of all cyclone words. How many are there? As a sanity check, we found 769 distinct cyclone words.<jupyter_code>def is_cyclone_word(word):
    """Return whether a word is a cyclone word."""
    
def is_cyclone_phrase(word):
    """Return whether a phrase is composed only of cyclone words."""<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11517979687071095, 'fraction_numerical': 0.020587427944002194, 'mean_word_length': 4.359223300970874, 'pattern_counts': {'":': 5, '<': 69, '<?xml version=': 0, '>': 108, 'https://': 8, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '17', 'dir': 'jupyter-structured-clean-dedup', 'id': '28016', 'license': 'BSD-2-Clause-FreeBSD', 'n_tokens_mistral': 5960, 'n_tokens_neox': 5519, 'n_words': 2444, 'path': 'archive/notebooks-win20/lab-2/data-structures-part-1.ipynb', 'repo_name': 'stanfordpython/python-labs', 'size': '18215'}