{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Goodbye!\n",
"\n",
"Thanks for having PWSAfrica in Ibadan! We're writing this while people are doing their group projects and it's fantastic to have people solve complex, real-world problems. Whatever you go on to do --- and however much Python you can use in it --- we're certain you'll go far, and we're proud of all our participants. \n",
"Well done, and thank you!\n",
"\n",
"We don't want the teaching to end when we leave, and we want to help you understand how you can teach *yourselves*, so that when problems come up which can be solved with programming, you can write a solution --- even if it doesn't use the techniques we've taught you.\n",
"\n",
"In this notebook, you'll find:\n",
"\n",
"1. Some extra problems to solve\n",
"2. Some libraries you might find helpful\n",
"3. Some tips and techniques we use when *we* write code\n",
"4. Our solutions to the problems in part 1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Problems to solve"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"*Remember! There are plenty of problems you can work on at [the pwsafrica projects page](http://pwsafrica.org/projects), where we hosted the four projects to be chosen from at the end of the workshop. You can work on these, too!*\n",
"\n",
"We've put together a few more puzzles for you to keep learning from when we're gone. Try out any that interest you!\n",
"\n",
"1. FizzBuzz\n",
"2. Tic-Tac-Toe\n",
"3. Collatz using *graph theory*\n",
"4. Dictionary for PWSAfrica instructors\n",
"5. RPN Calculator\n",
"6. ROT13 Encryption\n",
"\n",
"*Advanced*:\n",
"\n",
"1. Markov Chain\n",
"2. Conway's Game of Life\n",
"3. Elementary Cellular Automata"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Fizzbuzz\n",
"\n",
"**Fizzbuzz should be a relatively easy program for you to write --- it's similar to the problem you got on the first day of the workshop.**\n",
"\n",
"**Fizzbuzz is also a _common interview question_! You can already solve professional-level programming tasks. Tom has been asked this multiple times in job interviews.**\n",
"\n",
"\n",
"\"Fizzbuzz\" is a program where we write a function which takes a number `n`, and returns a list where --- for every number between `1` and `n` --- the list has:\n",
"* \"Fizz\" if the number divides by 3\n",
"* \"Buzz\" if the number divides by 5\n",
"* `n` as a string otherwise\n",
"\n",
"So, if we run `fizzbuzz(20)`, we should be returned:\n",
"\n",
"```python\n",
"['1', '2', 'Fizz', '4', 'Buzz', 'Fizz', '7', '8', 'Fizz', 'Buzz', '11', 'Fizz', '13', '14', 'FizzBuzz', '16', '17', 'Fizz', '19', 'Buzz']\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def fizzbuzz(n):\n",
" pass # You can write your solution here\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Run this cell after the solution cell above to see whether your solution is correct.\n",
"def test_fizzbuzz():\n",
" return fizzbuzz(20) == ['1', '2', 'Fizz', '4', 'Buzz', 'Fizz', '7', '8', 'Fizz', 'Buzz', '11', 'Fizz', '13', '14', 'FizzBuzz', '16', '17', 'Fizz', '19', 'Buzz']\n",
"test_fizzbuzz()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Tic-Tac-Toe\n",
"\n",
"Standard! This is just to implement the game of tic-tac-toe.\n",
"\n",
"Some hints to get things moving: \n",
"* You can have the user input their move as a number from 1 to 9, where each number refers to an index in an array, or a key in a dictionary.\n",
"* A loop with an `input()` at the beginning is all you really need to implement a game! Then you can get the user's move, work out how that changes the state of your game, and every iteration of the loop is effectively a \"turn\".\n",
"* You'll need to check whether somebody's won yet. I'm not going to give this away --- that'd spoil the challenge! --- but think about how you'll work that out. "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Go ahead and implement a solution here!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Collatz, using graph theory\n",
"\n",
"Toward the end of the first week, we wrote code which produced \"Collatz sequences\". Our solutions produced lists of collatz sequences.\n",
"\n",
"For problems like this, testing small numbers is much easier than testing large numbers. For example, the series for 3 is `7` numbers long, but for `3000`, it's 49! As we get into sequences that are thousands long --- or millions! --- our computers might get a bit slow.\n",
"\n",
"Graph theory can help us here. Instead of just producing a list, what if we recorded which numbers lead to others? The example we gave before on the board was the sequence for `3`:\n",
"\n",
"```python\n",
"[3, 10, 5, 16, 8, 4, 2, 1]\n",
"```\n",
"\n",
"If we generate the sequence for `6`, we *know* that, once we reach `3`, we'll end the sequence in exactly the same way:\n",
"\n",
"```python\n",
"[6, 3, 10, 5, 16, 8, 4, 2, 1]\n",
"```\n",
"\n",
"However, the sequence for `20` is similar, too.\n",
"\n",
"```python\n",
"[20, 10, 5, 16, 8, 4, 2, 1]\n",
"```\n",
"\n",
"We can use this to our advantage in a clever way. If we record the number one number leads to, we only ever have to compute the next number *once*! What's more: we just have to store what *single number* comes after another number, and then use that to find *it's* next number, again and again, until we reach 1 like before. (This technique is called \"memoization\", and is related to \"dynamic programming\", if you'd like to read more after the problem. It's phenomenally effective!)\n",
"\n",
"So. Instead of building a collatz *sequence*, we can put together a *dictionary* representing *all* collatz sequences. The dictionary has integers for both its keys and its values, and for every key in the dictionary, the next number in the sequences will be its value. We can do this because given any number in the collatz sequence, there is exactly one number it will lead to!\n",
"\n",
"What we are building is a directed graph. Each relationship in the dictionary is an edge in the graph, indicating the next step of the collatz sequence. A similar graph is drawn in [xkcd #710](https://xkcd.com/710/).\n",
"\n",
"*Your task:* Implement a Collatz function which --- like before --- will take a number and return a list representing its Collatz sequence, but which builds the sequence from a dictionary representation as soon as it can, and records every computation it makes in this dictionary for later."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# You can write your solution here!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Dictionary for PWSAfrica instructors\n",
"\n",
"While we spent time in Ibadan we were excited to learn some local phrases! Unfortunately our best way to remember them was to keep them in a note in Ben's phone. *Surely* we can do better.\n",
"\n",
"A task we very nearly set you while you were learning dictionaries was to write a translator between English and the various languages spoken in Nigeria. This should be implemented using a Python dictionary: english phrases are the keys, and the local translations are the values!\n",
"\n",
"Your task is the following:\n",
"1. Write a program which reads a file containing English and phrases in your Nigerian language of choice. The translations are on the same line, and take the form `english:your chosen language`. (Note: that means you can split on a `:`...). \n",
" \n",
" You should read the file into a Python dictionary, and then print the translations.\n",
"\n",
"\n",
"2. Write a prompt, where instead of printing the dictionary, a user is asked for an English phrase as `input()`, and they are given the translation in the file.\n",
"\n",
"\n",
"3. Write another prompt where a user can enter an English phrase --- *then* the translation in your chosen language! --- and writes it to the file you're *reading* from, so you can *add* to the dictionary. [This may be helpful when writing to a file.](https://stackoverflow.com/a/6160082)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# You can write your solution here!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## RPN Calculator\n",
"\n",
"A *Reverse Polish Notation* (RPN) calculator was a popular kind of calculator in the Soviet Union. RPN calculators are also supposed to be easier for children to learn to use than regular calculators, and it turns out that writing them is quite a good exercise!\n",
"\n",
"A traditional calculator works using *infix notation*. This looks like this:\n",
"\n",
"```python\n",
"6 * 4 + 6 # = 30\n",
"```\n",
"\n",
"Infix puts the operators *between* the digits they relate to. By contrast, RPN puts the operators *after* the digits they relate to:\n",
"\n",
"```python\n",
"6 6 4 * + # = 30\n",
"```\n",
"\n",
"This has some benefits. One is that it turns out to be quite easy for computers to understand! More relevant to us humans, it also turns out that you never have to specify your order of operations with RPN. For example: if I wanted to write:\n",
"\n",
"```python\n",
"6 * (4 + 6) # = 60\n",
"```\n",
"\n",
"...I have to include brackets. This isn't the case when working with RPN, because the intended order of operation is specified by the order your operators are in:\n",
"\n",
"```python\n",
"6 6 4 + * # = 60\n",
"```\n",
"\n",
"### How is RPN executed?!\n",
"\n",
"The computer takes the first operator and the last two digits, calculates the result, and leaves the result at the front of the digits. So:\n",
"\n",
"```python\n",
"6 6 4 + * # ...becomes...\n",
"6 10 * # ...which becomes...\n",
"60\n",
"```\n",
"\n",
"### Your task\n",
"\n",
"Write a calcuator, which takes a string as `input()` and evaluates it as if it was an RPN expression. Print the result.\n",
"\n",
"To keep things simple, we'll assume that the digits and the operators *never mix*. Actual RPN calculators don't really work this way, but it makes our code much easier. The solution found at the end of this notebook also makes this assumption."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# When you're ready, go ahead and write us a calculator here."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## ROT13 Encryption\n",
"\n",
"ROT13 encryption is a very simple encryption scheme, where for every character in a message, we replace it with the 13th next one in the alphabet. This means that when we see the letter `a` we replace it with `n`, and when we see the letter `L` we replace it with `Y`, and when we see the letter `o` we replace it with `b` (because we loop back around to the beginning).\n",
"\n",
"That is to say, we map:\n",
"\n",
"```\n",
"a -> n\n",
"b -> o\n",
"c -> p\n",
"...\n",
"l -> y\n",
"m -> z\n",
"n -> a\n",
"o -> b\n",
"```\n",
"\n",
"And so on. \n",
"\n",
"Your task is to write a function which will encrypt a string using ROT13. You should also write a function which decrypts an encrypted string --- can you see how this would work?\n",
"\n",
"### Advanced: use `ord()` and `chr()`\n",
"\n",
"Python has useful functions for this, called `ord()` and `chr()`. If you use them correctly, they'll make your code for this much more elegant!\n",
"\n",
"* `ord()` will take a *single character* and return the *number* associated with that character.\n",
"* `chr()` will take a *number* and return the *single character* associated with that number.\n",
"\n",
"This exists because all computers really understand is numbers, and when we type characters into the computer, it has to store them in some numerical way. The system for doing this is called *Unicode*, and every character has a number associated with it defined by unicode!\n",
"\n",
"Sometimes the best explanation is to see something working, so here's an explanatory code snippet:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(\"number associated with 'a' is:\\t\", ord('a'))\n",
"print(\"number associated with 'y' is:\\t\", ord('y'))\n",
"print(\"capital letters are treated separately! look:\\t ord('A') is \", ord('A'))\n",
"print()\n",
"print(\"we can also use chr() to go backwards. Look:\\t chr(100) should be 'd': \", chr(100))\n",
"print(\"infact, one is the inverse of the other. check it out:\\t chr(ord('a')) is \", chr(ord('a')))\n",
"print()\n",
"print(\"chr(ord('Z')) == 'Z' is \", chr(ord('Z')) == 'Z')\n",
"print()\n",
"print(\"We can also use this to manipulate numbers text. Look:\\t chr(ord('a')+1) is \", chr(ord('a') + 1))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# You can implement your solution here, with or without using ord() and chr()."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## *Advanced:* Markov Chain\n",
"\n",
"A Markov Chain is a graph, where every edge on the graph is weighted by a probability. We start on a node on the graph, and then select a future point on the graph by selecting an edge according to their probability weightings. [You can learn more about Markov Chains here](http://setosa.io/ev/markov-chains/), or alternatively [in more detail here](https://en.wikipedia.org/wiki/Markov_chain).\n",
"\n",
"Basically: for every state, we want to move to a future state according to some probability.\n",
"\n",
"Your task is to work out how to encode a Markov Chain in Python."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# You can write your solution here!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## *Advanced:* Conway's Game of Life\n",
"\n",
"Conway's Game of Life is a famous programming task built around the concept of *cellular automata*. More general cellular automata are explored in the next task.\n",
"\n",
"Conway's Game of Life is a simple simulation on a two dimensional grid of squares. From simple rules, fascinating and complex behaviours can be derived. [You can read detail about Conway's Game of Life here.](https://simple.wikipedia.org/wiki/Conway%27s_Game_of_Life)\n",
"\n",
"The basic idea behind the task is that, on the grid, squares are thier black (\"alive\") or white (\"dead\"). From a given state of the grid at time `t`, the state at time `t+1` is determined by applying the following rules for each square:\n",
"\n",
"1. Any alive cell that is touching less than two alive neighbours dies.\n",
"2. Any alive cell touching four or more alive neighbours dies.\n",
"3. Any alive cell touching two or three alive neighbours does nothing.\n",
"4. Any dead cell touching exactly three alive neighbours becomes alive.\n",
"\n",
"Try writing this and animating it! You can animate it in pygame, matplotlib or just by printing characters on the screen.\n",
"\n",
"Feel free to look up solutions online; there are lots of ways to implement this."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## *Advanced:* Elementary Cellular Automata\n",
"\n",
"Cellular automata can be very complex, but simple ones can be made out of grids like Conway's Game of Life uses. *Even simpler ones* can be made using a simple line, or a one-dimensional grid!\n",
"\n",
"For an automaton with cells which are either dead or alive, and have a one-dimensional grid, we can specify the rules for each cell in terms of its previous state and the state of its two neighbours. If `0` means a cell is dead, and `1` means a cell is alive, we can determine the future states by deciding whether each of these previous states results in a future dead or alive state:\n",
"\n",
"* `000` \n",
"* `001` \n",
"* `010` \n",
"* `011` \n",
"* `100` \n",
"* `101` \n",
"* `110` \n",
"* `111` \n",
"\n",
"Here, the cell we're deciding the future state for is the middle number. The numbers to their left and right are their left and right neighbours. So, for an automata with state `00110` at time `t`, the third cell at time `t+1` is determined by the `011` rule. [You can read more about this here if you're stuck.](https://en.wikipedia.org/wiki/Cellular_automaton#Elementary_cellular_automata)\n",
"\n",
"It turns out that some combinations of dead-alive rules for these automata are actually *\"Turing-Complete\"*, meaning that any mathematical proof can be encoded using them. That's amazing!\n",
"\n",
"Your task is to implement a *general* automata, which is given a set of eight rules --- one for each possible state for each possible cell, as detailled above --- and will animate this automata, using pygame, matplotlib, or just by printing lines of characters."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# You can implement your solution here!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Extra libraries & resources\n",
"\n",
"Parts more useful for software engineering are at the top of this section, while parts more useful for mathematicians are kept toward the bottom. So, if you're mostly interested in building large projects, pay most attention to the bits at the top. If you'd like to use Python to help with coursework and projects for your studies, pay attention to the bits at the bottom.\n",
"\n",
"## GitHub\n",
"\n",
"There's lots of useful code on GitHub! GitHub is a place where people publish their code for others to use. (Actually, it's much more than this, but for our purposes GitHub is a little like a shop window you can display your projects from.)\n",
"\n",
"Having a GitHub page is essential as a professional programmer, and if you're curioous about taking your programming further than PWSAfrica playing with GitHub is a great way to start. It also backs up your projects, in case you have a hard drive failure or similar, and is designed to take as little data as possible to work! Try it out.\n",
"\n",
"## Keon's Algorithms repository\n",
"\n",
"A useful GitHub repository is the [Keon repository of algorithms in Python](https://github.com/keon/algorithms). Keon is a GitHub user who has curated implementations of lots of algorithms and it's worth reading through the code in this repository. \n",
"\n",
"One nice thing about it being a GitHub repository is that lots of people can write and submit implemetations of things they've found useful, or have noticed are missing. Tom even contributed one of the implementations a couple of years ago!\n",
"\n",
"[You can see Keon's repository of Python algorithms here.](https://github.com/keon/algorithms)\n",
"\n",
"## Learning more Programming\n",
"\n",
"There are tons of resources to learn more programming skills!\n",
"\n",
"A wonderful tool to begin with --- especially if you are interested in learning web technologies --- is [codeacademy](https://codeacademy.com/). This free website is packed with excellent lessons on a variety of topics, including Python, and it's highly recommended for practice and picking up further Python fundamentals.\n",
"\n",
"Another useful project for practicing Python skills you've picked up at PWSAfrica is [Project Euler](https://projecteuler.net/). This is a repository of problems to solve that are mathematical in nature. Many of you noticed that we took some of our own problems from the list at Project Euler! There are hundreds of problems there of increasing difficulty, so however confident you are in both mathematics and Python --- whether you're still getting to grips or feel you're professional grade --- Project Euler will contain problems that are just challenging enough for you to tackle *today*.\n",
"\n",
"If you'd like to play with other languages, Haskell is a brilliant language for mathematicians who want to write reliable code. However, it comes with a very steep learning curve. [You can read a fantastic free Haskell book which Tom and Ben learned from here.](http://learnyouahaskell.com/) \n",
"\n",
"A language with a smaller learning curve is Clojure. Clojure works alongside Java code, so if you're already a Java developer, this might interest you. It is also very interesting from the perspective of language design. However, Clojure also comes with a steep learning curve. [You can read an excellent Clojure book that Tom recommends here.](https://www.braveclojure.com/)\n",
"\n",
"Note that these languages come with a steep learning curve because they require you to:\n",
"\n",
"* Understand more fundamental aspects of computation than Python does\n",
"* Think harder about problem solving than about the expression of ideas\n",
"* Write programs which don't work at all like the Python programs you already know\n",
"\n",
"*Tom strongly recommends that you become proficient at solving problems in Python before approaching these languages.* However, if you become interested in programming, learning these languages will bring massive advantages in training you how to solve problems, *and* in expressing your solutions to those problems in a way the computer will understand.\n",
"\n",
"## Learning Data Science\n",
"\n",
"A great resource for learning data science is [towardsdatascience.com](https://towardsdatascience.com/). \n",
"\n",
"If you're interested in more hardcore data science, taking and academic perspective, [distill.pub](https://distill.pub/) publishes academic papers which are designed to be as easy to read as possible.\n",
"\n",
"These might be pretty heavy if you're only just getting into data science! If you're curious about the mathematics behind things like AI and ML but don't know where to start, [Data Skeptic](https://dataskeptic.com/podcast/) is a great podcast which gives accessible introductions to an incredible number of topics.\n",
"\n",
"Remember: [codeacademy](https://codeacademy.com/) has lessons on data science, too!\n",
"\n",
"## Constraint Programming\n",
"\n",
"Constraint programming is a technique used when we have certain descriptions of problems, such as criteria that they have to meet, and want to produce a solution or set of solutions which satisfy those criteria. This technique is *very* popular in fields such as operations research.\n",
"\n",
"Constraint Programming don't have a massive Python community, but a good place to start is [the python-constraint library](https://github.com/python-constraint/python-constraint)\n",
"\n",
"## SymPy\n",
"\n",
"SymPy is a library that helps us to perform *Symbolic Computation*. Symbolic computation lets us manipulate equations like you might manipulate data with a regular program --- we figure this might be quite helpful for you!\n",
"\n",
"You can get started writing SymPy code [at this tutorial](http://docs.sympy.org/latest/tutorial/preliminaries.html). There's plenty to learn, but now that you know how to write Python code, we're sure you can work things out! When you get stuck, you can check StackOverflow; we talk about that below."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Our tips & Techniques\n",
"\n",
"We thought it might be helpful to make some notes here of useful Python things, and tips on how professional programmers write code, to help you out when you're teaching yourself.\n",
"\n",
"## Good programmers read as much code as they write\n",
"\n",
"In school, when we want to write an essay, we don't just write and write until we produce something we are happy with. The first step is to *read*! Indeed, the best writers spend lots of their time reading. \n",
"\n",
"Similarly, the best programmers read other people's code. This has a few benefits:\n",
"\n",
"* It helps to inform your own sense of style\n",
"* It trains you in computational thinking, because you have to learn to follow what the code *means* in your head.\n",
"* Sometimes, when you get good at reading code, you spot ways not to do things!\n",
"* You're constantly exposed to new ideas and ways of approaching problems\n",
"* You become more naturally familiar with the language you are working with, *helping you to express your own ideas in that language*.\n",
"\n",
"A good place to begin reading Python code is [Keon's repository of Python algorithms](https://github.com/keon/algorithms).\n",
"\n",
"## Readable code is absolutely essential.\n",
"\n",
"We don't just write our code --- other people have to read it too, and *we* might have to read it if we revisit a project a few months after we've written something. \n",
"\n",
"To make your code readable, remember to give your variable names some names that remind you what the variable is for! \n",
"\n",
"Also, remember to place many comments in your code. These are useful because they can serve as reminders to yourself of why you wrote particular parts of code the way you did; they are also a great way of making your code readable to others, as they explain what's happening *inline* with the code. Markdown cells in a Jupyter notebook are another great way to achieve this!\n",
"\n",
"## Debugging\n",
"\n",
"Pay attention to error messages! They contain useful information: usually they contain a line number and sometimes even an arrow pointing to the *character* in your code the error occurs on. If you pay attention, you'll spot when your error is indentation, or a missing colon at the end of a loop/if statement, and all of these common errors.\n",
"\n",
"Some debugging has to happen when code *runs*, but doesn't give us the right output. If your code isn't giving you the result you expect, the best way to find out what's going on is to try to execute it by hand or in your head. Get some paper and begin writing out th steps the computer will take when it runs your code, and the way it changes the state of your variables. Also, try placing as many print statements in your code as you need. This lets you see what's happening in the machine!\n",
"\n",
"*Hint*: with functional code, you can avoid a lot of errors with state! For this reason, a lot of professional software engineers are beginning to use functional code as much as possible.\n",
"\n",
"## [StackOverflow](https://stackoverflow.com) and Google are your friends\n",
"\n",
"You've seen us fail to solve problems *plenty* of times over the last few weeks, and you've probably heard us say that we don't always know the answer!\n",
"\n",
"The truth is that --- especially in a language like Python --- there are all sorts of things a language can do, and it takes years and years to learn them all. And in that time, the language changes! (Something that tripped Tom up a lot while teaching was that all of his research uses Python 2.7; we taught Python 3.6.)\n",
"\n",
"For example, did you know that Python is a very popular language for writing web servers in? It's also used sometimes in the software that runs banks. Python is also very popular for machine learning and AI. One person can't possible learn all of these fields properly!\n",
"\n",
"So, when we want to solve a problem, many software engineers will google for hints toward solving certain problems. These can be really simple problems, like how to replace characters in a string (Python has a method for this, but it's much easier to google all of the methods you rarely use than to memorise them).\n",
"\n",
"[StackOverflow](https://stackoverflow.com) is a *very* popular site for asking questions about code, or finding answers to the questions other people have asked too!\n",
"\n",
"And if you ever feel silly about googling something you think is simple, remember that [we all do the same](http://imposterroster.com).\n",
"\n",
"## Use GitHub to store your code\n",
"\n",
"As we mentioned earlier: if you're interested in software engineering, GitHub works as a kind of portfolio site, which is helpful when applying for further study or jobs. [You can find GitHub here.](https://github.com)\n",
"\n",
"## Play with Object Orientation\n",
"\n",
"*Object orientation* is a powerful concept used frequently in professional software engineering, which Python comes with excellent built-in support for. \n",
"\n",
"The concept of object orientation is that a variable should refer not just to data, but to the *behaviour* of the data. This is something you've actually already used! For example, when we call `mystring.split()`, the `.split()` function is actually a *\"method\"* called on a string *\"object\"*. \n",
"\n",
"What's especially useful is that we can define our own objects! The type of an object is known as its class. We often say that a variable of a certain class is an *instance* of that class. We can define classes like so:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"class MyClass:\n",
"\n",
" def __init__(self, some_argument):\n",
" print(\"The __init__ function is run every time we make an instance of a class!\")\n",
" self.data = some_argument\n",
"\n",
" # Methods *must* have at least one argument. It will refer to the current instance of our class.\n",
" # Pytohn programmers *always* call this argument \"self\".\n",
" def example_method(self):\n",
" print(\"I'm printing a message to show a method running on an instance of a class.\")\n",
"\n",
" \n",
"\n",
"# Here, we make an instance of our class, by calling the class name. The __init__ function is automatically run.\n",
"# We can see that the __init__ function has been run in this example, because it prints a message for us.\n",
"myInstance = MyClass(\"Arguments can be provided when we make an instance of a class.\")\n",
"\n",
"\n",
"# You can see that methods can be called on our objects, just like we've called methods on strings etc in the past.\n",
"# This method will print a second message.\n",
"myInstance.example_method()\n",
"\n",
"\n",
"# The object is made so that, when we run the __init__ function, \n",
"# we set an *attribute* of the object to the argument we passed in.\n",
"# Because we're accessing data, not a function, we're not calling anything.\n",
"# This means we don't need () brackets at the end when we access an attribute.\n",
"print(myInstance.data) # prints \"Arguments can be provided when we make an instance of a class.\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We encourage you to experiment with writing your own classes, and becoming proficient in object oriented code!\n",
"\n",
"You can begin to learn a little about object orientation in Python [at this documentation](https://python.swaroopch.com/oop.html)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Some example solutions to part 1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## FizzBuzz"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Normal python code:\n",
"def fizzbuzz(n):\n",
" out = []\n",
" for curr in range(1,n+1):\n",
" result = \"\"\n",
" if curr % 3 is 0: result += \"Fizz\"\n",
" if curr % 5 is 0: result += \"Buzz\"\n",
" if result is \"\": result = str(curr)\n",
" out.append(result)\n",
" return out\n",
"\n",
"print(\"Normal imperative function call:\", end=\"\\n\\t\")\n",
"print(fizzbuzz(20))\n",
"print()\n",
"\n",
"\n",
"# Functional-style python code:\n",
"three_rep = lambda n: \"Fizz\" if n%3 is 0 else \"\"\n",
"five_rep = lambda n: \"Buzz\" if n%5 is 0 else \"\"\n",
"fb_representation = lambda n: str(n) if n%3 is not 0 and n%5 is not 0 else three_rep(n) + five_rep(n)\n",
"fizzbuzz_functional = lambda n: list(map(fb_representation, range(1,n+1)))\n",
"\n",
"print(\"Functional implementation call:\", end=\"\\n\\t\")\n",
"print(fizzbuzz_functional(20))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Tic-Tac-Toe\n",
"\n",
"**Solution generously donated by Ify Okoh, with slight modification. *Thanks, Ify!***"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"theBoard = {'1': ' ', '2': ' ', '3': ' ', '4': ' ', '5': ' ', '6': ' ', '7': ' ', '8': ' ', '9': ' '}\n",
"\n",
"def gameBoard(board):\n",
" print(board['1'] + '|' + board['2'] + '|' + board['3'])\n",
" print('-+-+-')\n",
" print(board['4'] + '|' + board['5'] + '|' + board['6'])\n",
" print('-+-+-')\n",
" print(board['7'] + '|' + board['8'] + '|' + board['9'])\n",
" \n",
"def checkWin(board, turn):\n",
" \n",
" position_matches_turn = lambda position: board[position] == turn\n",
" winningCombinations = [['1','2','3'],\n",
" ['4','5','6'],\n",
" ['7','8','9'],\n",
" ['1','4','7'],\n",
" ['2','5','8'],\n",
" ['3','6','9'],\n",
" ['1','5','9'],\n",
" ['3','5','7']]\n",
" \n",
" # If we find at least one combination where all positions match the turn,\n",
" # return true.\n",
" for combo in winningCombinations:\n",
" if all(map(position_matches_turn, combo)):\n",
" return True\n",
" \n",
" # We *only* reach this block of code if we didn't return earlier, meaning that\n",
" # no winning combination matched the turn completely. Therefore, return False.\n",
" return False\n",
"\n",
"turn = \"X\"\n",
"gameWon = False\n",
"for i in range(9):\n",
" print('Player ' + turn + '\\'s Turn')\n",
" move = input()\n",
" theBoard[move] = turn\n",
" gameBoard(theBoard)\n",
" if checkWin(theBoard, turn):\n",
" print('You won! Player ' + turn)\n",
" gameWon = True\n",
" break\n",
" if turn == 'X':\n",
" turn = 'O'\n",
" else:\n",
" turn = 'X'\n",
" \n",
"if not gameWon:\n",
" print(\"Draw!....Try Again\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Collatz, with graph theory"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"memo = {}\n",
"next_in_sequence = lambda n: n//2 if n%2 == 0 else n*3 + 1\n",
"\n",
"def collatz(n): \n",
" # Terminate on 1\n",
" if n == 1:\n",
" return [1]\n",
" \n",
" if n not in memo.keys():\n",
" memo[n] = next_in_sequence(n)\n",
" \n",
" return [n] + collatz(memo[n])\n",
"\n",
"print(collatz(3))\n",
"\n",
"# And, to prove we're building it in this dictionary:\n",
"collatz(6)\n",
"collatz(20)\n",
"print(\"=====\")\n",
"print(memo)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## RPN Calculator"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# We keep all of our allowed operators in a dictionary.\n",
"# The benefit of this approach is that, if we want to support more functions, we just\n",
"# add more entries to the dictionary!\n",
"# We use whatever symbol the user gives as the key in the dictionary, so it's easy to look up.\n",
"# Then, we can use the function in the value to actually perform calculations.\n",
"funcs = {\n",
" \"+\": lambda a, b: a+b,\n",
" \"-\": lambda a, b: a-b,\n",
" \"*\": lambda a, b: a*b,\n",
" \"/\": lambda a, b: a/b\n",
"}\n",
"\n",
"# Get the input, and filter into operators and digits\n",
"uin = input(\"Give me an RPN string! Allowed operators are +,-,*,/\\t\\t\")\n",
"digits = filter(lambda n: n.isdigit(), uin.split(\" \"))\n",
"digits = list(map(int, digits)) # convert the digits to integers for later calculation\n",
"operators = list(filter(lambda o: not o.isdigit(), uin.split(\" \")))\n",
"\n",
"# Loop over the input\n",
"for op in operators:\n",
" \n",
" # Get our data for the calculation\n",
" a, b = digits.pop(), digits.pop()\n",
" \n",
" # Use `a` and `b` as arguments to the function `op` indicates in our dictionary. \n",
" # Add the result to `digits` so we can use it later.\n",
" digits.append(funcs[op](a,b))\n",
"\n",
"print(digits[-1]) # 30"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## ROT13 Encryption\n",
"\n",
"A trick you may have noticed: the function for encryption is *the same* as the function for decryption."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Without ord or chr\n",
"pairs = [['a', 'n'],\n",
" ['b', 'o'],\n",
" ['c', 'p'],\n",
" ['d', 'q'],\n",
" ['e', 'r'],\n",
" ['f', 's'],\n",
" ['g', 't'],\n",
" ['h', 'u'],\n",
" ['i', 'v'],\n",
" ['j', 'w'],\n",
" ['k', 'x'],\n",
" ['l', 'y'],\n",
" ['m', 'z']]\n",
"rotations = {}\n",
"# Build the dictionary from pairs\n",
"for pair in pairs:\n",
" rotations[pair[0]] = pair[1]\n",
" rotations[pair[1]] = pair[0]\n",
"\n",
"def rot13_no_ord_chr(plaintext):\n",
" cyphertext = \"\"\n",
" for char in plaintext:\n",
" upper = char.isupper()\n",
" char = char.lower()\n",
" if char.isalpha():\n",
" char = rotations[char]\n",
" if upper:\n",
" char = char.upper()\n",
" cyphertext += char\n",
" return cyphertext\n",
"\n",
"print(rot13_no_ord_chr('aB c'))\n",
"print(rot13_no_ord_chr(rot13_no_ord_chr('aB c')))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# With ord and chr\n",
"def rot13(text):\n",
" text = list(text)\n",
" for index in range(len(text)):\n",
" if text[index].isalpha():\n",
" if (text[index].islower() and text[index] < 'n') or (text[index].isupper() and text[index] < 'N'):\n",
" text[index] = chr(ord(text[index]) + 13)\n",
" else:\n",
" text[index] = chr(ord(text[index]) - 13)\n",
" \n",
" return ''.join(text)\n",
"\n",
"\n",
"print(rot13('aB c'))\n",
"print(rot13(rot13('aB c')))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## *Advanced:* Markov Chain"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import random\n",
"from time import sleep\n",
"\n",
"my_chain = {\n",
" 'A': {'A': 0.6,\n",
" 'E': 0.4},\n",
" 'E': {'A': 0.7,\n",
" 'E': 0.3}\n",
"}\n",
"\n",
"def __choose_state(state_map):\n",
" choice = random.random()\n",
" probability_reached = 0\n",
" for state, probability in state_map.items():\n",
" probability_reached += probability\n",
" if probability_reached > choice:\n",
" return state\n",
"\n",
"def next_state(chain, current_state):\n",
" next_state_map = chain.get(current_state)\n",
" next_state = __choose_state(next_state_map)\n",
" return next_state\n",
"\n",
"\n",
"# Print a new state every second, for 25 seconds\n",
"state = 'A' # Choose an initial state\n",
"for _ in range(25):\n",
" sleep(1)\n",
" state = next_state(my_chain, state)\n",
" print(state)\n",
"\n",
"print(\"===END===\")"
]
}
],
"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.5"
}
},
"nbformat": 4,
"nbformat_minor": 2
}