Re: [QUIZ] Grid Folding (#63)
Matthew Moss
> 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
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
> 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
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
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
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
> 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
"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
Vladimir Agafonkin
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")
Vladimir Agafonkin
"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
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
Vladimir Agafonkin
very slow (3 times slower than the nearest neighbour) - I just tested
it on my machine along with others.
asplake
(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 ;-)
Vladimir Agafonkin
asplake
and if "preallocate" was the wrong word, I apologise!
Vladimir Agafonkin
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
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
Morus Walter
"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
Morus Walter
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
Chris Turner
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
hornd...@gmail.com
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
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!
David Tran
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
Edward Faulkner
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
David Tran
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
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
Bill Dolinar
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
Matthew Moss
> 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
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
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
David Tran
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
Andrew Dudzik
> 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
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
Mike Harris
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
Morus Walter
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
Morus Walter
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
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