Lectures/Week-09-While&sentinelloops.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Spring 2018 Status: UNREVIEWED\n",
    "\n",
    "# What do we mean by loops?\n",
    "\n",
    "Honestly, this is a good question.  There is a lot of language in programming that was created on the fly and: \n",
    "\n",
    "* was never technically correct but understood by the community of practice\n",
    "* once was technically correct but no longer correct with modern systems, but the term is stil used for historical tradition\n",
    "\n",
    "So what do we mean when we use the word loop to describe a structure? It can mean many things!  For example, a for loop in Python repeats a block of code over items in a sequence.  \n",
    "\n",
    "# DEPRECATED While loops\n",
    "\n",
    "When it comes to data processing in python, the while loop is only deployed when the for loop won't cut it.  \n",
    "\n",
    "While loops are the standard way to loop for some languages, but not so much in python.  There are certain tasks, such as interactive programs, where the while loop is almost always what you use.\n",
    "\n",
    "This class is dealing with data, which is usually in files so you know exactly how many times to run.\n",
    "\n",
    "The while loop is valuable in the cases when you don't know how many times you'll need to run through things.\n",
    "\n",
    "Even though this isn't something that you'll use a huge amount, you should still know about it.\n",
    "\n",
    "A for loop goes over all the things and does whatever you want for all of them.  You can read that as \"for each in that thing...\".  Meanwhile, a while loop gets to loop over and over until it's question is answered correctly.  It has one question and will go until tha question comes up as true.\n",
    "\n",
    "As soon as that condition is met, the while loop is done.  This is great for conditions of trying to act as a gatekeeper for crappy user input, or waiting for a command from a user.\n",
    "\n",
    "This is not always a great choice for dealing with data, because we are almost always dealing with a known amount of stuff.\n",
    "\n",
    "The other limitation of the while loop is that you have to do all the legwork.  You can't just tell it to loop over all the things in a file, because that's the purpose of a for loop.  It will keep repeating the question, and it's up to you to traverse what's going on.\n",
    "\n",
    "So counters and other incrementers are required."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "count_sum = 0\n",
    "top = 100\n",
    "step_count = 0\n",
    "\n",
    "# generate random integers between 0 and 10, add them until the sum is greater than 100\n",
    "# report how many times it took to do that\n",
    "while count_sum < 100:\n",
    "    my_num =  random.randint(0, 10)\n",
    "\n",
    "    count_sum += my_num # sum = sum + my_num\n",
    "    step_count += 1 # step_count = step_count + 1\n",
    "    print(count_sum, step_count)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also have this repeat 100 times to see what the average step count is over 100 runs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "# priming all the values\n",
    "count_sum = 0\n",
    "top = 100\n",
    "step_count = 0\n",
    "\n",
    "all_step_counts = []\n",
    "\n",
    "for i in range(100):\n",
    "    while count_sum < 100:\n",
    "        my_num =  random.randint(0, 10)\n",
    "\n",
    "        count_sum += my_num # sum = sum + my_num\n",
    "        step_count += 1 # step_count = step_count + 1\n",
    "#     print(sum, step_count)\n",
    "    all_step_counts.append(step_count)\n",
    "    # reset!\n",
    "    count_sum = 0\n",
    "    step_count = 0\n",
    "\n",
    "print(all_step_counts)\n",
    "print(\"The average number of steps to take is:\", sum(all_step_counts) / len(all_step_counts))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "100 / 5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Do you see that reset process that we had to go through?  We need to reset our counters back to the beginning when we want it to start over.\n",
    "\n",
    "We'll be exploring a similar application of collecting things repeatedly, but then when that collection is done we want to reset our collectors before it continues along further."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# We aren't going to use for loops for the dracula chapter problem\n",
    "\n",
    "You could, but it would suck.  Instead, we can take an approach that is inspired by the while loop.\n",
    "\n",
    "The core problem here is that we need to traverse over the entire document, but the while loop will stop as soon as it finds the thing that it's looking for.  We could use a while loop to find the start of the chapters and the end of the chapters, but we would need a separate while loop for each.  Our problem is that there are 27 things to find, and there are just better ways of doing it.\n",
    "\n",
    "Let's look at a real data example here.\n",
    "\n",
    "So we know that there are states happening in the file, but we don't know how many universities will be listed under each.  We can use a combination of pattern here:\n",
    "\n",
    "* a decision tree to filter the lines we have found into their meaning groups\n",
    "* a main and sub accumalator pattern that you used in the week where you were going over a file and using an accumulaor on each of the lines, and then collecting all of the results in a final accumulator.\n",
    "\n",
    "Let's do the easy stuff first.\n",
    "\n",
    "## pattern 1: filter all the things\n",
    "\n",
    "Taking a look at the file in question, we can see that there are two kinds of lines:\n",
    "\n",
    "* a line talking about a state\n",
    "* a line talking about a university\n",
    "\n",
    "We need to figure out how to detect these differences.  Going back to our previous discussions:\n",
    "\n",
    "1. we could try and detect is only a state name is mentioned in a line\n",
    "2. we could exploit the known and steady sturucture\n",
    "\n",
    "Let's go for item 2 first.\n",
    "\n",
    "* some of the universities have () in the names\n",
    "* some of the universities have footnotes, and therefor end withd [a number]\n",
    "\n",
    "But is this something regular enough to depend on?\n",
    "\n",
    "We can test the () first, and let's print out what that might tell us about the states, since that is the smaller category."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fileio = open('crappystatedata.txt', 'r')\n",
    "\n",
    "text = fileio.read()\n",
    "lines = text.split(\"\\n\")\n",
    "fileio.close()\n",
    "\n",
    "for line in lines:\n",
    "    if '(' in line and ')' in line:\n",
    "        print(\"----\")\n",
    "    else:\n",
    "        print(\"this in a state:\", line)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ouch, we've got some universities in this.  Some of them have the [] in there, so we can add that in next."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fileio = open('crappystatedata.txt', 'r')\n",
    "\n",
    "text = fileio.read()\n",
    "lines = text.split(\"\\n\")\n",
    "fileio.close()\n",
    "\n",
    "for line in lines:\n",
    "    if '(' in line and ')' in line:\n",
    "        print(\"----\")\n",
    "    elif '[' in line and ']' in line:\n",
    "        print(\"----\")\n",
    "    else:\n",
    "        print(\"this in a state:\", line)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That made things worse. We've lost the states completely."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fileio = open('crappystatedata.txt', 'r')\n",
    "\n",
    "text = fileio.read()\n",
    "lines = text.split(\"\\n\")\n",
    "fileio.close()\n",
    "\n",
    "for line in lines:\n",
    "    if '(' in line and ')' in line and '[' in line and ']' in line:\n",
    "        print(\"----\")\n",
    "    else:\n",
    "        print(\"this in a state:\", line)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This also didn't work.\n",
    "\n",
    "Maybe this is time to think about what might be unique about the states. We can eyeball the first few in the file, and we can take a look at the source page this came from to find something.\n",
    "\n",
    "https://en.wikipedia.org/wiki/List_of_college_towns\n",
    "\n",
    "Skimming through the wixipedia page shows us that there appearts to be an edit link next to each state name.  Is this duplitated through the file?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fileio = open('crappystatedata.txt', 'r')\n",
    "\n",
    "text = fileio.read()\n",
    "\n",
    "print(text.count('[edit]'))\n",
    "fileio.close()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So there are 51 results!  Yes, there are 50 states but District of Columbia is counted as a state.  Also you can look at the outline of the page and it shows that there are 51 sections.\n",
    "\n",
    "We might think about now splitting the text on this [edit] text since it does mark the start of a new section. \n",
    "\n",
    "However, when we do that we end up with this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fileio = open('crappystatedata.txt', 'r')\n",
    "\n",
    "text = fileio.read()\n",
    "lines = text.split(\"[edit]\")\n",
    "\n",
    "print(lines[:2])\n",
    "fileio.close()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The state names are now separated from their contents, and the name of the next state is at the end of the previous one's data.\n",
    "\n",
    "So that sucks.\n",
    "\n",
    "Since we can't use split here, we might want to just use a filter.  In this case, we know that [edit] comes at the end. So we can use .endswith to check if that's our line."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fileio = open('crappystatedata.txt', 'r')\n",
    "\n",
    "text = fileio.read()\n",
    "fileio.close()\n",
    "\n",
    "lines = text.split(\"\\n\")\n",
    "\n",
    "states = []\n",
    "\n",
    "for line in lines:\n",
    "    if line.endswith(\"[edit]\"):\n",
    "        print(line)\n",
    "        states.append(line)\n",
    "\n",
    "print(len(states))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There we have it!  We found a filter that correctly identifies our states, without any false positives of false negatives.\n",
    "\n",
    "Now that we can correctly find the markers for a state, we can turn our attention to what we might want to do about that getting the data under it.\n",
    "\n",
    "So we have two kinds of line:\n",
    "\n",
    "1. lines that serve as a marke that a new state is reporting\n",
    "2. lines of data about college towns, that all belong to the state that above it\n",
    "\n",
    "We need to decide what we want to do when we hit a nen state line."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## the main/sub loop pattern\n",
    "\n",
    "Recall our previous pattern that dealt with lines, and you needed to act on those lines with another loop.  For example:\n",
    "\n",
    "``` python\n",
    "for line in file:\n",
    "    loop through stuff in that line\n",
    "    add that collected data to the broader list\n",
    "```\n",
    "\n",
    "Let's consider a final data structure here:\n",
    "\n",
    "\n",
    "``` python\n",
    "[ ['state1', 'city1', 'city2'],\n",
    "  ['state2', 'city3', 'city4'] ]\n",
    "```\n",
    "\n",
    "Our primary accumulator is our outermost list (the outside []).  It serves the purpose of collecting all the secondary accumulators.  \n",
    "\n",
    "## Analogy: making info packets\n",
    "\n",
    "Let's imagine a situation where you are assembling info packets for visiting candidates.  You have a table lined up with all the papers and packets to include.  You go down that table, grabbing one of each and pacing it on the bottom of your current pile.  At the end of the table, you staple all the papers together.  Finally, you put the packet into the box holding all the completed packets.\n",
    "\n",
    "That's a pretty defined accumulator pattern.  You just have to keep grabbing all the papers until there are none left to grab.\n",
    "\n",
    "Our data is a little different.\n",
    "\n",
    "## Analogy: a sandwich maker\n",
    "\n",
    "Say you work at a sub sandwich shop.  A customer comes in and puts in an order.  There are a few standard things to do, but then you get to toppings.  Your job is to keep adding toppings to the sandwhich until they tell you they are done. You don't know how many times you'll add stuff to the sandwich, but you'll know when they say they are done.  Then you package up the sandwich and hand it to the customer.\n",
    "\n",
    "All the customers you have in the day is your primary accumulator, and the secondary accumulators are the single sandwiches that you make.\n",
    "\n",
    "\n",
    "## OK so this still isn't perfect\n",
    "\n",
    "If finding a state line tells us that we need to start collecting a new bunch of data, then we need to decide what to do with the stuff we have previously collected.  Like a customer putting a bunch of shoe requests into you, and by the time you get back to them, they are gone and a new customer has a whole different set of requests.  You're still standing there with a bunch of shoes in your hand.  \n",
    "\n",
    "When you see that new customer, you excuse yourself and put the previous order to the side.  This is more what we are after.  The customer itself does't tell us that we are done, the fact that we see a new customer tells us that the previous order is done.\n",
    "\n",
    "So here's our plan:\n",
    "\n",
    "* loop through the lines\n",
    "* when the line is city (so not a state):\n",
    "    * add that data to the secondary accumulator\n",
    "* what the line is a state:\n",
    "    * add secondary accumulator package to your primary accumulator\n",
    "    * reset the secondary accumulator back to empty\n",
    "    * add the state to that newly empty secondary accumulator\n",
    "    \n",
    "We've sort of seen this before, where we had:\n",
    "\n",
    "```python\n",
    "allstuff = []\n",
    "\n",
    "for line in file:\n",
    "    newthing = []\n",
    "    for something in line:\n",
    "        ...\n",
    "        newthing.append(stuff)\n",
    "    allstuff.append(newthing)\n",
    "```\n",
    "\n",
    "`allstuff` is our primary accumulator and `newthing` is our secondary accumulator.  Because there's a very difinite place where we want to start over, we have `newthing = []` just inside our primary for loop, with the secondary loop adding to it.  This allows it to reset everytime we hit a new group.\n",
    "\n",
    "In our case, we are using a conditional to check when we need to reset things.  That reset process includes adding the currently accrued contents to the primary accumulator, and then setting the secondary accumulator back to empty.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fileio = open('crappystatedata.txt', 'r')\n",
    "\n",
    "text = fileio.read()\n",
    "lines = text.split(\"\\n\")\n",
    "\n",
    "allchunks = []\n",
    "statechunk = []\n",
    "\n",
    "for line in lines:\n",
    "    if line.endswith(\"[edit]\"):\n",
    "        print(\"a new state has begun!\", line)\n",
    "        # add completed state\n",
    "        print(\"beginning the reset process\")\n",
    "        allchunks.append(statechunk)\n",
    "        # reset the chunk\n",
    "        statechunk = [line]\n",
    "    else:\n",
    "        # otherwise, just keep adding things\n",
    "        statechunk.append(line)\n",
    "    allchunks.append(statechunk)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "print(allchunks)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, this doesn't look all bad.  We've got the things that we want, but we've got an empty list out front.  This is because the first thing that our script hits is a state line, which begins the full reset process.  But that isn't what we want to do.  We havn't collected any data yet, so there's nothing to add to the primary accumulator.  In fact, there's nothing to reset because we haven't done anything!\n",
    "\n",
    "So we need to add a little boolean check in here.  We'll set it to ta false to start, but then once we've gone through our first state we can set it to True."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "fileio = open('crappystatedata.txt', 'r')\n",
    "\n",
    "text = fileio.read()\n",
    "lines = text.split(\"\\n\")\n",
    "\n",
    "allchunks = []\n",
    "statechunk = []\n",
    "\n",
    "foundfirst = False\n",
    "\n",
    "for line in lines:\n",
    "    if line.endswith(\"[edit]\") and foundfirst == False:\n",
    "        print(\"This is the first state!\", line)\n",
    "        statechunk.append(line)\n",
    "        foundfirst = True\n",
    "    elif line.endswith(\"[edit]\"):\n",
    "        print(\"a new state has begun!\", line)\n",
    "        # add completed state\n",
    "        allchunks.append(statechunk)\n",
    "        # reset the chunk\n",
    "        statechunk = [line]\n",
    "    else:\n",
    "        statechunk.append(line)\n",
    "    allchunks.append(statechunk)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "allchunks[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fileio = open('crappystatedata.txt', 'r')\n",
    "\n",
    "text = fileio.read()\n",
    "lines = text.split(\"\\n\")\n",
    "\n",
    "allchunks = []\n",
    "statechunk = []\n",
    "\n",
    "foundfirst = False\n",
    "\n",
    "for line in lines[:20]:\n",
    "    print(\"XXX\", line)\n",
    "    if line.endswith(\"[edit]\"):\n",
    "        statechunk = []\n",
    "        statechunk = [line]\n",
    "        allchunks.append(statechunk)\n",
    "        print(\"IF\", allchunks)\n",
    "    else:\n",
    "        statechunk.append(line)\n",
    "        print(\"ELSESTATE\", statechunk)\n",
    "        print(\"ELSE\", allchunks)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = \"\"\"X\n",
    "a\n",
    "b\n",
    "X\n",
    "c\n",
    "d\n",
    "e\n",
    "\"\"\"\n",
    "\n",
    "lines = data.split()\n",
    "\n",
    "chunks = []\n",
    "chunk = []\n",
    "\n",
    "for line in lines:\n",
    "    if line == \"X\":\n",
    "        print(\"before\", id(chunk))\n",
    "        chunk = []\n",
    "        print(\"after\", id(chunk))\n",
    "        chunks.append(chunk) # I'm bleeding now\n",
    "        chunk.append(line)\n",
    "    else:\n",
    "        print(\"adding to\", id(chunk))\n",
    "        chunk.append(line)\n",
    "    print(list(map(id, chunks)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "chunks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = \"\"\"X\n",
    "a\n",
    "b\n",
    "X\n",
    "c\n",
    "d\n",
    "e\n",
    "\"\"\"\n",
    "\n",
    "lines = data.split()\n",
    "\n",
    "chunks = []\n",
    "chunk = []\n",
    "\n",
    "for line in lines:\n",
    "    if line == \"X\":\n",
    "        chunk = []\n",
    "        chunks.append(chunk[:]) # ???\n",
    "        chunk.append(line)\n",
    "    else:\n",
    "        chunk.append(line)\n",
    "        \n",
    "print(chunks)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}