[QUIZ] Symbolify (#169)

[Matthew Moss]

Mike mailed me his two solutions, here they are:

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

def simbolify(i)
"(?*-?*)"+"--(?*-?))"*i
end

 

[ThoML]

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?1log(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 = ( * 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
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

 

[Matthew Moss]

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...

 

[Jason Dew]

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

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

The three rules of Ruby Quiz 2:

1. Please do not post any solutions or spoiler discussion for this
quiz until 48 hours have passed from the time on this message.

2. Support Ruby Quiz 2 by submitting ideas as often as you can! (A
permanent, new website is in the works for Ruby Quiz 2. Until then,
please visit the temporary website at

<http://splatbang.com/rubyquiz/>.

3. Enjoy!
Suggestion: A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby Talk follow the discussion. Please reply to
the original quiz message, if you can.

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

## Symbolify (#169)

Your task this week is to count. Yup, that's it.

Oh, by the way... You may only use the characters `?`, `*`, `(`, `)` and `-`.

Specifically, define a function `symbolify` that accepts an integer
and returns a string composed of only the five characters shown above.
The string, when evaluated, will equal the original number passed in.

That is, the following test code should raise no exceptions:

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

There are at least a few different approaches that come to mind, so
don't expect everyone to have the same output. Well, not before the
output is passed through `eval`, that is.

I am not requiring that you produce the shortest string (though you
are welcome to attempt such a thing). The only thing I _do_ ask is
that you not produce megabytes of data to represent a simple integer.

P.S. Cheating is encouraged (except that you may not write code
outside of `symbolify`).

 

[Mike Dvorkin]

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!"

 

[Martin Boese]

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

 

[Frederick Cheung]

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

 

[krusty.ar]

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
## 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.

 

[Matthew Moss]

def symbolify (n)

=A0 s =3D "#{n}"
=A0 def s.delete(*args)
=A0 =A0 ""
=A0 end
=A0 s
end

How does this work? If I type in irb:

symbolify(60)

I get out:
=3D> "60"

Doesn't fit the problem specification.

 

[Chris Shea]

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!

Chris

 

[Ryan Davis]

How does this work? If I type in irb:
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.

 

[Ryan Davis]

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_.

 

[Bill Kelly]

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

 

[Matthew Moss]

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.

 

[Matthew Moss]

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(r)
"(#{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(r)
"#{rs}--(#{qs})*#{$cache[64]}"
end
end
end
end

end

 

[Matthew Moss]

that however, is _horrible_.

Yes. Yes is it.

 

[Matthew Moss]

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(r)
else
qs = symbolify(q)
if r.zero?
"(#{qs})*#{$cache}"
else
"#{symbolify(r)}--(#{qs})*#{$cache}"
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

 

[krusty.ar]

I am also part of the test.    

Users, always getting between the problem and the solution

Lucas.

 

[Rick DeNatale]

[Note: parts of this message were removed to make it a legal post.]

Here's a fairly straightforward solution, this passes the tests and works
for both positive and negative integers:

def symbolify(i)
digits = [
"?(-?(",
"?)-?(",
"?*-?(",
"?--?*",
"(?*-?()*(?*-?()",
"?--?(",
"(?--?*)*(?*-?()",
"(((?*-?()*(?*-?())*(?*-?())-(?)-?()",
"((?*-?()*(?*-?())*(?*-?()",
"((?*-?()*(?--?())-(?)-?()",
"(?*-?()*(?--?()"
]

if i < 0
"-(#{symbolify(-i)})"
else
if i < 9
digits
else
i.abs.to_s.split(//).map {|digit| digits[digit.to_i]}.inject(nil) {
|answer, rep| answer ? "((#{rep})--(#{answer})*(#{digits[10]}))": rep }
end
end
end

The basic approach is to generate an expression which works like a lexical
scan of the decimal representation of the (positive) integer, i.e. it's the
closed form of

val = 0
i.to_s(10).split(//).each |digit|
val = val * 10 + digit.to_i
end

except the the digits are represented by expressions following the rules.

For the positive integers <= 1000 the longest string generated was 157
characters for i = 777.

For the negative integers >= 1000 the longest string generate was 160
characters for i = -777 (i.e) the same string wrapped in parentheses
preceded by a -

 

[ara.t.howard]

## Symbolify (#169)

a full-on cheat:

cfp:~/src/ruby > cat a.rb
# impl
#
def symbolify i;def (s=i.to_s).delete _;'';end;s;end

# test
#
nums = (0...1000).sort_by { rand }
strs = nums.map { |n| symbolify(n) }

strs.zip(nums).sort_by { rand }.each do |str, num|
res = eval(str)
raise "Not a string!" unless str.is_a? String
raise "Invalid chars!" unless str.delete("?*()-").empty?
raise "Decode failed!" unless res == num
end

puts "Passed!"



cfp:~/src/ruby > time ruby a.rb
Passed!

real 0m0.026s
user 0m0.021s
sys 0m0.005s


a @ http://codeforpeople.com/