# Re: [QUIZ] Grid Folding (#63)

21 views

### Matthew Moss

Jan 20, 2006, 11:11:41 AM1/20/06
to
> Assuming it is only composed of [LRTB], is there any way in which the
> string can be invalid other than too many folds in a particular dimension?

Yes... too few folds. The 16x16 (or MxN) paper should be reduced via
folding to a 1x1 stack. Knowing that the input dimensions should be
powers of 2, you can determine the exact number of folds. If the
paper is 16 wide, there should be exactly log2(16) == 4 horizontal
folds.

### Matthew Moss

Jan 20, 2006, 11:16:27 AM1/20/06
to
The first extra credit (handling dimensions other than 16x16) is
pretty darn easy, so you may want to start out on a 2x2 to get yer
basics working and move up. With that in mind, here are a few tests
to help verify your work. The test_2x2 tests all possible folding
combinations.

(NOTE: The 16x16 test below is the result of my own solution. I'm
fairly certain it's correct, but not 100%. So if you run this and
pass the other two tests but fail the 16x16 test, I'd be interested to
see your output and between us figure out what the expected solution
is.)

Oh, and if you have more tests, feel free to share.

require 'test/unit'
require 'test/unit/ui/console/testrunner'

class FoldTest < Test::Unit::TestCase
def test_2x2
folds = {"TR" => [4, 2, 1, 3],
"BR" => [2, 4, 3, 1],
"TL" => [3, 1, 2, 4],
"BL" => [1, 3, 4, 2],
"RT" => [1, 2, 4, 3],
"RB" => [3, 4, 2, 1],
"LT" => [2, 1, 3, 4],
"LB" => [4, 3, 1, 2]}

folds.each do |cmds,xpct|
assert_equal xpct, fold(2, 2, cmds)
end
end

def test_16x16
xpct = [189, 77, 68, 180, 196, 52, 61, 205,
204, 60, 53, 197, 181, 69, 76, 188,
185, 73 , 72, 184, 200, 56, 57, 201,
208, 64, 49, 193, 177, 65, 80, 192,
191, 79, 66, 178, 194, 50, 63, 207,
202, 58, 55, 199, 183, 71, 74, 186,
187, 75, 70, 182, 198, 54, 59, 203,
206, 62, 51, 195, 179, 67, 78, 190,
142, 126, 115, 131, 243, 3, 14, 254,
251, 11, 6, 246, 134, 118, 123, 139,
138, 122, 119, 135, 247, 7, 10, 250,
255, 15, 2, 242, 130, 114, 127, 143,
144, 128, 113, 129, 241, 1, 16, 256,
249, 9, 8, 248, 136, 120, 121, 137,
140, 124, 117, 133, 245, 5, 12, 252,
253, 13, 4, 244, 132, 116, 125, 141,
157, 109, 100, 148, 228, 20, 29, 237,
236, 28, 21, 229, 149, 101, 108, 156,
153, 105, 104, 152, 232, 24, 25, 233,
240, 32, 17, 225, 145, 97, 112, 160,
159, 111, 98, 146, 226, 18, 31, 239,
234, 26, 23, 231, 151, 103, 106, 154,
155, 107, 102, 150, 230, 22, 27, 235,
238, 30, 19, 227, 147, 99, 110, 158,
174, 94, 83, 163, 211, 35, 46, 222,
219, 43, 38, 214, 166, 86, 91, 171,
170, 90, 87, 167, 215, 39, 42, 218,
223, 47, 34, 210, 162, 82, 95, 175,
176, 96, 81, 161, 209, 33, 48, 224,
217, 41, 40, 216, 168, 88, 89, 169,
172, 92, 85, 165, 213, 37, 44, 220,
221, 45, 36, 212, 164, 84, 93, 173]
assert_equal xpct, fold(16, 16, "TLBLRRTB")
end

def test_invalid
assert_raise(RuntimeError) { fold(2, 2, "LR") } # too many horz folds
assert_raise(RuntimeError) { fold(2, 2, "TRB") } # too many folds
assert_raise(RuntimeError) { fold(3, 2, "LR") } # bad input dimensions
end

end

Test::Unit::UI::Console::TestRunner.run(FoldTest)

### Chris Turner

Jan 21, 2006, 2:47:57 PM1/21/06
to
On 1/20/06, Matthew Moss <matthew.m...@gmail.com> wrote:
> def test_16x16
> # ...

> assert_equal xpct, fold(16, 16, "TLBLRRTB")
> end

Is this right? I was under the impression that the above fold string
is invalid. You shouldn't be able to fold "RR" or "TB", as you must
always fold in half. My solution, at least, tells me that. :-)

Chris

### asplake

Jan 21, 2006, 2:50:33 PM1/21/06
to
Matthew, thank you for sharing your results (and in the form of test
cases). Pleased to report that mine are identical (and pass!).

BTW it's not hard to work out (and - hint to Chris - validate) the grid
dimensions from the folds so my function takes just the one argument.

Regards, Mike

> assert_equal xpct, fold(16, 16, "TLBLRRTB")
> end
>

### Gavin Kistner

Jan 21, 2006, 2:58:47 PM1/21/06
to

You can fold a 4x8 sheet of paper in half four ways. Two of them
produce a dimensions 2x8, and two of them produce dimensions 4x4.
You seem to imply that 'folding in half' means always produce a
square result, unless the paper is already square.

### Chris Turner

Jan 21, 2006, 3:12:10 PM1/21/06
to
That's how I read it. Looking back at the requirements, however, I now
see that the reason "LR" in a 2x2 paper is invalid is for a completely
different reason. :-) Oops.

--
Check out my brand spankin' new website at bestfriendchris.com

### Guest

Jan 21, 2006, 4:56:37 PM1/21/06
to
Chris Turner wrote:
> That's how I read it. Looking back at the requirements, however, I now
> see that the reason "LR" in a 2x2 paper is invalid is for a completely
> different reason. :-) Oops.

I wrote a solution for this quiz yesterday (this will be my first
submission, by the way) and can assure everyone that the tests provided
by Matthew are 100% correct, as I have the same results. :-)

This was a good task, and somewhat hard for me too (I'm a total newbie
after all :-). Maybe that's because I didn't find a simple solution and
was forced to just model the situation roughly, without any hacks.

Thanks, Matt!

--
Posted via http://www.ruby-forum.com/.

### Morus Walter

Jan 21, 2006, 4:49:11 PM1/21/06
to

"asplake" <m...@asplake.co.uk> writes:
> Matthew, thank you for sharing your results (and in the form of test
> cases). Pleased to report that mine are identical (and pass!).
>
me too :-)

> BTW it's not hard to work out (and - hint to Chris - validate) the grid
> dimensions from the folds so my function takes just the one argument.
>

Good hint.

But doesn't that imply that any input is valid? E.g. LR is ok for
a 4x1 sheet (giving 4,1,2,3).
Or did you introduce a rule that the input has to be a square?

