[Date Prev][Date Next][Thread Prev][Thread Next] [Search] [Date Index] [Thread Index]

Re: [FWP] Jotto puzzle: first five guesses



Quoting Matthew Wickline (listbox@wickline.org):
> How can you efficiently find all sets of five words from
> that list which use up 25 unique letters of the alphabet.

I'm not sure it is possible to do it efficiently. Unless someone can figure
out an algorithm that doesn't use N*N time. Pre-trimming the dictionary
might be a neat trick, but then you're in danger of losing some of the
answers.

> What's the fastest code with unlimited RAM?

I suspect the qr() feature of Perl 5.005 would come in handy here. The
operation that gets done the most is to compare a word with a set of words
to see if they have common letters. This can be expressed naturally in perl
as /[$letters]/, where $letters is the union of all the letters in the set
of words. I tried doing this using a CODEREF (as I don't have Perl 5.005 on
my machine), but it used way too much memory.

I fear this may be a problem for which C is better than Perl.

> What's the fastest code with minimal RAM use (probably lots
> of disk use)?

The same as the above on an operating system with virtual memory :-)

-- 
Adam Rice -- wysiwyg@glympton.airtime.co.uk -- Blackburn, Lancashire, England

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe