{
 "metadata": {
  "name": "solutions-week5-coinflips"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "# Coin flipping!"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "import random\n\ndef flip_a_fair_coin(N):\n    coin = ['H', 'T']\n    \n    record = []\n    for i in range(N):\n        record.append(random.choice(coin))\n        \n    # record is a list of H and T; turn it into a string by using string.join.\n    record = \"\".join(record)\n    return record",
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "flip_a_fair_coin(5)",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 4,
       "text": "'HHTTT'"
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "# count the number of times you see a \"run\" of a given pattern, e.g. HTTHHT, in a given pattern of coinflips\ndef count_runs(run, coinflips):\n    return coinflips.count(run)\n    \nflips = flip_a_fair_coin(10000)\nthe_count = count_runs('HTHHTT', flips)\n\n# expected:\np = 1.0/2**6   # length of the 'HTHHTT' string, above\nexpected_count = p * len(flips)\nprint 'expected', expected_count, '; got:', the_count, '; diff: ', abs(the_count - expected_count)",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "expected 156.25 ; got: 153 ; diff:  3.25\n"
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "## Question A -- where is count_runs broken?\n\nThere are some strings -- hint, including some rather simple ones -- for which count_strings doesn't work properly: that is, the actual counts differ, sometimes dramatically, from the expected counts.  Write down at least two examples 'runs' and develop a simple hypothesis as to what's going on, i.e. why count_runs is broken."
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "# CTB -- the main problem is this: 'count' does not count overlapping runs.\n# so, for example:\nprint count_runs(\"HT\", \"HTHTHTHT\")\n# works fine, but:\n\nprint count_runs(\"HH\", \"HHHH\")\n\n# does not -- there should be THREE pairs of heads in there, but .count is only finding the one at position 0 and the one at position 2.\n# So basically any runs that could contain overlaps don't work.",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "4\n2\n"
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "## Question B -- fix count_runs.\n\nWrite your *own* count_runs -- you can use 'string.find' in a loop, for example -- that works properly.  Verify that it works on the above strings."
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "# There are a couple different ways to do this.  Perhaps the easiest is this:\ndef count_runs2(run, coinflips):\n    the_count = 0\n    for n in range(len(coinflips)):\n        if coinflips[n:n + len(run)] == run:\n            the_count += 1\n    return the_count\n\nprint count_runs2(\"HH\", \"HHHH\")\n",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "3\n"
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "# One important point for everyone -- string.find doesn't work the way you think it does!\ns = \"HH\"\nif s.find(\"HH\"):\n    print 'Found it!'\nelse:\n    print 'Didn\\'t find it...'",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "Didn't find it...\n"
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "# this is because string.find returns -1 when it *doesn't* find the string... and that evaluates to True in an if statement.\n\n# REMEMBER: ALWAYS TEST YOUR CODE WITH SOMETHING SIMPLE TO SEE IF IT'S WORKING!",
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 16
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "",
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}