From: Matthew Moss <matthew.moss.coder@...>
Date: 2006-01-26T14:53:11+09:00
Subject: [QUIZ.SUMMARY] Grid Folding (#63)

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] = 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 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 = 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