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