«

On 7/14/08, -j b- <> wrote:
> >
> > ## Symbolify (#169)
> >
> > Your task this week is to count. Yup, that's it.
> >
> >Oh, by the way... You may only use the characters `?`, `*`, `(`, `)` and `-`.
>
> 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 .

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[i]
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

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

On Tue, Jul 15, 2008 at 12:56 AM, Adam Shelly <> wrote:
> On 7/14/08, -j b- <> wrote:
>> >
>> > ## Symbolify (#169)
>> >
>> > Your task this week is to count. Yup, that's it.
>> >
>> >Oh, by the way... You may only use the characters `?`, `*`, `(`, `)` and `-`.
>>
>> 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 .
>
> 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[i]
> 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
>
>



--
Yogi Berra - "A nickel ain't worth a dime anymore."

On Fri, Jul 11, 2008 at 6:12 PM, ara.t.howard <> wrote:
Great Quiz indeed, but just coming back from vacations the fun stuff
has already be done.

BTW Ara ?* forever

Cheers
Robert

On Sun, Jul 13, 2008 at 6:08 PM, Matthew Moss <> 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
>
>
> 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...
>
>


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

Robert Dober wrote:
> On Fri, Jul 11, 2008 at 6:12 PM, ara.t.howard <> wrote:
> Great Quiz indeed, but just coming back from vacations the fun stuff
> has already be done.
>
> BTW Ara ?* forever

Define forever

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

--
vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407