{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution by: [Your Name] [No partners allowed]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Demonstration and Homework: Generating Music\n",
    "### Due by 10am Monday April 1\n",
    "\n",
    "This notebook uses conditional probabilities to generate random sequences of music. This notebook is mostly for demonstration and the code has already been written, but there is a small part at the end that you need to complete yourself for a grade.\n",
    "\n",
    "This notebook should be submitted as a file named `lastname.ipynb`, substituting `lastname` with your last name. \n",
    "\n",
    "**Collaboration:** No collaboration is allowed on this assignment.\n",
    "\n",
    "**Late submissions:** Late assignments will receive 80% of credit up to one day late, and 50% of credit if two days late. Assignments will not be accepted after two days."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sampling from a distribution in Python\n",
    "\n",
    "The function below is similar to the `sample` functions we've used in previous notebooks in class, but extended to more than two outcomes. It takes as input a *dictionary* where the keys are the outcomes and the value associated with each key is the probability of that outcome. A randomly chosen key will be returned as output."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def sample(distribution):\n",
    "    assert round(sum(distribution.values()), 6) == 1.0, 'Not a valid distribution!'\n",
    "    \n",
    "    random_point = random.random()\n",
    "    cumulative_probability = 0\n",
    "    \n",
    "    for outcome in distribution:\n",
    "        cumulative_probability += distribution[outcome]\n",
    "        if random_point < cumulative_probability:\n",
    "            return outcome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can try it in the cell below as a simple example. When you run the function, it will select one of the three colors in the dictionary according to their respective probabilities."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "colors = {}\n",
    "colors['red'] = 0.5\n",
    "colors['green'] = 0.3\n",
    "colors['blue'] = 0.2\n",
    "\n",
    "sample(colors)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Generating MIDI music in Python\n",
    "\n",
    "MIDI is a format for computer-generated music. You can control the pitch, octave, and duration (among other attributes) of notes. Various Python libraries exist for creating and editing MIDI files. \n",
    "\n",
    "We will use a library called [`pyknon`](https://github.com/kroger/pyknon/) which is a relatively small and simple library. You can install this library using `pip` or `conda`. If you are unable to install the library, you will not be penalized (you can still write code to generate notes), you just won't be able to listen to your results.\n",
    "\n",
    "The code below will attempt to install it for you, though if it does not work, you will need to use a different method. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "!{sys.executable} -m pip install pyknon"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This library uses a string representation to define notes. The number after the pitch indicates the duration of the note (half note, quarter note, etc.), which can be additionally lengthened by adding dots after the number. To adjust the octave, add one or more ' or , to increase or decrease the octave from the default, respectively.\n",
    "\n",
    "When you run the code below, it creates a short sequence of notes and writes it to a MIDI file named *output.mid*. The file will be created in whatever directory this notebook is saved in. When you open the file, you can hear the short song."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from pyknon.genmidi import Midi\n",
    "from pyknon.music import NoteSeq\n",
    "\n",
    "notes1 = NoteSeq(\"E8 E4 E4 C8 E4 G2 G2, C4.' G4., E4., A4, B4, Bb8, A4,\")\n",
    "midi = Midi(1, tempo=200)\n",
    "midi.seq_notes(notes1, track=0)\n",
    "midi.write(\"output.mid\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can directly open the MIDI file (with whatever your machine's default program is) by running the cell below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "!open output.mid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Building probabilities of note sequences\n",
    "\n",
    "Different algorithms exist for automatically composing music, usually involving randomness and probabilities. We will use a relatively simple approach called a [Markov model](https://en.wikipedia.org/wiki/Markov_model). This is a probability model where the probability of a note depends on the previous note. In other words, for every pair of notes, we have a *conditional probability* of one note conditioned on the other.\n",
    "\n",
    "Where do these probabilities come from? We can calculate them from an existing sequence of notes. For example, in the sequence in the `pyknon` cell above, E4 is followed by E4 once, followed by C8 once, and followed by G2 once. So the conditional probabilities would be estimated as: $P(E4|E4)=\\frac{1}{3}, P(C8|E4)=\\frac{1}{3}, P(G2|E4)=\\frac{1}{3}$.\n",
    "\n",
    "The function below takes a note sequence (written as a string) as input and calculates the conditional probabilities as they appear in the sequence. It returns a dictionary containing the conditional probabilities. You can then use this dictionary in combination with the `sample` function defined at the start of this notebook to randomly sample notes according to these probabilities.\n",
    "\n",
    "You need to understand the structure of the dictionary used in this code. It is a nested dictionary (dictionary within a dictionary) that has two levels. The keys of the first level indicate the first note, and the keys of the second level indicate the next note. Thus, `cond['E4']['C8']` contains the value of $P(C8|E4)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def calculate_conditional_probabilities(sequence):\n",
    "    sample_space = set()      # set of possible outcomes (notes in the example sequence)\n",
    "    notes = sequence.split()  # split the string sequence into a list of string tokens\n",
    "    for note in notes:\n",
    "        sample_space.add(note)\n",
    "    \n",
    "    # first initialize the dictionaries\n",
    "    cond = {}\n",
    "    denominator = {}\n",
    "    for note1 in sample_space:\n",
    "        cond[note1] = {}\n",
    "        for note2 in sample_space:\n",
    "            cond[note1][note2] = 0.0\n",
    "        denominator[note1] = 0.0\n",
    "    \n",
    "    # count the number of times note1 is followed by note2;\n",
    "    # also count the number of times note1 appears at all (for the denominator)\n",
    "    for i in range(1, len(notes)):\n",
    "        note1 = notes[i-1]   # previous note in list\n",
    "        note2 = notes[i]     # current note in list\n",
    "        \n",
    "        cond[note1][note2] += 1.0\n",
    "        denominator[note1] += 1.0\n",
    "    \n",
    "    # divide each value by the corresponding denominator;\n",
    "    # also add a small value 0.1 to avoid probabilities of zero\n",
    "    for note1 in sample_space:\n",
    "        for note2 in sample_space:\n",
    "            cond[note1][note2] = (cond[note1][note2] + 0.1) / (denominator[note1] + 0.1*len(sample_space))\n",
    "        \n",
    "    return cond"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Practice: generating random note sequences [6 points]\n",
    "\n",
    "The code below produces a randomly generated sequence of 25 notes. It first randomly selects a note to begin the sequence using the `random.choice` function. The remaining 24 notes should be sampled from the conditional probabilities, where each note is sampled according to the probability conditioned on the previous note in the sequence.\n",
    "\n",
    "The code below creates a variable called `new_note` which is currently simply set to the `previous_note`. You should change this line to instead use the `sample` function such that it randomly samples the value of `new_note` from the probability distribution conditioned on the value of `previous_note`.\n",
    "\n",
    "You only need to change the one line, although it is allowable for your solution to add other lines."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "example_sequence = \"E8 E4 E4 C8 E4 G2 G2, C4.' G4., E4., A4, B4, Bb8, A4,\"\n",
    "conditional_distribution = calculate_conditional_probabilities(example_sequence)\n",
    "#print(conditional_distribution)\n",
    "\n",
    "# begin by randomly selecting one of the notes from the sequence\n",
    "starting_note = random.choice(list(conditional_distribution.keys())) \n",
    "output_sequence = [starting_note]   # list of notes that will be randomly selected\n",
    "\n",
    "# populate the list with 25 notes\n",
    "while len(output_sequence) < 25:    \n",
    "    previous_note = output_sequence[-1]\n",
    "    new_note = previous_note               # TODO: change this line!\n",
    "    output_sequence.append(new_note)\n",
    "\n",
    "# use the 'join' function to combine the list of 25 notes into a single string and print it out\n",
    "random_sequence = ' '.join(output_sequence)\n",
    "print(random_sequence)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally (and optionally), you can use the `pyknon` library again to create a MIDI file of your randomly generated sequence, which will allow you to hear your song!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from pyknon.genmidi import Midi\n",
    "from pyknon.music import NoteSeq\n",
    "\n",
    "notes2 = NoteSeq(random_sequence)\n",
    "midi = Midi(1, tempo=200)\n",
    "midi.seq_notes(notes2, track=0)\n",
    "midi.write(\"output2.mid\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "!open output2.mid"
   ]
  },
  {
   "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}