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