I suggest other tests based on my solution
def test_1024_1024
xpct = 'b5319b3045af0ab0f931dacca739d90a'
md5 = MD5.new(fold(1024,1024,'TRTRTRTRTRTRTRTRTRTR').join(' '))
assert_equal xpct, md5.hexdigest
end
def test_2048_2048
xpct = '8e046199eee20b097e4948a5ea503516'
md5 = MD5.new(fold(2048,2048,'TRTRTRTRTRTRTRTRTRTRTR').join(' '))
assert_equal xpct, md5.hexdigest
end
(you need to add a 'require "md5"' to the test skript, the array itself
is a bit lengthy ;-))

For larger sheets my system (512M) starts to swap too much.
Probably I should have used a singe array instead of three dimensional
arrays of arrays...

Morus

Jan 22, 2006, 9:43:54 AM1/22/06
to
Here's my newbie solution:

class SquareSheet
def initialize(dim_power)
@dim = @cols = @rows = 2**dim_power
@power = dim_power
@order = [] #desired number order
@layers = [[0,0]] #array of layer coordinates
#(relative to the top left corner of the whole sheet)
@origin = [[:top, :left]] #array of layer spatial orientations
end

def opposite(dir)
case dir
when :bottom: :top
when :top: :bottom
when :left: :right
when :right: :left
end
end

def fold(sequence)
raise "Invalid sequence" \
unless (sequence.count("TB") == @power) && \
(sequence.count("LR") == @power)
sequence.split(//).each do |char|
len = @layers.length
case char
when "T", "B":
@rows /= 2
for i in 0..len-1 do #in such cases 'for' perfoms better than
'each'
#calculate new orientations and coordinates of each layer
@origin[2*len-i-1] = [opposite((@origin[i])),
(@origin[i])]
@layers[2*len-i-1] = [(@layers[i]), (@layers[i])]
if (@origin[i]) == :bottom: (@layers[2*len-i-1]) +=
@rows
else (@layers[i]) += @rows; end
end
@layers.reverse! if char=="B"
when "L", "R":
@cols /= 2
for i in 0..len-1 do
@origin[2*len-i-1] = [(@origin[i]),
opposite((@origin[i]))]
@layers[2*len-i-1] = [(@layers[i]), (@layers[i])]
if (@origin[i]) == :right: (@layers[2*len-i-1]) += @cols
else (@layers[i]) += @cols; end
end
@layers.reverse! if char=="R"
end
end
@layers.each {|coord| @order << coord*@dim+coord+1}
return @order.reverse
end
end

#example usage:
#sheet = SquareSheet.new(4) #creates 2**4 x 2**4 sheet
#p sheet.fold("TLBLRRTB")

Jan 22, 2006, 10:13:15 AM1/22/06
to
Thanks for the test, passed.

"Finished in 182.372 seconds." - quite long for my 2Ghz P4. I wonder
how much it takes to pass the test for the other participants.

### asplake

Jan 22, 2006, 10:22:23 AM1/22/06
to
> Or did you introduce a rule that the input has to be a square?

Sorry, I missed this earlier, but as per my submission a few minutes
ago I raise an exception if it's non-square, but only to pass the unit
tests. Otherwise I see no problem with this.

> For larger sheets my system (512M) starts to swap too much.
> Probably I should have used a singe array instead of three dimensional
> arrays of arrays...

Very interesting to see other solutions. So far I seem to be the only
one not to have modelled the grid explicitly, allocating an array only
for the output. Tried 1024x1024 just now (took 4 minutes - how about
you?) and I'll give your tests a try. Mine seems to be the most
verbose though...

Mike Burrows

Jan 22, 2006, 10:28:38 AM1/22/06
to
Mike, you have an interesting concept for this quiz, but the script is
very slow (3 times slower than the nearest neighbour) - I just tested
it on my machine along with others.

### asplake

Jan 22, 2006, 11:06:02 AM1/22/06
to
Not 100% surprised, and it's longer than others too. For the large
(e.g. 1024x1024) runs it's now about twice as fast, just by
preallocating the results array and using 'for' instead of 'each'
loops. Oh well. Still the slowest. Perhaps mine uses less memory ;-)

Jan 22, 2006, 11:26:51 AM1/22/06
to
Excuse me for a dumb question, but how do you preallocate the array?

### asplake

Jan 22, 2006, 11:39:31 AM1/22/06
to
with: result = Array.new(orig_width * orig_height)
and if "preallocate" was the wrong word, I apologise!

Jan 22, 2006, 12:09:44 PM1/22/06
to
Thanks. I don't know how to apply it to my code, though. Lets say I
have an array of symbol pairs such as: [[:top, :left], [:bottom,
:left], [:top, :right]] ... ], and there's an N of them.

Replacing "@origin = []" with something like "@origin = Array.new(2*N)"
gives out an error about accessing nil later in the code.

### Sander Land

Jan 22, 2006, 12:11:15 PM1/22/06
to
here is my solution, it uses a 3d array to keep track of the stack of
numbers in every location.

class Array
def reverse_each
map {|x| x.reverse}
end
end

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.length == 1
return grid
end

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

p fold("RB",2,2)
p fold("TLRBB",4,8)
p fold("TLBLRRTB",16,16)

