[SUMMARY] Reverse Divisible Numbers (#161)

Discussion in 'Ruby' started by Matthew Moss, May 8, 2008.

  1. Matthew Moss

    Matthew Moss Guest

    NOTE: I haven't updated the current (temporary) website, as I'm just
    about done with the first rev of a new (temporary) website. The new
    website is still not quite where I want it to be, but far more
    maintainable than the current. I have a bit more to do today to make
    it presentable, and I'll provide the new url either later today, or
    tomorrow morning. On to the summary...

    ----

    The heart of this week's quiz is two very simple problems: how to
    reverse a
    number, and how to determine whether one number is divisible by
    another.
    Robert's implementation was the shortest at about five lines of code,
    which
    we'll look here.

    limit = (ARGV.shift or 1_000_000).to_i

    The first line of Robert's solution (shown here with one minor change,
    to
    provide the default as specified in the quiz description) is an easy
    way to
    get a single argument, or provide a default if no argument is
    available, and
    convert it to an integer. Most folks had something similar to this,
    yet in
    experimentation as I began writing this summary, it falls down when an
    argument is provided but cannot be converted to an integer. In such a
    case,
    method `to_i` simply returns zero.

    That doesn't really hurt anyone here; the scripts provided will just
    never
    execute their loops and provide no output; the only exception I
    noticed was
    Sandro's explicit check to see if `to_i` returned zero. Now, we
    generally
    don't worry that much about error checking during Ruby Quiz, but I
    began to
    wonder if it was really that difficult to get argument input correct
    without
    bringing in an argument processing module.

    The following will assign an integer value to `limit`, either the
    program argument or the default, or will throw an exception if the
    program
    argument is not convertible to an integer:

    limit = Integer(ARGV.shift || 1_000_000)

    Strangely, here is what I actually tried first; I believed should be
    the
    same, but it doesn't even compile:

    limit = Integer(ARGV.shift or 1_000_000)

    I'm assuming that this is some sort of operator precedence issue, but
    I
    don't understand the problem. (Comments and explanations welcome.)

    Back to the quiz... here's the rest of Robert's solution:

    21.upto limit do |n|
    r = n.to_s.reverse.to_i
    n % r == 0 and n % 10 != 0 and r != n and puts n
    end

    Aside from the curious choice of 21 as a starting point, this is a
    straightforward loop counting up to the limit, checking each number in
    turn.

    First, the number is reversed. Most everyone had the same process for
    reversing a number: convert to string, reverse the string, convert
    back to
    integer. It makes sense and, in the case of Ruby, is probably the
    fastest.

    Robert next performs three checks. First (from left to right), a check
    is
    made to see if the remainder of division would be zero; this implies
    `r`
    divides `n`. Second, a check to see if the remainder of division by
    ten
    would _not_ be zero; this enforces an extra rule of the quiz, that
    numbers
    not end in zero. Third, to enforce the other extra rule, Robert
    ensures that
    the number and its reverse are not equal (i.e. they are not
    palindromes).

    Finally, if all those conditions hold, the short-circuited `and`
    operators
    then ensure `puts n` is evaluated. It's an interesting technique,
    though not
    one I've like myself. For me, it mixes "acting" with "observing" more
    than
    necessary; I much would prefer:

    puts n if (n % r == 0 and n % 10 != 0 and r != n)

    But that's mostly personal taste.

    The rest of the discussion was primarily spent on two things: speed
    and a few
    alternative methods. Because the problem was rather simple, output and
    performance results were posted to the discussion within an hour of
    the quiz
    itself. Straightforward solutions were O(n) solutions, which meant
    that
    performance differences were a matter of the equipment involved (i.e.
    hardware and, to a lesser degree, operating system and Ruby build).

    It was immediately apparent, though, that there should be some ways to
    reduce the set of numbers examined. For an upper limit of one million,
    there
    are only six reverse divisible numbers to be found:

    8712
    9801
    87912
    98901
    879912
    989901

    It was pretty apparent that all of these numbers are divisible by
    nine, and
    an informal proof showed that any reverse divisible number had to be
    also
    divisible by nine. That immediately reduced the search set by nearly
    an
    order of magnitude, and the posted timings reflected this. Still, even
    with
    the domain reduced by an order of magnitude, that is far more numbers
    to
    check than actually satisfy the problem.

    Marcelo, Thomas and Harry began to examine the visual patterns of the
    numbers, noting that there were arrangements of 8712 and 9801 (and
    their
    reverses) that repeated themselves in larger numbers. Their solutions
    reflect this approach, yet they admit to being incomplete solutions:
    they
    don't find every reverse divisible number.

    But they are extremely fast at not finding every number! Such
    solutions beg
    to me to work further on analyzing the patterns and determining
    properties
    of these reverse divisible numbers. If I don't put out a quiz
    tomorrow,
    you'll know where I am.
     
    Matthew Moss, May 8, 2008
    #1
    1. Advertising

  2. Matthew Moss

    ThoML Guest

    Re: Reverse Divisible Numbers (#161)


    > examine the visual patterns of the
    > numbers, noting that there were arrangements of 8712 and 9801 (and
    > their
    > reverses) that repeated themselves in larger numbers. Their solutions
    > reflect this approach, yet they admit to being incomplete solutions:
    > they
    > don't find every reverse divisible number.


    They may be incomplete (although I'm not so sure this is true for
    marcelo's approach) but at least they find some numbers in finite
    time.
     
    ThoML, May 9, 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. Michael Muller
    Replies:
    2
    Views:
    2,263
    Neomorph
    Sep 18, 2003
  2. Replies:
    15
    Views:
    591
    Jonathan Smith
    Dec 6, 2006
  3. Frederick Gotham

    Greatest number divisible by Y

    Frederick Gotham, Jul 1, 2006, in forum: C Programming
    Replies:
    21
    Views:
    857
    Dave Thompson
    Jul 10, 2006
  4. mdh

    p 161...File access

    mdh, Sep 29, 2008, in forum: C Programming
    Replies:
    17
    Views:
    591
    Keith Thompson
    Sep 29, 2008
  5. Matthew Moss
    Replies:
    34
    Views:
    560
    Harry Kakueki
    May 9, 2008
Loading...

Share This Page