[QUIZ][SOLUTION] Grid Folding (#63)

ruby-talk
1

def fold(row, col, operations)

  def t2b(table)
    t1 = table[0...table.size/2].reverse
    t2 = table[table.size/2..-1]
    row = t1.size
    col = t1[0].size
    row.times { |r| col.times { |c| t2[r][c] = t1[r][c].reverse + t2[r][c] } }
    t2
  end

  def b2t(table)
    t2b(table.reverse).reverse
  end

  def l2r(table)
    t2b(table.transpose).transpose
  end

  def r2l(table)
    t2b(table.transpose.reverse).reverse.transpose
  end

  if row <= 1 ||
     col <= 1 ||
     2**operations.size != row * col ||
     operations =~ /[^TBLR]/ ||
     2**operations.gsub(/[LR]/,'').size != row
    raise "Error: parameters are not correct."
  end

  index = 0
  table = Array.new(row) { Array.new(col) { [index += 1] } }

  operations.each_byte do |op|
    table = case op
      when ?T : t2b(table)
      when ?B : b2t(table)
      when ?L : l2r(table)
      when ?R : r2l(table)
      else raise "Error: Invalid fold operation."
    end
  end

  table[0][0]
end

···

#========================================================================#

def check_fold(row, col, result)

  # find all combinations with binary 0 for row and 1 for column operation
  def all_orders(r, c) #
    return [2**c - 1] if (r <= 0) # c bits of 1 is 2**c-1
    return [0] if (c <= 0) # r bits of 0 is 0
    table = []
    all_orders(r-1,c).each { |t| table << ((t << 1) + 0) }
    all_orders(r,c-1).each { |t| table << ((t << 1) + 1) }
    table
  end

  if row <= 1 ||
     col <= 1 ||
     row * col != result.size ||
     2 ** (Math.log(row)/Math.log(2)).to_i != row ||
     2 ** (Math.log(col)/Math.log(2)).to_i != col
    raise "Error: Parameters are not correct."
  end

  r = Integer(Math.log(row) / Math.log(2))
  c = Integer(Math.log(col) / Math.log(2))
  all_rc_orders = all_orders(r,c)

  row.times do |tb_operation|
    col.times do |lr_operation|
      all_rc_orders.each do |order|
        operations = ''
        tb_op = tb_operation
        lr_op = lr_operation
        (r+c).times do
          if (order & 1 == 0)
            operations += (tb_op & 1 == 0) ? 'T' : 'B'
            tb_op >>= 1
          else
            operations += (lr_op & 1 == 0) ? 'L' : 'R'
            lr_op >>= 1
          end
          order >>= 1
        end
        return operations if fold(row, col, operations) == result
      end
    end
  end
  "No solution."
end

2

This is the kind of problem where it makes sense to trade off
efficiency for simplicity.

class Paper
  def initialize(width, height)
    @grid = Array.new(width) { Array.new(height) }
    height.times { |y| width.times {|x| @grid[x][y] = [width*y+x+1] }}
  end

  def width; @grid.size; end
  def height; @grid[0].size; end

  def answer
    raise "Not enough folds" if width > 1 or height > 1
    @grid[0][0]
  end

  # Fold right side over to left
  def fold!
    raise "Bad input" if width%2 == 1
    @grid = (0 .. (width / 2 - 1)).map { |col|
      @grid[col].zip(@grid[width - col - 1]).map {|pair| pair[1].reverse + pair[0]}
    }
  end

  # 90 degree counter clockwise rotation
  def rotate!
    @grid = @grid.transpose.map{|c| c.reverse}
  end
end

def fold(width, height, commands)
  turns = commands.tr('RBLT', '0123').split(//).map{|x| x.to_i}
  paper = Paper.new(width, height)
  turns.each { |turn|
    4.times {|i|
      paper.fold! if i==turn
      paper.rotate!
    }
  }
  paper.answer
end

3

Correction:
found a little bug on my script.
The checking row <= 1 || col <= 1 is "too much".
These two checking should remove,
because it fail for doing something like fold( 1, 2, 'L' )

···

On 1/23/06, David Tran <email55555@gmail.com> wrote:

def fold(row, col, operations)

  def t2b(table)
    t1 = table[0...table.size/2].reverse
    t2 = table[table.size/2..-1]
    row = t1.size
    col = t1[0].size
    row.times { |r| col.times { |c| t2[r][c] = t1[r][c].reverse + t2[r][c] } }
    t2
  end

  def b2t(table)
    t2b(table.reverse).reverse
  end

  def l2r(table)
    t2b(table.transpose).transpose
  end

  def r2l(table)
    t2b(table.transpose.reverse).reverse.transpose
  end

  if row <= 1 ||
     col <= 1 ||
     2**operations.size != row * col ||
     operations =~ /[^TBLR]/ ||
     2**operations.gsub(/[LR]/,'').size != row
    raise "Error: parameters are not correct."
  end

  index = 0
  table = Array.new(row) { Array.new(col) { [index += 1] } }

  operations.each_byte do |op|
    table = case op
      when ?T : t2b(table)
      when ?B : b2t(table)
      when ?L : l2r(table)
      when ?R : r2l(table)
      else raise "Error: Invalid fold operation."
    end
  end

  table[0][0]
end

#========================================================================#

def check_fold(row, col, result)

  # find all combinations with binary 0 for row and 1 for column operation
  def all_orders(r, c) #
    return [2**c - 1] if (r <= 0) # c bits of 1 is 2**c-1
    return [0] if (c <= 0) # r bits of 0 is 0
    table =
    all_orders(r-1,c).each { |t| table << ((t << 1) + 0) }
    all_orders(r,c-1).each { |t| table << ((t << 1) + 1) }
    table
  end

  if row <= 1 ||
     col <= 1 ||
     row * col != result.size ||
     2 ** (Math.log(row)/Math.log(2)).to_i != row ||
     2 ** (Math.log(col)/Math.log(2)).to_i != col
    raise "Error: Parameters are not correct."
  end

  r = Integer(Math.log(row) / Math.log(2))
  c = Integer(Math.log(col) / Math.log(2))
  all_rc_orders = all_orders(r,c)

  row.times do |tb_operation|
    col.times do |lr_operation|
      all_rc_orders.each do |order|
        operations = ''
        tb_op = tb_operation
        lr_op = lr_operation
        (r+c).times do
          if (order & 1 == 0)
            operations += (tb_op & 1 == 0) ? 'T' : 'B'
            tb_op >>= 1
          else
            operations += (lr_op & 1 == 0) ? 'L' : 'R'
            lr_op >>= 1
          end
          order >>= 1
        end
        return operations if fold(row, col, operations) == result
      end
    end
  end
  "No solution."
end

--
www.doublegifts.com

4

Cleaned up the code in my previous solution. Made check_fold not copy the array and instead just index into the array passed. Completely changed FoldMatrix to use 3-d array and operations that make it more readable like split, flip, and place over.

#! /usr/bin/env ruby -w

require 'enumerator'

# 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)
   if (directions =~ /[^TLBR]/)
     raise ArgumentError, "Invalid direction given"
   end

   # build array of values
   # using each_slice as described by Levin Alexander
   values = (1..rows*cols).to_enum(:each_slice, 1).to_a
   values = values.to_enum(:each_slice, cols).to_a

   fold_matrix = FoldMatrix.new(values)

   directions.split(//).each do |direction|
     fold_matrix.fold(direction)
   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.
# Can iterate through last folded by continually cutting array in
# half. Throws ArgumentError on array not in fold order or rows or
# cols not power of 2.
def check_fold(fold_result, rows=16, cols=16)
   check_rows_and_cols(rows, cols)

   directions = ""
   folded = 0
   size = fold_result.size
   while folded < fold_result.size - 1
     # get direction in original matrix from last to first
     directions << direction_to(fold_result.last, fold_result[folded], cols)

     # move to next item last folded
     size = size/2
     folded += size
   end
   directions.reverse
end

class FoldMatrix

   attr_reader :values

   def initialize(values)
     @values = values
   end

   # Return a new fold matrix by folding in direction where direction
   # is one of :left, :right, :top, :bottom.
   def fold(direction)
     case direction
       when "L"
         left, @values = split_along_v
         flip_along_v(left)
         place_over(left)
       when "R"
         @values, right = split_along_v
         flip_along_v(right)
         place_over(right)
       when "T"
         top, @values = split_along_h
         flip_along_h(top)
         place_over(top)
       when "B"
         @values, bottom = split_along_h
         flip_along_h(bottom)
         place_over(bottom)
     end
   end

   # Return the result of folding in flattened array
   def result
     if (@values.size != 1 && @values[0].size != 1)
       raise ArgumentError, "Paper not completely folded"
     end
     @values.flatten
   end

protected

   def split_along_v
     left = []
     right = []
     cols = @values[0].size
     @values.each do |row|
       left << row[0...cols/2]
       right << row[cols/2...cols]
     end
     return left, right
   end

   def split_along_h
     rows = @values.size
     top = @values[0...rows/2]
     bottom = @values[rows/2...rows]
     return top, bottom
   end

   def flip_along_v(a)
     a.each do |row|
       row.reverse!
       row.each {|item| item.reverse!}
     end
   end

   def flip_along_h(a)
     a.reverse!
     a.each {|row| row.each {|item| item.reverse!}}
   end

   def place_over(top)
     top.each_with_index do |row, i|
       row.each_with_index do |item, j|
         @values[i][j] = item + @values[i][j]
       end
     end
   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

def coordinate(index, cols)
   index -= 1
   i, j = index/cols, index%cols
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, cols)
   unfolded_i, unfolded_j = coordinate(unfolded, cols)
   folded_i, folded_j = coordinate(folded, cols)

   i_compare = unfolded_i <=> folded_i
   j_compare = unfolded_j <=> folded_j

   case [i_compare, j_compare]
     when [ 0, 1] then "L"
     when [ 0, -1] then "R"
     when [ 1, 0] then "T"
     when [-1, 0] then "B"
     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