[QUIZ] Symbolify (#169)

M

Martin Boese

My previous post didn't work for i=0, this one does:

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

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

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

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`).
Click to expand...
Click to expand...
 
R

Ryan Davis

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
Click to expand...

My first version did roughly the same thing, but against the binary
representation:

15 = 0b1111 = "2**3+4+2+1".encode

encode would substitute + for -- and gsub numbers in from the table.
Powers of 2 were precalculated as were 0-9.

I also benchmarked and figured out that it was more often (roughly 55%
of the time) faster and a smaller result if I subtract the difference
between the next higher power of two and the number in question.

Regardless, answers got messy...
 
P

Paul Smith

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

Is it awful at this point to say that I just don't get it? How does eval on
these curious looking strings end up giving you an interger?
 
F

Frederick Cheung

Is it awful at this point to say that I just don't get it? How does
eval on
these curious looking strings end up giving you an interger?
Click to expand...

Well you've got multiplication, exponentiation and substraction/unary
minus (ie you've got addition) and parentheses. So they only thing
missing is getting some actual numbers to multiply together and so on.
Try evaluating ??, ?-, ?* etc... in the console :)

Fred
 
P

Paul Smith

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

Wow, so ?? gives you the ASCII code for the ? character. That's awesome.
Now I understand :)

On Mon, Jul 14, 2008 at 10:31 AM, Frederick Cheung <
 
T

ThoML

Try evaluating ??, ?-, ?* etc... in the console :)

Unfortunately(??), this doesn't work with ruby19 though. In ruby19, ?
( evaluates to "(".

irb(main):001:0> ?(.class
=> String

In irb 1.8:
irb(main):001:0> ?(.class
=> Fixnum
 
J

-j b-

## Symbolify (#169)
Click to expand...

Fairly straightforward; handles negative and positive. I tried for the
shortest resulting encoding but fell a little short compared to some of
the other results . Thats likely due to my use of addition instead of
multiplication.

def symbolify(j)
i = j.abs
add = "--"
unless $nums
code = {?? => "??", ?- => "?-", ?) => "?)", ?( => "?(", ?* =>
"?*"}
$nums = {}
code.keys.each do |x|
code.keys.each do |y|
$nums[x-y] = "%s-%s" % [code[x], code[y]]
$nums[x*y] = "%s*%s" % [code[x], code[y]]
$nums[x**y] = "%s**%s" % [code[x], code[y]]
end
end
end

if $nums
eq = "%s%s%s" % [j < 0 ? "-(" : "", $nums, j < 0 ? ")" : ""]
return eq
end

values = {}
remove = 0
$nums.keys.sort.reverse.each do |num|
next unless num > 1
if num < i and i % num == 0
return "%s(%s)*(%s)" % [j<0 ? "-" :
"",$nums[num],symbolify(i/num)]
end
pow = 0
pow += 1 while num**pow <= i
values[num**(pow-1)] = [num,pow-1]
remove = num**(pow-1) if remove < num**(pow-1)
end

base,pow = values[remove]
equation = "(%s)**(%s)" % [$nums[base], symbolify(pow)]
equation << add + symbolify(i-remove) if i - remove > 0
j < 0 ? "-(" + equation + ")" : equation

end
 
S

SHINDO Motoaki

Excuse me again(^_^;)

Thanks to the post;
--> On 2008/07/14, at 10:45, Rick DeNatale wrote:
being inspired&encouraged, I made refinements to my code;

Still I failed to convince eval() to back my string to original numbers,
but some folks're talk 'bout ASCII codes, I'm not too far to the punch =20=

line.
# but after long long the other-way-'round, sigh=E2=80=A6

Making wish this help somebody.
# I'm now going to sleep=E2=80=A6

=3D=3D source follows =3D=3D
#!/usr/bin/env ruby -Ku
Base =3D 5

def i_to_penta(i, penta)
# think of only Positive numbers

p =3D i / Base
if 0 < i
q =3D i % Base
penta << q
if p < Base
penta << p
else
i_to_penta(p, penta)
end
end
end

def penta_to_sym(penta)
outlet =3D []

# penta.reverse.each { |msd|
penta.each { |msd|
case msd
when 0
# outlet << '('
# outlet << '-'
outlet << '?'
when 1
# outlet << ')'
outlet << '*'
when 2
# outlet << '('
# outlet << '*'
outlet << '-'
when 3
# outlet << '?'
# outlet << '-'
# outlet << '*'
outlet << '('
# outlet << ')'
when 4
# outlet << '('
outlet << ')'
# outlet << '?'
# outlet << '-'
else
outlet << '!'
end
}
outlet
end

def symb1(i)
penta =3D Array.new=09
i_to_penta(i, penta)
outlet =3D penta_to_sym(penta)
end

def symbolify(i)
outlet =3D symb1(i)
#outlet
s =3D outlet.to_s
end

puts symbolify(ARGV[0].to_i)

=3D=3D source ends =3D=3D

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D
ContextSwitcher

Shindo Motoakira
<[email protected]>
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D
 
T

ThoML

Still I failed to convince eval() to back my string to original numbers,
but some folks're talk 'bout ASCII codes
Click to expand...

The point is that in ruby 1.8 something like ?( denoted the character
'(' but this really is only a fixnum (40) -- as it was already
described by others.

The task is: you have
the following symbols/numbers

irb(main):002:0> p ??, ?-, ?*, ?), ?(
63
45
42
41
40

the operations *, - (with -- being +)
and parentheses.

Use this to build any number.

E.g. 1:
irb(main):004:0> eval('?)-?(') # ~~ 41 - 40
=> 1

This is something slightly different than recoding a decimal number to
base-5 and using symbols instead of digits.

It took me some time to figure this out myself. It was really a nice
idea and an excellent quiz.
 
S

SHINDO Motoaki

Thank you for the explanation

E.g. 1:
irb(main):004:0> eval('?)-?(') # ~~ 41 - 40
=3D> 1
Click to expand...

ASCII code themselves are good old familiar things but
the idea that the numbers also operate as Operators
is quite over my head ;-(

I'm pretty confident on Context Switching, but
this one is too fine grained=E2=80=A6(to me)
It was really a nice idea and an excellent quiz.
Click to expand...

Yes, I agree. Good education to me: impressed;
still some sorrow to me
it'll took quite long to digest&utilize=E2=80=A6

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D
ContextSwitcher

Shindo Motoakira
<[email protected]>
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D
 
A

Adam Shelly

Fairly straightforward; handles negative and positive. I tried for the
shortest resulting encoding but fell a little short compared to some of
the other results .
Click to expand...

My solution tries for the absolute shortest encoding without cheating.
That makes it pretty slow, so I added some optional optimizations to
help it run faster.
Without the ** operator, I get

(0..1000).inject(''){|s,i|s+=symbolify(i)}.length == 16001


-Adam

---- symbolify.rb ---
class Symbolifier
def initialize opt_lvl=0,max=nil
@strings={} # @strings[n] = [symbolify(n),t]
@values = {} # @values[x] = [all n such that symbolify(n).size == x]
@todo = {}
@newlengths = {}
@optimization = opt_lvl
@max = max&&max*2 #store values 2x as big as max so we can subtract
insert(%w{ ?? ?- ?* ?) ?(}.map{|s|[s,:digit]})
update_todo
end

def [] x
rec = @strings[x]
p :EXP,rec if rec&&rec[1]==:exp

return rec[0] if rec
rec = @strings[-x]
if rec
r=(rec[1]==:add) ? '-('+rec[0]+')' : '-'+rec[0]
return r.sub(/^--/,'')
end
return rec if rec=gen_alternates(x) if @optimization>=2
until (rec=generate(x))
return rec if rec=gen_alternates(x) if @optimization>=1
end
return rec
end

private
def add_syms s1,s2
[((s2[0]==?-)? "%s%s":"%s--%s")%[s1,s2],:add]
end
def sub_syms s1,s2,t2
[((t2==:add)? "%s-(%s)":"%s-%s")%[s1,s2],:add]
end
def mul_syms s1,s2,t1,t2
ss="%s*%s"
ss = "(%s)*%s" if (t1==:add)
ss[-2..-1]="(%s)" if (t2==:add)
[ss%[s1,s2],:mul]
end
def exp_syms s1,s2
["(%s)**(%s)"%[s1,s2],:exp]
end

def store v,rep
(@values[rep[0].size]||=[])<<v
@strings[v] = rep
@newlengths[rep[0].size]=true
#~ p :EXP,rep if rep[1]==:exp
end

def insert newsyms
newsyms.each{|s|
if (0 > v=eval(s[0]))
v=-v
s[0]=(s[1]==:add) ? '-('+s[0]+')' : '-'+s[0]
end
next if @max && v>@max
if !@strings[v]
store(v,s)
elsif (@strings[v][0].size > s[0].size)
@values[@strings[v][0].size].delete(v)
store(v,s)
end
}
end

def generate(target)
a_idx,b_idx,newlen = 0,0,Float::MAX
@todo.each{|k,a| if (k+a[0]<newlen)
a_idx,b_idx = k,a[0]
newlen = a_idx+b_idx
end
}
@todo[a_idx].delete(b_idx)
p "generating strings of length>= #{newlen+1} (#{a_idx}+#{b_idx}+1)"
newvals=[]
@values[a_idx].each{|v1|
@values[b_idx].each{|v2|
s1,t1 = @strings[v1]
s2,t2 = @strings[v2]
newvals<< add_syms(s1,s2)
newvals<< sub_syms(s1,s2,t2)
newvals << mul_syms(s1,s2,t1,t2)
## REMOVE following line for significant speedup
newvals <<exp_syms(s1,s2)
}
}
insert(newvals)
update_todo
f=@strings[target]
p :EXP,f if f&&f[1]==:exp

return f[0] if f
end

def gen_alternates(x)
newvals=[]
len,alt = 3e30,nil
(1..5).each{|i|
s1,t1=@strings
if (s1)
s2,t2 = @strings[x-i]
newvals<< add_syms(s1,s2) if (s2)
s2,t2 = @strings[x+i]
newvals<< sub_syms(s2,s1,t1) if (s2)
s2,t2 = @strings[x/i]
m,tm=@strings[x%i]
if (s2 && m)
s3,t3 = mul_syms(s1,s2,t1,t2)
newvals<< add_syms(s2,m)
end
end
}
insert(newvals)
update_todo
f=@strings[x]
return f[0] if f
end

def update_todo
@newlengths.keys.each{|len|@todo[len]||=[]
@todo.each{|k,a| a<<len if k<=len;a.sort!.uniq!}
}
@newlengths={}
end
end

def symbolify x
$ymbolifier ||= Symbolifier.new
## CHANGE TO
# $ymbolifier ||= Symbolifier.new opt_level_1_or_2,max_input
## for faster performance

return $ymbolifier[x]
end
 
S

Sandro Paganotti

Here's mine solution (CHEATING)

def symbolify(i)
k = String.new("#{i}")
def k.is_a?(c); true; end;
def k.delete(s); [] end;
return k;
end

Fairly straightforward; handles negative and positive. I tried for the
shortest resulting encoding but fell a little short compared to some of
the other results .
Click to expand...

My solution tries for the absolute shortest encoding without cheating.
That makes it pretty slow, so I added some optional optimizations to
help it run faster.
Without the ** operator, I get

(0..1000).inject(''){|s,i|s+=symbolify(i)}.length == 16001


-Adam

---- symbolify.rb ---
class Symbolifier
def initialize opt_lvl=0,max=nil
@strings={} # @strings[n] = [symbolify(n),t]
@values = {} # @values[x] = [all n such that symbolify(n).size == x]
@todo = {}
@newlengths = {}
@optimization = opt_lvl
@max = max&&max*2 #store values 2x as big as max so we can subtract
insert(%w{ ?? ?- ?* ?) ?(}.map{|s|[s,:digit]})
update_todo
end

def [] x
rec = @strings[x]
p :EXP,rec if rec&&rec[1]==:exp

return rec[0] if rec
rec = @strings[-x]
if rec
r=(rec[1]==:add) ? '-('+rec[0]+')' : '-'+rec[0]
return r.sub(/^--/,'')
end
return rec if rec=gen_alternates(x) if @optimization>=2
until (rec=generate(x))
return rec if rec=gen_alternates(x) if @optimization>=1
end
return rec
end

private
def add_syms s1,s2
[((s2[0]==?-)? "%s%s":"%s--%s")%[s1,s2],:add]
end
def sub_syms s1,s2,t2
[((t2==:add)? "%s-(%s)":"%s-%s")%[s1,s2],:add]
end
def mul_syms s1,s2,t1,t2
ss="%s*%s"
ss = "(%s)*%s" if (t1==:add)
ss[-2..-1]="(%s)" if (t2==:add)
[ss%[s1,s2],:mul]
end
def exp_syms s1,s2
["(%s)**(%s)"%[s1,s2],:exp]
end

def store v,rep
(@values[rep[0].size]||=[])<<v
@strings[v] = rep
@newlengths[rep[0].size]=true
#~ p :EXP,rep if rep[1]==:exp
end

def insert newsyms
newsyms.each{|s|
if (0 > v=eval(s[0]))
v=-v
s[0]=(s[1]==:add) ? '-('+s[0]+')' : '-'+s[0]
end
next if @max && v>@max
if !@strings[v]
store(v,s)
elsif (@strings[v][0].size > s[0].size)
@values[@strings[v][0].size].delete(v)
store(v,s)
end
}
end

def generate(target)
a_idx,b_idx,newlen = 0,0,Float::MAX
@todo.each{|k,a| if (k+a[0]<newlen)
a_idx,b_idx = k,a[0]
newlen = a_idx+b_idx
end
}
@todo[a_idx].delete(b_idx)
p "generating strings of length>= #{newlen+1} (#{a_idx}+#{b_idx}+1)"
newvals=[]
@values[a_idx].each{|v1|
@values[b_idx].each{|v2|
s1,t1 = @strings[v1]
s2,t2 = @strings[v2]
newvals<< add_syms(s1,s2)
newvals<< sub_syms(s1,s2,t2)
newvals << mul_syms(s1,s2,t1,t2)
## REMOVE following line for significant speedup
newvals <<exp_syms(s1,s2)
}
}
insert(newvals)
update_todo
f=@strings[target]
p :EXP,f if f&&f[1]==:exp

return f[0] if f
end

def gen_alternates(x)
newvals=[]
len,alt = 3e30,nil
(1..5).each{|i|
s1,t1=@strings
if (s1)
s2,t2 = @strings[x-i]
newvals<< add_syms(s1,s2) if (s2)
s2,t2 = @strings[x+i]
newvals<< sub_syms(s2,s1,t1) if (s2)
s2,t2 = @strings[x/i]
m,tm=@strings[x%i]
if (s2 && m)
s3,t3 = mul_syms(s1,s2,t1,t2)
newvals<< add_syms(s2,m)
end
end
}
insert(newvals)
update_todo
f=@strings[x]
return f[0] if f
end

def update_todo
@newlengths.keys.each{|len|@todo[len]||=[]
@todo.each{|k,a| a<<len if k<=len;a.sort!.uniq!}
}
@newlengths={}
end
end

def symbolify x
$ymbolifier ||= Symbolifier.new
## CHANGE TO
# $ymbolifier ||= Symbolifier.new opt_level_1_or_2,max_input
## for faster performance

return $ymbolifier[x]
end
Click to expand...
 
R

Robert Dober

Great Quiz indeed, but just coming back from vacations the fun stuff
has already be done.

BTW Ara ?* forever ;)

Cheers
Robert
 
R

Robert Dober

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...
Click to expand...


But this is brilliant Matt, why cheat, we can do this without cheating too ;)

@digits = %w{ ??-?? ?)-?( ?*-?( ?--?* ?--?) ?--?( }

def symbolify i
s = i.to_s( 5 ).split( // )
f = s.shift
s.inject( @digits[f.to_i] ){ |so_far, b|
"(#{so_far})*(" << @digits[ 5 ] << ")--" << @digits[ b.to_i ]
}
end


Cheers
Robert
 
J

Joel VanderWerf

Robert said:
Great Quiz indeed, but just coming back from vacations the fun stuff
has already be done.

BTW Ara ?* forever ;)
Click to expand...

Define forever :p

$ ruby19 -v -e 'p ?*'
ruby 1.9.0 (2007-12-25 revision 14709) [i686-linux]
"*"
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

[SUMMARY] Symbolify (#169) 1
[QUIZ] Gathering Ruby Quiz 2 Data (#189) 10
[QUIZ] Circle Drawing (#166) 18
[QUIZ] Price Ranges (#164) 14
[QUIZ] AnsiString (#185) 7
[QUIZ] Finding Quiz Responses (#200) 2
[QUIZ] Uptime Since... (#174) 24
[QUIZ] Equation Graphing (#176) 1

Members online

No members online now.
Total: 28 (members: 1, guests: 27)
Robots: 320

Forum statistics

Threads
473,755
Messages
2,569,536
Members
45,009
Latest member
GidgetGamb

Latest Threads

Top