Symbolify (#169)

mansfiem · July 12, 2008, 9:51am

On 12 Jul 2008, at 08:40, ThoML wrote:

419100 for me. I’m pretty sure I’ve got the odd extra set of
parentheses I don’t really need so it should be possible to shave it
down a little.

Fred

mansfiem · July 13, 2008, 5:54pm

On Jul 13, 9:35 am, James G. [email protected] wrote:

def symbolify(n)
“??-??” + “–(?)-?()” * n
end

James Edward G. II

I had similar solutions (but a smidge longer). Here are some
cheaters:

Fix up muliplication so that it just returns the passed

number. Every integer is encoded as ‘?**?*’. Fails the

deylayed eval test.

def symbolify_m(i)
Fixnum.class_eval <<-EOD
def (other)
#{i}
end
EOD
'?**?’
end

Fix up eval so that it just returns the passed argument.

Every integer is encoded as the empty string. Fails the

delayed eval test. Aliased so that you can still use irb.

def symbolify_e(i)
Kernel.class_eval <<-EOD
alias_method :cheated_eval, :eval
def eval(*args)
if args.size == 1 and args.first == ‘’
#{i}
else
cheated_eval(*args)
end
end
EOD
‘’
end

Chris

mansfiem · July 13, 2008, 6:05pm

I have three non-MP/cheating solutions.

The second one is still quite compact and produces output that isn’t
too
long. The third one uses prime factorization. It can handle negative
integers and generates fairly short output.

For the second solution, the results for some tests are:

9999
=> 216: ?(?(?(-????-????-????-????-????-????-????-????-??
??-????-????-????-??
??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-
(?–?()-(?–?()
99999
=> 254: ??????-????-????-????-????-????-????-????-????-??
??-????-????-????-????-????-????-????-????-????-????-??
??-????-????-????-????-????-????-????-????-????-????-??
??-????-????-????-????-????-????-??*?–??-??-??-??-??-?-
(0…10000).to_a.inject(0) {|a, i| a + symbolify(i).size}
=> 1180737

real 0m7.480s
user 0m7.300s
sys 0m0.100s

For the third solution, the numbers are:

9999
=> 65: (?–?)(?–?)((?-?()(?-(?–?())-??)((?-?()(?-?
()?)-??)
99999
=> 60: (?–?)(?–?)?)((?-?()(?-?()(?–?)*(??-?()-(?–?())
(0…10000).to_a.inject(0) {|a, i| a + symbolify(i).size}
=> 539965

real 0m8.201s
user 0m7.991s
sys 0m0.110s

Regards,
Thomas.

And here is the code:

------------------ Solution 1

require ‘mathn’
include Math
def symbolify(int)
([’?(’](n=int<2?1:(log(int)/log(?()).ceil)).join(’’)<<’-(?)-?
()’*(?(**n-int)
end

------------------ Solution 2

require ‘mathn’
include Math
def symbolify(int)
syms = [’??’, ‘?-’, ‘?’, ‘?)’, ‘?(’]
ns = syms.map {|s| v = eval(s); [n = int < 2 ? 1 : (log(int) /
log(v)).ceil, s, v ** n - int]}
n, s, rest = ns.sort_by {|n, s, sum| sum}[0]
str = ([s] * n).join(’’)
(syms + syms[0…-2].map {|s| “(#{s}-?()”}).each do |s|
break if rest == 0
t, rest = rest.divmod(eval(s))
syms.each do |s1|
t1, t = t.divmod(eval(s1))
str << “-#{s}*#{s1}” * t1
end
str << “-#{s}” * t
end
str
end

------------------ Solution 3

require ‘mathn’
module Symbolify
@quick = false # Not for incremental benchmarking
SYMS = [’?(’, ‘?)’, ‘?’, ‘?-’, ‘??’].map {|e| [eval(e), e]}
BLACKLIST = []
@top = ??
@multiples = SYMS.map {|a,b| a}
@multiples_limit = 1000000
VALS = Hash.new do |h, k0|
k = k0.abs
if !h.has_key?(k)
BLACKLIST << k
h[k] = k.prime_division.map do |p, n|
pre = []
n1 = n
while n > 0 and n1 > 0
pn1 = p ** n1
if h.has_key?(pn1)
pre << h[pn1]
n1 = n -= n1
else
n1 -= 1
end
end
if n == 0
pre
else
ps = nil
SYMS.each do |i, sym|
pi = p + i
unless BLACKLIST.include?(pi)
BLACKLIST << pi
s = “(#{h[pi]}-#{sym})”
BLACKLIST.pop
ps = s unless ps and s.size > ps.size
break if @quick
if s.size == 7
SYMS << [p, s]
break
end
end
end
pre.concat([ps] * n)
end
end.join(’’)
BLACKLIST.pop
end
if k0 < 0
h[k0] = “#{h[k]}*(?(-?))”
else
h[k0]
end
end
VALS[0] = “(#{SYMS[0][1]}-#{SYMS[0][1]})”
VALS[1] = “(?)-?()”
SYMS.each {|v, s| VALS[v] = s}

def self.multiples(max)
    return if @multiples.empty? or @top > max * 2 or @quick or max

@multiples_limit
begin
multiples = []
SYMS.each do |j, jsym|
@multiples.each do |i|
sym = VALS[i]
ij = i * j
multiples << ij
ijsym = “#{sym}*#{jsym}”
VALS[ij] = ijsym unless VALS.has_key?(ij) and
VALS[ij].size > ijsym.size
@top = ij if ij > @top
break if @top > max * 2
end
end
@multiples = multiples
end until @multiples.empty? or @top > max * 2
end

def self.quick(bool)
    @quick = bool
end

end

def symbolify(int)
Symbolify.multiples(int)
Symbolify::VALS[int]
end

mansfiem · July 13, 2008, 6:08pm

Mike mailed me his two solutions, here they are:

def symbolify(i)
i<1?"?-?":"(?-?))"+"–(?-?))"*(i-1)
end

def simbolify(i)
“(?-?)”+"–(?*-?))"*i
end

mansfiem · July 13, 2008, 6:13pm

My first version cheats a bit, but passes the tests. Converts the num
to base-5 and back.

def symbolify(num)
def eval(str)
str.tr(’(?)-’, ‘01234’).to_i(5)
end
num.to_s(5).tr(‘01234’, '(?)-’)
end

My second solution cheats badly, failing the delayed eval test. Still,
it’s a single line of length 42.

def symbolify(num)
def eval(str) $num end; $num = num; “()”
end

I need to finish my non-cheating version…

mansfiem · July 13, 2008, 6:26pm

Here’s my long and expensive search:

module Symbolify

#allowed characters: ? * ( ) -

PRIMITIVES = { 40 => “?(”, 41 => “?)”, 42 => “?*”, 45 => “?-”, 63 =>
“??” }
OPERATIONS = [:add, :subtract, :multiply, :exponentiate]

def symbolify target
@cache ||= Hash.new

result = search PRIMITIVES, PRIMITIVES, target
return result if result

result = search cache_copy, PRIMITIVES, target
return result if result

result = search PRIMITIVES, cache_copy, target
return result if result

result = search cache_copy, cache_copy, target
return result if result

nil

end

private

def cache_copy
@cache.dup
end

def search alpha_space, beta_space, target
alpha_space.each do |(value_of_a, a)|
beta_space.each do |(value_of_b, b)|
expression = evaluate(a, b, target)
return expression if expression
end
end

nil

end

def evaluate a, b, target
OPERATIONS.each do |op|
expression = send(op, a, b)
next unless expression

  value = eval(expression)
  @cache[value] ||= expression if value >= 0 and value <= 1000

  return expression if value == target
end

nil

end

def add a, b
“(#{a}–#{b})”
end

def subtract a, b
return nil unless eval(a) >= eval(b)
“(#{a}-#{b})”
end

def multiply a, b
“(#{a}*#{b})”
end

def exponentiate a, n
return nil unless eval(n) <= 10
“(#{a}**#{n})”
end

end

mansfiem · July 13, 2008, 7:23pm

My solution:

def symbolify(i)
("?)-?(–"*i)[0…-3]
end

However, at about 3300 I get a SystemStackError and if I start at like
5000 I
segfault the ruby interpreter (1.8.6)

martin

mansfiem · July 13, 2008, 6:43pm

After sleeping on it, I’m down to 19 chars, no cheating:

def symbolify(i)
“?-?”+"-?)–?*"*i
end

1000.times do |i|
  s = symbolify(i)
  raise "Not a string!"  unless s.is_a? String
  raise "Invalid chars!" unless s.delete("?*()-").empty?

  x = eval(s)
  raise "Decode failed!" unless i == x
end

puts "Passed!"

mansfiem · July 13, 2008, 9:31pm

On Jul 11, 12:17 pm, Matthew M. [email protected] wrote:

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Symbolify (#169)

I thought by cheating you meant duck typing, not rewriting eval:

def symbolify (n)
s = “#{n}”
def s.delete(*args)
“”
end
s
end

Lucas.

mansfiem · July 13, 2008, 9:49pm

def symbolify (n)
s = “#{n}”
def s.delete(*args)
“”
end
s
end

How does this work? If I type in irb:

symbolify(60)
I get out:
=> “60”

Doesn’t fit the problem specification.

mansfiem · July 13, 2008, 10:08pm

On Jul 13, 1:43 pm, Matthew M. [email protected] wrote:

I get out:
=> “60”

Doesn’t fit the problem specification.

But it passes the code you gave in the quiz description!

Chris

mansfiem · July 13, 2008, 8:25pm

On 13 Jul 2008, at 16:35, James G. 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:

Express the number as a sum of powers of 63 (eg 250174 = 63^3 +
2*63 +1)
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)
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

mansfiem · July 13, 2008, 10:12pm

On Jul 13, 2008, at 09:08 , Matthew M. wrote:

My first version cheats a bit, but passes the tests. Converts the num
to base-5 and back.

def symbolify(num)
def eval(str)
str.tr(’(?)-’, ‘01234’).to_i(5)
end
num.to_s(5).tr(‘01234’, '(?)-’)
end

This was my cheating solution as well, written slightly differently:

FROM, TO = ‘01234’, ‘?*()-’

def symbolify n
n.to_s(5).tr(FROM, TO)
end

alias :real_eval :eval
def eval s
return real_eval(s) unless s =~ /^[#{Regexp.escape TO}]+$/
s.tr(TO, FROM).to_i(5)
end

My second solution cheats badly, failing the delayed eval test. Still,
it’s a single line of length 42.

def symbolify(num)
def eval(str) $num end; $num = num; “()”
end

that however, is horrible.

mansfiem · July 13, 2008, 10:42pm

On Jul 13, 2:55 pm, Chris S. [email protected] wrote:

How does this work? If I type in irb:

symbolify(60)
I get out:
=> “60”

Doesn’t fit the problem specification.

But it passes the code you gave in the quiz description!

But it doesn’t actually solve the problem. The test code is not the
quiz in its entirety. I am also part of the test. And I looked at
the string returned, and it contained characters other than the five
allowed.

mansfiem · July 13, 2008, 10:24pm

Enjoyed the quiz - thanks! Here are my solutions…

First, the CHEAT versions.

The first is an 18-character Kobayashi Maru cheat,

i.e., following the teachings of Adm. James T Kirk,

“I reprogrammed the simulation… I don’t like to lose.”

def symbolify(i)
def raise(a)end;""
end

Next, the 14-character uber-cheeze… (Yes, it

outputs the success indicator on stderr instead

of stdout, … but who’s going to notice?

def symbolify(i)
abort"Passed!"
end

Finally, the NON-CHEAT versions.

Nothing special but here’s what I came up with:

Default version. Constructs a binary number,

multiplying the previous digit by 2 before adding

in the next digit…

def symbolify(i)
x="(?(-?()";i.to_s(2).each_byte{|d|x="(#{x}(?-?()–(?#{(d-8).chr}-?())"};x
end

Sans-multiply solution. (Does not use ‘*’)

Constructs a binary number,

and performs each left shift by adding the previous

value to itself. Generates VERY large strings. Passes

the tests, but needs to be run with `ulimit -s unlimited`

def symbolify(i)
x="(?(-?()";i.to_s(2).each_byte{|d|x+="–#{x}–(?#{(d-8).chr}-?()"};x
end

Regards,

Bill

mansfiem · July 13, 2008, 10:45pm

Here’s my non-cheating solution. Base-64 ftw!

def symbolify(n)
unless $cache
$cache = {}
$cache[8] = “(?–?*–?--?()”
$cache[64] = “(??–?)-?()”
end

if $cache.has_key?(n)
$cache[n]
else
if n < 0
“-(#{symbolify(-n)})”
elsif n < 8
case n
when 0 then “??-??”
when 1 then “?)-?(”
when 2 then “?-?("
when 3 then "?–?”
when 4 then “?–?)”
when 5 then “?–?(”
when 6 then “?–?(–?)-?(”
when 7 then “?–?)–?--?"
end
elsif n < 64
q, r = n.divmod(8)
if q.zero?
symbolify(rs)
else
qs = symbolify(q)
if r.zero?
"(#{qs})#{$cache[8]}”
else
rs = symbolify®
“(#{qs})#{$cache[8]}–#{rs}"
end
end
else
q, r = n.divmod(64)
if q.zero?
symbolify(rs)
else
qs = symbolify(q)
if r.zero?
"(#{qs})#{$cache[64]}”
else
rs = symbolify®
“#{rs}–(#{qs})*#{$cache[64]}”
end
end
end
end

end

mansfiem · July 13, 2008, 10:47pm

def symbolify(num)
def eval(str) $num end; $num = num; “()”
end

that however, is horrible.

Yes. Yes is it.

mansfiem · July 13, 2008, 10:50pm

On Jul 13, 2008, at 12:43 , Matthew M. wrote:

I get out:
=> “60”

Doesn’t fit the problem specification.

True, but it passes your test loop just fine. Note the singleton
method defined on the string.

mansfiem · July 14, 2008, 12:05am

On Jul 13, 5:37 pm, Matthew M. [email protected] wrote:

end
But it passes the code you gave in the quiz description!

I am also part of the test.

Users, always getting between the problem and the solution

Lucas.

mansfiem · July 13, 2008, 10:57pm

I just found a few typos in my non-cheating version that were not
caught. I fixed them and shortened the solution a bit:

def symbolify(n)
unless $cache
$cache = {}
$cache[8] = “(?–?*–?--?()”
$cache[64] = “(??–?)-?()”
end

def symbobase(b, n)
q, r = n.divmod(b)
if q.zero?
symbolify®
else
qs = symbolify(q)
if r.zero?
“(#{qs})#{$cache[b]}"
else
"#{symbolify®}–(#{qs})#{$cache[b]}”
end
end
end

if $cache.has_key?(n)
$cache[n]
else
if n < 0
“-(#{symbolify(-n)})”
elsif n < 8
case n
when 0 then “??-??”
when 1 then “?)-?(”
when 2 then “?-?("
when 3 then "?–?”
when 4 then “?–?)”
when 5 then “?–?(”
when 6 then “?–?(–?)-?(”
when 7 then “?–?)–?--?*”
end
elsif n < 64
symbobase(8, n)
else
symbobase(64, n)
end
end

end

Symbolify (#169)

Fix up muliplication so that it just returns the passed

number. Every integer is encoded as ‘?**?*’. Fails the

deylayed eval test.

Fix up eval so that it just returns the passed argument.

Every integer is encoded as the empty string. Fails the

delayed eval test. Aliased so that you can still use irb.

Symbolify (#169)

First, the CHEAT versions.

The first is an 18-character Kobayashi Maru cheat,

i.e., following the teachings of Adm. James T Kirk,

“I reprogrammed the simulation… I don’t like to lose.”

Next, the 14-character uber-cheeze… (Yes, it

outputs the success indicator on stderr instead

of stdout, … but who’s going to notice?

Finally, the NON-CHEAT versions.

Nothing special but here’s what I came up with:

Default version. Constructs a binary number,

multiplying the previous digit by 2 before adding

in the next digit…

Sans-multiply solution. (Does not use ‘*’)

Constructs a binary number,

and performs each left shift by adding the previous

value to itself. Generates VERY large strings. Passes

the tests, but needs to be run with ulimit -s unlimited

the tests, but needs to be run with `ulimit -s unlimited`