[SUMMARY] Reverse Divisible Numbers (#161)

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.