{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"\"\"\"\n",
"Notated in half-steps\n",
"\"\"\"\n",
"d_partials = [0, 12, 7, 5, 3, 2]\n",
"partials = [10, 22, 29, 34, 37, 39]\n",
"\n",
"\"\"\"\n",
"It's all flats because I'm a brassist and I don't hate myself\n",
"\"\"\"\n",
"notes = {10: 'Bb', 11: 'B', 0: 'C', 1: 'Db', 2: 'D', 3: 'Eb', 4: 'E', 5: 'F', 6: 'Gb', 7: 'G', 8: 'Ab', 9: 'A'}\n",
"\n",
"def note_name(note_num):\n",
" \"\"\"\n",
" Return the note in scientific note notation (note name and octave number)\n",
" \"\"\"\n",
" return notes[note_num % 12] + str(note_num // 12 + 1)\n",
"\n",
"assert(note_name(10) == 'Bb1')\n",
"assert(note_name(22) == 'Bb2')\n",
"assert(note_name(23) == 'B2')"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def note_at(partial, position, trigger=False):\n",
" \"\"\"\n",
" On trombone, the note played is the base note of the partial reduced by some number\n",
" of half steps proportional to how far out the slide is. When the slide is all the\n",
" way in, this is \"first position\" (it is 1-indexed)\n",
" \"\"\"\n",
" return partials[partial] - (position - 1) - (5 if trigger else 0)\n",
"\n",
"assert(note_name(note_at(0, 1)) == 'Bb1')\n",
"assert(note_name(note_at(1, 3)) == 'Ab2')\n",
"assert(note_name(note_at(2, 1, True)) == 'C3')"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Ab1\n",
"\tPosition(partial=0, position=3, trigger=False)\n",
"E1\n",
"\tPosition(partial=0, position=2, trigger=True)\n",
"Ab2\n",
"\tPosition(partial=1, position=3, trigger=False)\n",
"\tPosition(partial=2, position=5, trigger=True)\n",
"D2\n",
"\tPosition(partial=1, position=4, trigger=True)\n",
"D4\n",
"\tPosition(partial=5, position=2, trigger=False)\n",
"Eb1\n",
"\tPosition(partial=0, position=3, trigger=True)\n",
"Bb1\n",
"\tPosition(partial=0, position=1, trigger=False)\n",
"C2\n",
"\tPosition(partial=1, position=6, trigger=True)\n",
"B2\n",
"\tPosition(partial=2, position=2, trigger=True)\n",
"Gb1\n",
"\tPosition(partial=0, position=5, trigger=False)\n",
"Bb2\n",
"\tPosition(partial=1, position=1, trigger=False)\n",
"\tPosition(partial=2, position=3, trigger=True)\n",
"C4\n",
"\tPosition(partial=4, position=2, trigger=False)\n",
"\tPosition(partial=5, position=4, trigger=False)\n",
"C3\n",
"\tPosition(partial=2, position=1, trigger=True)\n",
"\tPosition(partial=2, position=6, trigger=False)\n",
"\tPosition(partial=3, position=6, trigger=True)\n",
"A3\n",
"\tPosition(partial=3, position=2, trigger=False)\n",
"\tPosition(partial=4, position=5, trigger=False)\n",
"\tPosition(partial=5, position=2, trigger=True)\n",
"F1\n",
"\tPosition(partial=0, position=1, trigger=True)\n",
"\tPosition(partial=0, position=6, trigger=False)\n",
"F3\n",
"\tPosition(partial=2, position=1, trigger=False)\n",
"\tPosition(partial=3, position=1, trigger=True)\n",
"\tPosition(partial=3, position=6, trigger=False)\n",
"\tPosition(partial=4, position=4, trigger=True)\n",
"\tPosition(partial=5, position=6, trigger=True)\n",
"Db2\n",
"\tPosition(partial=1, position=5, trigger=True)\n",
"Gb2\n",
"\tPosition(partial=1, position=5, trigger=False)\n",
"Db1\n",
"\tPosition(partial=0, position=5, trigger=True)\n",
"Bb3\n",
"\tPosition(partial=3, position=1, trigger=False)\n",
"\tPosition(partial=4, position=4, trigger=False)\n",
"\tPosition(partial=5, position=1, trigger=True)\n",
"\tPosition(partial=5, position=6, trigger=False)\n",
"Db3\n",
"\tPosition(partial=2, position=5, trigger=False)\n",
"\tPosition(partial=3, position=5, trigger=True)\n",
"D3\n",
"\tPosition(partial=2, position=4, trigger=False)\n",
"\tPosition(partial=3, position=4, trigger=True)\n",
"Ab3\n",
"\tPosition(partial=3, position=3, trigger=False)\n",
"\tPosition(partial=4, position=1, trigger=True)\n",
"\tPosition(partial=4, position=6, trigger=False)\n",
"\tPosition(partial=5, position=3, trigger=True)\n",
"F2\n",
"\tPosition(partial=1, position=1, trigger=True)\n",
"\tPosition(partial=1, position=6, trigger=False)\n",
"Eb2\n",
"\tPosition(partial=1, position=3, trigger=True)\n",
"Eb3\n",
"\tPosition(partial=2, position=3, trigger=False)\n",
"\tPosition(partial=3, position=3, trigger=True)\n",
"\tPosition(partial=4, position=6, trigger=True)\n",
"E2\n",
"\tPosition(partial=1, position=2, trigger=True)\n",
"Eb4\n",
"\tPosition(partial=5, position=1, trigger=False)\n",
"C1\n",
"\tPosition(partial=0, position=6, trigger=True)\n",
"A1\n",
"\tPosition(partial=0, position=2, trigger=False)\n",
"E3\n",
"\tPosition(partial=2, position=2, trigger=False)\n",
"\tPosition(partial=3, position=2, trigger=True)\n",
"\tPosition(partial=4, position=5, trigger=True)\n",
"A2\n",
"\tPosition(partial=1, position=2, trigger=False)\n",
"\tPosition(partial=2, position=4, trigger=True)\n",
"Db4\n",
"\tPosition(partial=4, position=1, trigger=False)\n",
"\tPosition(partial=5, position=3, trigger=False)\n",
"G3\n",
"\tPosition(partial=3, position=4, trigger=False)\n",
"\tPosition(partial=4, position=2, trigger=True)\n",
"\tPosition(partial=5, position=4, trigger=True)\n",
"B3\n",
"\tPosition(partial=4, position=3, trigger=False)\n",
"\tPosition(partial=5, position=5, trigger=False)\n",
"Gb3\n",
"\tPosition(partial=3, position=5, trigger=False)\n",
"\tPosition(partial=4, position=3, trigger=True)\n",
"\tPosition(partial=5, position=5, trigger=True)\n",
"G2\n",
"\tPosition(partial=1, position=4, trigger=False)\n",
"\tPosition(partial=2, position=6, trigger=True)\n",
"D1\n",
"\tPosition(partial=0, position=4, trigger=True)\n",
"G1\n",
"\tPosition(partial=0, position=4, trigger=False)\n"
]
}
],
"source": [
"\"\"\"\n",
"Now we need to build the reverse map of this note_at function\n",
"\"\"\"\n",
"\n",
"from collections import defaultdict, namedtuple\n",
"\n",
"positions = defaultdict(lambda: [])\n",
"Position = namedtuple('Position', ['partial', 'position', 'trigger'])\n",
"\n",
"for partial in range(len(partials)):\n",
" for position in range(1, 7):\n",
" for trigger in [True, False]:\n",
" positions[note_name(note_at(partial, position, trigger))].append(\n",
" Position(partial, position, trigger))\n",
"\n",
"positions = {partial: sorted(choices) for partial, choices in positions.items()}\n",
" \n",
"for k, v in positions.items():\n",
" print(k)\n",
" for k in v:\n",
" print('\\t' + str(k))"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"test_sequence = ['C3', 'D3', 'F3', 'G3']\n",
"\n",
"def gen_sequence_stupid(notes):\n",
" \"\"\"\n",
" Use a stupid algorithm to map a sequence of notes into a sequence of positions\n",
" \"\"\"\n",
" return [positions[note][0] for note in notes]\n",
"\n",
"assert(gen_sequence_stupid(test_sequence) ==\n",
" [Position(2, 1, True), Position(2, 4, False), Position(2, 1, False), Position(3, 4, False)])\n",
"\n",
"def position_distance(a, b):\n",
" \"\"\"\n",
" Determine the cost to move from position |a| to position |b|\n",
" \"\"\"\n",
" return abs(a.position - b.position) + (0.5 if a.trigger != b.trigger else 0.0)\n",
"\n",
"def score_sequence(seq):\n",
" score = 0\n",
" for i in range(len(seq) - 1):\n",
" l, r = seq[i], seq[i + 1]\n",
" score += position_distance(l, r)\n",
" return score\n",
"\n",
"assert(score_sequence(gen_sequence_stupid(test_sequence)) == 9.5)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def gen_sequence_greedy(notes):\n",
" \"\"\"\n",
" Use a next-closest-position greedy algorithm\n",
" \"\"\"\n",
" ret = [positions[notes[0]][0]]\n",
" last = positions[notes[0]][0]\n",
" for note in notes[1:]:\n",
" minimizer = positions[note][0]\n",
" minimum = position_distance(minimizer, last)\n",
" for pos in positions[note]:\n",
" if position_distance(pos, last) < minimum:\n",
" minimum = position_distance(pos, last)\n",
" minimizer = pos\n",
" ret.append(minimizer)\n",
" last = minimizer\n",
" return ret\n",
"\n",
"assert(gen_sequence_greedy(test_sequence) ==\n",
" [Position(2, 1, True), Position(3, 4, True), Position(4, 4, True), Position(5, 4, True)])"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"\"\"\"\n",
"Brief interlude into graph land\n",
"\"\"\"\n",
"class Graph(object):\n",
" '''\n",
" This is an immutable graph. Attempts to modify this graph will result in\n",
" returning a new graph\n",
" '''\n",
" def __init__(self, lines=None):\n",
" self.lines = lines or {}\n",
" \n",
" def get_neighbors(self, node):\n",
" '''Get all the neighbors of the given node and the cost to get there'''\n",
" ret = {}\n",
" for pair, cost in self.lines.items():\n",
" if pair[0] == node:\n",
" ret[pair[1]] = cost\n",
" elif pair[1] == node:\n",
" ret[pair[0]] = cost\n",
" return ret\n",
" \n",
" def add_line(self, a, b, cost):\n",
" '''Add a connection to the graph and return the new graph'''\n",
" new_lines = dict(self.lines)\n",
" new_lines[tuple(sorted([a, b]))] = cost\n",
" return Graph(new_lines)\n",
" \n",
" def get_nodes(self):\n",
" ret = set()\n",
" for nodea, nodeb in self.lines.keys():\n",
" ret.add(nodea)\n",
" ret.add(nodeb)\n",
" return ret\n",
" \n",
" def get_neighbors(self, node):\n",
" neighbors = set()\n",
" for nodea, nodeb in self.lines.keys():\n",
" if nodea == node:\n",
" neighbors.add(nodeb)\n",
" return neighbors\n",
" \n",
" def get_edges(self):\n",
" return dict(self.lines)\n",
" \n",
" def get_cost(self, a, b):\n",
" return self.lines[tuple(sorted([a, b]))]\n",
" \n",
" def __str__(self):\n",
" ret = \"\"\n",
" for path, cost in self.lines.items():\n",
" ret += (\"From %s to %s: %d\\n\" % (path[0], path[1], cost))\n",
" return ret"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[(1, Position(partial=3, position=6, trigger=True)), (2, Position(partial=3, position=4, trigger=True)), (3, Position(partial=4, position=4, trigger=True)), (4, Position(partial=5, position=4, trigger=True))]\n"
]
}
],
"source": [
"\"\"\"\n",
"Turn this trombone pathfinding problem into a graph and solve using something resembling bellman ford\n",
"\"\"\"\n",
"\n",
"def create_sequence_graph(notes):\n",
" '''Map this sequence of notes into a one-directional graph'''\n",
" graph = Graph()\n",
" source_nodes = [(0, \"start\")]\n",
" dest_nodes = []\n",
" level = 1\n",
" for note in notes:\n",
" dest_nodes = [(level, pos) for pos in positions[note]]\n",
" for src in source_nodes:\n",
" for dst in dest_nodes:\n",
" if src == (0, \"start\"):\n",
" cost = 0\n",
" else:\n",
" cost = position_distance(src[1], dst[1])\n",
" graph = graph.add_line(src, dst, cost)\n",
" level += 1\n",
" source_nodes = dest_nodes\n",
" \n",
" for src in source_nodes:\n",
" graph = graph.add_line(src, (level, \"end\"), 0)\n",
" \n",
" return graph\n",
"\n",
"def solve_bellman_ford(source, dest, graph):\n",
" \"\"\"I strongly disagree with my textbook on this one\"\"\"\n",
" best = {source: 0}\n",
" predecessor = {}\n",
" to_visit = set([(0, \"start\")])\n",
" while len(to_visit) > 0:\n",
" this = to_visit.pop()\n",
" for neighbor in graph.get_neighbors(this):\n",
" this_cost = best[this] + graph.get_cost(this, neighbor)\n",
" if neighbor not in best or this_cost < best[neighbor]:\n",
" predecessor[neighbor] = this\n",
" best[neighbor] = this_cost\n",
" to_visit.add(neighbor)\n",
" \n",
" ret = []\n",
" i = dest\n",
" while i != source and len(ret) < 10:\n",
" ret = [i] + ret\n",
" i = predecessor[i]\n",
" ret = [i] + ret\n",
" return ret\n",
"\n",
"def gen_sequence_dijkstra(notes):\n",
" \"\"\"\n",
" use Dijkstra's pathfinding algorithm to find an optimal path through the position-graph\n",
" \"\"\"\n",
" graph = create_sequence_graph(notes)\n",
" source = (0, \"start\")\n",
" dest = (len(notes) + 1, \"end\")\n",
" path = solve_bellman_ford(source, dest, graph)[1:-1]\n",
" print(path)\n",
" \n",
"gen_sequence_dijkstra(test_sequence)"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"\"\"\"\n",
"Let's draw these graphs to help explain what just happened there\n",
"\"\"\"\n",
"import graphviz as gv\n",
"\n",
"def convert_mygraph_to_dvgraph(mygraph):\n",
" g = gv.Digraph(format='svg')\n",
" \n",
" nodes = mygraph.get_nodes()\n",
" for node in nodes:\n",
" g.node(str(node))\n",
" \n",
" edges = mygraph.get_edges()\n",
" for edges, cost in edges.items():\n",
" a, b = edges\n",
" g.edge(str(a), str(b))\n",
" \n",
" return g\n",
"\n",
"convert_mygraph_to_dvgraph(create_sequence_graph(test_sequence))\n",
"\n",
"\"\"\"\n",
"Per the diagram below, the sequence of notes and ways to play each note were transformed into a digraph. Each\n",
"layer represents all the possible ways to play the nth note of the sequence. All nodes in layer n connect to\n",
"all nodes in layer n+1. At the beginning and end are cap nodes that serve as source and destination for\n",
"bellman ford. The edge cost is the distance between the two connected positions. \n",
"\"\"\""
]
}
],
"metadata": {
"anaconda-cloud": {},
"kernelspec": {
"display_name": "Python [conda root]",
"language": "python",
"name": "conda-root-py"
},
"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.2"
}
},
"nbformat": 4,
"nbformat_minor": 1
}