Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid

Re^9: Words in Words

by choroba (Chancellor)
on Oct 02, 2011 at 20:55 UTC ( #929179=note: print w/replies, xml ) Need Help??

in reply to Re^8: Words in Words
in thread Words in Words

OK. In the while loop, I create a hash whose keys are the words from the list (there is no value, that's why the undef).

Then, I go through the words one by one. For each word, I try all the positions and all possible lengths of its subwords (and I skip the maximal length at position 0, because that would breake the rule #2). For each subword, I do nothing if it has already been printed out (each word should be reported just once). I do nothing if rules #3 or #4 apply. Otherwise, I check whether the subword is itself on the list of words. If it is, I report it and book it as such. And that's it.

The basic idea was this: Comparing each word to all other words would take ages. There would be many comparisons of words that are totally incompatible. How can I reduce the number of comparisons? I do not need all the words, I only need those that are possible for the given word.

As I read the code know, I think it might be optimized a bit further. Instead of caching the reported subwords, you can cache the tested ones (i.e. move the undef three lines up, before the "if"). %reported should be renamed to %checked then.

Replies are listed 'Best First'.
Re^10: Words in Words
by sarchasm (Acolyte) on Oct 03, 2011 at 00:06 UTC

    Got it!

    The only piece in the code I am wondering about is where you are checking for rules 3 and 4 and use "$subword . q{s}..."

    I know what it is doing but where did the "q" come from?

    Thank you!
      Customary Generic Meaning Interpolates '' q{} Literal no "" qq{} Literal yes `` qx{} Command yes* qw{} Word list no // m{} Pattern match yes* qr{} Pattern yes* s{}{} Substitution yes* tr{}{} Transliteration no (but see below) y{}{} Transliteration no (but see below) <<EOF here-doc yes* * unless the delimiter is ''.
        Perfect. Thank you.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://929179]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (5)
As of 2017-05-28 16:39 GMT
Find Nodes?
    Voting Booth?