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

on 2006-01-26 06:56

on 2006-01-26 16:36

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

on 2006-01-26 16:39

On Jan 25, 2006, at 11:53 PM, Matthew Moss 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 Gray II

on 2006-01-26 18:49

On Jan 26, 2006, at 8:35 AM, Andrew Dudzik 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