I love mathematics. I love to see problems explored, patterns emerge,

simplified and beautified. There is an absolute nature about

mathematics not present in most other disciplines, and an

understanding of math, I think, is the key to sanity.

Okay, so you may not totally agree with me on that, but I needed some

sort of intro here, right? Anyway, one area of mathematics that is

still rather young is that of origami. Yup, that Japanese art of paper

folding[1] is now being more thoroughly examined by mathematicians[2]

for applications in engineering and other fields.

The paper folding problem I proposed came to mind while thinking of

origami, but also while thinking on the mathematics of the Rubik’s

Cube[3]. If the cube could be reduced down to a study in permutations,

groups and God’s Algorithm, surely a simple folding problem could be

done as well.

Before we get to that, let’s look at the common solution that most

people tried: model the paper as a two-dimensional array, each element

an array representing a stack of numbers. Each fold, then, would grab

various sub-arrays, twist and turn them, mash 'em back together until

you were left with a single array representing the final stack of

numbers.

Let’s look at one of the cleanest solutions of the bunch, written by

Sander L.:

class Array

def reverse_each

map {|x| x.reverse}

end

end

First we have a helper method defined on Array that reverses each of

the items in the array, not the array itself. This is used to flip the

paper horizontally. My only complaint here is the name; I’m used to

seeing a number of “each” methods in Ruby as iterators that yield to a

block. Given the naturn of the problem, i would have preferred

“reflect_h” or similar.

def rightFold(grid)

grid.map { |row|

for ix in 0…row.length/2

row[ix] = row[-ix-1].reverse + row[ix]

end

row[0…row.length/2]

}

end

While some solutions included four different fold methods, one for

each direction, a few authors (including Sander) wrote only one fold

method, turning the paper before and after the fold to orient things

properly. A cleaner solution was generally found when turning, since

turn methods were generally much simpler than fold methods.

Sander implements a right-to-left fold a half-row at a time. Matching

pairs of stacks are found via positive (for the left side) and

negative (right side) indices. Since this is a right-to-left fold, the

right side folds over on top the left, which makes it first in the new

stack but also reversed.

def fold(str,w=8,h=8)

grid = Array.new(h) {|y| Array.new(w) {|x| [w*y+x+1] } }

str.each_byte {|c|

grid = case c

when ?R then rightFold(grid)

when ?L then rightFold(grid.reverse_each).reverse_each

when ?B then rightFold(grid.transpose).transpose

when ?T then rightFold(grid.reverse.transpose).transpose.reverse

end

}

raise “invalid folding instructions” unless grid.length == 1 &&

grid[0].length == 1

return grid[0][0]

end

Now the actual folding code. After creating the grid (i.e., paper),

Sander iterates over each command, updating the grid with the result

of a combination of rightFold, reverse_each, and the Array methods

transpose and reverse. Take a moment to see what gets passed into

rightFold and what gets done with the result from rightFold; with some

effort, you’ll see how he is turning the paper before folding, then

turning it back.

With a little more work here (an improved name, a couple more helpers)

would make it just a tad better:

class Array

def reflect_h

map { |x| x.reverse }

end

def turn_cw

reverse.transpose

end

def turn_ccw

transpose.reverse

end

end

grid = case c

when ?R then rightFold(grid)

when ?L then rightFold(grid.reflect_h).reflect_h

when ?B then rightFold(grid.turn_ccw).turn_cw

when ?T then rightFold(grid.turn_cw).turn_ccw

end

This next solution by Simon Kroeger is also quite clean and simple,

but doesn’t use three-deep arrays. In fact, Simon starts with an

unfold function, then uses it in the implementation of fold.

def unfold z, cmds

x, y, xdim, ydim, layer = 0, 0, 0.5, 0.5, 2**cmds.size

cmds.unpack(‘C*’).reverse_each do |cmd|

x, xdim = x - xdim, xdim * 2 if cmd == ?R

x, xdim = x + xdim, xdim * 2 if cmd == ?L

y, ydim = y - ydim, ydim * 2 if cmd == ?B

y, ydim = y + ydim, ydim * 2 if cmd == ?T

```
if z > (layer /= 2)
z = 1 + (layer * 2) - z
x = -x if cmd == ?R || cmd == ?L
y = -y if cmd == ?B || cmd == ?T
end
```

end

(xdim + x + 0.5 + (ydim + y - 0.5) * xdim * 2).to_i

end

unfold seeks to find the position of only one number (z) at a time.

Since this is unfolding, the commands are examined in reverse order.

Each fold command doubles the correspoing dimension of the paper (by

doubling either xdim or ydim), and also moves the number’s position

(x,y) in the proper direction: adding when folding left-to-right or

top-to-bottom, and subtracting in the other two fold directions.

The check of z against layer is a little strange at first sight. The

way I came to think of it is that you hold down a section of the paper

as you unfold the rest. That section doesn’t move, doesn’t get flipped

over, and so skips the extra work. However, if the number you’re

unfolding isn’t on that immobile section, a bit of fixup work is

needed since the region containing that number is flipped either

horizontally (x = -x) or vertically (y = -y) as it is unfolded.

The final line is similar to the conversion from 2d to 1d indices,

with a few cleanup values to make all the numbers come out right.

That’s all the code solutions I’m going to show here. I would suggest

looking at some of the other solutions though. In particular, Gregory

Seidman and Luke B. worked out a couple of non-array solutions.

They recognized that power-of-2 dimensions implied you could represent

cells as bit patterns and use bitwise operators (especially xor) to do

the folding. Neither solution is particularly easy to read, but can be

understood with a bit of work. However, their solutions, I think, come

closest to my desire of distilling the problem down to simple

mathematics. With some more effort (which I may attempt later), I

think this approach could yield some interesting insights into paper

folding and a beautiful solution.

I think there is still some interesting math to pull out of this

problem. For example, Andrew D. ponders: “There are never two

sequences that give the same perm. Does anybody know why this is?

Seems like an interesting math problem.” Myself, I wonder if he’s

right.

I also wonder if every possible permutaion of numbers is possible as a

result… absolutely not! Consider a mere 4x4 sheet of paper (i.e.,

16 grid cells). Now, a dimension of 4 implies only 2 folds in that

dimension. Since each fold in a particular dimension can be only one

of two choices, there are 4 ways to fold in that dimension. Since we

have two dimensions, so far we have 4*4 = 16 ways to completely fold

the paper. But the individual folds can occur in any order, which is

4! permutations. So the total number of ways to fold a 4x4 sheet of

paper is 16 * 4!, or 384 ways. But there are 16 grid cells, which

means 16! (or 20,922,789,888,000) permutations of those numbers.

Sheesh!

Footnotes:

[1] http://mathworld.wolfram.com/Origami.html

[2] http://www.merrimack.edu/~thull/OrigamiMath.html

[3] http://web.usna.navy.mil/~wdj/rubik_nts.htm