[Tutor] [Edu-sig] collection of ACM programming problems (fwd)

[Remco Gerlich]

On Thu, Jan 11, 2001 at 01:56:16PM -0800, Daniel Yoo wrote:
> > > >Well, the first solution I thought of (changing the primes.py program)
> > > >didn't work out, but it was still not that hard. Fun to do though :).
> > > >Keeping the source secret for the home solvers, but the answer I get is
> > > >859963392L.
> 
> Confirmed on 859963392 --- I used an simplistic brute force method, and
> got the same numbers.  (After about a few HOURS... I like Remco's program
> a lot better than mine.)

Thanks :). After several changes the computer scientist in me still thinks
it could be improved a lot, and the pragmatist says there's no reason to...

> It's definitely a good idea to try multiple solutions of this problem.  
> In fact, my first program had reported 74649600 as the 1500th ugly number
> --- only later when I tried a different approach did I find a bug in the
> program.  When we're talking in the range of hundreds of millions, double
> checking can't hurt... *grin*
 
I love all the problems on that site. A collection of different solutions
for them would be useful for a number of things - example Python code,
checking your solutions, and certainly good marketing for Python - I bet
that a Python solution will often be much shorter *and* faster than an
implementation in C or Pascal.

It seems the approach to solving most of these problems in Python is "use a
dict." :) And if I were doing this in C my first idea would not be to use a
hashing algorithm. Lots of speed gain simply because the higher concepts are
less work to implement (it's already done).

I think making such a collection is out of scope for this list though and
I'd like to make an announcement on comp.lang.python, but Rob is the one who
maintains the site. It could become quite some work. So let him decide how
big he wants this to be.

I've also got a pretty simplistic answer for problem 100 (using a dictionary
as a cache) and I've been playing with 759, interpreting Roman numerals (but
there are some complicated rules to take into account to make sure you
notice every illegal Roman numeral). I love little CS problems like this :)

-- 
Remco Gerlich