\documentclass[11pt]{cselabheader} \usepackage{wrapfig} \newcommand{\thelabnumber}{7} \newcommand{\thetitle}{Dictionaries and Sets, Types} \newcommand{\theauthor}{CSE/IT 107L} % Write title and author \title{\thetitle} \author{\theauthor} \date{NMT Department of Computer Science and Engineering} \fancyhead[R]{Lab \thelabnumber: \thetitle} \fancyhead[L]{\theauthor} \makeindex[title=Index of New Functions and Methods, intoc] \makehyperref \begin{document} \pagenumbering{roman} \maketitle \hrule % Quotes and comics \begin{multicols}{2} ``Vague and nebulous is the beginning of all things, but not their end.'' \begin{flushright} --- K. Gibran \end{flushright} ``The danger that computers will become like humans is not as big as the danger that humans will become like computers.'' (``Die Gefahr, dass der Computer so wird wie der Mensch ist nicht so gro\ss, wie die Gefahr, dass der Mensch so wird wie der Computer.'') \begin{flushright} --- Konrad Zuse \end{flushright} ``I don’t need to waste my time with a computer just because I am a computer scientist.'' \begin{flushright} --- Edsger W. Dijkstra \end{flushright} \section*{Introduction} This lab concludes the introduction to Python's data structures. Dictionaries are one of Python's fundamental data structures. They behave like lists, but you can use strings, tuples, floats or any set of integers as indices to Python values. Dictionaries are useful for storing elements that are best identified by a description or name rather than by a strict order. Sets are collections of unique (non-repeated) values. They support fast combination operations, like finding the elements that appear in two sets. We will define the \emph{types} of Python values and describe how to convert between different types. \begin{figure}[H] \centering \includegraphics[width=0.9\linewidth]{img/xkcd_1537.png} \caption{\url{http://xkcd.com/1537}} \end{figure} \end{multicols} \newpage \tableofcontents \newpage \pagenumbering{arabic} \section{Represent Relationships Between Values Using Dictionares} You will often need to define relationships between pairs of Python values. For example, a dataset of names of movies and their ratings could be represented using strings (movie names) that are related to floats (movie ratings). As another example, you could have time measurements (floats) related to another measurement (a float or integer). One of this lab's exercises involves counting the number of letters in the user's input. In this case, you could relate one-letter strings to integers. \subsection{Creating Dictionaries} How do you represent relationships between the two groups of values? Python offers dictionaries\index{dictionaries} to help you perform this task. They are a fundamental data structure and are also known as associative arrays, hash maps, or key-value pairs. Some examples: \begin{listing} \begin{python3code} movie_ratings = {"Sharknado 4": 2.0, "Spirited Away": 4.0, "The Big Lebowski": 4.0} temperatures = {0.0: 75.2, 0.5: 79.2, 1.0: 80.3, 1.5: 81.0, 2.0: 88.5, 2.5: 98.6} letter_count = {"e": 99, "t": 92, "a": 90, "q": 2} moons = {"venus": [], "earth": ["moon"], "mars": ["phobos", "deimos"]} \end{python3code} \caption{Example dictionaries.}\label{lst:dicts} \end{listing} \begin{multicols}{2} A dictionary is written by surrounding a list of comma-separated key-value pairs\index{key-value pairs} with curly braces. Key-value pairs are a Python value that represents the key, then a colon, and a Python value that represents the value. \begin{python3code} dictionary = {key1: value, key2: value} \end{python3code} The values in a dictionary can be any Python value: strings, integers, booleans, lists of any Python value, other dictionaries, etc.. The keys in a dictionary must not be repeated and must be immutable\index{immutable keys} Python values: these include strings, ints, floats, tuples of any of these, and some other values. Figure \ref{fig:dicts} visualizes the dictionaries given in the previous code sample. Notice that the order of key-value pairs is not preserved. Different keys can be related to the same value. For example, there are two keys in the \pythoninline{movie_ratings} dictionary that have the value 4.0. Values can be lists, but keys cannot be values. \newcolumn \begin{figure}[H] \begin{center} \includegraphics[width=\linewidth]{img/pythontutor_dicts.png} \caption{A visualization of the dictionaries in listing \ref{lst:dicts} created using \url{pythontutor.com}}\label{fig:dicts} \end{center} \end{figure} \end{multicols} Python raises a \pythonindex{TypeError} if there's a dictionary with mutable key. Keys can't be repeated: in this case, Python ignored all the key-value pairs with key set 1, except for the last one. The following session from a Python interactive shell demonstrates the definition of both valid and invalid dictionaries: \begin{pyconcode} >>> {1: 'a', 2: 'm', 3: 'z'} {1: 'a', 2: 'm', 3: 'z'} >>> {'a': 1, 'm': 2, 'z': 3} # order is not preserved {'a': 1, 'z': 3, 'm': 2} >>> {1: [1, 2, 3], 4: [9, 10]} {1: [1, 2, 3], 4: [9, 10]} >>> {[1, 2, 3]: 1, [9, 10]: 4} # lists can't be keys Traceback (most recent call last): File "", line 1, in TypeError: unhashable type: 'list' >>> {1: 1, 1: 2, 1: 3} # only the last is kept {1: 3} \end{pyconcode} \subsection{Indexing by Key to Access, Modify, and Add Dictionary Values} Similar to a list, you may access values in the dictionary by indexing\index{index} on the dictionary's keys to access elements. For example: \begin{pyconcode} >>> letter_count = {"e": 99, "t": 92, "a": 90, "q": 2} >>> "the letter {} occurs {} times".format("e", letter_count["e"]) 'the letter e occurs 99 times' >>> moons = {"venus": [], "earth": ["moon"], "mars": ["phobos", "deimos"]} >>> moons["venus"] [] >>> moons["mars"] ['phobos', 'deimos'] >>> moons["jupiter"] Traceback (most recent call last): File "stdin", line 1, in moons["jupiter"] KeyError: 'jupiter' \end{pyconcode} Notice, Python raises an \pythonindex{IndexError} whenever you try to access a key that doesn't appear in the dictionary. Just like lists, the values to a dictionary key can be reassigned by using indexing with assignment\index{assignment}. In the following example, the value of the key \pythoninline{'breakfast'} is changed to \pythoninline{'toast'}. You can also add key-value pairs by assigning to a key that isn't in the dictionary. In the example, the key \pythoninline{'brunch'} is added and it has value \pythoninline{'biscuits'}. \begin{pyconcode} >>> food = {'breakfast': 'burrito', 'lunch': 'burger', 'dinner': 'tacos'} >>> print(food) {'lunch': 'burger', 'breakfast': 'burrito', 'dinner': 'tacos'} >>> food['breakfast'] = 'toast' # add a new key! >>> print(food) {'dinner': 'tacos', 'lunch': 'burger', 'breakfast': 'toast'} >>> food['brunch'] = 'biscuits' >>> food {'dinner': 'tacos', 'brunch': 'biscuits', 'lunch': 'burger', 'breakfast': 'toast'} \end{pyconcode} \subsection{Safely Removing Key-Value Pairs Using \pythoninline{dict.pop(key, defaultvalue)}} To remove a key-value pair, use the \pythonindex{dict.pop(key, defaultvalue)} function. This function removes the given key from the dictionary if it exists, if it does not, then it returns the given default value. For example: \begin{pyconcode} >>> letter_count = {"e": 99, "t": 92, "a": 90, "q": 2} >>> letter_count["e"] 99 >>> removed_value = letter_count.pop("e", 0) >>> removed_value 99 >>> letter_count {'t': 92, 'a': 90, 'q': 2} >>> removed_value2 = letter_count.pop("z", 0) # key 'z' not in dictionary >>> removed_value2 0 \end{pyconcode} \subsection{Checking Dictionary Properties Using \pythoninline{len, in, ==}} The \pythonindex{in} keyword tests whether an item is a key in a dictionary. To find the number of key-value pairs in a dictionary, use the \pythonindex{len} function. Dictionary equality can be tested using the boolean operator \pythonindex{==}. \begin{pyconcode} >>> states = {'NM' : 'New Mexico', 'TX' : 'Texas', 'KS' : 'Kansas'} >>> states2 = {'NM' : 'New Mexico', 'TX' : 'Texas', 'KS' : 'Kansas'} >>> states3 = {'NY' : 'New York', 'TX' : 'Texas', 'KS' : 'Kansas'} >>> 'NM' in states True >>> 'NY' in states False >>> len(states) 3 >>> states == states2 True >>> states == states3 False \end{pyconcode} \subsection{Safe Access Using \pythoninline{dict.get(key, defaultvalue)}} The \pythonindex{dict.get(key, defaultvalue)} function is used to access a dictionary without the risk of Python raising a \pythonindex{KeyError} if the element does not exist. If the given key is not present in the dictionary, the function will return the given default value instead of causing an error. A sample: \begin{pyconcode} >>> moons = {"venus": [], "earth": ["moon"], "mars": ["phobos", "deimos"]} >>> moons.get("earth", []) ['moon'] >>> moons["jupiter"] Traceback (most recent call last): File "stdin", line 1, in moons["jupiter"] KeyError: 'jupiter' >>> moons.get("jupiter", []) [] \end{pyconcode} \subsection{Traversing Dictionaries using \pythoninline{dict.items(), dict.keys(), dict.values()}} You can use a for-loop to iterate over the keys, values, or key-value pairs of a dictionary. The \pythonindex{dict.items()} function returns something similar to a list of tuples where the first element of each tuple is the key of a dictionary item and the second element is the corresponding value. The \pythonindex{dict.values()} and \pythonindex{dict.keys()} functions return a list of the dictionary's values or a list of its keys. Any of these three functions can be used to iterate through a dictionary. For example, \begin{pyconcode} >>> states = {'NM' : 'New Mexico', 'TX' : 'Texas', 'KS' : 'Kansas'} >>> states.keys() dict_keys(['TX', 'KS', 'NM']) >>> states.values() dict_values(['Texas', 'Kansas', 'New Mexico'] >>> states.items() dict_items([('KS', 'Kansas'), ('TX', 'Texas'), ('NM', 'New Mexico')]) >>> for state_short, state_name in states.items(): ... print(state_short, state_name) KS Kansas TX Texas NM New Mexico >>> for state_short in states.keys(): ... print(state_short, states[state_short]) KS Kansas TX Texas NM New Mexico >>> for state_name in states.values(): ... print(state_name) Texas Kansas New Mexico \end{pyconcode} If you need the iteration to happen in order, you can sort dictionary keys\index{sort dictionary keys} and then iterate through the dictionary using \pythonindex{for key in sorted(d.keys())}. Otherwise, iteration order is not enforced. \subsection{Sample Program} \begin{python3code} states = {'NM' : 'New Mexico', 'TX' : 'Texas', 'KS' : 'Kansas'} capitals = { # multiline dictionaries are easier to read 'NM' : 'Santa Fe', 'TX' : 'Austin', 'KS' : 'Kansas City', } state = input('Enter a state >>> ') if state in states: print('You selected {}. The state capital is {}.'.format(states[state], capitals[state])) else: print('The state you selected is not known to this program.') \end{python3code} Notice the dictionary \pythoninline{capitals} was written on multiple lines for readability. \section{Sets: Collections With Unique Elements} \subsection{Creating Sets} Sets are a lot like lists, but \emph{no element can appear twice} and a set's elements are \emph{unordered}. Additionally, a set cannot contain mutable Python values (like lists). Sets are mutable. A set is made using curly braces by converting a list: \begin{pyconcode} >>> a = {5, 5, 4, 3, 2} # duplicates ignored >>> print(a) {2, 3, 4, 5} >>> b = set([5, 5, 4, 3]) >>> print(b) {3, 4, 5} \end{pyconcode} Because sets are unordered, they cannot be indexed. That means you cannot index a set using the \pythoninline![]! operator. \begin{pyconcode} >>> a = {5, 4, 3, 2} >>> a[1] Traceback (most recent call last): File "", line 1, in TypeError: 'set' object does not support indexing \end{pyconcode} \subsection{Combining Sets} The \pythoninline!|! operator can be used to join two sets together. This creates a new set that contains the elements in each of the two sets. This is called the \emph{union}\index{union} of the two sets. Since the result is also a set, duplicate values will only appear once. \begin{pyconcode} >>> a = {1, 2, 4, 8, 16} >>> b = {1, 3, 9, 27} >>> a | b {1, 2, 3, 4, 8, 9, 16, 27} \end{pyconcode} The \pythoninline!&! operator can be used to find the \emph{intersection}\index{intersection} of two sets. This is the set containing all elements that are in both sets. \begin{pyconcode} >>> a = {2, 4, 6, 8, 10, 12} >>> b = {3, 6, 9, 12, 15, 18} >>> a & b {12, 6} \end{pyconcode} The \pythoninline!-! operator can be used to find the \emph{difference}\index{difference} of two sets. This set contains all of the elements of the first set excluding the elements in the second set. \begin{pyconcode} >>> a = {2, 4, 6, 8, 10, 12} >>> b = {3, 6, 9, 12, 15, 18} >>> a - b {8, 2, 10, 4} \end{pyconcode} The \pythoninline!^! operator can be used to find the \emph{symmetric difference}\index{symmetric difference} of two sets. This is the set containing all elements in either of the original sets, but not in both. \begin{pyconcode} >>> a = {'one', 'eight'} >>> b = {'two', 'four', 'six', 'eight'} >>> a ^ b {'one', 'six', 'two', 'four'} \end{pyconcode} \begin{tabular}{lll} Operator & Meaning & Definition \\ \midrule \pythoninline!a | b! & in either & union of \pythoninline!a! and \pythoninline!b! \\ \pythoninline!a & b! & in both & intersection of \pythoninline!a! and \pythoninline!b! \\ \pythoninline!a - b! & all not in \pythoninline{b} & difference of \pythoninline!a! and \pythoninline!b! \\ \pythoninline!a ^ b! & all elements not in common & symmetric difference of \pythoninline!a! and \pythoninline!b! \\ \end{tabular} \subsection{Conversions Using \pythoninline{set(), list()}} A list can be converted into a set using the \pythoninline!set()! function: \begin{pyconcode} >>> a = [1, 5, 2, 2.3, 5, 2] >>> set(a) # duplicate removed! {1, 2, 2.3, 5} \end{pyconcode} Similarly, a set can be converted into a list using the \pythoninline!list()! function: \begin{pyconcode} >>> a = {1, 2, 2, 5, 3, 2} >>> a {1, 2, 5, 3} >>> list(a) [1, 2, 3, 5] \end{pyconcode} \subsection{Adding Elements Using \pythoninline{set.add()}} To add an element to a set, use the \pythonindex{set.add(element)} function. A sample: \begin{pyconcode} >>> a = {1, 2, 5, 3} >>> a.add(5) >>> a {1, 2, 3, 5} >>> a.add(7) >>> a {1, 2, 3, 5, 7} \end{pyconcode} \subsection{Removing Elements Using \pythoninline{set.remove()} or \pythoninline{set.pop()}} To remove an element that is present in the set, use the \pythonindex{set.remove(element)} function. To remove an arbitrary element from the set, use the \pythonindex{set.pop()} function. Python raises a \pythonindex{KeyError} if the set is empty or the element is not in the set. A sample: \begin{pyconcode} >>> a = {1, 2, 5, 3} >>> an_element = a.pop() >>> an_element, a (1, {2, 3, 5}) >>> a.remove(5) >>> a {2, 3} >>> a.remove(10) Traceback (most recent call last): File "", line 1, in a.remove(10) KeyError: 10 \end{pyconcode} \subsection{Traversing Sets With For Loops} You may also iterate over a set using a for-loop. Order of iteration is unspecified. \begin{pyconcode} >>> companions_nine = {'rose', 'jack'} >>> companions_ten = {'rose', 'mickey', 'jack', 'donna', 'martha', 'wilf'} >>> for companion in companions_nine: ... print(companion) jack rose \end{pyconcode} \subsection{Creating an Empty Set and an Empty Dictionary} Note that empty curly braces create an empty dictionary\index{empty dictionary}. To create an empty set\index{empty set}, use the \pythoninline!set()! function: \begin{pyconcode} >>> type({}) >>> type(set()) \end{pyconcode} \section{Ordered Access With Stacks} Imagine a stack of plates. You can only add plates to the top and remove plates from the top. This a ``Last-In-First-Out'' data structure: If you add three plates to the stack, the last one you added will be the first one you remove. \emph{Stacks}\index{stack} are a specialized data structure. They are at the heart of every operating system and used in many pieces of software. A stack is similar to a Python list where you can only add elements to the end or remove elements from the end. This is accomplished using the \pythonindex{list.pop()} and \pythonindex{list.append(element)} methods on lists. When given no arguments, the pop method will remove the last element of the list and return it. The append method will add an element to the end of the list. The array index \pythonindex{list[-1]} is used to inspect the top of the stack; or the last element of the list. For example: \begin{pyconcode} >>> stack = [1, 2, 3] >>> a = stack.pop() >>> print(a) 3 >>> print(stack) [1, 2] >>> stack.append(4) >>> print(stack) [1, 2, 4] >>> stack[-1] # top! 4 \end{pyconcode} Interacting with the elements of the list in any other way violates the idea of the list being a stack. By adhering to this restriction, we can effectively invent a new data structure based on existing Python data structures. There are more effective ways of creating data structures for organizing data according to specific needs. For example, you could compose two data structures. If you needed a dictionary with ordered key-value pairs, you could use a list of tuples where the first element in the tuple is the key and the second is the value. \section{List Comprehensions: Concise Iteration} \subsection{Modifying Collections} List comprehensions can be used to create new lists by doing something to each element of a currently existing list or range. For example, if we want to make every string in a list of strings lowercase we could use a for-loop to call \pythoninline{.lower()} on each string. \begin{pyconcode} >>> strings = ['Python', 'N.M.'] >>> result = [] >>> for string in strings: ... result.append(string.lower()) >>> result ['python', 'n.m.'] \end{pyconcode} List comprehensions are a more concise way of doing this. \begin{pyconcode} >>> strings = ['Python', 'N.M.'] >>> result = [string.lower() for string in strings] >>> print(result) ['python', 'n.m.'] \end{pyconcode} We can process more complicated elements with list comprehensions. If we have a list of dictionaries containing lists, we can find the maximum element in each sublist by using this list comprehension: \begin{pyconcode} >>> data = [{'d': [1,2,3]}, {'d': [4,5]}, ... {'d': [0,0,1]}] ... >>> [max(dictionary['d']) for dictionary in data] [3, 5, 1] \end{pyconcode} \subsection{Filtering Elements} What if we want to exclude elements? In this code, we take a list of words and keep all words of length less than 2. \begin{pyconcode} >>> strings = ['a', 'ab', 'abb', 'aab', 'aaa'] >>> result = [] >>> for string in strings: ... if len(string) <= 2: ... result.append(string) ... >>> result ['a', 'ab'] \end{pyconcode} This can be written more concisely by using an \pythoninline{if} statement within a list comprehension. \begin{pyconcode} >>> strings = ['a', 'ab', 'abb', 'aab', 'aaa'] >>> [x for x in strings if len(x) <= 2] ['a', 'ab'] \end{pyconcode} \subsection{Nested Comprehensions} We can also write multiple \pythoninline{for} statements and \pythoninline{if} statements in a list comprehension. This example creates a list of floating point numbers by dividing two integers. \begin{pyconcode} >>> result = [y / x for x in range(3) if x != 0 for y in range(3)] >>> print(result) [0.0, 1.0, 2.0, 0.0, 0.5, 1.0] \end{pyconcode} These statements should be read from right to left. So the previous list comprehension is the same as these nested statements: \begin{python3code} result = [] for x in range(10): if x != 0: for y in range(10): result.append(y / x) \end{python3code} \section{Types} % TODO revise. more purpose In Python, every value has a type. We have already seen a few types in action: integers, floating-point numbers, strings, and boolean values, lists, tuples, sets, and dictionaries. The type of a value or variable restricts what it can represent. Here is a list of some types and example values. \begin{center} \begin{tabular}{llll} Name & Description & Examples & Convert \pythoninline{y} \\ \midrule Int & Integer, whole number & \pythoninline{1, 123, -12} & \pythoninline{int(y)} \\ Float & Floating-point number & \pythoninline{1.0, 3.1415, -0.01} & \pythoninline{float(y)} \\ String & Sequence of characters & \pythoninline{"", "1", "abc 123\n"} & \pythoninline{str(y)} \\ Boolean & True or false & \pythoninline{True, False} & \pythoninline{bool(y)} \end{tabular} \end{center} Most programming languages have types for a good reason: for one, operations (such as \pythoninline{+}, \pythoninline{-}, \ldots) have different effects on different types. For example, an integer \pythoninline{*} an integer results in an integer (the multiplication of the two \emph{operands}), but an integer \pythoninline{*} a string results in the string repeated. However, a string \pythoninline{*} a string results in an error: \begin{pyconcode} >>> 5*3 15 >>> 5*'hi' 'hihihihihi' >>> 'hi'*'hi' Traceback (most recent call last): File "", line 1, in TypeError: can't multiply sequence by non-int of type 'str' \end{pyconcode} Also, Python can speed up your programs by picking efficient ways of dealing with different types. Multiplying integers and multiplying floating point numbers require very different techniques. Python may optimize code if the type of the number is known. \subsection{Types of Collections} In the previous labs, we have described and demonstrated several data structures. Each of them has its own type. \begin{tabular}{llll} Name & Description & Examples & Convert \pythoninline{y} \\ \midrule List & Sequence of values & \pythoninline{[], [0, 1], [True, True]} & \pythoninline{list(y)} \\ Tuple & Immutable sequence of values & \pythoninline{(0, 1), ('a', 'b')} & \pythoninline{(y)} \\ Dictionary & Relationship between values & \pythoninline{{}, {1:2}, {'a':True}} & \pythoninline{dict(y)} \\ Set & Collection of unique values & \pythoninline{{0,1}, {True}} & \pythoninline{set(y)} \\ \end{tabular} \subsection{\texorpdfstring% {Checking Types with the \pythoninline{type()} Function} {Checking Types with the type() Function}} The \pythonindex{type()} function returns the type of a value. \begin{pyconcode} >>> type(5) >>> x = 10 >>> type(x) >>> type('Allons-y!') >>> type(True) \end{pyconcode} \subsection{Converting Values to Different Types} There are several functions that can convert\index{converting between types} the types of Python values. Only values have types, variables can store values of any type. \begin{pyconcode} >>> float("5.5") # convert string with 5.5 to a float 5.5 >>> int("5") # integer containing 5 5 >>> str(5) # string containing 5 '5' >>> # Note that an impossible conversion will throw an error >>> int("55a") Traceback (most recent call last): File "", line 1, in ValueError: invalid literal for int() with base 10: '55a' \end{pyconcode} There are several functions that work on different types of collections. The \pythoninline!len()! function can be used on any collection object in order to find the number of elements. All collections can be iterated over with \pythoninline!for! loops, All collections can use the \pythoninline!in! keyword to test if an element is in that collection. For dictionaries, this will compare against the list of keys, not the values. % this could be something better than a table \begin{table}[!ht] \centering \begin{tabular}{p{1.6cm}lp{1.6cm}p{3.5cm}lp{4.5cm}} \toprule Data Structure & Mutable & Mutable elements & Indexing & Ordered & Other properties\\ \midrule List \pythoninline![]! & yes & yes & by whole numbers & yes & can contain elements more than once\\ Sets \pythoninline!{}! & yes & no & not indexable & no & no element can appear more than once\\ Tuples \pythoninline!()! & no & yes & by whole numbers & yes & can contain elements more than once\\ Dictionary \pythoninline!{}! & yes & yes & by anything ``hashable'' (immutable collections or basic types) & no & \\ \bottomrule \end{tabular} \caption{Summary of Data Structures in Python} \label{tab:sum} \end{table} Tuples, sets, and lists can all be freely converted from one to another using the \pythoninline!tuple()!, \pythoninline!set()!, \pythoninline!list()!, \pythoninline!str()!, and \pythoninline!dict()! functions. \begin{pyconcode} >>> food = ('nothing', 'cereal', 'lemonheads') >>> list(food) ['nothing', 'cereal', 'lemonheads'] >>> str(food) # not particularly useful "('nothing', 'cereal', 'lemonheads')" >>> s = "The cat in the" >>> list(s) ['T', 'h', 'e', ' ', 'c', 'a', 't', ' ', 'i', 'n', ' ', 't', 'h', 'e'] >>> tuple(s) ('T', 'h', 'e', ' ', 'c', 'a', 't', ' ', 'i', 'n', ' ', 't', 'h', 'e') \end{pyconcode} \subsection{Converting Sequences to Strings With \protect\pythoninline{str.join()}} Note \pythoninline{str()} cannot undo the action of \pythoninline{list()} on a string. That is, \pythoninline{str(list("ABC"))} is not equal to \pythoninline{"ABC"}. Use \pythoninline{"".join(list("ABC"))} for that. To add spaces between the elements of a list, change the string at the beginning. \begin{pyconcode} >>> "".join(['c', 'a', 't']) 'cat' >>> " ".join(['c', 'a', 't']) 'c a t' \end{pyconcode} The elements of the sequence can be of any type. \begin{pyconcode} >>> ' '.join(("dinosaurs", "roamed the", "earth")) 'dinosaurs roamed the earth' >>> print('\n> '.join(("dinosaurs", "roamed the", "earth"))) dinosaurs > roamed the > earth \end{pyconcode} \section{Sample Program} \pythoninput{lab7/solarsystem2.py} \newpage \section{Exercises}\label{exercises} \begin{ex}[lettercount.py] Write program that reads in a string on the command line and returns a table of the letters of the alphabet in alphabetical order which occur in the string together with the number of times each letter occurs. Case should be ignored. A sample run of the program would look this: \begin{verbatimcode} Enter some letters >>> The cat in the hat a 2 c 1 e 2 h 3 i 1 n 1 t 4 \end{verbatimcode} This should involve writing a function called \pythoninline{count_letters} that takes in a string and returns a dictionary with these letters and counts. \end{ex} \begin{infobox}{Supplementary Files} The file \pythoninline{test_letter_count.py} is available on Canvas. Open it to see more examples. \end{infobox} \begin{ex}[date2.py, horoscope2.py] You will use dictionaries to write more readable and compact versions of \texttt{date.py} and \texttt{horoscope.py}. The requirements for both files have changed, please read the following text. Write a program \pythoninline{date2.py}, which should take in a month and day of the month, and convert it to the corresponding day of the year. Assume that leap years exist. For incorrect dates the conversion function should return \pythoninline{-1}, and you should print an error from \pythoninline{main}. For example: \begin{bashcode} python3 date2.py Type stop or enter a month, day, and year. > March, 14, 2015 Day of the year: 73 > December, 14, 2016 Day of the leap year: 349 > Oktober, 91, 2015 Invalid date entered. > stop \end{bashcode} Use the following boolean expression to check if a year is a leap year or not: \begin{python3code} is_leap = (year % 4 == 0 and year % 100 != 0) or year % 400 == 0 \end{python3code} Next, the \pythoninline{horoscope2.py} program should take in a month and a day. It should print an error message if the date is invalid, otherwise it should print the horoscope of someone who was born on that day. You should use the \pythoninline{import} statement to make use of the code you wrote in \pythoninline{date.py} for determining the user's astrological sign. The horoscopes themselves are completely up to you, as long as they start with the correct sign. For example: \begin{bashcode} python3 horoscope2.py Type stop or enter a month, day, and year. > March, 14, 2015 Pisces: Tui and La, push and pull, commit and rebase... > May, 5, 1848 Taurus: today you must choose between earth and sea, C and miniKanren... > February, 29, 1847 Invalid date entered. > stop \end{bashcode} For a reference on the zodiac dates, see the ``Tropical zodiac'' column from this table: \url{https://en.wikipedia.org/wiki/Zodiac#Table_of_dates}. Watch out for Capricorn! That zodiac spans from December 22nd to January 20th, which for this program means that it will have two different date ranges, 1 to 20 and 356 to 365. \end{ex} \begin{ex}[rpn\_calculator.py] Write a reverse Polish notation calculator. In reverse Polish notation (also known as HP calculator notation), mathematical expressions are written with the operator following its operands. For example, $3 + 4$ becomes $3~4~+$. Order of operations is entirely based on the ordering of the operators and operands. To write $3 + (4 * 2)$, we would write $4~2~*~3~+$ in RPN. The expressions are evaluated from left to right. A longer example of an expression is this: \[ 5~1~2~/~4~*~+~3~- \] which translates to \[ 5 + ( (1 / 2) * 4 ) - 3 \] If you were to try to ``parse'' the RPN expression from left to right, you would probably ``remember'' values until you hit an operator, at which point you take the last two values and use the operator on them. In the example expression above, you would store 5, then 1, then 2, then see the division operator (/) and take the last two values you stored (1 and 2) to do the division. Then, you would store the result of that (0.5) and encounter 4, which you store. When you encounter the multiplication sign (*), you would take the last two values stored and do the operation ($4 * 0.5$) and store that. Following this through step by step, the steps would look something like this (the bold number is the most recently computed value): \begin{enumerate} \item 5 1 2 / 4 * + 3 - \item 5 \textbf{0.5} 4 * + 3 - \item 5 \textbf{2} + 3 - \item \textbf{7} 3 - \item \textbf{4} \end{enumerate} Writing this algorithm for evaluating RPN in pseudo code, we get: \begin{enumerate} \item Read next value in expression. \item If number, store. \item If operator: \begin{enumerate} \item Remove last two numbers stored. \item Do operation with these last two numbers. \item Store the result of the operation as last number. \end{enumerate} \end{enumerate} If you keep repeating this algorithm, you will eventually just end up with one number stored unless the RPN expression was invalid. Your task is to write an RPN calculator which asks the user for an RPN expression and prints the result of that expression. You \emph{must} use a stack (see Section~\ref{sec:stacks}). The RPN algorithm has to be in a separate function (not main). You need to support the four basic operators (+, -, *, and /). You should detect and display messages for the following errors: \begin{itemize} \item Operand is used when not enough numbers are stored. \item More or less than one number stored after the expression is evaluated. \end{itemize} Please see the example input and output below for expressions you can test with. \begin{center} \begin{tabular}{cc} RPN Expression & Output\\ \midrule \texttt{5 1 2 / 4 * + 3 -} & 4\\ \texttt{312 999 +} & 1311 \\ \texttt{4 2 + 1 5 + * +} & Not enough operands for +.\\ \texttt{2 100 3 * 5 + 2 2 2 + + * *} & 3660\\ \end{tabular} \end{center} Note that you need to support multi-digit numbers. You cannot expect all input to be single digits. \end{ex} \printindex \vfill \input{submitting} \end{document}