# Grid Folding (#63)

**URL:** <https://www.ruby-forum.com/t/grid-folding-63/97483>\
**Category:** Ruby\
**Created:** [January 26, 2006, 6:56am UTC](https://www.ruby-forum.com/t/grid-folding-63/97483 "2006-01-26T06:56:40Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![mansfiem](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/fbc32d/32.png) [@mansfiem](https://www.ruby-forum.com/u/mansfiem)\
**Post date:** [January 26, 2006, 6:56am UTC](https://www.ruby-forum.com/t/grid-folding-63/97483/1 "2006-01-26T06:56:40Z")

</div>

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] [Origami -- from Wolfram MathWorld](http://mathworld.wolfram.com/Origami.html)  
[2] [http://www.merrimack.edu/~thull/OrigamiMath.html](http://www.merrimack.edu/~thull/OrigamiMath.html)  
[3] [http://web.usna.navy.mil/~wdj/rubik\_nts.htm](http://web.usna.navy.mil/~wdj/rubik_nts.htm)

---

<div class="post-metadata">

**Author:** ![mansfiem](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/fbc32d/32.png) [@mansfiem](https://www.ruby-forum.com/u/mansfiem)\
**Post date:** [January 26, 2006, 4:36pm UTC](https://www.ruby-forum.com/t/grid-folding-63/97483/2 "2006-01-26T16:36:02Z")

</div>

> 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 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.

---

<div class="post-metadata">

**Author:** ![mansfiem](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/fbc32d/32.png) [@mansfiem](https://www.ruby-forum.com/u/mansfiem)\
**Post date:** [January 26, 2006, 4:39pm UTC](https://www.ruby-forum.com/t/grid-folding-63/97483/3 "2006-01-26T16:39:03Z")

</div>

On Jan 25, 2006, at 11:53 PM, Matthew M. wrote:

> I love mathematics.

Are there pills for that?!

Seriously, thank you Matthew for another wildly popular problem and  
top-notch summary!

This ends a sensational run of eight contributed quizzes and two  
contributed summaries. Thanks to all for the wonderful support.

Now back to the summary…

> class Array  
> def reverse\_each  
> map {|x| x.reverse}  
> end  
> end

[snip]

> 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.

It also clobbered the reverse\_each() iterator that already exists for  
Array:

> > [1, 2, 3].reverse\_each { |n| puts n }  
> > 3  
> > 2  
> > 1  
> > =\> [1, 2, 3]

James Edward G. II

---

<div class="post-metadata">

**Author:** ![mansfiem](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/fbc32d/32.png) [@mansfiem](https://www.ruby-forum.com/u/mansfiem)\
**Post date:** [January 26, 2006, 6:49pm UTC](https://www.ruby-forum.com/t/grid-folding-63/97483/4 "2006-01-26T18:49:10Z")

</div>

On Jan 26, 2006, at 8:35 AM, Andrew D. wrote:

> for check\_fold–the last fold is always uniquely determined by
> 
> 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