M

#### Matthew Moss

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.