From: Luke Blanshard <luke@...>
Date: 2006-01-25T21:42:31+09:00
Subject: Re: [/QUIZ] #63: Grid Folding

--------------090700010508010409000101
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

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

--------------090700010508010409000101
Content-Type: text/plain;
 name="fold2.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="fold2.rb"

#!/usr/bin/ruby -w
#
# Ruby Quiz #63, Grid Folding, take 2

# Creates XOR masks for the folds, generates the sequence directly.
def fold2 h, v, folds
  hbits, vbits = folds.count("LR"), folds.count("TB")
  raise "Illegal folds #{folds}" unless hbits+vbits == folds.length
  raise "Folds imply #{1<<hbits}x#{1<<vbits}, not #{h}x#{v}" unless 1<<hbits == h && 1<<vbits == v
  hmask, vmask = (1 << hbits) - 1, (1 << vbits) - 1
  masks, final_h, final_v = [], 0, 0
  folds.split(//).each do |fold|
    if fold =~ /[LR]/
      masks << hmask; hmask /= 2
      final_h = final_h*2 + (fold=="L"?1:0)
    else
      masks << (vmask << hbits); vmask /= 2
      final_v = final_v*2 + (fold=="T"?1:0)
    end
  end
  answer = [(n = (final_v<<hbits|final_h) ^ masks[-1]) + 1]
  while true
    i = answer.length.top_changed_bit
    return answer if i >= masks.length
    answer << (n ^= masks[i]) + 1
  end
end

# Takes a sequence generated by folding, reproduces the fold
# instructions (as best as possible) by recreating the masks.
def unfold seq
  nfolds = seq.size.log2
  mask = (seq[0]-1) ^ (seq[1]-1)
  hbits = ((mask.odd??mask : mask^((1<<nfolds)-1)) + 1).log2
  hfolds, vfolds = [], []
  final = seq[-1] - 1
  (0...hbits).each{|bit| hfolds.push(final[bit].odd?? "L":"R")}
  (hbits...nfolds).each{|bit| vfolds.push(final[bit].odd?? "T":"B")}
  folds = ""
  i = 1
  while i < seq.size
    mask = (seq[i-1]-1) ^ (seq[i]-1)
    folds.insert( -1, (mask.odd??hfolds:vfolds).pop )
    i *= 2
  end
  folds
end

class Integer
  # Returns the number of the top bit that changed from self-1
  def top_changed_bit; (self^(self-1)).log2 end
  def log2
    raise "Domain error" if (n=self) <= (answer=0)
    while n > 1: answer += 1; n /= 2 end
    answer
  end
  def odd?; return self[0] == 1 end
end

require "fold"

# Main program
if $0 == __FILE__
  h, v, folds = get_args
  a2 = fold2 h, v, folds
  a  = fold  h, v, folds
  raise "New folder returned\n #{a2.inspect}\nwhile old one returned\n #{a.inspect}" unless a == a2
  unfolds = unfold a
  raise "Unfolding returned #{unfolds}" unless unfolds == folds or unfolds.tr("TBLR","LRTB") == folds
  p a
  p unfolds
end

--------------090700010508010409000101--