In [2]:
## RUN THIS CELL FIRST!
%load_ext autoreload
%autoreload 2
from utils.tick import tick
from utils.test_utils import should_pass, should_fail
from utils.test_utils import reset_tracking, track, verify_track
from utils.complexity import time_complexity
from IPython.core.debugger import set_trace
print("All loaded OK")
In [24]:
# Solution goes here
def test_list(l):
assert(len(l) != 0)
assert(all(isinstance(s, str) for s in l))
assert(all(s.strip() for s in l))
assert(all(s.isalpha() and s == s.lower() for s in l))
assert(len(l) == len(set(l)))
assert(len(l) % 2 == 0)
In [25]:
## Tests
with tick():
should_fail(test_list, [])
should_fail(test_list, [""])
should_fail(test_list, ["a"])
should_fail(test_list, [1, "a"])
should_fail(test_list, [1, 2])
should_fail(test_list, ["a", "b", "c"])
should_fail(test_list, ["alpha", ""])
should_fail(test_list, ["a", "b", "c", "a"])
should_fail(test_list, ["a", "a"])
should_fail(test_list, ["a", "b", "3", "."])
should_fail(test_list, ["A", "B", "C", "D"])
should_fail(test_list, ["alpha", "Bravo", "charlIe", "delta"])
should_fail(test_list, ["a", "b", "c", ""])
with tick():
should_pass(test_list, ["a", "b"])
should_pass(test_list, ["alpha", "bravo"])
should_pass(test_list, ["alpha", "bravo", "charlie", "d"])
should_pass(test_list, ["ale", "base", "cheap", "liqour"])
should_pass(test_list, ["ale", "base", "cheap", "liqour", "twenty", "thirty"])
The function below runs in constant time -- it doesn't depend on the value of n and takes the same each time it is called regardless. The time_complexity() call shows this as a graph, and gives scores, which should show the time complexity is most likely to be constant (it will have the highest score printed).
In [30]:
def constant_time(n):
i = n
return i
# number=30: run the function 30 times and average the result
# ns= range(1, 1000, 50): set n to values from 1 to 1000, stepping by 50 each time
# reps=50: repeat the whole experiment 50 times
time_complexity(constant_time, ns=range(5, 1000, 50), number=30, reps=50);
Task Using nested loops write functions which take a parameter n and do computations which will run in:
linear_time(n) which runs in O(N) linear timequadratic_time(n) which runs in O(N^2) quadratic timecubic_time(n) which runs in O(N^3) cubic timePlot graphs for each, using time_complexity. Use number=20, ns=range(5, 100, 5), reps=15
In [41]:
def linear_time(n):
x = 0
for i in range(n):
x += n
return x
def quadratic_time(n):
x = 0
for i in range(n):
for j in range(n):
x += n
return x
def cubic_time(n):
x = 0
for i in range(n):
for j in range(n):
for k in range(n):
x += n
return x
In [42]:
## Tests
with tick():
_, _, scores = time_complexity(linear_time, ns=range(5, 100, 3), number=5, plot=False, reps=40);
assert scores["linear"]>0.2
with tick():
_, _, scores = time_complexity(quadratic_time, ns=range(5, 100, 3), number=5, plot=False, reps=40);
assert scores["quadratic"]>0.5
with tick():
_, _, scores = time_complexity(cubic_time, ns=range(5, 100, 3), number=5, plot=False, reps=40);
assert scores["cubic"]>0.5
In [3]:
# Solution goes here
import random
def nlogn_function(n):
items = [random.randint(0, 100) for i in range(n)]
return sorted(items)
time_complexity(nlogn_function, ns=range(5, 1000, 50), number=30, reps=50);
Many people find it hard to visualise what is going on in recursion. Use the principles of logging to add print statements that make a trace of what happens when the recursive function below is called.
Try and print out the results nicely; you might want to add additional parameters to the function to make logging nicer.
In [4]:
## This function returns the ordered permutations of a sequence
def permutations(l, perm=[]):
if len(l) == 0:
return [perm]
results = []
for i in range(len(l)):
results += permutations(l[:i] + l[i+1:], perm + [l[i]])
return results
permutations("abc")
Out[4]:
In [12]:
# Solution goes here
def permutations(l, perm=[]):
print()
print("----- START -----")
print("Permuting: {}".format(l))
if len(l) == 0:
print("Returning permutation {}".format([perm]))
return [perm]
results = []
for i in range(len(l)):
results += permutations(l[:i] + l[i+1:], perm + [l[i]])
print("Results: {}".format(results))
print("----- END -----")
print()
return results
permutations("abc")
Out[12]:
The code below is supposed to do something with colours. The hexify_colour function doesn't work and you don't know exactly what the code is supposed to do. It was written by a junior developer and has a lot of issues, even though it looks basically correct.
But you do have tests which check what the results should be. Using these tests:
In [47]:
def hexify_color(r,g=None,b=None):
if (g is None and b is not None) or (g is not None and b is None):
raise Exception()
if r < 0.0:
r = 0.0
elif r > 1.0:
r = 1.0
if g is None or b is None:
g = r
b = r
elif g < 0.0:
g = 0.0
elif g > 1.0:
g = 1.0
if b < 0.0:
b = 0.0
elif b > 1.0:
b = 1.0
r_int = int(r*255)
g_int = int(g*255)
b_int = int(b*255)
return "#{r:02x}{g:02x}{b:02x}".format(r=r_int, g=g_int, b=b_int)
print(hexify_color(-1.0, 0.0, 1.0))
In [48]:
## Tests
with tick():
assert hexify_color(0.0, 0.0, 0.0) == '#000000'
assert hexify_color(0.5, 0.5, 0.5) == '#7f7f7f'
assert hexify_color(1.0, 1.0, 1.0) == '#ffffff'
assert hexify_color(1.0, 0.0, 0.0) == '#ff0000'
assert hexify_color(0.0, 1.0, 0.0) == '#00ff00'
assert hexify_color(0.0, 0.0, 1.0) == '#0000ff'
assert hexify_color(1.0) == '#ffffff'
assert hexify_color(0.0) == '#000000'
assert hexify_color(-1.0, 0.0, 1.0) == '#0000ff'
assert hexify_color(-1.0, 0.0, 10.0) == '#0000ff'
assert hexify_color(10.0, 10.0, 10.0) == '#ffffff'
assert hexify_color(-1.0) == '#000000'
assert hexify_color(0.5) == '#7f7f7f'
should_fail(hexify_color, 0.5, 0.5)
should_fail(hexify_color, 0.5, 0.5)
In [12]:
# Solution goes here
The code below is a solution to Lab 3, A.4. Practice tracing through this code using the ipdb debugger. You should watch the video tutorial on ipdb (Week 7's video) before attempting this part.
Here's a quick reference to ipdb commands:
The ipdb debugger can either take single letter commands or the full text.
s step execute the next line, and enter any function that is calledn next execute the next line, and skip over any function that is calledc continue resume running until the next breakpoint is hitr run restart the programl list print out the code corresponding to the current execution pointu/d up/down in the call stackp print print out a value (e.g. p my_list to print out the current value of my_list)a args print out the arguments that were used in the call to the current functionq quit YOU MUST QUIT THE DEBUGGER BEFORE ANY OTHER CODE WILL RUN!b breakpoint b 20)You can pre-insert breakpoints where the debugger will stop and wait for input by writing set_trace() in the code.
Before you start: Click on the cell, and press ESC-L to enable line numbers
Add a breakpoint using set_trace() at the very start of all_rotates
ipdb will start.help at any time to get a list of commands inside the debuggerall_rotateslist to see where you are in the coderotate() in the first iterationup to see where the call to rotate came fromdown to go back into rotatenext)for looprotates is what you expectquit
In [86]:
def rotate(s):
rotated = s[1:] + s[0]
return rotated
def all_rotates(s):
set_trace()
rotates = []
for i in range(len(s)):
rotates.append(s)
s = rotate(s)
for rotated in rotates:
print(rotated)
all_rotates("steel")
In [ ]:
# Solution goes here
The code below is supposed to take a string then convert it to Morse code. It does this by reading a file containing a Morse code table. There are several bugs, but there are logging messages provided to help you understand what is going on. Use the log messages which are generated to work out what the problems are with this code is and fix the code so it works as described above, and passes the tests. Do not use the debugger, or add additional logging statements to the code.
In [70]:
def read_table(fname):
morse_table = {}
for letter in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
morse_table[letter] = ""
print("{n} blank entries in the Morse table".format(n=len(morse_table)))
fname = "morse.txt"
print("Reading morse table from file '{fname}'".format(fname=fname))
with open(fname) as f:
for line in f:
letter, code = line.split(" ")
morse_table = {letter: code}
print("Mapping {letter} to {code}".format(letter=letter, code=code))
print("{n} entries in Morse table after loading".format(n=len(morse_table)))
print()
return morse_table
def convert_to_morse(s):
print()
morse_table = read_table("data/morse.txt")
output = []
for ch in s:
upper_ch = ch.upper()
if upper_ch in morse_table:
print("Converting {ch} to {code}".format(ch=ch, code=morse_table[upper_ch]))
output.append(morse_table[ch.upper()])
else:
output.append(" ")
output.append(" ")
result = " ".join(output)
print("Conversion result is {result}".format(result=result))
return result
In [84]:
# Solution goes here
def read_table(fname):
morse_table = {}
for letter in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
morse_table[letter] = ""
print("{n} blank entries in the Morse table".format(n=len(morse_table)))
fname = "data/morse.txt"
print("Reading morse table from file '{fname}'".format(fname=fname))
with open(fname) as f:
for line in f:
letter, code = line.strip().split(" ")
morse_table[letter.upper()] = code
print("Mapping {letter} to {code}".format(letter=letter.upper(), code=code))
print("{n} entries in Morse table after loading".format(n=len(morse_table)))
print()
return morse_table
def convert_to_morse(s):
print()
morse_table = read_table("data/morse.txt")
output = []
for ch in s:
upper_ch = ch.upper()
if upper_ch in morse_table:
print("Converting {ch} to {code}".format(ch=ch, code=morse_table[upper_ch]))
output.append(morse_table[ch.upper()])
else:
output.append(" ")
result = " ".join(output)
print("Conversion result is {result}".format(result=result))
return result
In [85]:
with tick():
assert convert_to_morse('sos')=='... --- ...'
assert convert_to_morse('hello there')=='.... . .-.. .-.. --- - .... . .-. .'
assert convert_to_morse('sphinx of black quartz judge my vow') == '... .--. .... .. -. -..- --- ..-. -... .-.. .- -.-. -.- --.- ..- .- .-. - --.. .--- ..- -.. --. . -- -.-- ...- --- .--'
In [ ]: