by Matthew Moss
You have a square sheet of grid paper, 16 cells across by 16 down. A number is written in each cell, starting at 1 in the upper-left corner, going across each line then down the paper, ending with 256 in the lower-right corner.
Your task is write a Ruby function to fold the paper in half repeatedly (along the horizontal or vertical middle), until you are left with a single cell, 256 layers thick, and report back on the order of those layers, top to bottom.
The input to the function is a string containing the characters "T" (the top edge folded down to the bottom edge), "B" (bottom up to top), "R" (right to left) and "L" (left to right). Not every combination of those will be valid, so make sure you verify your input. Output will be an Array of Integers from 1 to 256, arranged in the top-to-bottom layer order after all folds are done.
To help clarify, here's a 2x2 example.
+-+-+
|1|2|
+-+-+
|3|4|
+-+-+
fold("RB") => [3, 4, 2, 1]
fold("TL") => [3, 1, 2, 4]
fold("LR") => raise exception for invalid input
Extra credit: Make your fold function take an additional input parameter(s), the dimensions of the paper; dimensions should be power-of-2 in order to fold down to one cell.
Extra extra credit: Write a method check_fold() that takes the resulting Array of Integers from the quiz and returns the transformation String argument (i.e. fold(check_fold(final_order)) == final_order).
Quiz Summary
by 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 is now being more thoroughly examined by mathematicians 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. 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:
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 nature of the problem, i would have preferred "reflect_h" or similar.
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.
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.
A little more work here (an improved name, a couple more helpers) would make it just a tad better:
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.
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 corresponding 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 permutation 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!
