#63: Grid Folding


#1

Greetings all,

Attached is my solution. It uses nested arrays to simulate the 3-d
grid cells, and adds methods to Array to effect this. It handles
arbitrary rectangles of 2n by 2m. The unit tests provided earlier
pass.

I can’t help feeling there should be a direct numerical way to
calculate this sequence. To study the sequence, I wrote a second
script, also attached, that prints the bits of the resulting sequence
from any given rectangle dimensions and list of folds. (I subtract one
from the sequence to make it zero-based.) However, even with a fair
amount of studying lists of bit patterns I haven’t cracked the code.

Luke B.


#2

And here’s mine. I didn’t use a grid at all - working it out a cell at
a
time.

One key difference is that mine works out the dimensions from the
supplied
folds. It checks that the grid to be square (raises an exception
otherwise), but only to pass what might have been an over-zealous test
case.

Regards,
Mike


#3

Attached is my solution–I wish very much that I knew about
Array#transpose
when I wrote this. Seems to work, though, although check_fold takes
about 8
seconds on my zippy Pentium III 750MHz–some restructuring could improve
that. From my observations, given a permutation of (1…256), there
seems to
be at most one sequence of folds that gives that result. i.e. there are
never two sequences that give the same permutation. Does anybody know
why
this is? Seems like an interesting math problem.

I also really hacked together a get_dup method… how to you correctly
tell
classes how to make copies of themselves?


#4

On Jan 22, 2006, at 10:45 AM, Gregory S. wrote:

P.S. Yes, I did add a method to the Enumerable module. It’s
unnecessary,
but convenient and kind of cute.

module Enumerable

Lisp-y!

def cdr
return self[1…-1]
end
end

But it has the downside of making Enumerable depend on a method,
which it normally doesn’t require. :wink:

Neat solution. Thanks for the nice walkthrough.

James Edward G. II


#5

On Sun, Jan 22, 2006 at 10:55:44PM +0900, Luke B. wrote:
[…]
} I can’t help feeling there should be a direct numerical way to
} calculate this sequence. To study the sequence, I wrote a second
} script, also attached, that prints the bits of the resulting sequence
} from any given rectangle dimensions and list of folds. (I subtract
one
} from the sequence to make it zero-based.) However, even with a fair
} amount of studying lists of bit patterns I haven’t cracked the code.

In fact, there is a very nice direct numerical way to calculate it.
There
are a few key facts/insights:

  1. Everything should be done zero-based (instead of one-based) until the
    final output.

  2. Given a width 2**N, only the lowest N bits change as one moves across
    (horizontally) the grid.

  3. Given a height 2**M, only the highest M bits change as one moves down
    (vertically) the grid.

  4. With a current (i.e. after any folds) width 2**n, every
    newly-touching pair
    of numbers A and B are related by A == B ^ ((1<<n)-1) after a
    horizontal
    (L or R) fold

  5. With a current (i.e. after any folds) height 2m and initial width
    2
    N, every newly-touching pair of numbers A and B are related by
    A == B ^ (((1<<m)-1)<<N) after a vertical (T or B) fold.

  6. The sequence of XOR operations that relate pairs of touching numbers
    is
    a palindrome at any given moment.

  7. The XOR sequence generated by a fold is the old sequence, then the
    XOR
    value for the newest fold, then the old sequence again.

