Re: Symbolify (#169)

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


On Jul 11, 11:17 am, "Matthew Moss" <[e-mail]> wrote:
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
>
> 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`).
>
> --
> Matthew Moss <[e-mail]>