Problem Solving: Paper Folding

Understand the problem:

Predict the sequence of up and down folds for any number of times you fold a strip of paper in half

Devise a Plan

1. Hypothesize what pattern will occur in the sequence of folds produced for each folding         operation made.
2. Observe and record the folding operation, folding the paper in half from 1 to 5 times, then record the number of 'half-folds' and their up and down pattern of creases produced in an organized  table.
3. Look for a pattern betweens between each sequence of up(U) and down(D) creases made    from each folding operation carried out and compare them with previous sequences made before the current fold operation. Note down and verify your conjectures with real results and simulations from your observation table in Step 2.
4. Create and test an algorithm on how you can predict the sequences produced from executing a number of n folding operations.
5. Simulate the folding operation in a Python program.

Carry out the plan

1. HypothesizeBecause the creases of previous folding operations are permanently embedded on the strip of paper, the next sequence will depend on the sequence of the previous folding operations. This hints to the fact that the folding operation is recursive. The next result depends on the previous results that ultimately depend on the first result, the smallest, simplest instance of this folding operation, the base case. When the folding operation is carried out once a single downward crease is made.


2. Observe and record
By making multiple folds, we can produce the following table of upward(U) and downward(D) creases occurring in each fold sequence.

3. Look for a pattern

Looking at the table, we can see that the first fold reappears in all sequences produced after      
the first folding operation. The 'D' fold can be found in the very middle of each sequence.

If the first downward fold recurs throughout all sequences, then there should be more
 reappearing patterns. Lets look for them...

The sequence from making n = 1 folds, DDU reappears. Also, notice how when we fold for          

more the strip of paper more than once, part of the fold sequence before the first D produced          

when n = 1, is reflected on the paper strip to the right of the first D crease, in a reversed  

pattern. The D made from when n = 1 acts as a 'mirror' in which everything to the left of D 

is reversed in folds, going from D -> U or U -> D, producing a 'reflection' on the right side of

mirror D. 

D recurs through all sequences. Our hypothesis is true.

In our example, the sequence DDU for n = 2 reappears in all other sequences for n > 2.
DDUDDUU, the sequence of n = 3 reappears in sequences for which n > 3...
The same thing occurs for the sequence n = 4, n = 5 and so forth.

Now what importance does this have?

Parts of the folding sequences enclosed in the same coloured rectangles are identical patterns that repeat from the previous n-1 before it.

we can see that...

4. Create and test an algorithm

- our simplest case of the folding operation is when n, the number of half-folds made on the strip of paper, is n = 1, the sequence produced is D

- Notice that the 'left pattern' to the left of the mirror D (produced from n = 1) is D, which is reflected(D changes to U), producing the 'right pattern' to the right of the mirror, U.
But, where do we get the left pattern from?
The entire previous sequence becomes the new left pattern.

Knowing these facts, we can create a rough idea that:

- resulting fold sequence =         left pattern           +       D       +          right pattern

                                       previous sequence           mirror          reflection of left pattern

Testing...
If this is so, knowing that when n = 2, a sequence of DDU is produced.
Then, for n = 3:
     - the left sequence should be DDU, the previous sequence in its entirety,
     - the mirror is D as always
     - the right sequence, generated by 'reflecting' the left sequence is: UUD
     - when 'reflecting' a sequence, you reverse the pattern sequence and change U or D's to their  
       opposites**
So the final fold sequence for n = 3 is: DDUDUUD
Checking our observation table, this pattern generated is correct.


Testing our formula to produce a sequence for n = 3 will match without error if true.

Given n = 3 produces a sequence DDUDUUD,

Then for n = 4, the sequence should be:
DDUDUUDDUDDUDUU,
which matches the real results according to the observation table.

Then, for n = 5, the fold sequence should be DDUDUUDDUDDUDUUDDDUDUUDUUDDUDUU,
which is correct.

5. Simulate

We can create pseudo code from this summary to structure the Python program for this problem:
=======================================================================
Pseudocode
fold_sequence(number of half-folds):
      sequence = ''
      mirror = D
      if number of half-folds == 1:

            sequence = D
      if number of half folds > 1:

            sequence += previous fold sequence + mirror + reflection of previous fold                      
                      #      ^                                               sequence
                      # recursive call here
      return sequence

reflect(fold sequence):''' Some helper method to 'reflect' fold sequences.'''
    reflection = ''
    for every character in fold sequence:

        if character is D:

            add U to reflection
        else:
            vice versa of above

        reverse reflection
return reflection
=======================================================================Python Code

DOWN = 'D'

UP = 'U'

MIRROR = 'D'

def gen_fold_sequence(n):

    ''' (int) -> str

    Return the sequence of upward(U) and downward(D) creases given the number

    of half-folds.

    '''

    sequence = ''

    if n == 1:

        sequence += MIRROR

    elif n > 1:

        left_pattern = gen_fold_sequence(n-1)

        sequence += gen_fold_sequence(n-1) + MIRROR + reflect(left_pattern)

    return sequence

def reflect(s):

    ''' (str) -> str

    Return a reflection given s, the sequence.

    '''

    reflection = ''

    if len(s) >= 1:

        for char in s:

            if char == UP:

                reflection += DOWN

            else:

                reflection += UP

    return reflection[::-1]

if __name__ == '__main__':

    for i in range(1, 6, 1):

        print(gen_fold_sequence(i))