Illustrating recursivity with fractals

Posted on 2012/02/29 by blondin

An interesting way to teach recursive algorithms is to show that it is possible to generate nice pictures by simple recursive algorithms.

For this purpose, the turtle Python-module is particularly well-adapted. When I was eight years old, I remember discovering the power of programing with LogoWriter, a very simple language that allows to draw pictures and initiate people to the basics of programing: loops, control structures, etc.

The following code allows one to draw a classical 2D plant-like graphic.

from turtle import *

def reset(x, y):
    r"""
    Moves the turtle to position (x, y) without
    drawing anything and sets the angle to 90.
    """
    penup()
    setpos(x, y)
    pendown()
    setheading(90)

def f(height, resolution):
    r"""
    Draws a plant of given height and given
    resolution.

    The highest the resolution is, the more
    detailed the plant is drawn. For instance,
    if the resolution is 1, then the basic
    plant is drawn. If the resolution is 3,
    then the plant presents many details.
    """
    if resolution == 0:
        forward(height)
    else:
        # Drawing the bottom
        f(height / 3.0, resolution - 1)

        # Drawing the right branch
        right(30)
        f(height / 3.0, resolution - 1)
        penup()
        backward(height / 3.0)
        pendown()

        # Drawing the middle
        left(30)
        f(height / 3.0, resolution - 1)

        # Drawing the left branch
        left(30)
        f(height / 3.0, resolution - 1)
        penup()
        backward(height / 3.0)
        pendown()

        # Drawing the top part
        right(30)
        f(height / 3.0, resolution - 1)

# Drawing parameters
height = 300                                    # height of plants
ss     = ['slowest', 'slow', 'fast', 'fastest'] # speeds
xs     = [-240, -80, 80, 240]                   # x positions of plants
y      = -100                                   # y position of plants

# Draw plants
for i in range(4):
    speed(ss[i])
    reset(xs[i], y)
    f(height, i + 1)

exitonclick()

Below is the final picture obtained:

Further details might be found there.

Posted in Uncategorized | Leave a comment

Solving tilings problem in Sage

Posted on 2011/10/20 by blondin

Today, I taught the induction principle in my class "Structures discrètes" at UQAC. I use the book Discrete mathematics and Applications of K. Rosen, which is a classical for basic discrete mathematics. In particular, I presented a proof by induction on an interesting tiling problem that I briefly state here:

Consider a grid of dimension 2^n \times 2^n from which one cell has been removed (it can be any cell). We may prove by induction that it is possible to tile the grid minus one square using as many times as we want one of the following four tiles:

The idea is to divide the main square into four sub-squares of size 2^{n-1} \times 2^{n-1}. Then, we identify which of the four sub-square contains the cell that has been initially removed. By induction, we can solve the problem for this sub-square. For the three remaining sub-squares, it suffices to remove their cell closest to the center of the main square: These three cells form the shape of one of the three basic tiles. By induction, we can solve the three remaining sub-squares then add the appropriate shape, ending the proof.

Interestingly, this proof by induction hides a recursive algorithm that allows one to tile the main square. Using the ticket #11379 (created by my friend and colleague S. Labbé) recently merged in Sage, I was able to generate the solution. Here is the output for the 8 \times 8 grid where the cell (2, 2) has been removed:

Note that the blue polyominoes are those obtained from the basis case while red polyominoes are those positionned at each recursive call. Of course, it computes the solution for other values of n. Below is an example on the 16 \times 16 grid with cell (10,3) removed:

The source code used is the following. Note that it depends on the ticket #11379 merged in sage-4.7.2-alpha2.

from sage.combinat.tiling import Polyomino

def find_tiling((x0,y0), (x1,y1), (cx,cy)):
    if x1 - x0 == 1:
        cells = set([(x0,y0), (x0,y1), (x1,y0), (x1,y1)])
        return [Polyomino(cells - set([(cx,cy)]), color='blue')]
    else:
        solution = []
        mx = int((x0 + x1) / 2)
        my = int((y0 + y1) / 2)

        # Center cells
        cells = set([(mx, my), (mx + 1, my), (mx, my + 1), (mx + 1, my + 1)])

        # Lower-left sub-square
        if cx <= mx and cy <= my:
            (dx, dy) = (cx, cy)
            solution.append(Polyomino(cells - set([(mx, my)]), color='red'))
        else:
            (dx, dy) = (mx, my)
        solution += find_tiling((x0, y0), (mx, my), (dx, dy))

        # Lower-right sub-square
        if cx > mx and cy <= my:
            (dx, dy) = (cx, cy)
            solution.append(Polyomino(cells - set([(mx + 1, my)]), color='red'))
        else:
            (dx, dy) = (mx + 1, my)
        solution += find_tiling((mx + 1, y0), (x1, my), (dx, dy))

        # Upper-left sub-square
        if cx <= mx and cy > my:
            (dx, dy) = (cx, cy)
            solution.append(Polyomino(cells - set([(mx, my + 1)]), color='red'))
        else:
            (dx, dy) = (mx, my + 1)
        solution += find_tiling((x0, my + 1), (mx, y1), (dx, dy))

        # Upper-right sub-square
        if cx > mx and cy > my:
            (dx, dy) = (cx, cy)
            solution.append(Polyomino(cells - set([(mx + 1, my + 1)]), color='red'))
        else:
            (dx, dy) = (mx + 1, my + 1)
        solution += find_tiling((mx + 1, my + 1), (x1, y1), (dx, dy))

        return solution

The two previous images have been generated by the following commands:

sum(p.show2d() for p in find_tiling((0,0), (7,7), (2,2))).show(aspect_ratio=1, axes=False)

sum(p.show2d() for p in find_tiling((0,0), (15,15), (10,3))).show(aspect_ratio=1, axes=False)
Posted in Combinatorics, Sage | Leave a comment

Environment eqnarray on multiple pages

Posted on 2011/09/16 by blondin

A quick post on Latex!

When writing many eqnarray environment in Latex files, it is sometimes annoying when it keeps breaking pages to fit the whole sequence of computations in one page. This may be remedied by adding the \allowdisplaybreaks command just after \begin{document}

Posted in Latex | Leave a comment