Skip to content

Instantly share code, notes, and snippets.

@gcr

gcr/Algs-hw-3.ipynb

Last active August 29, 2015 13:56
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save gcr/8938782 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save gcr/8938782 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
Algs-hw-3.ipynb
{
"metadata": {
"name": "Algs hw3"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 1,
"source": [
"Problem 1: Text wrapping"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import random\n",
"words = [random.randint(1,10) for _ in xrange(1000)]"
],
"language": "python",
"outputs": [],
"prompt_number": 1
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"words = np.array(words)"
],
"language": "python",
"outputs": [],
"prompt_number": 24
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def print_solution(lines):\n",
" begin=0\n",
" for line,nwords in enumerate(lines):\n",
" ss = \" \".join(\"x\"*wlen for wlen in words[begin:(begin+nwords)])\n",
" print \"Line %2d\"%line,\": \",ss + (\" \"*(80-len(ss)))+\"|\"\n",
" begin += nwords\n",
"\n",
"def slack(words):\n",
" length = sum(words) + len(words)\n",
" if length>80:\n",
" return infty\n",
" return (80 - length)**2\n",
"\n",
"cache = {} # Cache[nwords] is the cost of laying out nwords\n",
"opt = {} # Opt[nwords] stores how many words per line should be\n",
" # laid out for nwords words\n",
"\n",
"def cost_of_laying_words(nwords):\n",
" # Base case: Line 1\n",
" if nwords <= 0: return 0\n",
"\n",
" # To find out how many words to lay out for line 2, try everything\n",
" # between (0 words) and (as many words as will fit in line 2),\n",
" # then take the one with the min cost.\n",
" if nwords in cache:\n",
" return cache[nwords]\n",
" else:\n",
" costs = [\n",
" (slack(words[(nwords-i):nwords]) + cost_of_laying_words(nwords-i),\n",
" i)\n",
" for i in xrange(1,1+nwords)\n",
" ]\n",
" # print \"To lay out \",nwords,\"words, cost is: \",costs\n",
" best_cost, best_n_words_this_line = min(costs)\n",
" # Store the cost in the cache:\n",
" cache[nwords] = best_cost\n",
" # This solution is equal to the solution of the previous lines\n",
" # plus how many words we chose for this one:\n",
" opt[nwords] = opt.get(nwords-best_n_words_this_line, []) + [best_n_words_this_line]\n",
" return cache[nwords]"
],
"language": "python",
"outputs": [],
"prompt_number": 12
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"cost_of_laying_words(100)"
],
"language": "python",
"outputs": [
{
"output_type": "pyout",
"prompt_number": 14,
"text": [
"407"
]
}
],
"prompt_number": 14
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print_solution(opt[47])"
],
"language": "python",
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Line 0 : xxxx x x xxxxxxx xxxxxxxxx xx xxxxxx xxxxxxxx xxxxx xxxxxxxx xxx xx xx xx xxxxx |\n",
"Line 1 : xxxxx xxxxx xxxx xxxxxxxxxx xxxxxxxx xxxxxxxxxx xxxxxx xxx xxxxxxxxx xxxxxx |\n",
"Line 2 : xxxx xxxx xxxxxx xxx xxx xxxxxxxxx xxxx xxx xxxxxxxx xxxxxxxxxx xxxxxxxxx |\n",
"Line 3 : xxxxxx xx xx xxxxxxxx xxxxxx xxxxxxxx xxxxxxxxx xxxxxxxxxx xxxxxxx xxxxx xxxx |\n"
]
}
],
"prompt_number": 15
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print_solution(opt[48])"
],
"language": "python",
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Line 0 : xxxx x x xxxxxxx xxxxxxxxx xx xxxxxx xxxxxxxx xxxxx xxxxxxxx xxx |\n",
"Line 1 : xx xx xx xxxxx xxxxx xxxxx xxxx xxxxxxxxxx xxxxxxxx xxxxxxxxxx |\n",
"Line 2 : xxxxxx xxx xxxxxxxxx xxxxxx xxxx xxxx xxxxxx xxx xxx xxxxxxxxx |\n",
"Line 3 : xxxx xxx xxxxxxxx xxxxxxxxxx xxxxxxxxx xxxxxx xx xx xxxxxxxx |\n",
"Line 4 : xxxxxx xxxxxxxx xxxxxxxxx xxxxxxxxxx xxxxxxx xxxxx xxxx xx |\n"
]
}
],
"prompt_number": 16
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print_solution(opt[100])"
],
"language": "python",
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Line 0 : xxxx x x xxxxxxx xxxxxxxxx xx xxxxxx xxxxxxxx xxxxx xxxxxxxx xxx xx xx xx |\n",
"Line 1 : xxxxx xxxxx xxxxx xxxx xxxxxxxxxx xxxxxxxx xxxxxxxxxx xxxxxx xxx xxxxxxxxx |\n",
"Line 2 : xxxxxx xxxx xxxx xxxxxx xxx xxx xxxxxxxxx xxxx xxx xxxxxxxx xxxxxxxxxx |\n",
"Line 3 : xxxxxxxxx xxxxxx xx xx xxxxxxxx xxxxxx xxxxxxxx xxxxxxxxx xxxxxxxxxx xxxxxxx |\n",
"Line 4 : xxxxx xxxx xx xxxxxxx xxxxxx xxxxxxx xxxxxxxx xxxxxxxx x xxxxxxxxxx xx xxx |\n",
"Line 5 : xxxxxxxxx xxx xxxxxxxx xxxxxxx xxxxxxxx xxxxxxxxx xxxxxx xxxxxxxx xxxxxxxx |\n",
"Line 6 : x xxxxxx xxx xxxxxxxxxx xxxx xxxx xxxxxxxxxx xxx xx xxxxxxxxx xxxxxx |\n",
"Line 7 : xxxx xxxx xxxxxxxxxx xxxxx xxx xxxxxxxx xx xxxx xxxxxxx xxxxxx xxxxxxxxx |\n",
"Line 8 : xxxxx xxxxx xx xxxxxxxxx x xxxxxxxxxx xxxxxxxx xx xx xxxxxxx xxx xxxxxxxx |\n"
]
}
],
"prompt_number": 17
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"opt"
],
"language": "python",
"outputs": [
{
"output_type": "pyout",
"prompt_number": 18,
"text": [
"{1: [1],\n",
" 2: [2],\n",
" 3: [3],\n",
" 4: [4],\n",
" 5: [5],\n",
" 6: [6],\n",
" 7: [7],\n",
" 8: [8],\n",
" 9: [9],\n",
" 10: [10],\n",
" 11: [11],\n",
" 12: [12],\n",
" 13: [13],\n",
" 14: [14],\n",
" 15: [15],\n",
" 16: [8, 8],\n",
" 17: [8, 9],\n",
" 18: [8, 10],\n",
" 19: [9, 10],\n",
" 20: [10, 10],\n",
" 21: [11, 10],\n",
" 22: [12, 10],\n",
" 23: [13, 10],\n",
" 24: [14, 10],\n",
" 25: [15, 10],\n",
" 26: [9, 10, 7],\n",
" 27: [9, 10, 8],\n",
" 28: [10, 10, 8],\n",
" 29: [10, 10, 9],\n",
" 30: [10, 10, 10],\n",
" 31: [11, 10, 10],\n",
" 32: [11, 10, 11],\n",
" 33: [12, 10, 11],\n",
" 34: [13, 10, 11],\n",
" 35: [14, 10, 11],\n",
" 36: [15, 10, 11],\n",
" 37: [10, 10, 9, 8],\n",
" 38: [10, 10, 9, 9],\n",
" 39: [10, 10, 10, 9],\n",
" 40: [11, 10, 10, 9],\n",
" 41: [11, 10, 11, 9],\n",
" 42: [12, 10, 11, 9],\n",
" 43: [13, 10, 11, 9],\n",
" 44: [14, 10, 11, 9],\n",
" 45: [14, 10, 11, 10],\n",
" 46: [15, 10, 11, 10],\n",
" 47: [15, 10, 11, 11],\n",
" 48: [11, 10, 10, 9, 8],\n",
" 49: [11, 10, 10, 9, 9],\n",
" 50: [11, 10, 11, 9, 9],\n",
" 51: [12, 10, 11, 9, 9],\n",
" 52: [13, 10, 11, 9, 9],\n",
" 53: [13, 10, 11, 9, 10],\n",
" 54: [13, 10, 11, 9, 11],\n",
" 55: [14, 10, 11, 9, 11],\n",
" 56: [14, 10, 11, 10, 11],\n",
" 57: [14, 10, 11, 10, 12],\n",
" 58: [15, 10, 11, 11, 11],\n",
" 59: [15, 10, 11, 11, 12],\n",
" 60: [11, 10, 11, 9, 9, 10],\n",
" 61: [12, 10, 11, 9, 9, 10],\n",
" 62: [13, 10, 11, 9, 9, 10],\n",
" 63: [13, 10, 11, 9, 10, 10],\n",
" 64: [13, 10, 11, 9, 11, 10],\n",
" 65: [14, 10, 11, 9, 11, 10],\n",
" 66: [14, 10, 11, 10, 12, 9],\n",
" 67: [14, 10, 11, 10, 12, 10],\n",
" 68: [15, 10, 11, 11, 11, 10],\n",
" 69: [15, 10, 11, 11, 12, 10],\n",
" 70: [12, 10, 11, 9, 9, 10, 9],\n",
" 71: [13, 10, 11, 9, 9, 10, 9],\n",
" 72: [13, 10, 11, 9, 9, 10, 10],\n",
" 73: [13, 10, 11, 9, 10, 10, 10],\n",
" 74: [13, 10, 11, 9, 10, 10, 11],\n",
" 75: [13, 10, 11, 9, 11, 10, 11],\n",
" 76: [14, 10, 11, 9, 11, 10, 11],\n",
" 77: [14, 10, 11, 10, 12, 9, 11],\n",
" 78: [14, 10, 11, 10, 12, 9, 12],\n",
" 79: [14, 10, 11, 10, 12, 10, 12],\n",
" 80: [15, 10, 11, 11, 12, 10, 11],\n",
" 81: [12, 10, 11, 9, 9, 10, 9, 11],\n",
" 82: [13, 10, 11, 9, 9, 10, 10, 10],\n",
" 83: [13, 10, 11, 9, 10, 10, 10, 10],\n",
" 84: [13, 10, 11, 9, 10, 10, 10, 11],\n",
" 85: [13, 10, 11, 9, 10, 10, 10, 12],\n",
" 86: [13, 10, 11, 9, 10, 10, 11, 12],\n",
" 87: [14, 10, 11, 9, 11, 10, 11, 11],\n",
" 88: [14, 10, 11, 10, 12, 9, 11, 11],\n",
" 89: [14, 10, 11, 10, 12, 9, 12, 11],\n",
" 90: [14, 10, 11, 10, 12, 10, 12, 11],\n",
" 91: [14, 10, 11, 10, 12, 10, 12, 12],\n",
" 92: [15, 10, 11, 11, 12, 10, 11, 12],\n",
" 93: [15, 10, 11, 11, 12, 10, 11, 13],\n",
" 94: [13, 10, 11, 9, 10, 10, 10, 11, 10],\n",
" 95: [13, 10, 11, 9, 10, 10, 10, 12, 10],\n",
" 96: [13, 10, 11, 9, 10, 10, 10, 12, 11],\n",
" 97: [13, 10, 11, 9, 10, 10, 11, 12, 11],\n",
" 98: [14, 10, 11, 9, 11, 10, 11, 11, 11],\n",
" 99: [14, 10, 11, 9, 11, 10, 11, 11, 12],\n",
" 100: [14, 10, 11, 10, 12, 9, 11, 11, 12]}"
]
}
],
"prompt_number": 18
},
{
"cell_type": "heading",
"level": 1,
"source": [
"Iterative solution for Q1"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def cost_words_iter(words):\n",
" cache = {0: 0}\n",
" opt = {}\n",
" for nwords in xrange(1,1+len(words)):\n",
" costs = [\n",
" (slack(words[(nwords-i):nwords]) + cache[nwords-i],\n",
" i)\n",
" for i in xrange(1,1+nwords)\n",
" ]\n",
" # print \"To lay out \",nwords,\"words, cost is: \",costs\n",
" best_cost, best_n_words_this_line = min(costs)\n",
" cache[nwords] = best_cost\n",
" opt[nwords] = opt.get(nwords-best_n_words_this_line, []) + [best_n_words_this_line]\n",
" return opt[len(words)]"
],
"language": "python",
"outputs": [],
"prompt_number": 9
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print_solution(cost_words_iter(words))"
],
"language": "python",
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Line 0 : xxxx x x xxxxxxx xxxxxxxxx xx xxxxxx xxxxxxxx xxxxx xxxxxxxx xxx xx xx xx |\n",
"Line 1 : xxxxx xxxxx xxxxx xxxx xxxxxxxxxx xxxxxxxx xxxxxxxxxx xxxxxx xxx xxxxxxxxx |\n",
"Line 2 : xxxxxx xxxx xxxx xxxxxx xxx xxx xxxxxxxxx xxxx xxx xxxxxxxx xxxxxxxxxx |\n",
"Line 3 : xxxxxxxxx xxxxxx xx xx xxxxxxxx xxxxxx xxxxxxxx xxxxxxxxx xxxxxxxxxx xxxxxxx |\n",
"Line 4 : xxxxx xxxx xx xxxxxxx xxxxxx xxxxxxx xxxxxxxx xxxxxxxx x xxxxxxxxxx xx xxx |\n",
"Line 5 : xxxxxxxxx xxx xxxxxxxx xxxxxxx xxxxxxxx xxxxxxxxx xxxxxx xxxxxxxx xxxxxxxx |\n",
"Line 6 : x xxxxxx xxx xxxxxxxxxx xxxx xxxx xxxxxxxxxx xxx xx xxxxxxxxx xxxxxx xxxx |\n",
"Line 7 : xxxx xxxxxxxxxx xxxxx xxx xxxxxxxx xx xxxx xxxxxxx xxxxxx xxxxxxxxx xxxxx |\n",
"Line 8 : xxxxx xx xxxxxxxxx x xxxxxxxxxx xxxxxxxx xx xx xxxxxxx xxx xxxxxxxx xxxxxxxx |\n",
"Line 9 : xxxxxxxxxx xx x xxxxxxxxxx xxxxxx xxx x xxx x xxxxxxxxx xxxx xxxx xx xxxxxxxx |\n",
"Line 10 : xxxxxxxxxx xxxx x xxxxxxx xxxxxxx xxxxxxxx xxxxx xxxxxxx xxx xxxxxxxxx xx |\n",
"Line 11 : xxxxxxxxx xxxxxxxxx xxxx xxxx xxxxxxx xxxxxxxxxx xxxxxx xxxxxxx xxxxxxx xx |\n",
"Line 12 : xxx xxxx xx xxxxxxxxxx x xxxxx xx x xxxxxxx xxxxxx xxxxxxx xxxx xxxxx xxxxxx |\n",
"Line 13 : xxxxxx xx xxxxxxxxx xxxxxxx xxxxx xxxx xxxx xxxx xxxxxxxxxx xx xxxxxxxx xxx |\n",
"Line 14 : xxxxxx xxxxx xxxxxx xxxxxx xxxxxxx xxxxxxxx xxxx xx xxxxxxxxxx x xxxxxxxxxx |\n",
"Line 15 : xxx xxxxxxxxx xxx xxxx xxxxxx xxxxx xxx x xx xxxxx xxxxxx xxxxxxxxx xxxxxx |\n",
"Line 16 : xxxx x xxxxx xxxxxxxxxx xxxxxxxx xxxxxxx xxxxxxx xxxxxx xxxxxxxxx xx xxxx xx |\n",
"Line 17 : xxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxx xxxxx xxxx xxxxxxxx xxx xxx xx xxxxxx |\n",
"Line 18 : xxxxxx xxx xxxx xxxxxxxx xxxxxx x xxxxxxx xxxx xxxxxxxx xxxxx x x xxxxxxxx |\n",
"Line 19 : xxx xxxxx x xxxxxx xxxxxxxxxx xxxx xxxxxxx x xxxxxxxxx xxxxxxxx xxxxx xxxxxx |\n",
"Line 20 : x xxx x x xxxxxxxx xxxxxxx x xxxxxxxxx xxxxxxxxxx xxx x xxxxx xxxxxxxxx x |\n",
"Line 21 : xxxxxxxxxx xxx xxxxx xxx xxxxxxx xx x xxx xxxx xx xxx xxxxxx xxxxxxxxxx x xxxxx |\n",
"Line 22 : xxxxxxxxx xxxxxxxx xxx xx xxx xxxxxxxxxx xxxx xx xxxxxx xx xxxxxxxx xxxxx |\n",
"Line 23 : xxxxxxx x xxxxx xxxxxxxx xxxxxxxxx xxx xxxxxxx x xxx x xxxxxxxxxx xxxxxxxxxx |\n",
"Line 24 : x xx xxxxxxx xxxxxxxx xxxxxxxxx xxx xxx xxxxxxxxxx x xxxxx xxxxxxxx xxxxxx |\n",
"Line 25 : xxxx xxxxxxxx xxxxxxxx xxxxxxx xxxxx xxx xxxx xxxxx xxx xxxxx xxxxxxxxxx x |\n",
"Line 26 : xxxxxxxxx xxxxxx xxxxxxxx xxxxxxx xxxxxxx xxx xxxx xxxxxxxxx xx xxxxxxxxxx |\n",
"Line 27 : xxxxxxxxx xxxxxxxxx xxx xxxxxxxx xxxx xxxxx xxxxxx xxxxx xx xxx xxxxxxx xxxx |\n",
"Line 28 : x xxxxxxx xxxxxxxxxx xx xxxx x xxxxxxxxxx xxx xxxxxx xxx xx xxxxxxxxxx xxxx |\n",
"Line 29 : x xxxxxxx xxxxxxxx xxxxxx xxxxxxxx xxxxxx xxxxxx xx xxxxx xxxxxxx xxxxxxxxx |\n",
"Line 30 : xxxxxxx xxxxxxx xxxxxxxxx xxxxxx x xxxxx xxx xxxxxxxxxx xxxxxxxxx xxx xx xx |\n",
"Line 31 : xxxx xxxxx x xxx xxxx xxxxxxxxx xxx xxxxxx xxxx xxxx xxxxx x xxx xxxxxxxx |\n",
"Line 32 : xxxxxxxx xxxxxxxx xxxxxx xx xxxxxx xxxxxxx xxxx xx xxxxxx xxxxxxxx xxxxxxxxx |\n",
"Line 33 : xxxxxxxx xxxxx xxxxxxxxxx xxxxxxxx xxxxx xxxxxxxxx x xxxxxxxxxx xxxxx xxxx |\n",
"Line 34 : xxxxxx xxxxxx xxxxx xxxx xxxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxxx xxxxx |\n",
"Line 35 : xxxxxx x xxxxxxxx xxxxxxxxxx xxxx xx xxxxx xx xxxx xxxxxxxxx xxxxxxxxx xxxxx |\n",
"Line 36 : xx xxxxxxxxxx xxxxxxx xxxxxxxxx xxxxxxxxx xxx xx xxxx xxxxx xxxxx xxxxxxxxx xx |\n",
"Line 37 : xxxxxxxxxx xxxxxxx xxxxxxx xxxxxxxx xxx xxxxxxxxx xxxxxxxxxx xxxxxx xx xxxxx |\n",
"Line 38 : xxxxxxxxx xxxx x xxxx xxx xxxxx xxxxxxx xxxxxx xxxxxxxxx xxx xxxxx xxx xxxxx |\n",
"Line 39 : xxxxxxxx xxxxx x xxxxxxx xx xxxxxxxxxx xxxxxxxxxx xxxxxxxxx xxxxx xxx xxxx |\n",
"Line 40 : xxxxxxxxx xxxxxx xxxxxxxxx xxx xxx xxxxxxxxx xxx xxx x xxxxxx xxxxxxxxx xxxxxxx |\n",
"Line 41 : xxxxxxxxxx x x xxxxxx xxxxxxx xxxxxxxx xxxxxx xxxxxxxx xxxxxxx xxxxxxxx xxx x |\n",
"Line 42 : xxxxxxxx xxxxx x x xxxxxxx xxxxxxxx xxxxxxxxxx xx xxxxx xxxxxxxxx xxx x xxx xxx |\n",
"Line 43 : xxx xxxx xxxxx xxx xxx xxxx xxxxxx xxxxxxxxx xxxxxxx xxx xxxxxxxxx xxxxxxxx x |\n",
"Line 44 : xxxxxxx xx xxxxxxxxxx xxxxxxxxx x xxx xxxxxxxxx xxxxxxxx xxx xxx xxxxx xxxxxx |\n",
"Line 45 : x xx xxxxxxxxxx xxx xx xx xxxxxxxxxx xxxxxxx xxx xxxxxxxxx xx xxxxxxxx xxxx |\n",
"Line 46 : xxxxxxx x xxxxxx x xxxxx xxxxxxxx x xxxxxxxx xxxxxxxxx xxxx x xxxxxx xxxx |\n",
"Line 47 : xxxxxxx xxxxx xxxxxxxxx xxxxxxx xxx xxxxx xxxxxxxxxx xxxxxxx xxxxxxx xxx x xx |\n",
"Line 48 : xxxxxxxxx x xxxxxxx xxxxxxxxx xxxxxxxxxx x xxxxx xxxxxxxxx xxxxxxxx xxxxxxxx |\n",
"Line 49 : xxxxxxxx xxxxxxxx xxx xxxxx xxxxxx xxxxxx xx xxxx xxxxxxxxxx xxxxxxxx xxxx xx |\n",
"Line 50 : x xxx xxxxxxx xxx xxxx xxxx xx xxxxxx xx xxxx xxxxxxxxx xxxxxx xx xxxx xxxxx |\n",
"Line 51 : xxxxxxxx xxx xxx x x xxxxxx xxxxxxxx xxx xxxxxx xxxxx xxxxxxx xx xxxxxxxx |\n",
"Line 52 : xxx xxxx xxxxxxxx xxxxxxx xxx xxxxxxxxx xxxxxx xxx xx xxxxxx xxxxxx xx xxxx |\n",
"Line 53 : xxxxxxxxx xx xxxx xxxxxx xxxxxx xxxx xxxxxxxx xxx xx xxxxx xxxxxxxxx xxxxxxx |\n",
"Line 54 : xx xx xxxxxxxxx xxxxxxxxx xx xx xx x xx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xx |\n",
"Line 55 : xx xxxx xxx xxx xxxxxxxxxx xxxxxxxxxx xxxxx xxx xxxxxx xxxxxxxxx xx xxxxxxxxx |\n",
"Line 56 : xxxxxxxx xxx x xxxx xxxxxxxxxx xxxxxxxxx xxxxxxxxx xx xxxxxx x xxxxxx xxxxxxxxx |\n",
"Line 57 : xxxxxx xx xxxxxxxxxx xxxxxxxx xxxxxx xxx x xxxxx xxxxxxx xx x xxxxx xxx xxx |\n",
"Line 58 : x xxxxx xxx xxxxxx xxxxxxxx xxxxxxxxx xxxxxxxxx xxxxx xxxxxxxxx x xxxxx x |\n",
"Line 59 : xxxxxxxxxx xxxxxx xx xxxxxx xxx xxxxxxx xxxxxxx xxxxxx xxx xxx xxxxxxx xxxx |\n",
"Line 60 : xxxxx xxxxxxxxx xxxxxxxx xxxxxxxxx xxxxx xxx xxxxxxxxx xxxxxx xx xxxxxx |\n",
"Line 61 : xxxxxxxx xxx xxxxxxxx xxxx x xxxxxxxxxx xxxxxxxxxx xxxxxxxx xxxxxx xx xxxxxx |\n",
"Line 62 : xxxx xxxxxxxxx xxx xxxxxxxxxx xxxxxxxxx x xxxxxxxxx xxxxx x xxxxxxxxxx xxxxx |\n",
"Line 63 : xxx xxxxx xxxxxx xxxx xxxx xxxxxx xxxxxxxxx xxxxxxx x xxxxx xxx xxxxxxxxxx |\n",
"Line 64 : xxxxxxxxxx xx xxxxxx x xxxxxxxxx xxx xxxxxxxxxx xx x x x xxxx xxxxxxxxx |\n",
"Line 65 : xxxxxxxx xxxxxxx xxxxxxxxx xxxxxxx xxxxxxxxx xxxxxx x x xxxxxxxx xxxx xxx xxxxx |\n",
"Line 66 : xxxxxxxx xxxxxxxxxx xxx xxxxxxx xxx xxxxxxxx xxxxx xxxxxx xxxxx xxxxxxxxxx |\n",
"Line 67 : xxxxx xxxxxxxxxx xxxx xxx xxxxxxxxxx xxxx xxxxx xxxxxxxxx xxxxxxxxxx xxxxxxxx |\n",
"Line 68 : xxxxxx xxxx xxxxxxxxx xxxxx xxxxxxx xxxxxx xx xxxx xx xxxxxxx xxxxxxxx xxx |\n",
"Line 69 : xxxx xxxxxxxxxx xxxxxxxxx xxxxxxxxx x xxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxx |\n",
"Line 70 : xxxxxx xxxxxxxxx xxxxxxxxxx xxx xxxxxxxx xx xxxxxxx xxxxxx xxxx xxxxxxxxxx |\n",
"Line 71 : xxxxxxxx xxxxxxxx xxxxxxxx xx xxxx xxxxxxx x xxxxx x xx xxxxxx xxx x xxxxxxx |\n",
"Line 72 : xxx xxxxx xxxxxxxxxx xxxxxxxx xxxxxxxxx xxxxxxxx x xxxxxxxxx xxxxxxxx x xxxxx |\n",
"Line 73 : xxxxxxxxx xxx xxxxxxx xxxxxxxx xxxxx xxxxxxxxx xxxxxxxxx xxxxxxxx xxxxxxxx |\n",
"Line 74 : xxxxxxx xxxxxx xxxxxx xxxxxx xxxxxxxx xxx xxxxxxxxxx xxxxxx xx xxxxxxxxx xxxxxx |\n",
"Line 75 : x xxxxxxxxx xxxxxxx xxxxxxxxx xxxxxxx xxxxxxxx xxxxxxxxx xxxxxxxxxx xxxxxxx xx |\n",
"Line 76 : xxxxxxx x x xxxxxxxxxx xxxx xxx xxxxxx xxxxxxxxxx xxxx xxxxxxxxx xxx xxxxxxx |\n",
"Line 77 : xxxxxx xxx xxx xxxxxx xx xxxxxx xx xxxxxxxx xxxx xxxxx xxxxx xxxxxx xxxx xxxx |\n",
"Line 78 : xxxxxx xx xxxxxxxx xxxxxxx xxxxxxxx xxxx xxxxxxxxx xxxxx xxxxxxxxx xxxxxxxxxx |\n",
"Line 79 : xxxxxxxxxx xxxxxxxx xxxxxxx xxxxxxx xxxxx xxx x xxxxxxxxx xxxxx x x xxxxxx |\n",
"Line 80 : xxxx xxxxxxxxx xxxxxxx xxxxxxxxx xxxxxxx xxxxxx xxxxxxxxx xx xxxxxx xxxx xx |\n",
"Line 81 : xxxxxxx xxxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxx xxxx |\n",
"Line 82 : xx x xxxxxxxxxx xxxxxxxxx xxx xxxx xxxxxxxxx xxxxx xxxxxxxx xxxxxx xxxxxxxxxx x |\n",
"Line 83 : xxxxxxxx xxxxxxxx xxxxxxxxx xxxxxx xxx xx xxxxxxx xxx xxx xxx xxxx xx xx xxxx |\n",
"Line 84 : xxxxxxxx xxxxxxx xxxxxxxx xxx xxxxx xxxxxxxxxx xxxxxxxxx xxxxxxx xxxxxxxxx |\n"
]
}
],
"prompt_number": 19
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"%timeit cost_words_iter(words)"
],
"language": "python",
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"1 loops, best of 3: 5.42 s per loop\n"
]
}
],
"prompt_number": 25
}
]
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment