Invisible wrote:
>>     Well, for all but one of the problems I've worked on, the definitions
>> in the problem statements are fairly unambiguous.
> 
> Well, for "find the millionth prime number" or something, there's not
> much to check. But when the problem is "sum all the primes below 1
> million", it might be nice to know, for example, how many primes there
> are. (Or rather, be able to ask "are there 722 primes?" and get a yes/no
> answer.)

	That'd make it easier to solve, though.



	That's an interesting currency conversion you have there...

	Unless you have a good reason to stick with them, simply dump them and
ask around for recommendations of cheaper and better hosts. I'm
currently paying a bit less than you are (albeit that's because I paid
in advance), and I get probably much more than what you want.

(I use Dreamhost - often maligned, but more than satisfies my needs and
wants and I can't find similarly priced alternatives that do).

> I don't know - almost all of the problems seem to be a case of "write
> this brute-force search algorithm so it doesn't take all day". Very few
> problems appear to possess an elegant mathematical solution. For example:
> 
> - Find the 10,001st prime number. Well, sure, there's only one possible
> way to do that. You can't know whether a given prime is the 10,001st or
> not without finding all 10,000 primes below it! Brute-force search,
> plain and simple.
> 
> - Take this file full of data, generate some numbers from it, find the
> highest one. Well, again, no mathematics involved. It's a trivial search
> problems. Just gotta write a program fast enough.

	I'm assuming that these two are just prepping you up for more difficult
(but related) problems later on. Certainly if someone has trouble
generating 10001 primes, he won't get too far.

> - Find a number having some highly obscure property. Well you can
> probably use elegant mathematics to elimatine a few classes of
> possibilities, but it still comes down to a simple search in the end.

	That's sort of the point. Take Problem 43:

"The number, 1406357289, is a 0 to 9 pandigital number because it is
made up of each of the digits 0 to 9 in some order, but it also has a
rather interesting sub-string divisibility property.

Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we
note the following:

    * d2d3d4=406 is divisible by 2
    * d3d4d5=063 is divisible by 3
    * d4d5d6=635 is divisible by 5
    * d5d6d7=357 is divisible by 7
    * d6d7d8=572 is divisible by 11
    * d7d8d9=728 is divisible by 13
    * d8d9d10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property."

	A REAL brute force solution is simple to write, but do you really want
to check over a billion numbers? (I'm guessing anyone who got this far
would not even realize the search space is that big - they'll
automatically optimize).

	Now with some thought you can bring that number down to something very
manageable. You could then code it and be happy, or think more and try
to reduce the search space even more. The more you do this, the more
"painful" it is to code. So then you take on the challenge of writing
the code in a "nicer" way so that it doesn't look like an ugly hack.

	I just went halfway and coded it. I felt bad about that after looking
at the solutions. There were some really simple ways to reduce the
search space _much_ further - on the other hand I did a simplification
few thought of - but the ones I missed negated the need for mine.

	Now some people simply solved this on paper (some of those did use a
calculator to help, though). 	

	The point of the problems is not to solve it _entirely_ mathematically
(although if you can, that's wonderful). It's to use math to make the
problem more tractable (even if it _can_ be done under a minute via
brute force). And for me, it's also a challenge to write the code
somewhat nicely.

	The last problem I worked on (in the 40's) was somewhat brute force and
took over 40 minutes. Haven't had time to think about it much since
then, but I look forward to bringing that down. I have a few ideas on
making the algorithm faster which may suffice, but before I had obtained
the solution, I noticed some mathematical properties which I suspected
held true in general (but couldn't prove it). After computing the
solution, I find the answer does satisfy my hypothesis, and now I don't
want to simply speed up the algorithm, but rather explore my hypothesis
and "speed" it up that way.

	Which is why I enjoy a number of the problems...

> A few of the problems admit an elegant mathematical solution. The thing
> with Pythagorean triples, or finding the sum of numbers or the number of
> combinations or something. Slightly more involve some actual maths
> somewhere. But most seem to just involve blindly searching as fast as
> possible. It's not very interesting, but I like seeing my score
> increase. :^)

	I assume that it'll demand more math thought as you get higher. Many
(most?) have not impressed me as much in that regard thus far. But heck,
it was fun anyway!

-- 
As a child my family's menu consisted of two choices: "Take it, or leave
it."


                    /\  /\               /\  /
                   /  \/  \ u e e n     /  \/  a w a z
                       >>>>>>mue### [at] nawazorg<<<<<<
                                   anl

Post a reply to this message