====================================================================
Softwaretechnik und Programmiersprachen SS06 - Exercices for Python
====================================================================

Links:
======

The following links might help you with the exercices below:

* http://www.python.org: Install Python (it is usually pre-installed on
  non-Windows machines)

* http://docs.python.org: Python documentation


Exercice 1 (easy)
=================

Get acquainted with the interactive Python interpreter. Try out the following::

    >>> x = []
    >>> dir(x)

What are all the methods that are you get returned for? (disregard those that
start with a '_').

Hint: to get help on a method or a function you can say::

    >>> help(function)

For example try::

    >>> help(x.append)


Exercice 2 (easy)
=================

Write a function which takes a list of objects.  The function should
remove all duplicates from the list.  Hint: internally, you need to use
a dictionary to record which objects have already be seen, to make your
algorithm O(n).

Add some tests to be sure that your function works correctly.  Here is a
template::

    def remove_duplicates(lst):
        ...

    l = [4, 7, 30, "hello", 7, "world", 30, 7]
    remove_duplicates(l)
    assert l == [4, 7, 30, "hello", "world"]


Exercice 3 (easy)
=================

Take the following function::

    def fib(n):
        if n <= 2:
            return 1
        return fib(n - 1) + fib(n - 2)

It calculates the ``n`` th fibonacci number in exponential time. Extend
it to make it O(n) by using memoization: that is, use a global
dictionary to store a mapping of ``n`` to the answer ``fib(n)``, for all
``n`` for which the answer has already been computed.


Exercice 4 (easy - medium)
==========================

Implement the sieve of Eratosthenes to compute prime numbers. See
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes for a description.


Exercice 5 (medium)
===================

Write a function that takes a URL as an argument, downloads the page and returns a list of (absolute) links that occur on this page. Hint: see the modules urllib and urlparse; especially the functions urllib.urlopen and urlparse.urljoin.  You will also need the method string.find(substring, startposition).

Links in html look like this: ``<A HREF="local-url">some text</A>``


Exercice 6 (medium)
===================

Write a web crawler based on the function in the previous exercice. It should start from a given address and recursively follow links. Use a dictionary to make sure that you don't visit a page twice. Print the url of every page that is visited.


Exercice 7 (medium)
===================

Write a function that takes a string containing slashes as an argument
(for example 'a/b/c/d/e/f') and returns the following object:
``a.b.c.d.e.f`` where 'a', 'b', ... are the substrings between the
slashes.  The first substring (in this case, 'a') is the name of a
module object; each following substring is the name of the attribute to
read from the previous object.

For example, for the string 'urllib/urlopen/func_code' the function
should return the code object of the function urlopen in the module
urllib.

Hints:

* ``__import__(modulename)`` returns the module with the given name

* ``getattr(obj, "attr")`` is equivalent to ``obj.attr``

* you will also need string.split(separator).


Exercice 8 (hard)
=================

Write an HTTP server that lets you inspect Python objects, using the
function of the previous exercice.  Using a web browser, going to the
url ``http://localhost:8000/a/b/c/d`` should load the object 'a/b/c/d'
using that function.  The page that you get should show some information
about the object that you get, like:

* a string representing the object, as returned by ``repr(obj)``

* for each attribute of the object, as returned by ``dir(obj)``, there
  should be a link with this attribute's name.  It should point to the
  page corresponding to this attribute's value (which is simply the same
  url path with the new attribute name appended).

For example, ``http://localhost:8000/urllib/urlopen`` should show the
text ``<function urlopen at 0x12345678>``, followed by many links
corresponding to all attributes of this function object.  One of these
links is called ``func_code`` and points to
``http://localhost:8000/urllib/urlopen/func_code``.

Here is a template that you can use::

    import SimpleHTTPServer
    import htmlentitydefs
    import StringIO

    # HTML quoting

    text_to_html = {}
    for key, value in htmlentitydefs.entitydefs.items():
        text_to_html[value] = '&' + key + ';'

    def htmlquote(string):
        # return html code that will look exactly like the
        # argument 'string' in a web browser.
        return ''.join([text_to_html.get(c, c) for c in string])


    class MiniHandler(SimpleHTTPServer.SimpleHTTPRequestHandler):

        def send_head(self):
            path = self.path     # it's a string, e.g. '/name1/name2/name3/'

            lines = []
            lines.append('<HTML>')
            lines.append('<BODY>')

            # content of the page here

            # strings should be quoted with htmlquote(string), otherwise
            # characters like '<' will look like html tags to the browser

            lines.append('</BODY>')
            lines.append('</HTML>')

            self.send_response(200)
            self.send_header("Content-type", "text/html")
            self.end_headers()
            return StringIO.StringIO('\n'.join(lines))

    SimpleHTTPServer.test(HandlerClass = MiniHandler)


Exercice 9 (hard)
=================

Install Pygame (http://www.pygame.org) and find an image of a soccer ball.

::

    import pygame

    ballimage = pygame.image.load('filename')
    
    screen = pygame.display.set_mode((500, 400))   # window size

    x = 100
    y = 100
    for i in range(500):
        screen.fill((255, 255, 255))     # fill with white
        screen.blit(ballimage, (x, y))   # draw the image
        pygame.display.flip()            # show result in window

        x = x + 2                        # then move the ball
        y = y + 1

Adapt the above example to make the ball bounce off the border of the
window.  Add several balls (hint: with a list of current positions and
speeds).

Then add gravity (hint: you need to have a variable containing the
current vertical downward speed, and increase it by a small constant
every loop).