[QUIZ.SUMMARY] Grid Folding (#63)

[Matthew Moss]

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 Land:

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] =3D 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=3D8,h=3D8)
grid =3D Array.new(h) {|y| Array.new(w) {|x| [w*y+x+1] } }
str.each_byte {|c|
grid =3D 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 =3D=3D 1 &&
grid[0].length =3D=3D 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 =3D 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 =3D 0, 0, 0.5, 0.5, 2**cmds.size

cmds.unpack('C*').reverse_each do |cmd|
x, xdim =3D x - xdim, xdim * 2 if cmd =3D=3D ?R
x, xdim =3D x + xdim, xdim * 2 if cmd =3D=3D ?L
y, ydim =3D y - ydim, ydim * 2 if cmd =3D=3D ?B
y, ydim =3D y + ydim, ydim * 2 if cmd =3D=3D ?T

if z > (layer /=3D 2)
z =3D 1 + (layer * 2) - z
x =3D -x if cmd =3D=3D ?R || cmd =3D=3D ?L
y =3D -y if cmd =3D=3D ?B || cmd =3D=3D ?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 =3D -x) or vertically (y =3D -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 Blanshard 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 Dudzik 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 =3D 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

 

[Andrew Dudzik]

------=_Part_8096_16282783.1138289738402
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

I think there is still some interesting math to pull out of this
problem. For example, Andrew Dudzik 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 think that this is true, and that it follows from Bill Dolinar's solution
for check_fold--the last fold is always uniquely determined by picking some
x and y coordinates and looking at the numbers on the top and bottom of the
stack--if, say, 4 and 7 are on opposite sides of the folded paper, they mus=
t
have been in the same sheet one fold ago--the direction of this fold is
determined by the relative orientation of 4 and 7 in the original, unfolded
paper.

Since there is only ever one possible direction to unfold, there can only b=
e
at most one sequence of unfolds that gives the desired 1--n^2 pattern.
Hence there is at most one sequence of folds that produces a given
permutation.

------=_Part_8096_16282783.1138289738402--

 

[Bill Dolinar]

I think that this is true, and that it follows from Bill Dolinar's
solution
for check_fold--the last fold is always uniquely determined by
picking some
x and y coordinates and looking at the numbers on the top and
bottom of the
stack--if, say, 4 and 7 are on opposite sides of the folded paper,
they must
have been in the same sheet one fold ago--the direction of this
fold is
determined by the relative orientation of 4 and 7 in the original,
unfolded
paper.

Since there is only ever one possible direction to unfold, there
can only be
at most one sequence of unfolds that gives the desired 1--n^2 pattern.
Hence there is at most one sequence of folds that produces a given
permutation.

When I was testing my solution for check_fold I found that it was
very fast at going through the unfolding. I ran a test on the
unfolding the 2048x2048 data and found that I could run unfold a
thousand times in about 2.5 seconds. Quite the difference compared
to fold running once in about 160 seconds. With the unfold being so
fast, one would think there must be some way to speed up folding
considerably. I spent some time trying to find a pattern and came up
with formulas for the first fold where given the array index it gave
the new index, but when considering layers as well on the second fold
it made my head spin. Thinking about it though, in the algorithm to
unfold you only have to consider two elements of the array each time
you unfold. For folding you have to consider every element of the
array for each fold.

Bill

 

[Morus Walter]

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.

I don't think so.
The number of folds for a 4x4 sheet is only 96 (and 17920 for 16x16).
You don't take into account that not all permutations are different.
E.g. you count 4 permutations for LLTT, but that's just one way to fold.
For a 2^n x 2^n grid the number of different folds is
sum_i=0^n/2 sum_j=0^n/2 n! / i! / (n/2-i)! / j! / (n/2-j)!

But that doesn't invalidate your argument. On the contrary that number of
possible folds is even smaller...

Morus