{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"[Oregon Curriculum Network](http://www.4dsolutions.net/ocn)
\n",
"[Discovering Math with Python](Introduction.ipynb)\n",
"\n",
"\n",
"# Chapter 2: FUNCTIONS AT WORK\n",
"\n",
"Lets start off with a Python function, using the keyword def (for \"define\"). Functions help organize code, primarily by doing fixed unchanging things, step by step, to something changing we give them to work on.\n",
"\n",
"For example, we might have a function called \"dress this doll\" that dresses any doll we give it. Think of a function as a verb that typically works on an object, creating a result that, typically is another object (what the function returns). \n",
"\n",
"The mathematical idea of a *function* is not far off. Mathematical functions never produce a different result, given the same inputs or arguments. Different inputs may give the same output, that's fine, but not different outputs given the same inputs. Functions behave as deterministic machines, not subject to \"environmental factors\" behind the scenes.\n",
"\n",
"That's a standard to aim for with the functions you design. Be sparing with global variables that might be passed as arguments instead, lest you confuse your reader. Global constants (read-only), clearly flagged as such, are less problematic and should be conceived of as additional function inputs. \n",
"\n",
"In the example below, the function named *cyclic* is what we call a \"callable\" in Python, meaning you invoke it by putting parentheses after it, with or without arguments. Not only callables are functions. Functions are instances of one type of callable. \n",
"\n",
"When we initialize an instance of a class, we'll call the class. Lets take a look at that now. \n",
"\n",
"## Callable objects in general\n",
"\n",
"The built-in types serve as templates for actual lists, dicts, tuples, other data structures. These are callables. Lets list some of those types: \n",
"\n",
"* bool (True or False) \n",
"* str (string)\n",
"* list (a collection type) \n",
"* tuple (similar to list, but less mutable)\n",
"* dict (not a sequence, called a mapping) \n",
"* range (yes, a type, not a function) \n",
"* zip (yes, also a type, for creating instances of the zip class)\n",
"\n",
"Lets not forget the other numeric types either, such as float, int and Decimal. The bool type is actually a subclass of the integers in Python, the True and False serving as keyword names for 1 and 0 respectively:"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"issubclass(bool, int)"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"isinstance(False, int)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Calling types\n",
"\n",
"Calling any type with no arguments logically suggests an empty instance of whatever we're creating, whatever Something, e.g. d = dict() would be \"empty dictionary\" and the_list = list() should start an empty list. \n",
"\n",
"How about int(); float(); Decimal()? These would produce their respective versions of zero, one would think, and they do.\n",
"\n",
"Lets do some testing, starting with collection types (objects that hold or contain other objects):"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[] {} set() ()\n"
]
}
],
"source": [
"the_list = list()\n",
"nada_dict = dict(the_list) # converting\n",
"empty_set = set() # can't use {} as that means empty dict\n",
"empty_tuple = tuple()\n",
"print(the_list, nada_dict, empty_set, empty_tuple)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"print( ) is an example of a built-in Python function. It sends strings to the console, converting objects to strings first, as a part of its job. We fed it not-string type objects, but it didn't complain.\n",
"\n",
"In a Jupyter Notebook, the \"console\" is the output area immediately beneath the code cell. More typically, print() will output to a terminal window, from inside a running program. We use the input() function to go the other way, from a console to a program. Execution pauses waiting for a user to type something and hit the Enter key. input() always returns strings in Python 3, the version we're using here.\n",
"\n",
"Lets continue calling the built-in types, with no arguments..."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"empty_string: \n",
"logical: False\n",
"float_zero: 0.0\n",
"int_zero: 0\n",
"d: 0\n"
]
}
],
"source": [
"import decimal # needs to be imported\n",
"# lets create more \"empty stuff\" by calling types with no arguments\n",
"empty_string = str()\n",
"logical = bool()\n",
"float_zero = float()\n",
"int_zero = int()\n",
"d = decimal.Decimal() # Decimal is a class name inside the decimal module\n",
"\n",
"# a triple-quoted string may go on for many lines...\n",
"# and a format string -- note the f prefix -- enables \n",
"# substitution of surrounding objects into curly brace \n",
"# placeholders -- new as of 3.6 (or use the format method)\n",
"print(f\"\"\"\n",
"empty_string: {empty_string}\n",
"logical: {logical}\n",
"float_zero: {float_zero}\n",
"int_zero: {int_zero}\n",
"d: {d}\"\"\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The empty string doesn't show up, because it's empty. Spaces wouldn't show up either, when printed. However an empty string and single space are different. \n",
"\n",
"The former has a length of 0, the latter a length of 1. "
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0 1\n"
]
}
],
"source": [
"print(len(str()), len(\" \"))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"If we check for equality (==), we find the answer is False. \n",
"\n",
"You may also compare values using >, <, =>, <=, and != (not equal). Not all objects are \"ordered\" such that these operators would make sense. When we define our own types, we'll have the choice whether to implement these comparators for them."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"str() == \" \" # empty string equals space? (no way)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"What have we been looking at so far? \n",
"\n",
"Built-in callables mainly (including a built-in *print* function). Callable objects include more than just functions; but also types. \n",
"\n",
"None of the keywords are callables, nor are numbers or strings. \"Dog\"() or 3() would be a syntax error. \n",
"\n",
"If you wish instances of your own types to behave as callables, you'll have that choice. Python is standing by to equip your instances with all the bells and whistles the built-in types have.\n",
"\n",
"In conclusion, lets see if we can tease out all the built-in types from what's available on boot up into Python. We'll filter out any type having to do with raising errors or exceptions."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"['bool',\n",
" 'bytearray',\n",
" 'bytes',\n",
" 'classmethod',\n",
" 'complex',\n",
" 'dict',\n",
" 'enumerate',\n",
" 'filter',\n",
" 'float',\n",
" 'frozenset',\n",
" 'int',\n",
" 'list',\n",
" 'map',\n",
" 'memoryview',\n",
" 'object',\n",
" 'property',\n",
" 'range',\n",
" 'reversed',\n",
" 'set',\n",
" 'slice',\n",
" 'staticmethod',\n",
" 'str',\n",
" 'super',\n",
" 'tuple',\n",
" 'type',\n",
" 'zip']"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def get_types():\n",
" output = []\n",
" for name in dir(__builtins__):\n",
" the_type = eval(name) # turn string into original object\n",
" if type(the_type) == type:\n",
" if not issubclass(the_type, BaseException):\n",
" output.append(name)\n",
" return output\n",
"\n",
"types = get_types()\n",
"types"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## A First Function\n",
"\n",
"Now lets look at a user-defined function, a source code for an object of that type. \n",
"\n",
"The function below expects a single object, a data structure for input. It also returns an object. \n",
"\n",
"The triple quoted docstring at the top of *cyclic* tells its user what it does, plus the annotations feature lets us write that we expect a dict more explicitly, although the intepreter does not enforce annotations. \n",
"\n",
"If we wanted any type checking at the start of our function, to make sure a dict is really what was passed in, we would need to write that ourselves.\n",
"\n",
"The triple-quoted docstring shows the annotated version of the function head, the line with def in it. In future functions, annotations will often be used.\n",
"\n",
"We've also made abundant use of comments. Comments and docstrings have a different audience. Docstrings print out, nicely formatted, in response to help(), even for an end user without source code. They should only appear right at the top of a function, as a string with no name.\n",
"\n",
"Comments (with a pound sign) are aimed at readers of the actual source code. They can go anywhere. Python has no \"multi-line comment\" construct. Docstrings should carry the weight of describing the API (\"how to use me\")."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def cyclic(the_dict):\n",
" \"\"\"\n",
" accepts a permutation as a dict, returns cyclic notation, \n",
" a compact view of a permutation\n",
" \n",
" could say (annotated version):\n",
" def cyclic(the_dict : dict) -> tuple:\n",
" \n",
" without annoying, or troubling, the Python interpreter (try it!).\n",
" \"\"\"\n",
" output = [] # we'll make this a tuple before returning\n",
" while the_dict:\n",
" start = tuple(the_dict.keys())[0]\n",
" the_cycle = [start]\n",
" the_next = the_dict.pop(start) # take it out of the_dict\n",
" while the_next != start: # keep going until we cycle\n",
" the_cycle.append(the_next) # following the bread crumb trail...\n",
" the_next = the_dict.pop(the_next) # look up what we're paired with\n",
" output.append(tuple(the_cycle)) # we've got a cycle, append to output\n",
" return tuple(output) # giving back a tuple object, job complete"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Don't let the above code intimidate you. \n",
"\n",
"This is about the right size for a function, and does just the right amount of work. \n",
"\n",
"Note that it delegates to the methods our high level data structures bring to the table, such as *pop* and *append*. We get a lot done in just a few lines.\n",
"\n",
"Lets look at these data structures in action, in isolation, before coming back to this function to see exactly what it's about.\n",
"\n",
"### Looking at Data Structures\n",
"\n",
"All list type objects know how to append, as a part of their heritage. Lists also respond to square brackets, or \"get item\" syntax."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"bear scorpion\n"
]
}
],
"source": [
"zoo = [\"bear\", \"tiger\", \"lion\"]\n",
"zoo.append(\"scorpion\")\n",
"print(zoo[0], zoo[3]) # print first and last"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We may also insert into a list, at any point:"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"['bear', 'tiger', 'monkey', 'lion', 'scorpion']"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"zoo.insert(2, \"monkey\") # after item 2\n",
"zoo"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"To pop, in the case of a dict, is to remove an item by key, while returning the value. Lets look at that:"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"{'bear': 2.5, 'monkey': 3, 'otter': 1.5}"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ages = {\"monkey\":3, \"bear\":2.5, \"otter\":1.5} # remember me?\n",
"ages"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"2.5"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bear_age = ages.pop(\"bear\") # take a key, return a value\n",
"bear_age"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"{'monkey': 3, 'otter': 1.5}"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ages # the bear item is gone"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Or just use the keyword del, for delete, if you don't have a need for the object in future:"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"{'monkey': 3}"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"del ages['otter'] # delete this element\n",
"ages"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now lets get back to our function, wherein these data structures, each with a bag of tricks (methods) play a starring role.\n",
"\n",
"In this function *cyclic*, we're \"diasy chaining\" through a dict, meaning each key points to a value, which value then becomes the key to a next value, and so on, until we loop back around to the first in the sequence, if we do (we must eventually because the dict is finite).\n",
"\n",
"Sounds like [a square dance](https://youtu.be/QuaojjCV1Tk) of some kind.\n",
"\n",
"Our input dict, what gets the ball rolling so to speak, is not just any dict. Animals paired with ages would not work. The docstring mentions expecting a \"permutation\" which you may think of as a set of objects paired with themselves in a different order. We might call it a \"scramble\". In the case of animals, a permuation might look like this..."
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Keys: dict_keys(['monkey', 'tiger', 'scorpion', 'bear'])\n",
"Values: dict_values(['bear', 'scorpion', 'monkey', 'tiger'])\n"
]
}
],
"source": [
"pairings = {\"monkey\":\"bear\", \"tiger\":\"scorpion\", \"scorpion\":\"monkey\", \"bear\":\"tiger\"}\n",
"print(\"Keys:\", pairings.keys())\n",
"print(\"Values:\", pairings.values())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Notice the keys and values are the same elements. Think of the values as simply the keys but in a different order. We could say \"monkey maps to bear\" and \"tiger maps to scorpion\".\n",
"\n",
"Now lets feed the above dict to the function and see what we get:"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"(('monkey', 'bear', 'tiger', 'scorpion'),)"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"result = cyclic(pairings)\n",
"result"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The resulting tuple is read left to right and says \"monkey maps to bear\" and \"bear to tiger\" and \"tiger to scorpion\". The last element wraps around to the first i.e. \"scorpion maps to monkey\". That all corresponds to what we said in the original dict.\n",
"\n",
"Instead of animals, now, lets think in terms of individual letters instead.\n",
"\n",
"If letter 'd' maps to letter 'd' then ('d',) is the cyclic subgroup (an inner tuple); whereas if 'd' maps to 'a', 'a' back to 'd', then ('d' 'a') or ('a' , 'd') says it all. Any permutation may be expressed as a tuple of such tuples.\n",
"\n",
"Pick a letter, any letter (in our set). It maps to something, which maps to something else, and so on, until you come back around. We'll always be able to express a permutation in this form.\n",
"\n",
"Lets run the above function on a permutation mapping all lowercase ASCII letters (US keyboard), as well as space, to themselves. \n",
"\n",
"First, lets create the input dictionary:"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"ASCII abcdefghijklmnopqrstuvwxyz\n",
"Coding Key: {'a': 'p', 'b': 'y', 'c': 'j', 'd': 'z', 'e': 'h', 'f': 'l', 'g': 'i', 'h': 'f', 'i': 'o', 'j': 'r', 'k': 'd', 'l': ' ', 'm': 'e', 'n': 'q', 'o': 'n', 'p': 's', 'q': 'x', 'r': 'g', 's': 'b', 't': 'a', 'u': 'c', 'v': 't', 'w': 'w', 'x': 'k', 'y': 'm', 'z': 'u', ' ': 'v'}\n"
]
}
],
"source": [
"from string import ascii_lowercase # a string\n",
"from random import shuffle\n",
"the_letters = list(ascii_lowercase) + [\" \"] # lowercase plus space, as a list\n",
"shuffled = the_letters.copy() # copy me\n",
"shuffle(shuffled) # works \"in place\" i.e. None returned\n",
"permutation = dict(zip(the_letters, shuffled)) # make pairs, each letter w/ random other\n",
"print(\"ASCII\", ascii_lowercase)\n",
"print(\"Coding Key:\", permutation)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"ASCII is the precursor to [Unicode](https://youtu.be/Z_sl99D2a18), a vast lookup table containing a huge number of important symbols, such as world alphabets and ideograms, special symbols (chess pieces, playing cards), emoji. \n",
"\n",
"In some romantic science fiction we might imagine sharing Unicode with distant aliens, as if this were a helpful puzzle piece. When talking with humans though, it really helps to share a database.\n",
"\n",
"We take all 26 letters from lowercase ascii, a canned (pre-stored) string within the string module, part of the Standard Library, plus the space (space bar, ASCII character 32), and turn that into a list of 27 elements. \n",
"\n",
"Feed two such lists, one a clone of the other, but reshuffled, to the zip type, making pairs, in turn feeding all those pairs in one object to dict, a type which knows how to deal with precisely that format.\n",
"\n",
"Lets look at that same creation process with some integers instead:"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"((0, 12),\n",
" (1, 16),\n",
" (2, 5),\n",
" (3, 1),\n",
" (4, 7),\n",
" (5, 2),\n",
" (6, 10),\n",
" (7, 17),\n",
" (8, 0),\n",
" (9, 8),\n",
" (10, 6),\n",
" (11, 13),\n",
" (12, 20),\n",
" (13, 9),\n",
" (14, 3),\n",
" (15, 4),\n",
" (16, 19),\n",
" (17, 15),\n",
" (18, 11),\n",
" (19, 14),\n",
" (20, 18))"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# feel free to keep re-running this, a different permutation every time!\n",
"seq1 = list(range(21))\n",
"seq2 = seq1.copy()\n",
"shuffle(seq2)\n",
"the_zip = tuple(zip(seq1, seq2)) # actually a tuple already\n",
"the_zip"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Although the above data structure is a tuple of tuples, its not in cyclic notation. Rather, its a step on the way to becoming a dict type object.\n",
"\n",
"Lets feed the above to the native the dict type, an essential job of which is to spawn instances of its own type, given compatible input. A tuple of pairs is a form the dict type knows how to eat, because the meaning is obvious. We want each pair to become an element in our dict.\n",
"\n",
"To that end, in its capacity as a dict-maker, the dict type is a callable, as we have seen, taking in the raw material needed for the constitution of new such objects, new dict objects in this case:"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"{0: 12,\n",
" 1: 16,\n",
" 2: 5,\n",
" 3: 1,\n",
" 4: 7,\n",
" 5: 2,\n",
" 6: 10,\n",
" 7: 17,\n",
" 8: 0,\n",
" 9: 8,\n",
" 10: 6,\n",
" 11: 13,\n",
" 12: 20,\n",
" 13: 9,\n",
" 14: 3,\n",
" 15: 4,\n",
" 16: 19,\n",
" 17: 15,\n",
" 18: 11,\n",
" 19: 14,\n",
" 20: 18}"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"perm_ints = dict(the_zip) # the_zip is by now a tuple of tuples, which dict will digest\n",
"perm_ints"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Our function will work equally well on any permutation dict, as we're not depending on the type of our keys and/or values for this recipe to work. \n",
"\n",
"In the one dict, *permutation*, we map letters to letters, in this other *perm_ints*, we maps ints to ints. \n",
"\n",
"The cyclic function doesn't care about these details and works the same either way. Python is good at letting us generalize. \n",
"\n",
"That doesn't mean *cyclic* is immune from crashing. It's expecting a dict wherein every value is also a valid key. Not every dict is like that."
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"(('a', 'p', 's', 'b', 'y', 'm', 'e', 'h', 'f', 'l', ' ', 'v', 't'),\n",
" ('c', 'j', 'r', 'g', 'i', 'o', 'n', 'q', 'x', 'k', 'd', 'z', 'u'),\n",
" ('w',))"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"cyclic(permutation)"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"((0, 12, 20, 18, 11, 13, 9, 8),\n",
" (1, 16, 19, 14, 3),\n",
" (2, 5),\n",
" (4, 7, 17, 15),\n",
" (6, 10))"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"cyclic(perm_ints)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You may be wondering, considering the above pipeline, which went from zip type, to tuple, then to dict, whether a dict might eat a zip type directly. Lets try that..."
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"{0: 12,\n",
" 1: 16,\n",
" 2: 5,\n",
" 3: 1,\n",
" 4: 7,\n",
" 5: 2,\n",
" 6: 10,\n",
" 7: 17,\n",
" 8: 0,\n",
" 9: 8,\n",
" 10: 6,\n",
" 11: 13,\n",
" 12: 20,\n",
" 13: 9,\n",
" 14: 3,\n",
" 15: 4,\n",
" 16: 19,\n",
" 17: 15,\n",
" 18: 11,\n",
" 19: 14,\n",
" 20: 18}"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"cipher = dict(zip(seq1, seq2)) # will a dict eat a zip?\n",
"cipher"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So yes, that works great.\n",
"\n",
"So why did we call our dict thing a cipher just now? Because a permutation suggests a way of encrypting a message, meaning to make it \"hard to crack\" where \"prying eyes\" are concerned. \n",
"\n",
"So-called substitution codes are not that easy to crack if changed frequently and used for only short messages, or so they tell me. If we know the encrypted language, such as English, then a letter frequency analysis may help with the crack.\n",
"\n",
"However lets not get into making any claims about uncrackability, and just take a look of how if two people, call them Alice and Bob, share the same secret key, then message between them might stay encrypted, impeneterable to Eve, at least for awhile."
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def encrypt(plain : str, secret_key : dict) -> str:\n",
" \"\"\"\n",
" turn plaintext into cyphertext using the secret key\n",
" \"\"\"\n",
" output = \"\" # empty string\n",
" for c in plain:\n",
" output = output + secret_key.get(c, c) \n",
" return output"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"c = encrypt(\"able was i ere i saw elba\", permutation) # something Napoleon might have said"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"'able was i ere i saw elba'"
]
},
"execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"c"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Excuse me? That doesn't look scrambled at all? The reason is subtle: feeding permuation to cyclic above rendered it empty. We operated upon \"the_dict\" and in turning out a corresponding tuple of tuples, consumed the object fed it. The function worked on our only copy, on the original itself."
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"{}"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"permutation"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's do two things to improve the situation:\n",
"* generate permutations from a function, that takes a set of what to permute\n",
"* make sure the cyclic function doesn't mess with the passed-in original\n",
"\n",
"Let's do first things first:"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def make_perm(incoming : set) -> dict:\n",
" seq1 = list(incoming)\n",
" seq2 = seq1.copy()\n",
" shuffle(seq2)\n",
" return dict(zip(seq1, seq2))"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"{0: 3, 1: 7, 2: 5, 3: 2, 4: 1, 5: 8, 6: 6, 7: 9, 8: 0, 9: 4}"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"make_perm(set(range(10)))"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"{' ': 'z',\n",
" 'a': ' ',\n",
" 'b': 'r',\n",
" 'c': 'm',\n",
" 'd': 'i',\n",
" 'e': 'd',\n",
" 'f': 'x',\n",
" 'g': 'v',\n",
" 'h': 'w',\n",
" 'i': 'y',\n",
" 'j': 'k',\n",
" 'k': 'n',\n",
" 'l': 'h',\n",
" 'm': 'p',\n",
" 'n': 's',\n",
" 'o': 'a',\n",
" 'p': 'g',\n",
" 'q': 'e',\n",
" 'r': 'b',\n",
" 's': 'o',\n",
" 't': 'u',\n",
" 'u': 'l',\n",
" 'v': 'j',\n",
" 'w': 'c',\n",
" 'x': 't',\n",
" 'y': 'f',\n",
" 'z': 'q'}"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"make_perm(the_letters) # defined above as lowercase ascii letters plus space"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"That's all working great, and now the second change, a new cyclic:"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def cyclic(the_perm : dict) -> tuple:\n",
" \"\"\"\n",
" cyclic notation, a compact view of a permutation\n",
" \"\"\"\n",
" output = [] # we'll make this a tuple before returning\n",
" \n",
" the_dict = the_perm.copy() # protect the original from exhaustion\n",
" \n",
" while the_dict:\n",
" start = tuple(the_dict.keys())[0]\n",
" the_cycle = [start]\n",
" the_next = the_dict.pop(start) # take it out of the_dict\n",
" while the_next != start: # keep going until we cycle\n",
" the_cycle.append(the_next) # following the bread crumb trail...\n",
" the_next = the_dict.pop(the_next) # look up what we're paired with\n",
" output.append(tuple(the_cycle)) # we've got a cycle, append to output\n",
" return tuple(output) # giving back a tuple object, job complete"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"original = make_perm(the_letters) # the_letters is a string"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"cyclic_view = cyclic(original)"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"(('a',\n",
" 'n',\n",
" 'h',\n",
" 'v',\n",
" 'y',\n",
" 'u',\n",
" 'j',\n",
" 'z',\n",
" 'c',\n",
" 'w',\n",
" 't',\n",
" 's',\n",
" 'g',\n",
" 'r',\n",
" 'o',\n",
" 'x',\n",
" 'q',\n",
" 'k',\n",
" 'p',\n",
" 'l',\n",
" 'd',\n",
" 'm',\n",
" 'i',\n",
" ' ',\n",
" 'f',\n",
" 'e'),\n",
" ('b',))"
]
},
"execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"cyclic_view"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"{' ': 'f',\n",
" 'a': 'n',\n",
" 'b': 'b',\n",
" 'c': 'w',\n",
" 'd': 'm',\n",
" 'e': 'a',\n",
" 'f': 'e',\n",
" 'g': 'r',\n",
" 'h': 'v',\n",
" 'i': ' ',\n",
" 'j': 'z',\n",
" 'k': 'p',\n",
" 'l': 'd',\n",
" 'm': 'i',\n",
" 'n': 'h',\n",
" 'o': 'x',\n",
" 'p': 'l',\n",
" 'q': 'k',\n",
" 'r': 'o',\n",
" 's': 'g',\n",
" 't': 's',\n",
" 'u': 'j',\n",
" 'v': 'y',\n",
" 'w': 't',\n",
" 'x': 'q',\n",
" 'y': 'u',\n",
" 'z': 'c'}"
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"original"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Life is good. As a final touch, we'd like to deciper or decrypt, what was encrypted, using the very same secret_key. All encrypt( ) needs to do is reverse the secret key, giving what's called the inverse permutation, and call encrypt with that. \n",
"\n",
"The original message magically reappears.\n",
"\n",
"Lets make a new permutation for this test, so we don't confuse ourselves."
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"cipher = make_perm(the_letters)\n",
"c = encrypt(\"hello alice this is bob lets hope eve does not decrypt this\", cipher)"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def decrypt(cyphertext : str, secret_key : dict) -> str:\n",
" \"\"\"\n",
" Turn cyphertext into plaintext using ~self\n",
" \"\"\"\n",
" reverse_P = {v: k for k, v in secret_key.items()} # invert me!\n",
" output = \"\"\n",
" for c in cyphertext:\n",
" output = output + reverse_P.get(c, c)\n",
" return output"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"'cbiijkqiwgbkmcwokwoknjnkibmokcjybkbebkvjbokujmkvbg zymkmcwo'"
]
},
"execution_count": 37,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"c"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"p = decrypt(c, cipher)"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"'hello alice this is bob lets hope eve does not decrypt this'"
]
},
"execution_count": 39,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"p"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Final thing: I bet you might be wondering about a function that ate a tuple of tuples, some cyclic notation, and gave back the corresponding dictionary object. \n",
"\n",
"This would be the inverse function of *cyclic* so we could call it *inv_cyclic*. That's a great cliff-hanger for a next chapter wouldn't you think? Feel free to try writing *inv_cyclic*. \n",
"\n",
"Here's something to get you started:"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def inv_cyclic(cycles : tuple) -> dict:\n",
" output = {} # empty dig\n",
" pass # more code goes here\n",
" return output"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Have fun!\n",
"\n",
"Back to Chapter 1: [Welcome to Python](Welcome%20to%20Python.ipynb)
\n",
"Continue to Chapter 3: [A First Class](A%20First%20Class.ipynb)
\n",
"[Introduction](Introduction.ipynb)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.0"
}
},
"nbformat": 4,
"nbformat_minor": 2
}