i tried to use map(&:reverse) for the reverse_each function but that
doesn't seem to work :(
irb(main):001:0> require 'extensions/symbol'
irb(main):002:0> [[1,2,3]].map(&:reverse)
NoMethodError: undefined method `reverse' for 1:Fixnum

### Morus Walter

Jan 22, 2006, 12:29:46 PM1/22/06
to

"asplake" <m...@asplake.co.uk> writes:
>> Or did you introduce a rule that the input has to be a square?
>
> Sorry, I missed this earlier, but as per my submission a few minutes
> ago I raise an exception if it's non-square, but only to pass the unit
> tests. Otherwise I see no problem with this.
>
I don't see a problem, I was just curious how you understand validation
if you get the sizes from the folding instructions, since I'd say any
instruction is valid then. But that's just a question of interpretation

Morus

### Morus Walter

Jan 22, 2006, 12:24:50 PM1/22/06
to
502.175 (~90 for the 1024x1024 and 411 for the 2048x2048)
on a AMD Athlon XP 1600+ (1400 MHz).

Pretty slow I guess.
So I redid that using a single array instead of arrays of arrays of arrays.
I'm still accessing each cell indidually. But that turned out to be even
slower (I used a Array3d class and the additional method lookup is obviously
too expensive, especially since I access each point individually).

So here's my solution:

#! /usr/bin/ruby

class Sheet

def check(dim)
n = Math.log(dim)/Math.log(2) # ' /x
if n != n.to_i
raise "dimension must be power of 2"
end
end
def initialize(width, height)
check(width)
check(height)
sheet = []
0.upto(height-1) do | y |
sheet[y] = []
0.upto(width-1) do | x |
sheet[y][x] = [ width*y + x ]
end
end
set_sheet(sheet)
end

def set_sheet(sheet)
@sheet = sheet
@width = sheet.size
@height = sheet.size
@depth = sheet.size
end

def output()
0.upto( height-1 ) do | y |
0.upto( width-1 ) do | x |
(depth-1).downto( 0 ) do | z |
print "%3d " % (@sheet[y][x][z]+1)
end
print " "
end
puts ""
end
puts ""
end

def result
@sheet.reverse.collect { | i | i+1 }
end

# ok, here comes the ugly part...
# for each folding direction a new (stacked) sheet is calculated
def fold(dir)
new_sheet = []
if dir == "T"
s2 = height/2 # i'd really liked to know why xemacs has problems with foo/2; probably it's confused with a regex
raise "cannot fold" if s2 == 0
0.upto( s2-1 ) do | y |
new_sheet[y] = @sheet[y + s2]
0.upto( width-1 ) do | x |
0.upto( depth-1 ) do | z |
new_sheet[y][x][depth+depth-1-z] = @sheet[s2-1-y][x][z]
end
end
end
elsif dir == "B"
s2 = height/2 #'/x
raise "cannot fold" if s2 == 0
0.upto( s2-1 ) do | y |
new_sheet[y] = @sheet[y]
0.upto( width-1 ) do | x |
0.upto(depth-1) do | z |
new_sheet[y][x][depth+depth-1-z] = @sheet[s2+s2-1-y][x][z]
end
end
end
elsif dir == "L"
s2 = width/2 #'/x
raise "cannot fold" if s2 == 0
0.upto( height-1 ) do | y |
new_sheet[y] ||= []
0.upto( s2-1 ) do | x |
new_sheet[y][x] ||= []
0.upto( depth-1 ) do | z |
new_sheet[y][x][z] = @sheet[y][x+s2][z]
new_sheet[y][x][depth+depth-1-z] = @sheet[y][s2-1-x][z]
end
end
end
elsif dir == "R"
s2 = width/2 #'/x
raise "cannot fold" if s2 == 0
0.upto( height-1 ) do | y |
new_sheet[y] ||= []
0.upto( s2-1 ) do | x |
new_sheet[y][x] ||= []
0.upto( depth-1 ) do | z |
new_sheet[y][x][z] = @sheet[y][x][z]
new_sheet[y][x][depth+depth-1-z] = @sheet[y][s2+s2-1-x][z]
end
end
end
else
raise "unknown edge #{dir}"
end
set_sheet(new_sheet)
end

def folds(dirs)
dirs.split(//).each do | dir |
fold(dir)
end
end

end

def fold(width, height, cmds)
sheet = Sheet.new(width, height)
sheet.folds(cmds)
raise "to few folds..." if sheet.width > 1 || sheet.height > 1
return sheet.result
end

if ARGV
cmds = ARGV
width = (ARGV || 16).to_i
height = (ARGV || width).to_i
digits = (Math.log(width*height)/Math.log(10)).ceil
puts fold(width, height, cmds).collect { | i | "%#{digits}d" % i }.join(", ")
end

### Chris Turner

Jan 22, 2006, 12:44:24 PM1/22/06
to
Here's my (first ever) solution. For the extra-extra credit, my
sincere thanks go out to Tristan Allwood, who's solution to the
Numeric Maze I used to check_fold. It is incredibly slow, as it has to
try every possible unfold, but it ends up working.

Chris Turner

# folding.rb ---------------------------------------------------------------------------------------------------------

# A few helper methods

def try
begin
yield
rescue
end
end

class Object
def deep_dup
end
end

module Math
def Math.log2(num)
Math.log(num) / Math.log(2)
end
end

class Fixnum
def power_of_2?
power_of_two = 2
begin
return true if power_of_two == self
end while((power_of_two = power_of_two*2) <= self)
false
end
end

# First part of solution (plus first extra credit)
class Paper
def initialize(size=16)
raise "Paper size must be power of 2" unless size.power_of_2?
@paper = []
(1..size).each do |h|
@paper.push((((h-1)*size)+1..(((h-1)*size)+size)).to_a)
@paper[-1].map! {|x| [x]}
end
@size = size
self
end

def fold(commands)
size = commands.size
folds_req = Math.log2(@size).to_i*2
raise "Need #{folds_req-size} more folds" if folds_req > size
raise "Have too many folds (by #{size-folds_req})" if folds_req < size

directions = parse_fold_commands(commands)
directions.each do |direction|
send(direction)
end
@paper
end

def fold_bottom
fold_vert(false)
end

def fold_top
fold_vert(true)
end

def fold_left
fold_horiz(true)
end

def fold_right
fold_horiz(false)
end

private
def parse_fold_commands(commands)
commands.split("").map do |d|
case d.downcase
when "r"
:fold_right
when "l"
:fold_left
when "t"
:fold_top
when "b"
:fold_bottom
else
raise "Invalid command: #{d}"
end
end
end

def fold_two_halves(new_half, old_half)
new_half.each_with_index do |new_row, r_index|
old_row = old_half[r_index]
new_row.each_with_index do |new_col, c_index|
old_col = old_row[c_index]
new_col.unshift(old_col.reverse).flatten!
end
end
end

def fold_vert(top_to_bottom)
check_foldable(:v)
top_half, bottom_half = get_top_and_bottom
new_half, old_half = if top_to_bottom
[bottom_half, top_half]
else
[top_half, bottom_half]
end
old_half = old_half.reverse
fold_two_halves(new_half, old_half)
(@paper.size/2).times do
if top_to_bottom
@paper.shift
else
@paper.pop
end
end
self
end

def fold_horiz(left_to_right)
check_foldable(:h)
left_half, right_half = get_left_and_right
new_half, old_half = if left_to_right
[right_half, left_half]
else
[left_half, right_half]
end
old_half = old_half.map { |x| x.reverse }
fold_two_halves(new_half, old_half)
@paper.each do |row|
(row.size/2).times do
if left_to_right
row.shift
else
row.pop
end
end
end
self
end

def get_top_and_bottom
new_size = @paper.size/2
[@paper[0,new_size], @paper[new_size,new_size]]
end

def get_left_and_right
new_size = @paper.size/2
[@paper.map {|x| x[0,new_size]}, @paper.map {|x| x[new_size,new_size]}]
end

def check_foldable(direction)
if (@paper.size % 2 != 0) || (@paper.size % 2 != 0)
raise "Must be foldable" if @paper.size != 1 && @paper.size != 1
end

if direction == :v
raise "Can't fold this direction" if @paper.size == 1
elsif direction == :h
raise "Can't fold this direction" if @paper.size == 1
end
end
end

def fold(command, size=16)
Paper.new(size).fold(command)
end

if __FILE__ == \$0
paper_size = ARGV || 16
p fold(STDIN.gets.chomp, paper_size.to_i)
end

#
# Begin extra extra
credit-----------------------------------------------------------------------------------
#
class Paper
def unfold(commands)
directions = parse_unfold_commands(commands)
directions.each do |direction|
send(direction)
end
self
end

def reset_to(new_paper)
@paper = new_paper
self
end

def at_start?
if @paper.size == @size and @paper.size == @size
catch(:not_correct) do
(0..@size-1).each do |row|
(0..@size-1).each do |col|
throw :not_correct if(@paper[row][col] != (row*@size)+col+1)
end
end
return true
end
false
end
end

def unfold_to_bottom
check_unfoldable(:v)
@paper.reverse.each do |row|
new_row = []
row.each do |col|
new_col = []
(col.size/2).times { new_col.unshift(col.shift) }
new_row.push(new_col)
end
@paper.push(new_row)
end
self
end

def unfold_to_top
check_unfoldable(:v)
me = @paper.dup
me.each do |row|
new_row = []
row.each do |col|
new_col = []
(col.size/2).times { new_col.unshift(col.shift) }
new_row.push(new_col)
end
@paper.unshift(new_row)
end
self
end

def unfold_to_left
check_unfoldable(:h)
@paper.each do |row|
row_dup = row.dup
row_dup.each do |col|
new_col = []
(col.size/2).times { new_col.unshift(col.shift) }
row.unshift(new_col)
end
end
self
end

def unfold_to_right
check_unfoldable(:h)
@paper.each do |row|
row.reverse.each do |col|
new_col = []
(col.size/2).times { new_col.unshift(col.shift) }
row.push(new_col)
end
end
self
end

private
def parse_unfold_commands(commands)
commands.split("").map do |d|
case d.downcase
when "r"
:unfold_to_right
when "l"
:unfold_to_left
when "t"
:unfold_to_top
when "b"
:unfold_to_bottom
else
raise "Invalid command: #{d}"
end
end
end

def check_unfoldable(direction)
if (@paper.size % 2 != 0) || (@paper.size % 2 != 0)
raise "Must be foldable" if @paper.size != 1 && @paper.size != 1
end

raise "Already unfolded" if (@paper.size == 1)
end
end

def check_fold(ary)
raise "Invalid solution" unless ary.size.power_of_2?
try_all(paper, [""])
end

def try_all(start, directions)
n = []
directions.each do |sol|
new_sol = start.deep_dup.unfold(sol)
ufl = ufr = uft = ufb = nil

try { ufl = new_sol.deep_dup.unfold_to_left }
try { ufr = new_sol.deep_dup.unfold_to_right }
try { uft = new_sol.deep_dup.unfold_to_top }
try { ufb = new_sol.deep_dup.unfold_to_bottom }

return (sol + "l").reverse if ufl and ufl.at_start?
return (sol + "r").reverse if ufr and ufr.at_start?
return (sol + "t").reverse if uft and uft.at_start?
return (sol + "b").reverse if ufb and ufb.at_start?

n << (sol + "l") if ufl
n << (sol + "r") if ufr
n << (sol + "t") if uft
n << (sol + "b") if ufb
end
try_all(start, n) if directions.size != 0
end

### hornd...@gmail.com

Jan 22, 2006, 9:57:18 PM1/22/06
to
I didn't use multidimensional arrays for my solution. I keep track of
where each number is (row, col, position in paper stack) during the
folds and just insert it directly into the final array. The folding code
isn't as succinct as I'd like it to be with quite a bit of duplication.
Any thoughts on that?

The unfolding function is just magic. I know that's bad, but I'll give
my theory as to why it works. So my original plan was to start in the
middle and look at the numbers on the joint of the fold. Check if
they're in the same row or column to determine if it was a vertical or
horizontal fold and check which number is bigger to determine if it
which side was folded onto the other. This mostly works, but breaks if
there are two folds of the same orientation in a row (ie horizontal
folds: RR, RL, LL, LR). If you look at the end I have it rerun unfold on
the stack generated from folding the new string. This creates the
correct string. As an example lets say we have a 4x1 paper. The valid
folds are:

cmds => stack => unfold(stack)
RR => 2341 => RL
RL => 1432 => RR
LL => 3214 => LR
RL => 4132 => LL

So in this little set we can see that there are pairs of inputs that
give each other as outputs to the unfold section. This happens to also
work for larger paper stacks. I haven't proved this, but I added this to
the unit tests to make sure:

def random_string(len)
vert_folds = ['T', 'B']
horiz_folds = ['L', 'R']
folds = []
(len/2).times do folds << vert_folds[rand(2)] end
(len/2).times do folds << horiz_folds[rand(2)] end
folds.sort{rand}.join
end

def test_random_unfold
100.times do |i|
side_pow = rand(7)+1
side = 2**side_pow
s = random_string(side_pow*2)
assert_equal s, unfold(fold(s, side))
end
end

No failures yet. I'd bet that there is a simple way to fix the
algorithm, but I need to just sit down an figure it out. I can probably
just be able to do a global replace on the string instead of rerunning
fold and unfold. Well, thanks for the quiz!

-----Horndude77

#!/usr/bin/ruby -w

module Math
def Math.lg(n) log(n)/log(2) end
end

def fold(s, n)
#validate inputs
pow = Math.lg(n)
raise "Bad dimension" if pow != pow.round
raise "Bad string length" if s.length != (pow*2).round
horiz, vert = 0, 0
s.downcase.split('').each do |orient|
case orient
when 'r', 'l'
vert += 1
when 't', 'b'
horiz += 1
end
end
raise "Unbalanced folds" if horiz != vert

#do the folding
max = n**2
stack = Array.new(max)
1.upto(max) do |i|
row, col, pos, height = (i-1)/n, (i-1)%n, 0, 1
x, y = n, n
s.each_byte do |move|
pos += height
height *= 2
case move
when ?L
x /= 2
if col < x then
col = x-col-1
pos = height - pos - 1
else
col -= x
end
when ?R
x /= 2
if col >= x then
col = x*2 - col - 1
pos = height - pos - 1
end
when ?T
y /= 2
if row < y then
row = y-row-1
pos = height - pos - 1
else
row -= y
end
when ?B
y /= 2
if row >= y then
row = y*2 - row - 1
pos = height - pos - 1
end
end
end
stack[pos] = i
end
stack
end

def same_row?(a,b,n)
(a-1)/n == (b-1)/n
end

def same_col?(a,b,n)
(a-1)%n == (b-1)%n
end

def unfold(stack, recurse = :yes)
pow = Math.lg(stack.length)
raise "Bad dimension" unless pow == pow.round && (pow.round % 2) ==
0
side = Math.sqrt(stack.length).round
s = ""
while stack.length > 1
half = stack.length/2
a, b = stack[half-1], stack[half]
if same_row? a, b, side then
if a<b then s << 'L' else s << 'R' end
elsif same_col? a, b, side then
if a<b then s << 'T' else s << 'B' end
else
raise "Stack not generated from folding"
end
stack = stack[half, half]
end

s.reverse!
if(recurse == :yes) then
unfold(fold(s, side), :no)
else
s
end
end

### Bob Showalter

Jan 22, 2006, 11:21:15 PM1/22/06
to
My solution is at
peeking at other solutions.

I only did the first extra credit. The extra extra credit looks hard!

### David Tran

Jan 23, 2006, 1:13:47 AM1/23/06
to
def fold(row, col, operations)

def t2b(table)
t1 = table[0...table.size/2].reverse
t2 = table[table.size/2..-1]
row = t1.size
col = t1.size
row.times { |r| col.times { |c| t2[r][c] = t1[r][c].reverse + t2[r][c] } }
t2
end

def b2t(table)
t2b(table.reverse).reverse
end

def l2r(table)
t2b(table.transpose).transpose
end

def r2l(table)
t2b(table.transpose.reverse).reverse.transpose
end

if row <= 1 ||
col <= 1 ||
2**operations.size != row * col ||
operations =~ /[^TBLR]/ ||
2**operations.gsub(/[LR]/,'').size != row
raise "Error: parameters are not correct."
end

index = 0
table = Array.new(row) { Array.new(col) { [index += 1] } }

operations.each_byte do |op|
table = case op
when ?T : t2b(table)
when ?B : b2t(table)
when ?L : l2r(table)
when ?R : r2l(table)
else raise "Error: Invalid fold operation."
end
end

table
end

#========================================================================#

def check_fold(row, col, result)

# find all combinations with binary 0 for row and 1 for column operation
def all_orders(r, c) #
return [2**c - 1] if (r <= 0) # c bits of 1 is 2**c-1
return  if (c <= 0) # r bits of 0 is 0
table = []
all_orders(r-1,c).each { |t| table << ((t << 1) + 0) }
all_orders(r,c-1).each { |t| table << ((t << 1) + 1) }
table
end

if row <= 1 ||
col <= 1 ||
row * col != result.size ||
2 ** (Math.log(row)/Math.log(2)).to_i != row ||
2 ** (Math.log(col)/Math.log(2)).to_i != col
raise "Error: Parameters are not correct."
end

r = Integer(Math.log(row) / Math.log(2))
c = Integer(Math.log(col) / Math.log(2))
all_rc_orders = all_orders(r,c)

row.times do |tb_operation|
col.times do |lr_operation|
all_rc_orders.each do |order|
operations = ''
tb_op = tb_operation
lr_op = lr_operation
(r+c).times do
if (order & 1 == 0)
operations += (tb_op & 1 == 0) ? 'T' : 'B'
tb_op >>= 1
else
operations += (lr_op & 1 == 0) ? 'L' : 'R'
lr_op >>= 1
end
order >>= 1
end
return operations if fold(row, col, operations) == result
end
end
end
"No solution."
end

### Edward Faulkner

Jan 23, 2006, 4:47:49 AM1/23/06
to
This is the kind of problem where it makes sense to trade off
efficiency for simplicity.

class Paper
def initialize(width, height)
@grid = Array.new(width) { Array.new(height) }
height.times { |y| width.times {|x| @grid[x][y] = [width*y+x+1] }}
end

def width; @grid.size; end
def height; @grid.size; end

raise "Not enough folds" if width > 1 or height > 1
@grid
end

# Fold right side over to left
def fold!
raise "Bad input" if width%2 == 1
@grid = (0 .. (width / 2 - 1)).map { |col|
@grid[col].zip(@grid[width - col - 1]).map {|pair| pair.reverse + pair}
}
end

# 90 degree counter clockwise rotation
def rotate!
@grid = @grid.transpose.map{|c| c.reverse}
end
end

def fold(width, height, commands)
turns = commands.tr('RBLT', '0123').split(//).map{|x| x.to_i}
paper = Paper.new(width, height)
turns.each { |turn|
4.times {|i|
paper.fold! if i==turn
paper.rotate!
}
}
end

signature.asc

### David Tran

Jan 23, 2006, 10:01:53 AM1/23/06
to
Correction:
found a little bug on my script.
The checking row <= 1 || col <= 1 is "too much".
These two checking should remove,
because it fail for doing something like fold( 1, 2, 'L' )

### Morus Walter

Jan 23, 2006, 3:12:31 PM1/23/06
to
In article <2orca3-...@morus.walter.news.arcor.de>,
morus....@gmail.com (Morus Walter) writes:

I did another solution doing an unfold of the final stack.
It's much cleaner than the first one.
Unfortunately it's still pretty slow for large grids.
So I did a third one, based on the second one replacing the calculation
by C. The drawback is that it isn't portable anymore, though it should
run on any unix environment having a gcc compiler ;-)

--- second one ---
#! /usr/bin/ruby

def fold(width, height, cmds)

size = width * height

horz = cmds.count("RL")
vert = cmds.count("BT")
raise "illegal width" if 2**horz != width
raise "illegal height" if 2**vert != height

func = "def unfold(z)\n(x,y,z) = [ 0,0,z ]\n"

w = 1
h = 1
d = size
cmds.split(//).reverse.each do | dir |
if dir == 'R'
func += "(x,z) = (z < #{d/2}) ? [ #{2*w-1}-x, #{d/2-1}-z ] : [ x, z-#{d/2} ]\n"
w*=2
elsif dir == 'L'
func += "(x,z) = (z < #{d/2}) ? [ #{w-1}-x, #{d/2-1}-z ] : [ x+#{w}, z-#{d/2} ]\n"
w*=2
elsif dir == 'B'
func += "(y,z) = (z < #{d/2}) ? [ #{2*h-1}-y, #{d/2-1}-z ] : [ y, z-#{d/2} ]\n"
h*=2
elsif dir == 'T'
func += "(y,z) = (z < #{d/2}) ? [ #{h-1}-y, #{d/2-1}-z ] : [ y+#{h}, z-#{d/2} ]\n"
h*=2
end
d/=2
end
func += "x + y * #{width} + 1\n"
func += "end\n"

eval func

(0..size-1).collect { | i | unfold(i) }
end

if ARGV
dirs = ARGV

width = (ARGV || 16).to_i
height = (ARGV || width).to_i

res = fold(width, height, dirs)

puts res.join(", ")
end

--- third one ---
#! /usr/bin/ruby

def fold(width, height, cmds)

size = width * height

horz = cmds.count("RL")
vert = cmds.count("BT")
raise "illegal width" if 2**horz != width
raise "illegal height" if 2**vert != height

func = "#include <stdio.h>\n#include <stdlib.h>\n"
func += "int unfold(int z) { \n int x=0; int y=0;\n"

w = 1
h = 1
d = size
cmds.split(//).reverse.each do | dir |
if dir == 'R'
func += "x = (z < #{d/2}) ? #{2*w-1}-x : x;\n"
func += "z = (z < #{d/2}) ? #{d/2-1}-z : z-#{d/2};\n"
w*=2
elsif dir == 'L'
func += "x = (z < #{d/2}) ? #{w-1}-x : x+#{w};\n"
func += "z = (z < #{d/2}) ? #{d/2-1}-z : z-#{d/2};\n"
w*=2
elsif dir == 'B'
func += "y = (z < #{d/2}) ? #{2*h-1}-y : y;\n"
func += "z = (z < #{d/2}) ? #{d/2-1}-z : z-#{d/2};\n"
h*=2
elsif dir == 'T'
func += "y = (z < #{d/2}) ? #{h-1}-y : y+#{h};\n"
func += "z = (z < #{d/2}) ? #{d/2-1}-z : z-#{d/2};\n"
h*=2
end
d/=2
end
func += "return x + y * #{width} + 1; }\n"
func += "int main(int argc, char**argv) {\n"
func += "int i=0;\nint max=atoi(argv);for (i=0;i<max;i++) { printf(\"%d \",unfold(i)); } }\n"

File.open("unfold.c", "w") do | fh |
fh.puts func
end

`gcc -O2 -o unfold unfold.c`

IO.popen("./unfold #{size}").readline.split(" ").collect { | i | i.to_i }
end

if ARGV
dirs = ARGV

width = (ARGV || 16).to_i
height = (ARGV || width).to_i

res = fold(width, height, dirs)

puts res.join(", ")
end

### Bill Dolinar

Jan 24, 2006, 4:17:47 AM1/24/06
to
Cleaned up the code in my previous solution. Made check_fold not
copy the array and instead just index into the array passed.
Completely changed FoldMatrix to use 3-d array and operations that
make it more readable like split, flip, and place over.

#! /usr/bin/env ruby -w

require 'enumerator'

# Fold up matrix of numbers using given directions where directions
# are in a string with T = top, B = bottom, L = left, R = right:
# "TLBR". Throws ArgumentError on invalid direction or rows or cols
# not a power of 2.
def fold(directions, rows=16, cols=16)
check_rows_and_cols(rows, cols)
if (directions =~ /[^TLBR]/)
raise ArgumentError, "Invalid direction given"
end

# build array of values
# using each_slice as described by Levin Alexander
values = (1..rows*cols).to_enum(:each_slice, 1).to_a
values = values.to_enum(:each_slice, cols).to_a

fold_matrix = FoldMatrix.new(values)

directions.split(//).each do |direction|
fold_matrix.fold(direction)
end
fold_matrix.result
end

# Get the folding directions from a fold array. The item that has
# never been folded over is at end of array. The item that wasn't
# folded until the last fold and is now at at the first of array.
# Can iterate through last folded by continually cutting array in
# half. Throws ArgumentError on array not in fold order or rows or
# cols not power of 2.
def check_fold(fold_result, rows=16, cols=16)
check_rows_and_cols(rows, cols)

directions = ""
folded = 0
size = fold_result.size
while folded < fold_result.size - 1
# get direction in original matrix from last to first
directions << direction_to(fold_result.last, fold_result
[folded], cols)

# move to next item last folded
size = size/2
folded += size
end
directions.reverse
end

class FoldMatrix

def initialize(values)
@values = values
end

# Return a new fold matrix by folding in direction where direction
# is one of :left, :right, :top, :bottom.
def fold(direction)
case direction
when "L"
left, @values = split_along_v
flip_along_v(left)
place_over(left)
when "R"
@values, right = split_along_v
flip_along_v(right)
place_over(right)
when "T"
top, @values = split_along_h
flip_along_h(top)
place_over(top)
when "B"
@values, bottom = split_along_h
flip_along_h(bottom)
place_over(bottom)
end
end

# Return the result of folding in flattened array
def result
if (@values.size != 1 && @values.size != 1)
raise ArgumentError, "Paper not completely folded"
end
@values.flatten
end

protected

def split_along_v
left = []
right = []
cols = @values.size
@values.each do |row|
left << row[0...cols/2]
right << row[cols/2...cols]
end
return left, right
end

def split_along_h
rows = @values.size
top = @values[0...rows/2]
bottom = @values[rows/2...rows]
end

def flip_along_v(a)
a.each do |row|
row.reverse!
row.each {|item| item.reverse!}
end
end

def flip_along_h(a)
a.reverse!
a.each {|row| row.each {|item| item.reverse!}}
end

def place_over(top)
top.each_with_index do |row, i|
row.each_with_index do |item, j|
@values[i][j] = item + @values[i][j]
end
end
end
end

# Determine if a number is a power of 2
def is_power_of_2(number)
return false if number < 1

# keep on shifting left until number equals one (power of 2) or has
# one bit set but isn't one (not power of 2)
while number > 1
number >>= 1
return false if ((number & 1) == 1 && number != 1)
end
true
end

def coordinate(index, cols)
index -= 1
i, j = index/cols, index%cols
end

# Get the direction from an unfolded matrix element to the one
# just folded to the top. Both must be in same row or column.
def direction_to(unfolded, folded, cols)
unfolded_i, unfolded_j = coordinate(unfolded, cols)
folded_i, folded_j = coordinate(folded, cols)

i_compare = unfolded_i <=> folded_i
j_compare = unfolded_j <=> folded_j

case [i_compare, j_compare]
when [ 0, 1] then "L"
when [ 0, -1] then "R"
when [ 1, 0] then "T"
when [-1, 0] then "B"
else
raise ArgumentError, "Values not in same row or column: " +
"#{unfolded}, #{folded}, #{rows}x#{cols}"
end
end

def check_rows_and_cols(rows, cols)
unless is_power_of_2(rows)
raise ArgumentError, "Rows must be power of two"
end
unless is_power_of_2(cols)
raise ArgumentError, "Cols must be power of two"
end
end

### Matthew Moss

Jan 24, 2006, 11:27:27 AM1/24/06
to
> BTW it's not hard to work out (and - hint to Chris - validate) the grid
> dimensions from the folds so my function takes just the one argument.

Well, sure... That's like setting the speed limit to 300mph and
suddenly there are no more speeders. :) But since this is rubyquiz
and not traffic school, that's cool.

### Matthew Moss

Jan 24, 2006, 11:30:09 AM1/24/06
to

My solution took only 143 seconds to do all the tests... of course,
my machine is a 3.2GHz P4, so it the solution ain't that fast.

### Matthew Moss

Jan 26, 2006, 12:53:11 AM1/26/06
to
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:

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.length == 1
return grid
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!

### David Tran

Jan 26, 2006, 10:43:03 AM1/26/06
to
I wonder for 4x4 the total solution is 16 * 4! = 384

My solution about check_fold is try to find all combinations possible.

Below is modified version of my check_fold, it will print out all
possible combinations and total count number.
However I found for 4x4 there is only 96 possible not 384.
Can someone tell me that I am wrong ( missing some combination ) or
the previous math formula is not correct ?

Thanks,

def check_fold(row, col, result)

# find all combinations with binary 0 for row and 1 for column operation
def all_orders(r, c) #
return [2**c - 1] if (r <= 0) # c bits of 1 is 2**c-1
return  if (c <= 0) # r bits of 0 is 0
table = []
all_orders(r-1,c).each { |t| table << ((t << 1) + 0) }
all_orders(r,c-1).each { |t| table << ((t << 1) + 1) }
table
end

=begin
if row <= 0 ||
col <= 0 ||

row * col != result.size ||
2 ** (Math.log(row)/Math.log(2)).to_i != row ||
2 ** (Math.log(col)/Math.log(2)).to_i != col
raise "Error: Parameters are not correct."
end

=end

r = Integer(Math.log(row) / Math.log(2))
c = Integer(Math.log(col) / Math.log(2))
all_rc_orders = all_orders(r,c)

count = 0

row.times do |tb_operation|
col.times do |lr_operation|
all_rc_orders.each do |order|
operations = ''
tb_op = tb_operation
lr_op = lr_operation
(r+c).times do
if (order & 1 == 0)
operations += (tb_op & 1 == 0) ? 'T' : 'B'
tb_op >>= 1
else
operations += (lr_op & 1 == 0) ? 'L' : 'R'
lr_op >>= 1
end
order >>= 1
end

puts operations
count += 1
# return operations if fold(row, col, operations) == result
end
end
end
p count
end

check_fold(4,4, nil)

#==================================#
The output:

TTLL
TLTL
TLLT
LTTL
LTLT
LLTT
TTRL
TRTL
TRLT
RTTL
RTLT
RLTT
TTLR
TLTR
TLRT
LTTR
LTRT
LRTT
TTRR
TRTR
TRRT
RTTR
RTRT
RRTT
BTLL
BLTL
BLLT
LBTL
LBLT
LLBT
BTRL
BRTL
BRLT
RBTL
RBLT
RLBT
BTLR
BLTR
BLRT
LBTR
LBRT
LRBT
BTRR
BRTR
BRRT
RBTR
RBRT
RRBT
TBLL
TLBL
TLLB
LTBL
LTLB
LLTB
TBRL
TRBL
TRLB
RTBL
RTLB
RLTB
TBLR
TLBR
TLRB
LTBR
LTRB
LRTB
TBRR
TRBR
TRRB
RTBR
RTRB
RRTB
BBLL
BLBL
BLLB
LBBL
LBLB
LLBB
BBRL
BRBL
BRLB
RBBL
RBLB
RLBB
BBLR
BLBR
BLRB
LBBR
LBRB
LRBB
BBRR
BRBR
BRRB
RBBR
RBRB
RRBB
96

### Andrew Dudzik

Jan 26, 2006, 10:35:51 AM1/26/06
to
>
> 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.

### Bill Dolinar

Jan 26, 2006, 12:48:09 PM1/26/06
to

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

### Mike Harris

Jan 26, 2006, 8:16:53 PM1/26/06
to
I was waiting to clean up my solution, but it's Thursday, so here it
is. It's too late for the summary, I'm just looking to get my first
successful RubyQuiz up. I also used this as my first TDD "project,"
which explains why it's so verbose in places. I've also included the
tests, can't hurt.

class String
def each_char
for i in 0...length
yield(self[i,1])
end
end
end

class Array
alias_method :old_eq, :==
def ==(arg)
return arg == self if arg.kind_of?(Grid)
old_eq(arg)
end
end

class Range
def middle
(first+last)/2
end

def flip(i)
last-1-(i-first)
end

def flip_doubled(i)
(last*2)-1-(i-first)
end
end

module DiscreteMethod
def make_disc_meth(sym)
define_method(sym) do |*args|
temp_var = clone
temp_var.send(sym.to_s + "!",*args)
temp_var
end
end
end

class Grid
extend DiscreteMethod
attr_accessor :size, :rows, :cols, :vert, :cells
def initialize(n = 0)
@size = n
@rows = 0...n
@cols = 0...n
@vert = 0...1
@cells = {}
init_cells if n > 0
end

def init_cells
num = 1
for r in 0...size
for c in 0...size
@cells[[r,c,0]] = num; num += 1;
end
end
end

def [](r,c,v)
@cells[[r,c,v]]
end

make_disc_meth "fold"
def fold!(str)
if str.length > 1
str.each_char { |c| fold!(c) }
return
end
raise "bad attempted fold" unless ["R","T","L","B"].include?(str)
raise "bad attempted fold" if (str == "R" or str == "L") and
cols.first == cols.last-1
raise "bad attempted fold" if (str == "B" or str == "T") and
rows.first == rows.last-1
@cells.keys.find_all { |k| k >= cols.middle }.each { |k|
self[k,cols.flip(k),vert.flip_doubled(k)] = @cells[k];
@cells.delete(k) } if str == "R"
@cells.keys.find_all { |k| k < cols.middle }.each { |k|
self[k,cols.flip(k),vert.flip_doubled(k)] = @cells[k];
@cells.delete(k) } if str == "L"
@cells.keys.find_all { |k| k >= rows.middle }.each { |k|
self[rows.flip(k),k,vert.flip_doubled(k)] = @cells[k];
@cells.delete(k) } if str == "B"
@cells.keys.find_all { |k| k < rows.middle }.each { |k|
self[rows.flip(k),k,vert.flip_doubled(k)] = @cells[k];
@cells.delete(k) } if str == "T"
update_boundaries!(str)
end

make_disc_meth "update_boundaries"
def update_boundaries!(d)
@vert = (0...vert.last*2)
@rows = (rows.first...rows.middle) if d == "B"
@rows = (rows.middle...rows.last) if d == "T"
@cols = (cols.first...cols.middle) if d == "R"
@cols = (cols.middle...cols.last) if d == "L"
end

def []=(r,c,v,n)
@cells[[r,c,v]] = n
end

def clone
g = Grid.new
g.rows,g.cols,g.vert = rows.clone,cols.clone,vert.clone
@cells.each_key do |k|
g[k,k,k] = @cells[k]
end
g
end

def ==(g)
return false if @cells.keys.size != g.cells.keys.size
return false if size != g.size or cols != g.cols or rows != g.rows
or vert != g.vert
@cells.keys.each { |k| return false if @cells[k] != g.cells[k] }
true
end

def sorted_keys
@cells.keys.sort { |a,b| x = b <=> a; (x = a <=> b) if
x==0; (x = a <=> b) if x==0; x }
end

def to_a
a = []
sorted_keys.each { |k| a << @cells[k] }
a
end
end

def fold(r,c,str)
raise "Bad Input Dimensions" if r != c or
![1,2,4,8,16,32,64,128].include?(r)
g = Grid.new(r)
g.fold!(str)
g.to_a
end

-----------

require 'test/unit'
require '../grid.rb'

class TestGridFold < Test::Unit::TestCase
def setup
@two = Grid.new(2)
@two_folded_rb = Grid.new
@two_folded_rb.rows = (0...1)
@two_folded_rb.cols = (0...1)
@two_folded_rb.vert = (0...4)
@two_folded_rb[0,0,3] = 3
@two_folded_rb[0,0,2] = 4
@two_folded_rb[0,0,1] = 2
@two_folded_rb[0,0,0] = 1
@st = Grid.new(16)
end

def test_size
assert @two.size == 2
end

def test_get
assert @two[0,0,0] == 1
assert @two[0,1,0] == 2
assert @two[1,0,0] == 3
assert @two[1,1,0] == 4
end

def test_out_bounds
assert @two[2,2,2].nil?
end

def test_full_fold
g = @two.fold("RB")
assert g == @two_folded_rb,g.to_a
#assert @two.fold("TL") == [3,1,2,4]
end

def test_one_fold
g = @two.fold("R")
assert g == [2,4,1,3],g.to_a
g = g.fold("B")
assert g == @two_folded_rb
end

def test_fold_not_modify
@two.fold("R")
test_get
end

def test_fold_exc
assert @two.fold("RB") == @two_folded_rb
end

def test_init_boundaries
assert @two.rows == (0...2)
assert @two.cols == (0...2)
assert @two.vert == (0...1)
end

def test_boundaries_after_fold
assert @two.fold("R").cols == (0...1)
assert @two.fold("L").cols == (1...2)
assert @two.fold("R").rows == (0...2)
assert @two.fold("L").rows == (0...2)
end

def test_update_boundaries_r
g = @two.update_boundaries("R")
assert g.rows == (0...2)
assert g.cols == (0...1),g.cols
assert g.vert == (0...2)
end

def test_update_boundaries_t
assert @two.update_boundaries("T").rows == (1...2)
assert @two.update_boundaries("T").cols == (0...2)
assert @two.update_boundaries("T").vert == (0...2)
end

def test_update_boundaries_l
g = @two.update_boundaries("L")
assert g.rows == (0...2)
assert g.cols == (1...2),g.cols
assert g.vert == (0...2)
end

def test_update_boundaries_ll
g = @st.update_boundaries("L").update_boundaries("L")
assert g.rows == (0...16)
assert g.cols == (12...16),g.cols
assert g.vert == (0...4)
end

def test_update_boundaries_llrbt
g =
@st.update_boundaries("L").update_boundaries("L").update_boundaries("R").update_boundaries("B").update_boundaries("T")
assert g.rows == (4...8)
assert g.cols == (12...14),g.cols
assert g.vert == (0...32)
end

def test_update_boundaries_no_update
@two.update_boundaries("R")
assert @two.cols == (0...2)
end

def test_update_boundaries_exc_update
@two.update_boundaries!("R")
assert @two.cols == (0...1)
end

def test_clone
g = @two.clone
assert g[0,0,0] == 1
assert g[1,1,0] == 4
g[0,0,0] = 9
assert g[0,0,0] == 9
assert @two[0,0,0] == 1
end

def test_set
@two[0,0,0] = 9
assert @two[0,0,0] == 9
end

def test_equality_grid
assert @two == Grid.new(2)
assert Grid.new(2).fold("R") == Grid.new(2).fold("R")
assert Grid.new(2).fold("RB") == Grid.new(2).fold("RB")
end

def test_equality_array
assert @two_folded_rb == [3,4,2,1]
end

def test_to_a
a = @two_folded_rb.to_a
assert a == [3,4,2,1],a
end

end

### Morus Walter

Jan 27, 2006, 2:10:19 AM1/27/06
to

Matthew Moss <matthew.m...@gmail.com> writes:
> 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

### Morus Walter

Jan 28, 2006, 2:06:51 AM1/28/06
to
In article <91b08b8a0601260742w321...@mail.gmail.com>,

David Tran <email...@gmail.com> writes:
> I wonder for 4x4 the total solution is 16 * 4! = 384
> My solution about check_fold is try to find all combinations possible.
> Below is modified version of my check_fold, it will print out all
> possible combinations and total count number.
> However I found for 4x4 there is only 96 possible not 384.
> Can someone tell me that I am wrong ( missing some combination ) or
> the previous math formula is not correct ?

96 is correct.
I'm not sure how the 16 * 4! formula was created but you can easily
see that it must be wrong since the total number of 4 letter strings
constisting of R/L/T/B is 4**4 = 256 (each of the 4 characters can take
one of 4 values; for n characters that would be 4**n) and that includes
invalid combinations such as TTTT.
So the right answer must be smaller than 256.
As already noted in a comment on Matthews summary post, I think the
correct number is

sum_i=0^n/2 sum_j=0^n/2 n! / i! / (n/2-i)! / j! / (n/2-j)!

for a 2^(n/2) x 2^(n/2) size grid.
This is a bit hard to read in ascii but the basic thought is, that there
must be n/2 letters R or L and n/2 letters T or B.
Now the number of R characters can be 0 up to n/2. Same for T.
For a given number i of Rs and j of Ts the number of permutations is
the number of permutations of n items divided by the number of permutations
of Rs, Ls, Ts and Bs. The total number of possibilites is the sum over
all possibilities for i and j.
Probably this can be rewritten to a simpler form.
I checked the calculation using the following ruby program (up to n=8).
The first part creates and counts all valid folding strings, the second
one calculates the above expression.

---
#! /usr/bin/ruby

n=8
n2=n/2

strs = [ "" ]
n.times do
strs = strs.collect do | str | [ str+'R', str+'L', str+'T', str+'B' ] end.flatten
end

strs.reject! do | str | str.count("RT") != n2 end

#puts strs
puts strs.size

def fak(n)
return 1 if n <= 1
return n*fak(n-1)
end

sum = 0
(0..n2).each do | i |
(0..n2).each do | j |
sum+= fak(n)/fak(i)/fak(n2-i)/fak(j)/fak(n2-j)
end
end
puts sum
---

Morus

### Morus Walter

Jan 28, 2006, 3:30:01 AM1/28/06
to
In article <bphra3-...@morus.walter.news.arcor.de>,

morus....@gmail.com (Morus Walter) writes:
> As already noted in a comment on Matthews summary post, I think the
> correct number is
> sum_i=0^n/2 sum_j=0^n/2 n! / i! / (n/2-i)! / j! / (n/2-j)!
> for a 2^(n/2) x 2^(n/2) size grid.
...

> Probably this can be rewritten to a simpler form.

It can:
Its n!/(n/2)!**2 * 2^n
(using 2^n = sum_i=0^n n! / i! / (n-i)!)

Now the remaining challenge is, if that can be seen directly without
calculation.
I guess one could argue:
The number of choices which positions will be used for vertical
folds (leaving the others for horizontal folds) is n over n/2 (n!/(n/2)**2).
And for each position there remain two possiblities (L/R or T/B) which
gives 2^n.
Strange that I didn't see that before doing the calculation...

Morus