From: Sandro Paganotti <sandro.paganotti@...>
Date: 2008-07-15T17:16:54+09:00
Subject: Re: Symbolify (#169)

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 <adam.shelly@gmail.com> wrote:
> On 7/14/08, -j b- <jrb562@drexel.edu> 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."