#! /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

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.

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

Neat solution.  Thanks for the nice walkthrough.

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

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

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

#! /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]

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

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.

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

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