IPython notebook, didn't work in normal repository, seeing if it works as a gist

minimum-block.ipynb

{
 "metadata": {
  "name": "Minimum Block"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Finding the Block with the Smallest Number"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<img src=\"https://encrypted-tbn2.gstatic.com/images?q=tbn:ANd9GcSVUawG9VyEn-JigaWLefMTDteksXsfTMuo-oQqu3dukPTDp9cG\">"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<h2>The Problem</h2>\n",
      "You're given a row of 10 blocks, each with a number printed on the block.  The numbers are arbitrary, but you can imagine that they are generated randomly at the start of problem.  Unfortunately you're mostly blind, so you can only read the numbers of the blocks you are holding.  Since you have two hands, we'll assume you can hold, at most, one block in each hand for a total of two blocks at a time.  Imagine you're getting old, so your brain is not what it used to be -- let's assume you can only remember one number at a time.  This last bit of information may be useful, but is not entirely necessary to come up with a solution.  The end goal of this scenario is to identify (i.e. report) the minimum number that was observed on the blocks. "
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<h2>Your Operations</h2>\n",
      "So what are you able to do in this crazy world?  Your actions are:\n",
      "<ul><li>pick up block (left hand)</li>\n",
      "<li>pick up block (right hand)</li>\n",
      "<li>set a block down anywhere</li>\n",
      "<li>compare the numbers on the blocks (i.e. perform <, >, and = checks)</li>"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<h2>The Solution(s)</h2>\n",
      "<h3>My Solution</h3>\n",
      "<ol><li>Pick up block (left hand)</li>\n",
      "<li>Pick up block (right hand)</li>\n",
      "<li>Compare blocks</li>\n",
      "    <ol>\n",
      "    <li>If right block &gt; left block Then set right block down (discard)</li>\n",
      "    <li>Otherwise, set left block down (discard) and place block from right hand into left </li>\n",
      "    </ol>\n",
      "<li>While there are blocks left, go to Step 2</li>\n",
      "<li>Report the number on the block in the left hand</li>\n",
      "</ol>\n",
      "\n",
      "<h3>Your Solution (Recursion)</h3>\n",
      "<ol><li>Pick up block (left hand)</li>\n",
      "<li>Pick up block (right hand)</li>\n",
      "<li>Compare blocks</li>\n",
      "    <ol><li>If right block &gt; left block Then <ul><li>set right block down (discard)</li><li>set left block down below row from which it was picked</li></ul></li>\n",
      "    <li>Otherwise <ul><li>set left block down (discard)</li><li>set right block down below row from which it was picked</li></ul></li>\n",
      "    </ol>\n",
      "<li>While there is at least 2 blocks in the bottom row, go to Step 1 and pick from bottom row</li>\n",
      "<li>Pick up single block on bottom row</li>\n",
      "<li>Report the number on the only block in your hands</li></ol>\n",
      "\n",
      "There is one caveat to your solution which is that the number of blocks, $n$, needs to be of the form $n = 2^k$ where $k$ is an integer.  In other words, there always needs to be an even number of blocks in the row you're picking from, so with 10 blocks after one recursive step there are 5 blocks left, which won't work.  That's fine though, since 10 is a somewhat arbitrary number anyhow -- we'll look at coding both of these solutions."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<h2>Working with Python</h2>\n",
      "There are really two ways that I would suggest on how to work with Python.  The first way involves making an interactive notebook (which is how I'm generating this document) so you can experiment with Python commands and whatnot, and the other is to run Canopy.  Notebooks are run and edited through the web browser (I'm using Firefox, which is working okay).  To open up the notebook dashboard open Windows Command Prompt and type:"
     ]
    },
    {
     "cell_type": "raw",
     "metadata": {},
     "source": [
      "ipython notebook"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This should open a page that doesn't have much on it.  You should find a button that says 'New Notebook'.  Simply click this button to generate a new notebook in your root directory.  The notebook operates in 'cells', which allow you to execute single statements or groups of statements at a time.  For example, if I want to declare a variable and set it to 42, then print that number I could type the following (as a 'code cell'):"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "x = 42\n",
      "print x"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "42\n"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Once I typed in the Python statements, I hit Shift+Enter to EXECUTE the code.  Notice that any output from the statements will be appended to the cell -- in this case, Python printed the number 42.  IPython notebooks support HTML in the form of 'markdown cells', so you can document your thoughts in the same view with the code, which is really helpful for learning.  For more information about using the notebook check here: http://nbviewer.ipython.org/urls/github.com/ipython/ipython/raw/master/examples/notebooks/Part%25201%2520-%2520Running%2520Code.ipynb.  If you're not comfortable with the notebook interface, the other option is to use Canopy.  Upon launching Canopy, simply open up the Editor and create a new file.  Say I want to create a python file that does the same thing as the notebook example I just gave above.  Simply type in the Python statements into the blank file (the top tile) and save.  Remember to include the file extension '.py' when you save the file.  The bottom window of the Canopy Editor is the <i>shell</i>, which functions much like a code cell in the notebook.  To run your code, simply type the following (replacing <i>file</i> with whatever you named the file):"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "`%run <file.py>`"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "You should see something like"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "`Out [1]: 42`"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "For now, I'll refer you to a somewhat crash course in Python basics to give you a flavor of how we will translate our algorithms into real Python code:\n",
      "<ul><li><a href='https://github.com/profjsb/python-bootcamp/blob/master/Lectures/01_BasicTraining/day_1_basic_training.pdf'>The Basics (PDF)</a></li>\n",
      "<li><a href='http://nbviewer.ipython.org/urls/github.com/profjsb/python-bootcamp/raw/master/DataFiles_and_Notebooks/02_AdvancedDataStructures/data_structures.ipynb'>Data Structures (IPython Notebook! :D)</a></li></ul>"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<h2>Getting Started With Code</h2>\n",
      "At this point, our solutions are merely algorithms -- when we translate an algorithm into usable code it is called an implementation.  There are many ways to implement each of the solutions given above (in addition, of course, to there being many more algorithms).  I'll introduce some tools that may be helpful in implementing our solutions.\n",
      "\n",
      "<h3>Functions</h3>\n",
      "Suppose we would like our implementation to simply be a function that receives some sort of representation of blocks and outputs the smallest number on any of the blocks.  The following syntax is used for defining functions:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def myFunction(arg1):\n",
      "    #do something with arg1\n",
      "    return arg1"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Note the  **`def`**  statement in the first line, which stands for *define*.  It's followed by  **`myFunction`**  which is the name we're going to give to our new function.  The function name is ALWAYS succeeded by parenthesis which contain the arguments or parameters to the function (i.e. inputs).  In this case we have one input to the function called  **`arg1`**, but we could also have more arguments or none.  A function definition is our first example of a Python **code block**.  Notice there is a colon at the end of the function definition line.  This lets Python know that the following lines constitute the function.  Also, statements inside a block are indented (this is done automatically).  Line 2 begins with a  **`#`**  which indicates the line is a *comment*, meaning it is not to be executed, and is only intended for human consumption (usually as part of the documentation explaining the code).  Lastly, notice that the function ends with a  **`return`**  statement which is the function's way of interacting with the outside world -- whatever follows this keyword is output to the caller when the function is finished executing.\n",
      "\n",
      "Our function can be called like this (note we'll have to pass SOMETHING to the function since it is expecting exactly one input)."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "myFunction(5)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "5"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "In this case, our function is not very useful since all it does is output whatever we put into it.\n",
      "\n",
      "<h3>Iteration & Looping</h3>\n",
      "It's often the case that we'll want to repeat various tasks over and over again.  This is also known as iteration, and it can be utilized quite simply in Python:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "cats = ['Henry','Clara','Paul']\n",
      "for cat in cats:\n",
      "    print 'Hello',cat"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Hello Henry\n",
        "Hello Clara\n",
        "Hello Paul\n"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "There is something called a  **`while`**  loop, but for now we'll stick with  **`for`**  loops for iterating over data.  This is another example of a code block -- in this case, the statements inside the code block get executed based on the loop definition (line 1).  For now, think of  **`cats`**  as a collection, or list of 3 `string`s.  In practice, we can put any sort of collection, list, set, or iterable in this position -- basically anything that implements the `__iter()__` method (more on this much later!).  In this case, the variable `cats` is a `list` (denoted by __[__ and __]__ with comma delimited entries).  With this interpretation in mind, what the second line is really saying is ''for each item that is inside of this list do the following...''\n",
      "\n",
      "<h3>Conditional Branching</h3>\n",
      "It's also nice to be able to test conditions and/or make comparisons in order to determine which code to execute next.  At this point, I'll introduce the `Boolean` variable type, which takes on either a `True` or `False` value.  Sometimes functions will return `Boolean` values, other times we can write our own `Boolean` expressions using `==`, `!=`, `>`, `<`, etc.  Note the first operator tests equality, unlike a single `=` which is used for assignment!  The second symbol stands for 'not equal'. Here are some examples:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "5<4"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 8,
       "text": [
        "False"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "x = 5 * 2 / 3.123\n",
      "if x != 1:\n",
      "    print 'The variable is not equal to 1'\n",
      "    print 'x = ', x"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "The variable is not equal to 1\n",
        "x =  3.20204931156\n"
       ]
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<h3>Coding My Solution</h3>\n",
      "Now we can begin translating the physical description of the problem into a Python representation for us to work with.  First off, we can envision the initial row of blocks as a list of numbers so that we can perform calculations on them later on.  In this case since we will be using a `list` and a `for` loop, we don't need to worry about 'discarding' blocks, as it's described in the algorithm given above."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def minimum(blocks):\n",
      "    #initialize left hand to hold the first blocks using the list accessor [ and ]\n",
      "    #lists are indexed starting at zero\n",
      "    left = blocks[0]\n",
      "    for block in blocks[1:]:\n",
      "        # pick up next block\n",
      "        right = block\n",
      "        #check to see which hand has the smaller number\n",
      "        if right > left:\n",
      "            right = None #essentially we're discarding the value by doing this\n",
      "        else:  #if the previous condition does not hold, that means the right number is smaller\n",
      "            left = right  #switch hands (i.e. always keep the smallest number on the left)\n",
      "    #after the for loop has gone through each block, we need to output the minimum value\n",
      "    return left\n",
      "        "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 17
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This is what our function looks like without all the comments!"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def minimum(blocks):\n",
      "    left = blocks[0]\n",
      "    for block in blocks[1:]:\n",
      "        right = block\n",
      "        if right > left:\n",
      "            right = None\n",
      "        else:\n",
      "            left = right\n",
      "    return left"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 18
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The initial problem statement said to assume there are 10 blocks in a row, but in reality we would like our function to be a little more robust.  Basically we should be able to handle any (reasonable) number of blocks.  So let's come up with a little test scenario to see if the function does what it was designed to do."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "testBlocks = [3, 9, 4, 75, 1, 8]\n",
      "minimum(testBlocks)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 19,
       "text": [
        "1"
       ]
      }
     ],
     "prompt_number": 19
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This is actually what we wanted, since out of the list of blocks in `testBlocks` the smallest was indeed 1."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}