21 views

Skip to first unread message

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?

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

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.

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)

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

> 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

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

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

>

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.

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.

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

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.

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

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

to

In article <1137873033.0...@g49g2000cwa.googlegroups.com>,

"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 :-)

"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!).

>

> 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])[0]),

(@origin[i])[1]]

@layers[2*len-i-1] = [(@layers[i])[0], (@layers[i])[1]]

if (@origin[i])[0] == :bottom: (@layers[2*len-i-1])[0] +=

@rows

else (@layers[i])[0] += @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])[0],

opposite((@origin[i])[1])]

@layers[2*len-i-1] = [(@layers[i])[0], (@layers[i])[1]]

if (@origin[i])[1] == :right: (@layers[2*len-i-1])[1] += @cols

else (@layers[i])[1] += @cols; end

end

@layers.reverse! if char=="R"

end

end

@layers.each {|coord| @order << coord[0]*@dim+coord[1]+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.

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.

very slow (3 times slower than the nearest neighbour) - I just tested

it on my machine along with others.

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

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

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!

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.

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.

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.

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[0].length == 1

return grid[0][0]

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

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

to

In article <1137943343.6...@g47g2000cwa.googlegroups.com>,

"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

of the task.

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

>

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

of the task.

Morus

Jan 22, 2006, 12:24:50 PM1/22/06

to

In article <1137942795....@g43g2000cwa.googlegroups.com>,502.175 (~90 for the 1024x1024 and 411 for the 2048x2048)

on a AMD Athlon XP 1600+ (1400 MHz).

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

attr_reader :width, :height, :depth

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[0].size

@height = sheet.size

@depth = sheet[0][0].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[0][0].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[0]

cmds = ARGV[0]

width = (ARGV[1] || 16).to_i

height = (ARGV[2] || width).to_i

digits = (Math.log(width*height)/Math.log(10)).ceil

puts fold(width, height, cmds).collect { | i | "%#{digits}d" % i }.join(", ")

end

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.

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

Marshal::load(Marshal.dump(self))

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

attr_reader :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[0][0]

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[0].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[0].size % 2 != 0)

raise "Must be foldable" if @paper.size != 1 && @paper[0].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[0].size == 1

end

end

end

def fold(command, size=16)

Paper.new(size).fold(command)

end

if __FILE__ == $0

paper_size = ARGV[0] || 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[0].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][0] != (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[0].size % 2 != 0)

raise "Must be foldable" if @paper.size != 1 && @paper[0].size != 1

end

raise "Already unfolded" if (@paper[0][0].size == 1)

end

end

def check_fold(ary)

raise "Invalid solution" unless ary.size.power_of_2?

answer_size = Math.sqrt(ary.size).to_i

paper = Paper.new(answer_size).reset_to([[ary.deep_dup]])

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

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?

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

Jan 22, 2006, 11:21:15 PM1/22/06

to

My solution is at

http://users.adelphia.net/~showaltb/rubyquiz/63/fold.rb, made without

peeking at other solutions.

http://users.adelphia.net/~showaltb/rubyquiz/63/fold.rb, made without

peeking at other solutions.

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

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[0].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[0][0]

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 [0] 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

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.

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[0].size; end

def answer

raise "Not enough folds" if width > 1 or height > 1

@grid[0][0]

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[1].reverse + pair[0]}

}

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!

}

}

paper.answer

end

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

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

Jan 23, 2006, 3:12:31 PM1/23/06

to

In article <2orca3-...@morus.walter.news.arcor.de>,

morus....@gmail.com (Morus Walter) writes:

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[0]

dirs = ARGV[0]

width = (ARGV[1] || 16).to_i

height = (ARGV[2] || 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[1]);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[0]

dirs = ARGV[0]

width = (ARGV[1] || 16).to_i

height = (ARGV[2] || width).to_i

res = fold(width, height, dirs)

puts res.join(", ")

end

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.

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

attr_reader :values

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[0].size != 1)

raise ArgumentError, "Paper not completely folded"

end

@values.flatten

end

protected

def split_along_v

left = []

right = []

cols = @values[0].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]

return top, bottom

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

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.

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

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.

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.

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

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 [0] 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

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

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

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

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.

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[1] >= cols.middle }.each { |k|

self[k[0],cols.flip(k[1]),vert.flip_doubled(k[2])] = @cells[k];

@cells.delete(k) } if str == "R"

@cells.keys.find_all { |k| k[1] < cols.middle }.each { |k|

self[k[0],cols.flip(k[1]),vert.flip_doubled(k[2])] = @cells[k];

@cells.delete(k) } if str == "L"

@cells.keys.find_all { |k| k[0] >= rows.middle }.each { |k|

self[rows.flip(k[0]),k[1],vert.flip_doubled(k[2])] = @cells[k];

@cells.delete(k) } if str == "B"

@cells.keys.find_all { |k| k[0] < rows.middle }.each { |k|

self[rows.flip(k[0]),k[1],vert.flip_doubled(k[2])] = @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[0],k[1],k[2]] = @cells[k]

end

g

end

def ==(g)

return to_a == g if g.kind_of? Array

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[2] <=> a[2]; (x = a[0] <=> b[0]) if

x==0; (x = a[1] <=> b[1]) 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

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

to

In article <381ad2d20601252152u778...@mail.gmail.com>,

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

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.

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

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 ?

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

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.

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu