```On Sun, Jan 22, 2006 at 10:55:44PM +0900, Luke Blanshard 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 2**m 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 Blanshard
--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__} <width> <height> <fold string>" 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

```