[SUMMARY] Symbolify (#169)

Discussion in 'Ruby' started by Matthew Moss, Jul 17, 2008.

  1. Matthew Moss

    Matthew Moss Guest

    Apologies for being a bit late... Here's this week's summary.


    The primary point of this week's quiz was to highlight the `?`
    pseudo-operator... Simply, a character preceded by `?` is converted
    to its ASCII value. (I hesitate to call it a true operator, since it
    is almost certainly not defined nor implemented in such manner.
    Rather, I expect, it is part of Ruby's lexer and so forms part of the
    definition of a number. But, in some ways, it _looks_ like a unary
    operator.) Type `?(` into irb and the interpreter will return the
    value 40.

    Knowing this, the five quiz-permitted characters give easy access to
    five integer values.

    > [?(, ?), ?*, ?-, ??]

    => [40, 41, 42, 45, 63]

    But I specifically permitted four characters (aside from the `?`) that
    can be used for a number of mathematical operations.
    Grouping/precedence, addition, subtraction, multiplication and
    exponentiation are all possible using those four characters, and so we
    can express values aside from the five shown above.

    > ?) - ?( # 41 - 40

    => 1

    > (?* - ?() ** ?( # 2 ** 40

    => 1099511627776

    Using these techniques, it is possible to form an expression that
    evaluates to any number, though perhaps not compactly. Let's look at a
    couple solutions.

    Our first solution is from _Alex LeDonne_:

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

    Remember, it's the string output from `symbolify` that, by request of
    the quiz specification, must contain only the five permitted
    characters. Alex begins with `??-??`. As shove above, `??` evaluates
    to 63, so this expression is `63-63`: that is, zero.

    I'm going to examine the next string in a few steps, just to make it
    clear what's going on. First, add in some whitespace.

    "- ?( - - ?)"

    Second, replace the `?` pseudo-operators with appropriate ASCII values.

    "- 40 - - 41"

    Third, realize that one of those `-` characters now represent unary
    negation operators.

    "- 40 - -41"

    Fourth, simply the mathematical identity that subtracting a negative
    is the same as adding the positive.

    "- 40 + 41"

    Finally, do the math.

    "+ 1"

    So now let's look at Alex's solution again, using these equivalent
    strings, to understand the intent.

    def symbolify(i)
    "0" + "+1" * i
    end

    So the call `symbolify(5)` results in a string that is effectively
    `0+1+1+1+1+1`. Which, when evaluated, equals five. It's not the most
    efficient way to count, but it is the simplest. Of course, this
    conversion was done just to show how Alex's solution produces the
    correct values on evaluation. The _actual_ output of `symbolify(5)`
    is:

    => "??-??-?(--?)-?(--?)-?(--?)-?(--?)-?(--?)"

    I apologize for a bit long-winded explanation, but I wanted to make it
    clear for anyone who might be confused about all this. For the rest of
    the solutions I look at here, I'll skip the string and symbol details
    and look specifically at the algorithm.

    As programmers, I certainly expected someone to provide a simple
    powers-of-two solution, and _Bill Kelly_ provides one. (Bill golfed
    this to a single line, but it is shown here with additional whitespace
    for readability.)

    def symbolify(i)
    x = "(?(-?()"
    i.to_s(2).each_byte { |d|
    x="(#{x}*(?*-?()--(?#{(d-8).chr}-?())"
    }
    x
    end

    The first line assigns a default value of zero. The second line
    enumerates over the digits of the binary representation of the input
    (as provided by `to_s(2)`). For each digit, the preceding value of `x`
    is doubled (multiplication by `(?*-?()`), and then the next digit is
    added in. This is basic binary counting.

    What might be a little confusing here is why eight is subtracted from
    `d`. Realize that enumerating the binary string using `each_byte` sets
    `d` to the ASCII value: in this case, either 48 or 49, the ASCII
    values of "0" and "1". Subtracting eight gives us 40 or 41, equivalent
    to `?(` or `?)`.

    As a final non-cheating solution, I want to look at one from _Dana Merrick_.

    require 'mathn'

    def symbolify(i)
    i.zero?? "??-??":"-"+("(?(-?))-"*i).chop
    end

    def symbolify_short(i)
    return "??-??" if i.zero?
    factors = i.prime_division
    factors.inject("") do |string,pair|
    string << "(" << symbolify(pair.first) << ")**("
    << symbolify(pair.last) << ")*"
    end.chop
    end

    Dana's `symbolify` function is very similar to Alex's solution above:
    counting by ones. But in the added function, `symbolify_short`, Dana
    makes use of `prime_division` from the `mathn` module, which will
    calculate the prime factorization of an integer. For example:

    > 360.prime_division

    => [[2, 3], [3, 2], [5, 1]

    > (2 ** 3) * (3 ** 2) * (5 ** 1)

    => 360

    This provides an efficient way to represent the inputs while still
    adhering to the permitted characters. `symbolify_short` alone isn't
    enough, since it can't provide output for the prime numbers, but it
    calls on the simpler `symbolify` to take care of that.

    Now, I figured there might be some other representations possible,
    except that `eval` was going to be too limiting. So I allowed
    cheating. And cheats we got, of a few different varieties.

    _Chris Shea_ redefines the multiplication operator for numbers like so:

    def symbolify(i)
    Fixnum.class_eval <<-EOD
    def *(other)
    #{i}
    end
    EOD
    '?**?*'
    end

    This isn't, of course, a general purpose solution, and fails the
    delayed evaluation test I provided. Still, Chris managed to return a
    string (the same string every time) and have that evaluate to the
    number passed in.

    Then we have one _Ryan Davis_, which converts the number to base-5,
    using the five symbols as the digits:

    FROM, TO = '01234', '?*()-'

    def symbolify n
    n.to_s(5).tr(FROM, TO)
    end

    Of course, using `eval` on the result of `symbolify` won't work, so
    `eval` had to be redefined as well.

    alias :real_eval :eval
    def eval s
    return real_eval(s) unless s =~ /^[#{Regexp.escape TO}]+$/
    s.tr(TO, FROM).to_i(5)
    end

    Another method redefinition comes from _Lucas_ (and done in similar
    fashion by a few other Rubyists), which was written solely to pass the
    automated tests provided.
    def symbolify (n)
    s = "#{n}"
    def s.delete(*args)
    ""
    end
    s
    end

    Note that here Lucas adds a method directly to instance `s` rather
    than the String class, so it won't interfere with other code. The sole
    intent of this `delete` method is to fool the automated tests.

    It didn't fool _me_, as the output clearly contains characters other
    than those permitted, but that's okay... I'll let it slide. They're
    ugly, but I like 'em.

    Finally, I present to you my own disturbingly ugly cheat:

    def symbolify(num)
    def eval(str) $num end; $num = num; "()"
    end

    Not only did I redefine `eval` (bad) in a poor manner (badder), but I
    started using globals (baddest). Now that you've seen it, I recommend
    you never look at it again. Just learn from the experience.

    Thanks for all the submissions! I applaud your techniques and
    occasional deviousness...



    --
    Matthew Moss <>
     
    Matthew Moss, Jul 17, 2008
    #1
    1. Advertising

  2. Matthew Moss

    Matthew Moss Guest

    Re: Symbolify (#169)

    I suppose I should have also talked about ruby 1.9, since it seems the
    behavior of `?` has changed... but I was too lazy to install it. :)
     
    Matthew Moss, Jul 17, 2008
    #2
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Adam Barr
    Replies:
    1
    Views:
    512
  2. Libs
    Replies:
    0
    Views:
    1,540
  3. zPaul

    Validation Summary

    zPaul, Jun 26, 2003, in forum: ASP .Net
    Replies:
    0
    Views:
    472
    zPaul
    Jun 26, 2003
  4. BillLi
    Replies:
    0
    Views:
    168
    BillLi
    Jul 10, 2003
  5. Matthew Moss

    [QUIZ] Symbolify (#169)

    Matthew Moss, Jul 11, 2008, in forum: Ruby
    Replies:
    74
    Views:
    741
    Joel VanderWerf
    Jul 17, 2008
Loading...

Share This Page