Week 3: This is how folding paper is very hard

We were presented with an interesting problem in this Friday's lecture:

If you continuously fold a strip of paper in half, each time folding the left end over the right end, how will the resulting sequence of up and down creases correlate with how many times it was folded?

Copious folding ensued and was recorded (reading RIGHT to LEFT):

#1 = D
#2 = D D U
#3 = D D U D D U U
#4 = D D U D D U U D D D U U D U U
#5 = we got very confused!

where the number of times the paper was folded is followed by the resulting sequence with U representing an upward crease and D representing a downward crease.

My partner and I noticed the following patterns:

- the entire sequence from the previous fold is contained in and at the beginning of the next fold
- there is some symmetry across all "middle" folds that divide their segment of the paper in half
- a lot of other details, like how creases of the next fold build on existing creases, so new creases crop up between each old crease, inspiring us to draw complicated pyramid structures with lines linking old creases down the pyramid, which turned out to be completely useless so please don't try to make sense of this sentence!

It took a third partner to pull us out of this pointless pyramid-scribbling to find a simple solution:

step 1: start with the entire sequence from the previous fold; and then add a D
step 2: "mirror" everything across the last D
step 3: replace each character from the previous step with its "opposite" character

My attempt to put this into code produces (I didn't test this a whole lot!):

public static String fold(int times)
{
if(times == 0) return "";
return sequence(times, 1, "0"); // 0 for down crease, 1 for up crease
}

private static String sequence(int times, int count, String prev)
{
if(count == times) return prev;
String mirrored = "";
for(int i = prev.length() - 1; i >= 0; i--)
{
mirrored += (Character.getNumericValue(prev.charAt(i)) + 1) % 2;
}
prev += "0" + mirrored;
return sequence(times, ++count, prev);
}

Using these methods, fold(5) returns 0010011000110110001001110011011, where 0 = D and 1 = U.

From this exercise I learned the importance of mastering the mighty computer science laziness! While I was hung up on distracting details that were clearly leading me to a complicated and wholly impractical solution, the obvious patterns were right there on the page, ready to be assembled into a very simple solution!