The Folding Problem

After reading about Mandy's "Streetcar Drama" and attempting it myself last week, I've decided that I'm going to try solving the "Folding" problem Danny Heap has presented to us in lectures.

The "Folding Problem" handout can be found here:
http://www.cdf.toronto.edu/~heap/165/W13/ProblemSolving/folding.pdf


1. Understand the problem:

What the problem presented to us is finding a solution to predict the sequence of up creases and down creases for any number of times you carry out a folding operation.

2. Device a plan:

My plan - a bit rudimentary and brute force - is to do carry out fold operations starting from 1 fold and observe any apparent patterns in the next fold that are relative to the the first fold. I will do this until I find a certain/definite pattern:

3. Carry out the plan:

Let v represent up creases and ^ represent up creases.

Folds	Crease Sequence
1	v
2	^vv
3	^^vv^vv
4	^^v^^vvv^^vv^vv

Here's a look at the table again, pointing out the noticable patterns:

Folds	Crease Sequence
1	|v|
2	^|v|v
3	^^v|v|^vv
4	^^v^^vv|v|^^vv^vv

  4. Look back:

As we can see, the first crease, which is an up crease, remains throughout each new fold and it is the pivotal point of the crease sequence. There is always an equal number of creases to the left of the pivotal first crease and to the right of the pivotal first crease. After each new fold, the previous crease sequence is replicated to the right of the middle crease sequence. Most importantly, the sub crease sequence to the left of the middle pivotal first crease is a 180 degree rotation of the sub crease sequence to the right of the middle pivotal first crease. This means that each new fold has the previous fold's crease sequence to the right of the middle crease, which is the first initial up crease, and to the left of that middle crease is the 180 degree rotation of the previous fold's crease sequence. These patterns are shown in the table above with the first crease, which is the pivotal point through each new fold, shown as |v| and the sub crease sequence that are 180 degree rotations of eachother shown in green and red. Also, the crease sequence with the slight blue background colour shows that the previous fold's crease sequence is exactly the same as the sub crease sequence to the right of the middle crease on the next fold. Here is the necessary information again listed:

• First crease is an up crease
• First crease remains as the middle crease in the sequence throughout each new fold
• After each new fold, the previous fold's crease sequence is replicated to the right of the middle crease, which is the initial upcrease, and a 180 degree rotation of the previous fold's crease sequence is on the left of the middle crease

Now, with this information, we can accurately predict a pattern.

Using Python, we can write a miniture program to predict the sequence of creases for n folds:

def crease_sequence(folds):
    ''' (int) -> str
    Return the crease sequence of a paper with certain number of given folds.
    '''
    if folds == 1:
        return 'v'
    else:
        previous_seq = crease_sequence(folds - 1)
        return rotate(previous_seq) + 'v' + previous_seq

def rotate(sequence):
    ''' (str) -> str
    Return a 180 degree rotation of a given crease sequence.
    '''
    rotation = ''
    for c in sequence:
        if c == 'v':
            rotation = '^' + rotation
        elif c == '^':
            rotation = 'v' + rotation

    return rotation
 

 Yay! I used recursion!
 This Python has been tested and is working! Please feel free to try it out yourself!