Thus, all we have to do is be able to generate the XOR value for a
particular fold (#4 & #5), generate the new sequence from that and the
old
sequence (#7), keep track of where in the sequence the zero value is,
and
keep track of whether the zero value is “face up” or “face down.”

You take the final sequence and generate the actual numbers by XORing
along
the sequence backward and forward from zero. Depending on whether zero
is
face up or not, you may have to reverse the list of numbers. You then
add
one to each number to get the one-based values instead of zero-based
values.

Note that this solution works for any width and height that are powers
of
two, and need not be square. In addition, it could be trivially extended
to
three or more dimensions. The code is below.

} Luke B.
–Greg
P.S. Yes, I did add a method to the Enumerable module. It’s unnecessary,
but convenient and kind of cute.

test63.rb

################################################################

require ‘63’

fail "Usage: #{FILE} " if ARGV.length
!= 3
g = Grid.new(ARGV[0].to_i, ARGV[1].to_i)
p g.fold(ARGV[2])

63.rb

####################################################################

module Enumerable

Lisp-y!

def cdr
return self[1…-1]
end
end

module GridFolding

Opposite = {
“L” => “R”,
“R” => “L”,
“T” => “B”,
“B” => “T”
}

IsXFold = {
“L” => true,
“R” => true,
“T” => false,
“B” => false
}

def validate_dims(x, y)
fail “x dimension must be at least 1” if x < 1
fail “y dimension must be at least 1” if y < 1
xbits = x.to_s(2).cdr
ybits = y.to_s(2).cdr
fail “x dimension must be a power of 2” if xbits.count(“1”) != 0
fail “y dimension must be a power of 2” if ybits.count(“1”) != 0
return [xbits.length, ybits.length]
end

def validate_folds(folds)
x_folds = folds.count(“L”) + folds.count(“R”)
y_folds = folds.count(“T”) + folds.count(“B”)
if folds.length != (x_folds + y_folds)
fail “Invalid characters in fold string”
else
if x_folds < @x_foldable
fail “Too few x folds”
elsif x_folds > @x_foldable
fail “Too many x folds”
end
if y_folds < @y_foldable
fail “Too few y folds”
elsif y_folds > @y_foldable
fail “Too many y folds”
end
end
return folds.split(//)
end

end

class Grid

def initialize(x, y)
@x_foldable, @y_foldable = validate_dims(x, y)
end

def fold(fold_str)
folds = validate_folds(fold_str.upcase)
zero_corner = [“T”, “L”]
zero_slice = 0
operations = []
width = @x_foldable
height = @y_foldable
folds.each { |f|
if not zero_dir(zero_corner)
zero_slice += operations.length + 1
end
if zero_corner[0] == f
zero_corner[0] = Opposite[f]
elsif zero_corner[1] == f
zero_corner[1] = Opposite[f]
end
temp_ops = operations.clone()
op = 0
if IsXFold[f]
op = (1 << width) - 1
width -= 1
else
op = ((1 << height) - 1) << @x_foldable
height -= 1
end
operations << op
operations << temp_ops
operations.flatten!
}
below_zero = operations[0…zero_slice].reverse
above_zero = operations[zero_slice…-1]
curval = 0
below_zero.map! { |n| (curval ^= n) + 1 }
curval = 0
above_zero.map! { |n| (curval ^= n) + 1 }
list = []
if zero_dir(zero_corner)
list << above_zero.reverse
list << 1
list << below_zero
else
list << below_zero.reverse
list << 1
list << above_zero
end
return list.flatten!
end

private
include GridFolding

#true is up
def zero_dir(zero_corner)
not ((zero_corner[0]==“T”) ^ (zero_corner[1]==“L”))
end
end

vim:ts=2 sw=2 ai expandtab foldmethod=syntax foldcolumn=5


#6

Hi,

i hope there is something new in my solution. Rather than folding my
solution unfolds and keeps track of the position of a certain layer. It
starts with a 1x1 stack of paper and undos all cmds that leed to this
stack (doubling the size of the paper each step). Doing this for every
layer of the stack gives the solution to this quiz. (no arrays,
matrixes, etc. needed except for returning the result)


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

def fold xsize, ysize, cmds
raise RuntimeError if cmds.scan(/[^RLBT]/).size.nonzero?
raise RuntimeError if 2cmds.scan(/[RL]/).size != xsize
raise RuntimeError if 2
cmds.scan(/[BT]/).size != ysize

(1…(xsize * ysize)).map{|z| unfold(z, cmds)}.reverse
end

puts fold(16, 16, ‘TLBLRRTB’)

cheers

Simon


#7

That’s a neat way to go about it. That’s how I wrote my
check_fold–exploring backwards from the final stack, and throwing out
paths
that were obviously wrong–but I never thought of implementing the
entire
thing using backwards folds.


#8

My solution.

#! /usr/bin/env ruby

def fold row_siz, cmds

paper is an array of layers,

each layer is an array of rows,

each row is an array of integers

paper = []
layer = []
1.upto(row_siz){|i|
row = []
1.upto(row_siz){|j| row << j + row_siz*(i-1)}
layer << row
}
paper = [ layer ]

nfold = (Math.log(row_siz)/Math.log(2)) # Number of folds each
direction

validate inputs

raise “Array size not a power of 2” unless 2**nfold == row_siz
raise “Invalid cmd length” unless cmds.length == nfold * 2
raise “Invalid fold chars” unless cmds.scan(/[TBLR]/).length == nfold

  • 2
    raise “Invalid fold list” unless cmds.scan(/[TB]/).length == nfold

    cmds.split(//).each{|f|
    new_paper = []
    case f
    when ‘L’,‘R’
    row_siz = paper[0][0].length/2
    s1, s2 = (f == ‘L’) ? [0,row_siz] : [row_siz,0]
    paper.reverse.each { |layer|
    new_layer = []
    layer.each {|row|
    new_layer << row.slice(s1,row_siz).reverse
    }
    new_paper << new_layer
    }
    paper.each { |layer|
    new_layer = []
    layer.each {|row|
    new_layer << row.slice(s2,row_siz)
    }
    new_paper << new_layer
    }
    when ‘T’,‘B’
    col_siz = paper[0].length/2
    s1, s2 = (f == ‘T’) ? [0,col_siz] : [col_siz,0]
    paper.reverse.each { |layer|
    new_paper << layer.slice(s1,col_siz).reverse
    }
    paper.each { |layer|
    new_paper << layer.slice(s2, col_siz)
    }
    end
    paper = new_paper
    }
    return paper.flatten
    end

def usage
puts “Usage #{File.basename($0)} "
puts " grid sz must be power of 2”
puts " valid fold are T, B, R, L"
puts " you must have enough folds to get NxN to 1x1"
exit
end

usage unless ARGV.length == 2

row_siz = ARGV[0].to_i
cmds = ARGV[1]

res = fold(row_siz, cmds)
puts “RES”
puts “[ #{res.join(’, ')} ]”


#9

Of four solutions submitted so far, Luke’s performs the best (2 times
better than the nearest neighbour - mine) - and the code is very clear
and easy to understand for a newbie like me. Great work!


#10

Here’s mine. I use arrays within arrays as well. I wrote my own loops
to do the folding. I see now I could have done it much more
succinctly. I went for all the extra credit. Can unfold by noticing
the last element of the array hasn’t been folded over and the first
element was previously unfolded. The direction from the first to the
last element gives the fold direction. Then just keep cutting off the
first part of the array.

#! /usr/bin/env ruby -w

=begin
Manages the matrix of values for folding:
[[1], [2],
[3], [4]]

left_fold returns new matrix:
[[1, 2],
[3, 4]]
=end
class FoldMatrix

attr_reader :values

def initialize(values, rows, cols)
@rows = rows
@cols = cols
@values = values
end

Fold left side of matrix over to right returning new FoldMatrix

def left_fold
fold(:left)
end

Fold right side of matrix over to left returning new FoldMatrix

def right_fold
fold(:right)
end

Fold top of matrix down and return new FoldMatrix

def top_fold
fold(:top)
end

Fold bottom of matrix up and return new FoldMatrix

def bottom_fold
fold(:bottom)
end

Return the result of folding in flattened array

def result
if (@rows != 1 && @cols != 1)
raise ArgumentError, “Paper not completely folded”
end

@values.flatten

end

private

Return a matrix element

def array_element(i, j)
@values[i*@cols + j]
end

Iterate through items in array by folded direction where direction

is one of :left, :right, :top, :bottom. Iterates going left to

right then down. Values are already in proper order top to

bottom.

Example:

each_by_fold do |top, bottom|

new_cell_value = top + bottom

end

def each_by_fold(fold)
# make sure there are enough rows or columns to fold
case fold
when :left, :right
if @cols <= 1
raise ArgumentError,
“Attemting to fold to #{fold.to_s} with only 1 column”
end
when :top, :bottom
if @rows <= 1
raise ArgumentError,
“Attemting to fold to #{fold.to_s} with only 1 row”
end
end

# setup loop boundaries to loop through unfolded part of page
case fold
  when :left
    row_start = 0
    row_end = @rows - 1
    col_start = @cols/2
    col_end = @cols - 1
  when :right
    row_start = 0
    row_end = @rows - 1
    col_start = 0
    col_end = @cols/2 - 1
  when :top
    row_start = @rows/2
    row_end = @rows - 1
    col_start = 0
    col_end = @cols - 1
  when :bottom
    row_start = 0
    row_end = @rows/2 - 1
    col_start = 0
    col_end = @cols - 1
end

# loop through row by row reversing items folded to top
row_start.upto(row_end) do |i|
  col_start.upto(col_end) do |j|
    case fold
    when :left, :right
      top = array_element(i, @cols - j - 1).reverse
      bottom = array_element(i, j)
    when :top, :bottom
      top = array_element(@rows - i - 1, j).reverse
      bottom = array_element(i, j)
    end
    yield(top, bottom)
  end
end

end

Return a new fold matrix by folding in direction where direction

is one of :left, :right, :top, :bottom.

def fold(direction)
new_values = []
each_by_fold(direction) do |top, bottom|
new_values << top + bottom
end

case direction
  when :left, :right
    new_cols = @cols/2
    new_rows = @rows
  when :top, :bottom
    new_cols = @cols
    new_rows = @rows/2
end
FoldMatrix.new(new_values, new_rows, new_cols)

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

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, rows, cols)
unfolded -= 1
unfolded_i = unfolded / cols
unfolded_j = unfolded % cols

folded -= 1
folded_i = folded / cols
folded_j = folded % cols

case
when unfolded_i == folded_i && unfolded_j < folded_j
:right
when unfolded_i == folded_i && unfolded_j > folded_j
:left
when unfolded_j == folded_j && unfolded_i < folded_i
:bottom
when unfolded_j == folded_j && unfolded_i > folded_i
:top
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

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)

build array of values

values = []
1.upto(rows*cols) do |i|
values << [i]
end

fold_matrix = FoldMatrix.new(values, rows, cols)

directions.each_byte do |fold_direction|
case fold_direction
when ?T
fold_matrix = fold_matrix.top_fold
when ?B
fold_matrix = fold_matrix.bottom_fold
when ?L
fold_matrix = fold_matrix.left_fold
when ?R
fold_matrix = fold_matrix.right_fold
else
raise ArgumentError, “Invalid direction #{fold_direction}”
end
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.

Therefore…

while size of array is greater than 1

get direction in original matrix from last item number

in folded array to first

push direction on front of directions

cut off front half of array

end

Throws ArgumentError on array not in fold order or rows or cols not

power of 2.

def check_fold(folded, rows=16, cols=16)
check_rows_and_cols(rows, cols)

directions = “”
while folded.size > 1
# get direction in original matrix from last to first
direction = direction_to(folded.last, folded.first, rows, cols)

# and push it on front of directions
case direction
  when :top
    directions = "T" + directions
  when :bottom
    directions = "B" + directions
  when :left
    directions = "L" + directions
  when :right
    directions = "R" + directions
end

# cut array in half
folded = folded[folded.size/2...folded.size]

end
directions
end

if FILE == $0
if (ARGV.size == 1 || ARGV.size == 3)
if (ARGV.size == 3)
rows = ARGV[1].to_i
cols = ARGV[2].to_i
else
rows = 16
cols = 16
end
p fold(ARGV[0], rows, cols)
else
puts “Usage: #$0 folds [rows cols]”
end
end


#11

Hello all,

Here’s my solution. It’s not terribly efficient (uses arrays of
arrays), but the algorithm should be pretty easy to read.

Cheers,

-Nathan

module Folding

def fold(h, w, commands)
page = Page.new_page_of_size(h, w)
commands.downcase.scan(/./).each do |command|
raise “Invalid input!” if page.invalid_command?(command)
page = page.send(“fold_#{command}”.to_sym)
end
raise “Invalid input!” if !page.is_one_cell?
page.first_cell
end

end

class Page

def self.new_page_of_size(h, w)
Page.new(create_page_map(h, w))
end

def height
@page_map.size
end

def width
@page_map.first.size
end

def fold_r
new_map = (1…height).inject([]) {|r, i| r << [] }
0.upto(height - 1) do |r|
0.upto(width / 2 - 1) do |c|
head = @page_map[r][c]
tail = @page_map[r][width - c - 1].reverse
new_map[r][c] = tail + head
end
end
Page.new(new_map)
end

def fold_l
turn_180.fold_r.turn_180
end

def fold_t
turn_cw.fold_r.turn_ccw
end

def fold_b
turn_ccw.fold_r.turn_cw
end

def turn_cw
new_map = (1…width).inject([]) {|r, i| r << [] }
0.upto(height - 1) do |r|
0.upto(width - 1) do |c|
new_map[c][height - r - 1] = @page_map[r][c]
end
end
Page.new(new_map)
end

def turn_ccw
turn_180.turn_cw
end

def turn_180
turn_cw.turn_cw
end

def invalid_command?©
height == 1 && (c == ‘t’ || c == ‘b’) ||
width == 1 && (c == ‘l’ || c == ‘r’)
end

def is_one_cell?
height == 1 && width == 1
end

def first_cell
@page_map[0][0]
end

private

def initialize(map)
@page_map = map
end

def self.create_page_map(h, w)
(1…h).inject([]) do |page, i|
page << (1…w).inject([]) do |row, j|
row << [w*(i-1) + j]
end
end
end

end


#12

Here is mine.

It supports square grids of all size, the size is “autodetected” from
the
length of the fold string.

Dominik

A simple 2D array, the width and height are immutable once it is

created.
class Array2D
attr_reader :w, :h
def initialize(w, h, init_array = nil)
@w, @h=w, h
@array = init_array || []
end
def [](x, y)
@array[(y%h)*w+(x%w)]
end
def []=(x, y, v)
@array[(y%h)*w+(x%w)]=v
end
end

class GridFold
attr_reader :grid

 # the initial grid will be (2**n)x(2**n)
 def initialize(n = 4)
     d = 1 << n
     @grid = Array2D.new(d, d, (1..(d*d)).map { |i| [i] })
 end

 def fold_t
     fold_help(@grid.w, @grid.h / 2) { |x, y, _, nh|
         @grid[x, nh-1-y].reverse + @grid[x, nh+y]
     }
 end
 def fold_b
     fold_help(@grid.w, @grid.h / 2) { |x, y, _, _|
         @grid[x, @grid.h-1-y].reverse + @grid[x, y]
     }
 end
 def fold_l
     fold_help(@grid.w / 2, @grid.h) { |x, y, nw, _|
         @grid[nw-1-x, y].reverse + @grid[nw+x, y]
     }
 end
 def fold_r
     fold_help(@grid.w / 2, @grid.h) { |x, y, _, _|
         @grid[@grid.w-1-x, y].reverse + @grid[x, y]
     }
 end

 def self.fold(folds_str)
     folds = folds_str.to_s.downcase
     n = folds.size / 2
     unless folds =~ /\A[tblr]*\z/ && folds.size == n * 2
         raise "invalid argument"
     end
     gf = self.new(n)
     folds.scan(/./) { |f| gf.send("fold_#{f}") }
     gf.grid[0, 0]
 end

 private

 def fold_help(new_width, new_height)
     raise "impossible" unless new_width >= 1 && new_height >= 1
     new_grid = Array2D.new(new_width, new_height)
     new_width.times { |x| new_height.times { |y|
         new_grid[x, y] = yield x, y, new_width, new_height
     } }
     @grid = new_grid
     self
 end

end

if $0 == FILE
begin
p GridFold.fold(ARGV.shift.to_s)
rescue => e
warn e
exit 1
end
end


#13

Vladimir A. wrote:

Of four solutions submitted so far, Luke’s performs the best (2 times
better than the nearest neighbour - mine) - and the code is very clear
and easy to understand for a newbie like me. Great work!

Wow, that’s excellent. I would have thought that the prepending
(“unshift”) I do would have slowed things down. But I do reuse all the
arrays wherever possible, and that probably makes the difference.

Now I’m working on a variant of Greg Seidman’s approach. It should be
lots faster yet, but the tradeoff is it’s much less clear.

Luke


#14

Brilliant idea, Simon! Though it’s somewhat slow comparing to other
solutions, I guess it has a very low memory consumption instead.

Still, my favourite is Sander’s - very simple and short and still quite
performant.

Gregory’s solution is the fastest (and thats great), however, it is too
big and complicated for only a ~100% performance boost over Sander’s,
IMHO.


#15

Good, though your solution is still not THAT slower then Greg’s:

C:\eclipse\workspace\quizes\other>fold_luke.rb
Each operation will run 1000 times.
2x2 sheet folding done in 0.2 seconds
4x4 sheet folding done in 0.491 seconds
8x8 sheet folding done in 1.282 seconds
16x16 sheet folding done in 3.915 seconds

C:\eclipse\workspace\quizes\other>fold_greg.rb
Each operation will run 1000 times.
2x2 sheet folding done in 0.381 seconds
4x4 sheet folding done in 0.581 seconds
8x8 sheet folding done in 1.071 seconds
16x16 sheet folding done in 2.744 seconds

PS: I tried using memoize library to evaluate the performance boost,
and the results are quite interesting:

(with memoize)
Each operation will run 1000 times.
2x2 sheet folding done in 0.02 seconds
4x4 sheet folding done in 0.01 seconds
8x8 sheet folding done in 0.02 seconds
16x16 sheet folding done in 0.03 seconds
32x32 sheet folding done in 0.04 seconds
64x64 sheet folding done in 0.1 seconds
128x128 sheet folding done in 0.341 seconds
256x256 sheet folding done in 1.372 seconds

(without)
Each operation will run 1000 times.
2x2 sheet folding done in 0.241 seconds
4x4 sheet folding done in 0.56 seconds
8x8 sheet folding done in 1.703 seconds
16x16 sheet folding done in 5.818 seconds
(didn’t go further, the things are already clear enough)


#16

Gregory S. wrote:

are a few key facts/insights: …

I see your insights, and raise you a couple.

* If you associate the XOR masks with the folds, ie arranging them
  in an array whose size is the number of folds, then you can choose
  which mask to use for a given output element by indexing into this
  array.  The order of these indexes is like this: 0, 1, 0, 2, 0, 1,
  0, 3, 0, 1, ...  If this looks familiar, it is because it is
  related to counting in binary arithmetic.
* The folds quickly and easily determine the bottom grid square:
  just translate them to bits, with the forward folds (T and L)
  being 1 and backwards ones being 0, and then arrange the bits with
  the vertical folds' bits on top.
* The XOR of the first and last elements of the answer is the last
  mask in our array of masks.

With all of this, I have a solution that generates the output in
sequence without any simulation of folding, or generating extraneous
arrays. And it was easy to turn this into an unfolder as well.

The downside is that it is just as long as my original solution, and it
is completely incomprehensible. But I bet it’s plenty fast!

Luke B.