From: Bill.Dolinar@...
Date: 2006-01-25T00:42:21+09:00
Subject: Re: [/QUIZ] #63: Grid Folding

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