Re: [QUIZ] Symbolify (#169)

On 13 Jul 2008, at 16:35, James Gray wrote:
>
> Mine was similar to this:
>
>  def symbolify(n)
>    "??-??" + "--(?)-?()" * n
>  end

I came up with something along those lines.
The version that produces shorter output worked along these lines:

1. Express the number as a sum of powers of 63 (eg 250174 = 63^3 +  
2*63 +1)
2. Rewrite that polynomial to reduce the number of operations required  
(ie 3x^4+2x^2+x is written as x(x(3x^2+2)+1)
3. write that out. the exponents are dealt with by calling itself.  
Coefficients (which by definition are < 63) are dealt with by a  
function that deals with that.
Initially I just hardcoded numbers 1 to 5 (?( - ?) etc...) and dealt  
with others by dividing out by 5 and calling itself recursively. Later  
on I added special cases for most of the numbers to produce shorter  
output. Some other parts of the program can be simplified/eliminated  
as all they do is produce slightly more compact output. This forms the  
bulk of the program. Off the top of my head I'd assume that the  
approach taken results in O(ln n) complexity.

Fred

def strip_parens x
   x.gsub(/^\(/,'').gsub(/\)$/,'')
end

INVERTIBLE = [1,2,3,4,5,18,21,22,23,46,47,48,49,50]
def small_symbolify x
  case x
  when 0: return '(?*-?*)'
  when 1: return '(?)-?()'
  when -1: return '(?(-?))'
  when 2: return '(?*-?()'
  when -2: return '(?(-?*)'
  when 3: return '(?--?*)'
  when -3: return '(?*-?-)'
  when 4: return '(?--?))'
  when -4: return '(?)-?-)'
  when 5: return '(?--?()'
  when -5: return '(?(-?-)'
  when 6: return '('+small_symbolify(3)+'*'+small_symbolify(2)+')'
  when 8: return '('+small_symbolify(2)+'*'+small_symbolify(4)+')'
  when 9: return '('+small_symbolify(3)+'*'+small_symbolify(3)+')'
  when 10: return '(?--?(-(?(-?-))'
  when 12: return '('+small_symbolify(3)+'*'+small_symbolify(4)+')'
  when 13: return '(??-?--(?--?())'
  when 14: return '('+strip_parens(small_symbolify(18)) 
+'-'+small_symbolify(4)+')'
  when 16: return small_symbolify(2)+'**'+small_symbolify(4)
  when 17: return '('+strip_parens(small_symbolify(18)) 
+'-'+small_symbolify(1)+')'
  when 18: return '(??-?-)'
  when -18: return '(?--??)'
  when 19: return '('+strip_parens(small_symbolify(21)) 
+'-'+small_symbolify(2)+')'
  when 21: return '(??-?*)'
  when -21: return '(?*-??)'
  when 22: return '(??-?))'
  when -22: return '(?)-??)'
  when 23: return '(??-?()'
  when -23: return '(?(-??)'
  when 24: return '('+strip_parens(small_symbolify(23)) 
+'-'+small_symbolify(-1)+')'
  when 25: return small_symbolify(5)+'**'+small_symbolify(2)
  when 26: return '('+strip_parens(small_symbolify(23)) 
+'-'+small_symbolify(-3)+')'
  when 27: return small_symbolify(3)+'**'+small_symbolify(3)
  when 28: return '('+strip_parens(small_symbolify(23)) 
+'-'+small_symbolify(-5)+')'
  when 32: return small_symbolify(2)+'**'+small_symbolify(5)
  when 36: return '('+small_symbolify(18)+'*'+small_symbolify(2)+')'
  when 38: return '('+strip_parens(small_symbolify(40)) 
+'-'+small_symbolify(2)+')'
  when 39: return '('+small_symbolify(3)+'*'+small_symbolify(13)+')'
  when 40: return '?('
  when 41: return '?)'
  when 42: return '?*'
  when 45: return '?-'
  when 46: return '('+small_symbolify(45)+'-'+small_symbolify(-1)+')'
  when -46: return '('+strip_parens(small_symbolify(-1)) 
+'-'+small_symbolify(45)+')'
  when 47: return '('+small_symbolify(45)+'-'+small_symbolify(-2)+')'
  when -47: return '('+strip_parens(small_symbolify(-2)) 
+'-'+small_symbolify(45)+')'
  when 48: return '('+small_symbolify(45)+'-'+small_symbolify(-3)+')'
  when -48: return '('+strip_parens(small_symbolify(-3)) 
+'-'+small_symbolify(45)+')'
  when 49: return '('+small_symbolify(45)+'-'+small_symbolify(-4)+')'
  when -49: return '('+strip_parens(small_symbolify(-4)) 
+'-'+small_symbolify(45)+')'
  when 50: return '('+small_symbolify(45)+'-'+small_symbolify(-5)+')'
  when -50: return '('+strip_parens(small_symbolify(-5)) 
+'-'+small_symbolify(45)+')'
  when 52: return '('+small_symbolify(4)+'*'+small_symbolify(13)+')'
  when 54: return '('+small_symbolify(3)+'*'+small_symbolify(18)+')'
    end
  if x > 31
    return '(??-'+small_symbolify(63-x)+')'
  end
  quotient = x/5
  rem = x - quotient * 5
  if quotient==0
    small_symbolify rem
  else
    if quotient == 1
      quotient_string = ''
    else
      quotient_string = small_symbolify(quotient)+'*'
    end
    '('+quotient_string+small_symbolify(5)+(rem > 0 ? '-' +  
small_symbolify(-rem) : '') + ')'
  end
end


def log63(x)
   power=0
   value=1
   x=-x if x < 0
   while value <= x
     value*=63
     power+=1
   end
   power-1
end

def convert_to_base_63 x
   return [] if x == 0
   leading_term = log63(x).to_i
   if leading_term==0
     [[x,0]]
   else
     v = 63**leading_term

     quotient = x/v
     remainder = x - quotient*v
     [[quotient, leading_term]]+convert_to_base_63(remainder)
   end
end


def symbolify x
  return '(?*-?*)' if x == 0
  transform_polynomial(convert_to_base_63(x))
end

def transform_polynomial p
   return '' if p.empty?
   last = p.pop

   m_power_term = (['??']*last[1]).join('*')
   p_power_term = "??**#{symbolify last[1]}"

   power_term = m_power_term.length > p_power_term.length ?  
p_power_term : m_power_term
   if p.empty?
     if last[1]==0
       result = small_symbolify(last[0])
     elsif last[0] == 1
       result = power_term
     else
       result = small_symbolify(last[0]) + '*'+power_term
     end
   else
     remainder = transform_polynomial(p.collect {|t| [t[0], t[1] -  
last[1]]})
     if INVERTIBLE.include?(last[0])
       remainder += '-'
       remainder +=small_symbolify -last[0]
     else
       remainder += '--'
       remainder +=small_symbolify last[0]
     end
     if last[1]==0
       result = remainder
     else
       result = power_term + "*(#{remainder})"
     end
   end
   result
end