17 views

Skip to first unread message

Jan 22, 2006, 8:55:44 AM1/22/06

to

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 2**n by 2**m. 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 Blanshard

Jan 22, 2006, 9:32:49 AM1/22/06

to

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

Jan 22, 2006, 9:45:59 AM1/22/06

to

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.

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

Jan 22, 2006, 10:23:48 AM1/22/06

to

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!

better than the nearest neighbour - mine) - and the code is very clear

and easy to understand for a newbie like me. Great work!

Jan 22, 2006, 11:45:39 AM1/22/06

to

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.

[...]

} 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

Jan 22, 2006, 12:49:02 PM1/22/06

to

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?

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

Jan 22, 2006, 1:35:00 PM1/22/06

to

On Jan 22, 2006, at 10:45 AM, Gregory Seidman 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. ;)

Neat solution. Thanks for the nice walkthrough.

James Edward Gray II

Jan 22, 2006, 1:40:56 PM1/22/06

to

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

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

Jan 22, 2006, 2:13:25 PM1/22/06

to

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 2**cmds.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

Jan 22, 2006, 2:51:27 PM1/22/06

to

Brilliant idea, Simon! Though it's somewhat slow comparing to other

solutions, I guess it has a very low memory consumption instead.

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.

Jan 22, 2006, 2:50:45 PM1/22/06

to

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)} <grid sz> <fold list>"

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(', ')} ]"

Jan 22, 2006, 2:56:21 PM1/22/06

to

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.

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.

Jan 24, 2006, 4:56:07 PM1/24/06

to

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

Jan 24, 2006, 7:17:23 PM1/24/06

to

Vladimir Agafonkin wrote:

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

Jan 24, 2006, 8:24:17 PM1/24/06

to

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)

Jan 25, 2006, 7:42:31 AM1/25/06

to

Gregory Seidman wrote:

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

>

>

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 Blanshard

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu