From: Gregory Seidman <gsslist+ruby@...>
Date: 2006-01-23T01:45:39+09:00
Subject: Re: [/QUIZ] #63: Grid Folding

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