Solutions

The Pi Wallis Solution

Compute the decimals of Pi using the Wallis formula:

"""
The correction for the calculation of pi using the Wallis formula.
"""
from __future__ import division
pi = 3.14159265358979312
my_pi = 1.
for i in range(1, 100000):
my_pi *= 4 * i ** 2 / (4 * i ** 2 - 1.)
my_pi *= 2
print pi
print my_pi
print abs(pi - my_pi)
###############################################################################
num = 1
den = 1
for i in range(1, 100000):
tmp = 4 * i * i
num *= tmp
den *= tmp - 1
better_pi = 2 * (num / den)
print pi
print better_pi
print abs(pi - better_pi)
print abs(my_pi - better_pi)
###############################################################################
# Solution in a single line using more adcanved constructs (reduce, lambda,
# list comprehensions
print 2 * reduce(lambda x, y: x * y,
[float((4 * (i ** 2))) / ((4 * (i ** 2)) - 1)
for i in range(1, 100000)])

The Quicksort Solution

Implement the quicksort algorithm, as defined by wikipedia:

function quicksort(array)
var list less, greater
if length(array) ≤ 1
return array
select and remove a pivot value pivot from array
for each x in array
if x ≤ pivot then append x to less
else append x to greater
return concatenate(quicksort(less), pivot, quicksort(greater))
"""
Implement the quick sort algorithm.
"""
def qsort(lst):
""" Quick sort: returns a sorted copy of the list.
"""
if len(lst) <= 1:
return lst
pivot, rest = lst[0], lst[1:]
# Could use list comprehension:
# less_than = [ lt for lt in rest if lt < pivot ]
less_than = []
for lt in rest:
if lt < pivot:
less_than.append(lt)
# Could use list comprehension:
# greater_equal = [ ge for ge in rest if ge >= pivot ]
greater_equal = []
for ge in rest:
if ge >= pivot:
greater_equal.append(ge)
return qsort(less_than) + [pivot] + qsort(greater_equal)
# And now check that qsort does sort:
assert qsort(range(10)) == range(10)
assert qsort(range(10)[::-1]) == range(10)
assert qsort([1, 4, 2, 5, 3]) == sorted([1, 4, 2, 5, 3])

Fibonacci sequence

Write a function that displays the n first terms of the Fibonacci sequence, defined by:

  • u_0 = 1; u_1 = 1
  • u_(n+2) = u_(n+1) + u_n
>>> def fib(n):
... """Display the n first terms of Fibonacci sequence"""
... a, b = 0, 1
... i = 0
... while i < n:
... print(b)
... a, b = b, a+b
... i +=1
...
>>> fib(10)
1
1
2
3
5
8
13
21
34
55

The Directory Listing Solution

Implement a script that takes a directory name as argument, and returns the list of ‘.py’ files, sorted by name length.

Hint: try to understand the docstring of list.sort

"""
Script to list all the '.py' files in a directory, in the order of file
name length.
"""
import os
import sys
def filter_and_sort(file_list):
""" Out of a list of file names, returns only the ones ending by
'.py', ordered with increasing file name length.
"""
file_list = [filename for filename in file_list
if filename.endswith('.py')]
def key(item):
return len(item)
file_list.sort(key=key)
return file_list
if __name__ == '__main__':
file_list = os.listdir(sys.argv[-1])
sorted_file_list = filter_and_sort(file_list)
print sorted_file_list

The Data File I/O Solution

Write a function that will load the column of numbers in data.txt and calculate the min, max and sum values.

Data file:

10.2
43.1
32.6
32.5
61.3
58.2

Solution:

"""Script to read in a column of numbers and calculate the min, max and sum.
Data is stored in data.txt.
"""
def load_data(filename):
fp = open(filename)
data_string = fp.read()
fp.close()
data = []
for x in data_string.split():
# Data is read in as a string. We need to convert it to floats
data.append(float(x))
# Could instead use the following one line with list comprehensions!
# data = [float(x) for x in data_string.split()]
return data
if __name__ == '__main__':
data = load_data('data.txt')
# Python provides these basic math functions
print('min: %f' % min(data))
print('max: %f' % max(data))
print('sum: %f' % sum(data))

The PYTHONPATH Search Solution

Write a program to search your PYTHONPATH for the module site.py.

"""Script to search the PYTHONPATH for the module site.py"""
import os
import sys
import glob
def find_module(module):
result = []
# Loop over the list of paths in sys.path
for subdir in sys.path:
# Join the subdir path with the module we're searching for
pth = os.path.join(subdir, module)
# Use glob to test if the pth is exists
res = glob.glob(pth)
# glob returns a list, if it is not empty, the pth exists
if len(res) > 0:
result.append(res)
return result
if __name__ == '__main__':
result = find_module('site.py')
print result