# 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:

```"""
===================
I/O script example
===================

Script to read in a column of numbers and calculate the min, max and sum.

Data is stored in data.txt.
"""

fp = open(filename)
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__':
# 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)

```