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